RAIRO-Theor. Inf. Appl.
Volume 57, 2023
|Number of page(s)||20|
|Published online||08 March 2023|
On the computational difficulty of the terminal connection problem*
Federal University of Rio de Janeiro,
Rio de Janeiro, Brazil
2 Fluminense Federal University, Niterói, Brazil
** Corresponding author: firstname.lastname@example.org
Accepted: 31 January 2023
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-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.
Mathematics Subject Classification: 68Q17 / 68Q25 / 68R10 / 05C40 / 05C85
Key words: Computational difficulty of problems / parameterized complexity / terminal vertices / connection tree / steiner tree / split graphs / strongly chordal graphs / cographs / bounded degree
© The authors. Published by EDP Sciences, 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.