2026-10-08T15:23:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24274 2025-11-12T12:39:43Z ddc:004 open_access

On the Complexity of Finding 1-Center Spanning Trees Lee, Pin-Hsian Tsai, Meng-Tsung Wang, Hung-Lung Treeradius Spanning tree polytope Shortest s t-path polytope 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pin-Hsian Lee and Meng-Tsung Tsai and Hung-Lung Wang 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.43 urn:nbn:de:0030-drops-242743 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.43 eng https://creativecommons.org/licenses/by/4.0/legalcode