On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges

ABSTRACT The min‐cost group Steiner tree problem ( GSTP ) is a well‐known problem in graph theory, not only being NP‐complete but also not admitting a constant‐factor approximation even under strong restrictions. Given a graph and groups of vertices in , the problem GSTP asks for a minimum‐cost subtree of that contains at least one vertex from each group. In this paper, we address two variants of the GSTP : First, we consider groups of edges rather than vertices. Perhaps surprisingly, this problem is not equivalent to the vertex group variant. For instance, in the edge version it is even NP‐complete to decide whether there exists a feasible solution. Next, we consider the restriction that all of the (vertex or edge) groups are connected. We show that these variants can be solved in polynomial time, provided both the treewidth of and the vertex frequency (the number of groups a vertex is contained in) are bounded. However, the problems remain NP‐complete when only one of these parameters is bounded. Furthermore, we give various approximation algorithms for the connected edge GSTP on trees.

Authors

Institutions

Publication Details

Journal
Networks
Published
2026-11-13
DOI
https://doi.org/10.1002/net.70086
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges

Sven Oliver Krumke, Christoph Geis
Networks
Complexity and Algorithms in Graphs
article

On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges

Sven Oliver Krumke, Christoph Geis
article en

Abstract

ABSTRACT The min‐cost group Steiner tree problem ( GSTP ) is a well‐known problem in graph theory, not only being NP‐complete but also not admitting a constant‐factor approximation even under strong restrictions. Given a graph and groups of vertices in , the problem GSTP asks for a minimum‐cost subtree of that contains at least one vertex from each group. In this paper, we address two variants of the GSTP : First, we consider groups of edges rather than vertices. Perhaps surprisingly, this problem is not equivalent to the vertex group variant. For instance, in the edge version it is even NP‐complete to decide whether there exists a feasible solution. Next, we consider the restriction that all of the (vertex or edge) groups are connected. We show that these variants can be solved in polynomial time, provided both the treewidth of and the vertex frequency (the number of groups a vertex is contained in) are bounded. However, the problems remain NP‐complete when only one of these parameters is bounded. Furthermore, we give various approximation algorithms for the connected edge GSTP on trees.

Networks
University of Kaiserslautern (DE), Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau (DE)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon