{"ID":2923624,"CreatedAt":"2026-06-02T04:05:25.881865328Z","UpdatedAt":"2026-06-04T13:12:39.622923895Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.02325","arxiv_id":"2606.02325","title":"Terminal Steiner tree problem : Complexity and Algorithms","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.","short_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 vertice...","url_abs":"https://arxiv.org/abs/2606.02325","url_pdf":"https://arxiv.org/pdf/2606.02325v1","authors":"[\"Jyothish S\",\"Sadagopan Narasimhan\"]","published":"2026-06-01T14:37:12Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}