betaFeedback

WorksComputer Science

Two (2+ε)(2+ε)-Approximation Algorithms for Minimum Spanning Tree Interdiction

Abstract

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.

Paper details

vlnc:W_29z26ych
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…