On the computational difficulty of the terminal connection problem^*

¹ Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
² Fluminense Federal University, Niterói, Brazil

^** Corresponding author: aamelo@cos.ufrj.br

Received: 21 March 2022
Accepted: 31 January 2023

Abstract

A connection tree of a graph G for a terminal set W is a tree subgraph T of G such that leaves(T) ⊆ W ⊆ V(T). A non-terminal vertex 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 ℓ 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, if r ≥ 1 is fixed, then TCP is polynomial-time solvable when restricted to split graphs. This result separates the complexity of TCP from the complexity of Steiner tree, which is known to be NP-complete on split graphs. Additionally, we prove that TCP is NP-complete on strongly chordal graphs, even if r ≥ 0 is fixed, whereas Steiner tree is known to be polynomial-time solvable. We also prove that, when parameterized by clique-width, TCP is W[1]-hard, whereas STeiner tree is known to be in FPT. On the other hand, agreeing with the complexity of Steiner tree, we prove that TCP is linear-time solvable when restricted to cographs (i.e. graphs of clique-width 2). Finally, we prove that, even if either ℓ ≥ 0 or r ≥ 0 is fixed, TCP remains NP-complete on graphs of maximum degree 3.