2015 | OriginalPaper | Buchkapitel
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
verfasst von : Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
Subset Feedback Vertex Set (Subset FVS)
problem, the input is a graph
$$G$$
G
on
$$n$$
n
vertices and
$$m$$
m
edges, a subset of vertices
$$T$$
T
, referred to as terminals, and an integer
$$k$$
k
. The objective is to determine whether there exists a set of at most
$$k$$
k
vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the
Feedback Vertex Set
problem has received significant attention over the last few years. In fact the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable (
FPT
). Using tools from graph minors Kawarabayashi and Kobayashi obtained an algorithm for
Subset FVS
running in time
$${\mathcal {O}}(f(k)\cdot n^2 m)$$
O
(
f
(
k
)
·
n
2
m
)
[SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for
Subset FVS
running in time
$$2^{{\mathcal {O}}(k \log k)}\cdot n^{{\mathcal {O}}(1)}$$
2
O
(
k
log
k
)
·
n
O
(
1
)
. More recently, Wahlström obtained the first single exponential time algorithm for
Subset FVS
, running in time
$$4^{k}\cdot n^{{\mathcal {O}}(1)}$$
4
k
·
n
O
(
1
)
[SODA 2014]. While the
$$2^{{\mathcal {O}}(k)}$$
2
O
(
k
)
dependence on the parameter
$$k$$
k
is optimal under the Exponential Time Hypothesis (ETH), the dependence of this algorithm as well as those preceding it, on the input size is far from linear.
In this paper we design the first linear time parameterized algorithms for
Subset FVS
. More precisely, we obtain two new algorithms for
Subset FVS
.
A randomized algorithm for
Subset FVS
running in time
$${\mathcal {O}}(25.6^k k^{{\mathcal {O}}(1)} (n + m))$$
O
(
25
.
6
k
k
O
(
1
)
(
n
+
m
)
)
.
A deterministic algorithm for
Subset FVS
running in time
$$2^{{\mathcal {O}}(k \log k)} (n + m)$$
2
O
(
k
log
k
)
(
n
+
m
)
.
In particular, the first algorithm obtains the best possible dependence on both the parameter as well as the input size, up to the constant in the exponent. Both of our algorithms are based on “cut centrality”, in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.