Låt G vara en oriktad, begränsad grad graf med n hörn. Fixa en ändlig graf H, och anta att man måste ta bort εn kanter från G för att göra det H-minor fri (för några små konstant ε > 0). Vi ger en N 1/2+o(1) -tid randomiserat förfarande som, med hög sannolikhet, finner en H-minor i en sådan graf. Som ett program, anta att man måste ta bort εn kanter från en begränsad grad graf G för att göra det planar. Detta resultat innebär en algoritm, med samma körtid, som producerar en K 3,3 eller K 5 minor i G. Ingen tidigare sublinjär tidsbindning var känd för detta problem. Av grafen mindre teorem, får vi ett analogt resultat för alla mindre slutna egendom. Upp till n o(1) faktorer löser detta ett antagande av Benjamini-Schram-Shapira (STOC 2008) om förekomsten av ensidiga egendom testare för mindre slutna egenskaper. Dessutom är vår algoritm nästan optimal, med en lägre gräns för Czumaj et al (RSA 2014). Innan detta arbete, de enda diagram H för vilka icke-trivial ensidig egendom testare var kända för H-minor frihet är följande: H är en skog eller en cykel (Czumaj et al, RSA 2014), K 2,k, (k × 2)-grid, och k-cirkus (Fichtenberger et al, Arxiv 2017).
Nyligen, Kumar-Seshadhri-Stolman (därför KSS) nästan löst BSS gissning med en n 1/2+o(1) -kräv ensidig testare för H-minor-freeness REF.
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
{'venue': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}