de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Quartic Kernel for Pathwidth-One Vertex Deletion

MPS-Authors
There are no MPG-Authors available
Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC03-C
Abstract
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.