Terminal Steiner tree problem : Complexity and Algorithms
For researchers in graph algorithms and parameterized complexity, this work extends the understanding of Steiner tree variants with leaf constraints, though results are largely incremental.
The paper studies the Terminal Steiner Tree problem, where all terminals must be leaves, and proves it is NP-complete on general graphs. It provides an FPT algorithm parameterized by the number of terminals and analyzes complexity on various graph classes.
Given a connected graph $G$ and a terminal set $R \subseteq V(G)$, the Steiner tree problem (ST) asks for a tree that spans all of $R$ with at most $r$ vertices from $V(G)\backslash R$, for some integer $r\geq 0$. It is known from (Garey et al.,1977 ) that ST is NP-complete. A Steiner tree in which all terminal vertices are constrained to be leaves is called a terminal Steiner tree. Our study addresses the existence of a terminal Steiner tree, its complexity across various graph classes, black-box applications of the ST, and a fixed-parameter tractable (FPT) algorithm with respect to the number of terminals.