Advertisement
Published in:
2012 | OriginalPaper | Chapter
Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n
Authors : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Published in: LATIN 2012: Theoretical Informatics
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
2-Disjoint Connected Subgraphs
problem, given a graph along with two disjoint sets of terminals
Z
1
,
Z
2
, asks whether it is possible to find disjoint sets
A
1
,
A
2
, such that
Z
1
⊆
A
1
,
Z
2
⊆
A
2
and
A
1
,
A
2
induce connected subgraphs. While the naive algorithm runs in
O
(2
n
n
O
(1)
) time, solutions with complexity of form
O
((2 −
ε
)
n
) have been found only for special graph classes [15, 19]. In this paper we present an
O
(1.933
n
) algorithm for
2-Disjoint Connected Subgraphs
in general case, thus breaking the 2
n
barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.