Tvådimensionellitetsteori introducerades av Demaine et al. [JACM 2005] som ett ramverk för att få algoritmiska resultat för svåra problem på mindre slutna grafklasser. Teorin har med framgång tillämpats för att ge subexponentiella tidsparameteriserade algoritmer, EPTAS och linjära kärnor för många problem på familjer av grafer exklusive en fast graf H som en minderårig. I detta dokument använder vi flera av de viktigaste idéerna från tvådimensionellitet för att ge ett nytt generiskt tillvägagångssätt för att designa EPTAS och subexponentiella tidsparameteriserade algoritmer för problem på klasser av grafer som inte är mindre slutna, utan istället uppvisar en geometrisk struktur. I synnerhet presenterar vi EPTAS och subexponentiella tidsparameteriserade algoritmer för FEEDBACK VERTEX SET, VERTEX COVER, CONNECTED VERTEX COVER, DIAMOND HITTING SET, på kartgrafer och enhet disk grafer, och för CYCLE FÖRPACKNING och MINIMI-VERTEX FEEDBACK EDGE SET på enhet disk grafer. Såvitt vi vet var dessa resultat tidigare okända, med undantag för EPTAS och en subexponentiell tidsparameteriserad algoritm på enhetsskivan grafer för VERTEX COVER, som erhölls av Marx ] och nya rutnät- exkluderade teorem i enhet skiva och karta grafer utan stora klichéer. Våra algoritmer fungerar direkt på ingångsgrafen och kräver inte de geometriska representationerna av ingångsgrafen. Vi visar också att vårt tillvägagångssätt inte kan utvidgas i sin fulla generalitet till mer allmänna klasser av geometriska grafer, såsom skärningsdiagram över enhet bollar i R d, d ≥ 3. Specifikt bevisar vi att FEEDBACK VERTEX SET på enhet-boll grafer i R 3 varken erkänner PTASs om inte P=NP, eller subexponentiella tid algoritmer om inte Exponential Time Hypotesen misslyckas. Dessutom visar vi att de nedbrytningsteorem som vår strategi bygger på misslyckas för diskgrafer och att därför varje utvidgning av våra resultat till diskgrafer skulle kräva nya algoritmiska idéer. Å andra sidan bevisar vi att våra EPTAS och subexponentiella tidsalgoritmer för VERTEX COVER och CONNECTED VERTEX COVER för över både till diskgrafer och till enhet-ball grafer i R d för varje fast d.
Trots detta, Fomin et al. REF kunde erhålla subexponentiella parameteriserade algoritmer av körtid 2 O(k 0.75 log k) n O(1) på enhetsdiskgrafer för Long Path, Long Cycle, Feedback Vertex Set och Cycle Packing.
Bidimensionality and Geometric Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}