On the Terminal Connection Problem

Abstract

A connection tree of a graph G for a terminal set W is a tree subgraph T of G such that ${\text {leaves}}(T) \subseteq W \subseteq V(T)$. A non-terminal vertex of a connection tree T is called linker if its degree in T is exactly 2, and it is called router if its degree in T is at least 3. The Terminal connection problem (TCP) asks whether G admits a connection tree for W with at most $\ell$ linkers and at most r routers, while the Steiner tree problem asks whether G admits a connection tree for W with at most k non-terminal vertices. We prove that TCP is NP-complete even when restricted to strongly chordal graphs and $r \ge 0$ is fixed. This result separates the complexity of TCP from the complexity of Steiner tree, which is known to be polynomial-time solvable on strongly chordal graphs. In contrast, when restricted to cographs, we prove that TCP is polynomial-time solvable, agreeing with the complexity of Steiner tree. Finally, we prove that TCP remains NP-complete on graphs of maximum degree 3 even if either $\ell \ge 0$ or $r\ge 0$ is fixed.