On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges
Networks · 13.11.2026
DOI: 10.1002/net.70086 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 13.11.2026. Verfasst von Christoph Geis und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Geis, C., & Krumke, S. O. (2026). On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges. Networks. https://doi.org/10.1002/net.70086
Vancouver
Geis C, Krumke SO. On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges. Networks. 2026. doi:10.1002/net.70086
BibTeX
@article{Geis2026,
author = {Geis, Christoph and Krumke, Sven O.},
title = {On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges},
journal = {Networks},
year = {2026},
doi = {10.1002/net.70086}
}
EUVIMED