# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### A Single-exponential FPT Algorithm for the K4-Minor Cover Problem

##### 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

Kim, E. J., Paul, C., & Philip, G. (2012). A Single-exponential FPT Algorithm for
the K4-Minor Cover Problem. In F. V. Fomin, & P. Kaski (*Algorithm
Theory - SWAT 2012* (pp. 119-130). Berlin: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-BDEF-A

##### Abstract

Given an input graph G on \(n\) vertices and an integer k,
the parameterized \textscK_4-minor cover} problem asks whether there is a
set S
of at most k vertices whose deletion results in a K_4-minor
free graph or, equivalently, in a graph of treewidth at most
2. The problem can thus also be called \textsc{Treewidth-2
Vertex Deletion}. This problem is inspired by two well-studied
parameterized vertex deletion problems, \textsc{Vertex Cover}
and \textsc{Feedback Vertex Set}, which can be expressed as
\textsc{Treewidth-t Vertex Deletion} problems: t=0 for {\sc
Vertex Cover} and t=1 for {\sc Feedback Vertex Set}. While
a single-exponential FPT algorithm has been known for a long
time for \textsc{Vertex Cover}, such an algorithm for
\textsc{Feedback Vertex Set} was devised comparatively
recently. While it is known to be unlikely that
\textsc{Treewidth-t Vertex Deletion} can be solved in time
c^{o(k)}⋅ n^{O(1)}, it was open whether the \textsc{K_4-minor cover}
could be
solved in single-exponential FPT time, i.e. in c^k⋅
n^{O(1) time. This paper answers this question in the
affirmative.