An FPTAS for Connectivity Interdiction
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Mathematical Programming
Abstract
In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes the knapsack problem as a special case, hence it is NP-hard. For this problem, Zenklusen [Zenklusen’14] designed a polynomial-time approximation scheme (PTAS) and exact algorithms for the special case of unit edge costs. He posed the question of whether a fully polynomial-time approximation scheme (FPTAS) is possible for the general case. We give an affirmative answer. For the special case of unit edge costs, we also give faster exact and approximation algorithms. Our main technical contribution is to establish a connection with an intermediate graph cut problem, called the normalized min-cut, which, roughly speaking, penalizes the edge weights of the remaining edges more severely, when more edges are taken out for free.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Other note
Citation
Huang, C C, Obscura Acosta, N & Yingchareonthawornchai, S 2025, 'An FPTAS for Connectivity Interdiction', Mathematical Programming. https://doi.org/10.1007/s10107-025-02312-2