Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry WojtaszczykAlgorithmica 2014 · DOI

Abstract

The 2-Disjoint Connected Subgraphs (2-DCS) problem is a fundamental challenge in graph theory and exact algorithms. For decades, the $O(2^n)$ brute-force limit remained an unbroken theoretical barrier for general graphs. This paper, published in Algorithmica, presents the first algorithm to break this barrier, achieving a complexity of $O(1.933^n)$. Furthermore, the authors establish lower bounds using the Strong Exponential Time Hypothesis (SETH), demonstrating that the problem is unlikely to admit a polynomial kernel or a solution significantly faster than $2^k$, where $k$ represents the number of non-terminal vertices.

Introduction

The 2-Disjoint Connected Subgraphs (2-DCS) problem asks a deceptively simple question: Given a graph $G$ and two disjoint sets of "terminal" vertices, $Z_1$ and $Z_2$, can we partition a subset of the vertices into two disjoint sets $A_1$ and $A_2$ such that $Z_1 \subseteq A_1$, $Z_2 \subseteq A_2$, and both induced subgraphs $G[A_1]$ and $G[A_2]$ are connected?

This problem is a classic NP-complete challenge with deep roots in the "Graph Minors" project pioneered by Robertson and Seymour. While specific graph classes (such as those with restricted path lengths) had previously yielded faster-than-exponential solutions, the general case remained stuck at the $O(2^n)$ complexity of a naive search. This paper provides the theoretical breakthrough necessary to move beyond this limit while simultaneously defining the boundaries of further optimization.

Algorithmic Framework: Branch and Reduce

The authors achieve their $O(1.933^n)$ result using a Branch and Reduce framework. The efficiency of the algorithm stems from several key technical innovations that prune the search space more effectively than previous methods.

Inclusion-Minimal Formulations

A critical insight in the paper is the shift toward finding an inclusion-minimal set $A_1$. The authors simplify the problem by searching for a partition where $G[A_1]$ is connected and all vertices of $Z_2$ reside within the same connected component of $G[V \setminus A_1]$. By focusing on the smallest possible $A_1$ that satisfies the connectivity requirements for $Z_1$, the branching rules become more constrained and easier to analyze.

The Role of Articulation Points

The core technical innovation lies in the combinatorial analysis of articulation points. The authors prove that in an inclusion-minimal solution, every non-terminal vertex in $A_1$ must be an articulation point of the subgraph. This observation leads to Lemma 1, which provides a tight bound on the number of "branching points"—vertices that are either terminals or high-degree articulation points that break the graph's connectivity upon removal. By bounding these points, the algorithm can navigate the graph's structure rather than simply iterating through vertex combinations.

Reduction Rules and Edge Contraction

The algorithm employs a hierarchy of reduction rules to simplify the graph before and during branching. For instance, if a vertex is identified as essential for maintaining connectivity between terminals in $Z_1$, the algorithm contracts the edge between that vertex and a terminal. This reduces the effective size of the vertex set $n$, accelerating the search.

Complexity and Hardness Results

Beyond the upper bound improvement, the paper provides a rigorous treatment of the problem's inherent hardness through the lens of parameterized complexity.

Breaking the $2^n$ Barrier

The primary result is the proof that 2-DCS can be solved in $O(1.933^n)$ time using polynomial space. While a concurrent result by Telle and Villanger eventually pushed this further to $O(1.7804^n)$ using a more complex combinatorial study, this paper established the initial methodology for breaking the $2^n$ limit.

SETH Hardness and Non-Terminals

The authors highlight a distinction between the total number of vertices ($n$) and the number of non-terminal vertices ($k$). Under the Strong Exponential Time Hypothesis (SETH), they prove that no algorithm can solve 2-DCS in $O((2-\epsilon)^k \cdot |V|^{O(1)})$ time. This suggests that the "computational hardness" of the problem is concentrated in the vertices that are not pre-assigned to a specific subgraph. While we can beat $2^n$, we likely cannot beat $2^k$.

Kernelization

The paper also addresses whether the problem can be efficiently pre-processed. The authors show that 2-DCS is unlikely to have a "polynomial kernel," meaning there is no polynomial-time algorithm to reduce a large instance into a significantly smaller equivalent instance. As a byproduct of this proof, the authors also resolved a long-standing question by showing that the Set Splitting problem similarly lacks a polynomial kernel.

Conclusion

This work represents a significant step forward in exact graph algorithms. By combining combinatorial insights regarding articulation points with a refined Branch and Reduce framework, the authors successfully bypassed the $2^n$ barrier for the 2-Disjoint Connected Subgraphs problem. While the $O(1.933^n)$ complexity has since been improved, the hardness results provided here offer a definitive map of the problem's complexity landscape, showing that the $2^k$ limit for non-terminals is likely an absolute boundary.

Summary updated

BibTeX
@article{cygan2014solving,
  author = {Marek Cygan and Marcin Pilipczuk and Michal Pilipczuk and Jakub Onufry Wojtaszczyk},
  title = {{Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n}},
  journal = {Algorithmica},
  year = {2014},
  doi = {10.1007/s00453-013-9796-x},
}
Figure