Advertisement
Published in:
2010 | OriginalPaper | Chapter
An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
Authors : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The
Pathwidth One Vertex Deletion
(POVD) problem, given an undirected graph
G
and an integer
k
, asks whether one can delete at most
k
vertices from
G
so that the remaining graph has pathwidth at most 1. Recently Philip et al.[14] initiated the study of the parameterized complexity of (POVD) and have shown a quartic kernel and a 7
k
n
O
(1)
algorithm. In this paper we improve these results by showing a quadratic kernel and a 4.65
k
n
O
(1)
algorithm.