Connecting Terminals and 2-Disjoint Connected Subgraphs

Jan Arne Telle, Yngve Villanger

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 sub…