Improved Algorithms for MST and Metric-TSP Interdiction

DOI10.4230/LIPICS.ICALP.2017.32zbMATH Open1441.68290arXiv1706.00034OpenAlexW2963443829MaRDI QIDQ5111362FDOQ5111362

Authors: André Linhares, Chaitanya Swamy 

Publication date: 27 May 2020

Abstract: We consider the {em MST-interdiction} problem: given a multigraph $G=(V,E)$, edge weights ${w_{e}geq0}_{einE}$, interdiction costs ${c_{e}geq0}_{einE}$, and an interdiction budget $Bgeq0$, the goal is to remove a set $RsubseteqE$ of edges of total interdiction cost at most $B$ so as to maximize the $w$-weight of an MST of $G-R:=(V,EsetminusR)$. Our main result is a $4$-approximation algorithm for this problem. This improves upon the previous-best $14$-approximation~cite{Zenklusen15}. Notably, our analysis is also significantly simpler and cleaner than the one in~cite{Zenklusen15}. Whereas~cite{Zenklusen15} uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the {em tree knapsack problem} that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our analysis (and the one in~cite{Zenklusen15}). Our guarantee for MST-interdiction yields an $8$-approximation for {em metric-TSP interdiction} (improving over the $28$-approximation in~cite{Zenklusen15}). We also show that the {em maximum-spanning-tree interdiction} problem is at least as hard to approximate as the minimization version of densest-$k$-subgraph.

Full work available at URL: https://arxiv.org/abs/1706.00034

Recommendations

• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Matching interdiction
• Hardness and approximation for network flow interdiction
• Increasing the Weight of Minimum Spanning Trees
• Connectivity interdiction

zbMATH Keywords

approximation algorithmsiterative roundinginterdiction problemssupermodular functionsLP-rounding algorithmstree-knapsack problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (4)

• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Vertex downgrading to minimize connectivity
• Maximum Capacity Path Interdiction Problem with Fixed Costs
• Parametric matroid interdiction

This page was built for publication: Improved Algorithms for MST and Metric-TSP Interdiction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111362)