跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 (2+ε)(2+ε)-approximation algorithms for every fixed ε>0ε>0, improving the previous best factor of 44. Both algorithms respect the original budget and run in NO(1/ε)N^{O(1/ε)} time for 0<ε≤10<ε\le1, where NN 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 P≠NP\mathsf P\ne\mathsf{NP}, no deterministic polynomial-time (2−δ)(2-δ)-approximation exists for any fixed 0<δ<10<δ<1, even on simple graphs with weights in {0,1}\{0,1\}. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a (4+ε)(4+ε)-approximation for metric-TSP interdiction.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 (2+ε)(2+ε)-approximation algorithms for every fixed ε>0ε>0, improving the previous best factor of 44. Both algorithms respect the original budget and run in NO(1/ε)N^{O(1/ε)} time for 0<ε≤10<ε\le1, where NN 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 P≠NP\mathsf P\ne\mathsf{NP}, no deterministic polynomial-time (2−δ)(2-δ)-approximation exists for any fixed 0<δ<10<δ<1, even on simple graphs with weights in {0,1}\{0,1\}. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a (4+ε)(4+ε)-approximation for metric-TSP interdiction.

查看此版本解读 →查看此版本原文 ↗