← 研踪 PaperTrailarXiv:2611.24526 · v1
Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction
首次提交 2026-11-18 22:40
版本更新 2026-11-18 22:40
雷达观测 2026-11-19 15:04
摘要
Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic -approximation algorithms for every fixed , improving the previous best factor of . Both algorithms respect the original budget and run in time for , where is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and , no deterministic polynomial-time -approximation exists for any fixed , even on simple graphs with weights in . Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a -approximation for metric-TSP interdiction.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 22:40 · 最新观测版本
Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction
Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic -approximation algorithms for every fixed , improving the previous best factor of . Both algorithms respect the original budget and run in time for , where is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and , no deterministic polynomial-time -approximation exists for any fixed , even on simple graphs with weights in . Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a -approximation for metric-TSP interdiction.
查看此版本解读 →查看此版本原文 ↗