Vi förbättrar körtiden för den allmänna algoritmiska teknik som kallas Bakers tillvägagångssätt (1994) på H-minorfria grafer från O(n f ( och h) ) till O(f ( till h)n O(1) ) som visar att det är fast-parameter dragbar w.r.t. Parametern "H". De många tillämpningarna inkluderar t.ex. en 2- approximation för färgning och PTASes för olika problem som dominerande set och max-cut, där vi får liknande förbättringar. På klasser av udda-minorfria grafer, som har fått betydande uppmärksamhet på senare tid, får vi en liknande acceleration för en variant av den strukturella nedbrytning teorem visat av Demaine et al. (2010) och en Bakerstyle nedbrytning i 2 grafer av avgränsad trädbredd. Vi använder dessa algoritmer för att härleda snabbare 2- approximationer; dessutom presenterar vi de första PTASes och subexponentiella FPT-algoritmer för oberoende uppsättning och vertex täcka på dessa graf klasser med hjälp av en ny dynamisk programmeringsteknik. Vi introducerar också en teknik för att härleda (nästan) subexponentiella parameteriserade algoritmer på H-minorfria grafer. Vi tillhandahåller en enhetlig algoritm som körs i tid där n är storleken på inmatningen och k är antalet hörn eller kanter i lösningen. Vår teknik gäller i synnerhet för problem som Steiner träd, (riktad) subgraf med en egenskap, (riktad) längsta väg, och (ansluten / oberoende) dominerande uppsättning, på vissa eller alla riktiga mindre slutna graf klasser, av vilka många tidigare inte ens var kända för att erkänna en algoritm med körtid bättre än O(2 k n O(1) ). Vi får som en följd av att alla problem med en mindre monoton subexponentiell kärna och amenable till vår teknik kan lösas i subexponentiell FPT-tid på H-minor fria grafer. Detta resulterar i en allmän metod för subexponentiella parameteriserade algoritmer utanför ramen för tvådimensionellhet. Nyckelord: Parameterized Complexity; Graph Minors; Odd Minors; Subexponential Algorithms; Kernels. Ett av de mest seminala resultaten i algoritmisk grafteori är utan tvekan Baker's approach [1] för att utforma polynom tid approximation system (PTAS) för ett brett spektrum av problem på planar grafer. Ända sedan upptäckten har den tillämpats och generaliserats på olika sätt, se t.ex. [2, 3, 4, 5, 6, 7, 8, 9]. Kärnan i idén är följande: för varje givet t, man kan partitionera en planar graf i t delar, så att ta bort någon av delarna resulterar i en graf av avgränsad trädbredd. Nu, för att få en PTAS, Vi observerar att om t är lämpligt valt, Det måste finnas en del som innehåller som mest en brott av en optimal lösning; Detta kan ofta kombineras med lösningen i resten av grafen för att få en (1 +  på) - approximation. H-minorfria grafer, dvs. korrekt graf klasser som är stängda under byggnad minderåriga, har fått betydande uppmärksamhet under de senaste två decennierna, särskilt på grund av Robertson och Seymour graf mindre teori, en av de djupaste och mest långtgående teorier i diskret matematik under de senaste decennierna. Dessa klasser inkluderar t.ex. plana grafer, avgränsade-genus grafer, länklöst inbäddbara grafer och apex grafer. Med hjälp av den djupa Robertson-Seymour (RS-) nedbrytningsteorem [10] generaliserade Grohe [4] Bakers teknik till H-minorfria grafer och Demaine et al. [7] visade den partitioneringsteorem som nämns ovan för alla dessa grafklasser. Men båda deras metoder resulterar i algoritmer med körtid O(n f ( på h) ), för vissa beräkningsbar funktion f ; eftersom H antas vara fast, anses detta polynom. Förbättra Bakers upplösning. Vi tillhandahåller den första algoritmen för Bakers nedbrytning som körs i tiden O(g( ska)n O(1) ), för vissa beräkningsbara funktion g. Detta är en betydande acceleration av de tidigare resultaten, särskilt med tanke på det faktum att konstanterna i graf mindre teori, såsom funktionerna f, g ovan, är vanligtvis enorma. Detta innebär omedelbart liknande förbättringar av alla konsekvenser av denna algoritm, särskilt alla allmänna approximationsalgoritmer och system i [4, 7] och Bakers ursprungliga problem [1]. I synnerhet får vi den första 2- approximation för COLORING H-minor-free grafer i den givna tiden bundna och den första PTAS för INDEPENDENT SET, MINIMI COLOR SUM, MAX-CUT, MAXIMUM P -MATCHING, och DOMINERING SET på dessa graf klasser samtidigt undvika  på exponenten av n i sin körtid. Vår huvudidé är härledd från Dawar et al.'s tillvägagångssätt [11] för att hitta en viss trädnedbrytning av H-minorfria grafer som är mer dragbar än RS-nedbrytningen. Parameteriserad komplexitet. På det språk av parameteriserad komplexitet, vårt resultat ovan visar att partitionering H-minor-free grafer på det beskrivna sättet är fast-parameterdragbar (FPT) när parameterized av. I detta ramverk, för ett givet problem av storlek n och parameter k, är vi intresserade av algoritmer med en körtid av O(f (k)n O(1) ), där f är någon beräkningsbar funktion beroende enbart på k; vi säger sedan att problemet är i FPT. Teorin ger också negativa bevis för att vissa problem sannolikt inte är FPT; vi hänvisar till böckerna Downey och Fellows [12] och Flum och Grohe [13] för mer bakgrund om parameteriserad komplexitet. När ett problem visar sig vara FPT är utmaningen att tillhandahålla algoritmer som har det minsta beroendet av parametern k, dvs.. göra funktionen f i körtiden så liten som möjligt. Det är särskilt önskvärt att erhålla subexponentiella funktioner och därmed ge särskilt snabba algoritmer. Medan detta ofta inte är möjligt i allmänna grafer, finns en uppsjö av resultat som visar förekomsten av sådana algoritmer på begränsade grafklasser, såsom H-minorfria grafer. Den kanske mest allmänna tekniken för att erhålla subexponentiella parameteriserade algoritmer på dessa grafklasser är teorin om tvådimensionellhet [14] som fångar nästan alla kända resultat av denna typ på H-minorfria grafer. Ändå är denna teori inte tillämplig på ett antal framträdande problem, såsom STEINER TREE, CONNECTED DOMINERING SET, och DIREKT K-PATH. Ett sätt att visa ett problems fastparameteregenskaper är att visa förekomsten av en kärna för problemet, som är en polynom-tidsalgoritm som omvandlar varje instans till en likvärdig instans vars storlek avgränsas av en funktion g som enbart är beroende av k, som kallas kärnans storlek. Kernelisering kan ses som polynom-tid förbearbetning med en kvalitetsgaranti och har fått mycket teoretisk betydelse under de senaste åren -förutom dess naturliga praktiska betydelse. För en introduktion till kärnor hänvisar vi till Guo och Niedermeiers undersökning [15]. I detta arbete ger vi en ny ram, som vi kallar gissning och erövra, för att erhålla (nästan) subexponentiella parameteriserade algoritmer på H-minorfria grafer för ett överflöd av parameteriserade problem. Närhelst problemet till hands medger en mindre-monoton subexponentiell kärna, resulterar vår metod faktiskt i en subexponentiell algoritm; annars får vi en algoritm med en körtid O(2
Frågan om förekomsten av en subexponentiell tidsalgoritm för PLANAR STEINER TREE följdes först uttryckligen av Tazari REF.
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}