Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

A Quartic Kernel for Pathwidth-One Vertex Deletion

MPG-Autoren
Es sind keine MPG-Autoren in der Publikation vorhanden
Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Philip, G., Raman, V., & Villanger, Y. (2010). A Quartic Kernel for Pathwidth-One Vertex Deletion. In D. M. Thilikos (Ed.), Graph Theoretic Concepts in Computer Science (pp. 196-207). Berlin: Springer. doi:10.1007/978-3-642-16926-7_19.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0019-DC03-C
Zusammenfassung
The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is \npc{}. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G=(V,E),k);|V|=n, we can construct, in polynomial time, an instance (G',k') such that (i) (G,k) is a YES instance if and only if (G',k') is a YES instance, (ii) G' has \Oh(k^4}) vertices, and (iii) k'≤ k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in \Oh(7^{kk⋅ n²) time.