Connecting Terminals and 2-Disjoint Connected Subgraphs

Abstract

Given a graph $G=(V,E)$ and a set of terminal vertices $T$ we say that a superset $S$ of $T$ is $T$-connecting if $S$ induces a connected graph, and $S$ is minimal if no strict subset of $S$ is $T$-connecting. In this paper we prove that there are at most $\left(\genfrac{}{}{0ex}{}{|V\setminus T|}{|T|-2}\right)\cdot 3^{\frac{|V\setminus T|}{3}}$ minimal $T$-connecting sets when $|T|\le n/3$ and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case $|T|=2$. We apply our enumeration algorithm to solve the {\sc 2-Disjoint Connected Subgraphs} problem in time $O^{\ast }(1.7804^n)$, improving on the recent $O^{\ast }(1.933^n)$ algorithm of Cygan et al. 2012 LATIN paper.

13 pages, 1 figure