A Quartic Kernel for Pathwidth-One Vertex Deletion - Computer Science > Data Structures and AlgorithmsReport as inadecuate




A Quartic Kernel for Pathwidth-One Vertex Deletion - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: The pathwidth of a graph is a measure of how path-like the graph is. Given agraph G and an integer k, the problem of finding whether there exist at most kvertices in G whose deletion results in a graph of pathwidth at most one is NP-complete. We initiate the study of the parameterized complexity of thisproblem, parameterized by k. We show that the problem has a quarticvertex-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, kis a YES instance if and only if G-, k- is a YES instance, ii G- hasOk^{4} vertices, and iii k- \leq k. We also give a fixed parametertractable FPT algorithm for the problem that runs in O7^{k} k \cdot n^{2}time.



Author: Geevarghese Philip, Venkatesh Raman, Yngve Villanger

Source: https://arxiv.org/







Related documents