A Quartic Kernel for Pathwidth-One Vertex Deletion - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




A Quartic Kernel for Pathwidth-One Vertex Deletion - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.



Autor: Geevarghese Philip, Venkatesh Raman, Yngve Villanger

Fuente: https://arxiv.org/







Documentos relacionados