An FPTAS for Connectivity Interdiction

• 成果类型: Article
• 署名作者: Huang, Chien-Chung; Acosta, Nidia Obscura; Yingchareonthawornchai, Sorrachai
• 署名单位: IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Universite PSL; Telecom SudParis; Ecole Normale Superieure (ENS); Aalto University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02312-2
• 发表日期: 2026-03
• 页码: 605-626
• 关键词: approximation algorithms; Combinatorial Optimization; VITAL ARCS; network; cuts

摘要

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.