DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.43

On the Complexity of Finding 1-Center Spanning Trees

Authors: Pin-Hsian Lee, Meng-Tsung Tsai, and Hung-Lung Wang

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We consider the problem of finding a spanning tree T of a given undirected graph G such that any other spanning tree can be obtained from T by removing k edges and subsequently adding k edges, where k is minimized over all spanning trees of G. We refer to this minimum k as the treeradius of G. Treeradius is an interesting graph parameter with natural interpretations: (1) It is the smallest radius of a Hamming ball centered at an extreme point of the spanning tree polytope that covers the entire polytope. (2) Any graph with bounded treeradius also has bounded treewidth. Consequently, if a problem admits a fixed-parameter algorithm parameterized by treewidth, it also admits a fixed-parameter algorithm parameterized by treeradius. In this paper, we show that computing the exact treeradius for n-vertex graphs requires 2^Ω(n) time under the Exponential Time Hypothesis (ETH) and does not admit a PTAS, with an inapproximability bound of 1153/1152, unless P = NP. This hardness result is surprising, as treeradius has significantly higher ETH complexity compared to analogous problems on shortest path polytopes and star subgraph polytopes.

Cite as

Pin-Hsian Lee, Meng-Tsung Tsai, and Hung-Lung Wang. On the Complexity of Finding 1-Center Spanning Trees. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.WADS.2025.43,
  author =	{Lee, Pin-Hsian and Tsai, Meng-Tsung and Wang, Hung-Lung},
  title =	{{On the Complexity of Finding 1-Center Spanning Trees}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.43},
  URN =		{urn:nbn:de:0030-drops-242743},
  doi =		{10.4230/LIPIcs.WADS.2025.43},
  annote =	{Keywords: Treeradius, Spanning tree polytope, Shortest s, t-path polytope}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2019.10

The Complexity of Packing Edge-Disjoint Paths

Authors: Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract

We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.

Cite as

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.10,
  author =	{Dreier, Jan and Fuchs, Janosch and Hartmann, Tim A. and Kuinke, Philipp and Rossmanith, Peter and Tauer, Bjoern and Wang, Hung-Lung},
  title =	{{The Complexity of Packing Edge-Disjoint Paths}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.10},
  URN =		{urn:nbn:de:0030-drops-114710},
  doi =		{10.4230/LIPIcs.IPEC.2019.10},
  annote =	{Keywords: parameterized complexity, embedding, packing, covering, Hamiltonian path, unary binpacking, path-perfect graphs}
}

Search Results

Documents authored by Wang, Hung-Lung

On the Complexity of Finding 1-Center Spanning Trees

Abstract

Cite as

The Complexity of Packing Edge-Disjoint Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message