日本語
 
User Manual Privacy Policy ポリシー/免責事項 連絡先
  詳細検索ブラウズ

アイテム詳細


公開

会議論文

A Quartic Kernel for Pathwidth-One Vertex Deletion

MPS-Authors
There are no MPG-Authors available
URL
There are no locators available
フルテキスト (公開)
公開されているフルテキストはありません
付随資料 (公開)
There is no public supplementary material available
引用

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.


引用: http://hdl.handle.net/11858/00-001M-0000-0019-DC03-C
要旨
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.