Vi presenterar de första resultaten på den parameteriserade komplexiteten av omkonfigureringsproblem, där en omkonfigurering variant av ett optimeringsproblem Q tar som ingång två genomförbara lösningar S och T och bestämmer om det finns en sekvens av omkonfigurering steg, dvs... en omkonfigurationssekvens, som kan appliceras för att omvandla S till T så att varje steg resulterar i en genomförbar lösning till Q. För de flesta av resultaten i detta papper, S och T är uppsättningar av hörn i en given graf och en omkonfigurering steg lägger till eller tar bort en vertex. Vår studie motiveras av resultat som visar att för många NP-hårda problem är den klassiska komplexiteten i omkonfigurering PSPACE-fullständig. Vi tar upp frågan för flera viktiga graf egenskaper under två naturliga parameteriseringar: k, en bunden på storleken på lösningar, och, En gräns på längden av omkonfigurering sekvenser. Vårt första allmänna resultat är ett algoritmiskt paradigm, omkonfigureringskärnan, som används för att få fastparameterdragbara algoritmer för recon-A preliminär version av detta papper dök upp i Algorithmica (2017) 78:274-297 275 figurationsvarianter av Vertex Cover och, mer allmänt, Bounded Hitting Set och Feedback Vertex Set, alla parameteriserade av k. Däremot visar vi att omkonfigurering Obundet Hitting Set är W[2]-hård när parameteriserad av k +. Vi demonstrerar också W[1]-hårdheten av omkonfigurering varianter av en stor klass av maximering problem parameteriserade av k +, och av deras motsvarande radering problem parameteriserade av ; genom att göra så, visar vi att det finns problem i FPT när parameterized av k, men vars omkonfigurering varianter är W[1]-hård när parameterized av k +.
Mouawad m.fl. REF var först med att överväga omkonfigureringsproblem i samband med parameteriserad komplexitet.
On the Parameterized Complexity of Reconfiguration Problems
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}