Terminal Steiner tree problem : Complexity and Algorithms
2026-06-01 • Data Structures and Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
AI summaryⓘ
The authors study a special version of the Steiner tree problem, where the goal is to connect certain key nodes in a graph with a tree, using only a limited number of extra nodes. They focus on a specific case where these key nodes must be leaves of the tree, called terminal Steiner trees. The paper examines when such trees exist, how hard it is to find them in different types of graphs, and develops an efficient algorithm that works well when the number of key nodes is small. Their work builds on previously known complexity results about the Steiner tree problem.
Steiner tree problemterminal setterminal Steiner treeNP-completegraph theoryfixed-parameter tractabilitytree spanninggraph classesalgorithm complexity
Authors
Jyothish S, Sadagopan Narasimhan
Abstract
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.