Name
Abstract | ||
|---|---|---|
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 (van 't Hof et al. in Theor. Comput. Sci. 410(47---49):4834---4843, 2009 ; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761---6769, 2011 ). 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-013-9796-x | Algorithmica |
Keywords | Field | DocType |
Exact algorithms,2,n,barrier,2-Disjoint Connected Subgraphs,Kernelization,Exponential Time Hypothesis | Kernelization,Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Polynomial kernel,Connected component,Strongly connected component,Mathematics,Speedup,Exponential time hypothesis | Journal |
Volume | Issue | ISSN |
70 | 2 | 0178-4617 |
Citations | PageRank | References |
3 | 0.40 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| michal pilipczuk | 2 | 403 | 51.93 |
| Michał Pilipczuk | 3 | 23 | 1.74 |
| jakub onufry wojtaszczyk | 4 | 154 | 9.48 |