2013/05/07 by Feng Pan, Pan, Feng, Aaron Schild +1
Computer Science · Mathematics · Social Sciences · #Crime, Illicit Activities, and Governance #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1305.1407
25 pages, 9 figures. Extended abstract in APPROX-RANDOM 2013
openalex publication_date 2013/05/07 · arxiv created 2013/10/01 · arxiv updated 2013/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Interdiction problems are leader-follower games in which the leader is allowed to delete a certain number of edges from the graph in order to maximally impede the follower, who is trying to solve an optimization problem on the impeded graph. We introduce approximation algorithms and strong NP-completeness results for interdiction problems on planar graphs. We give a multiplicative (1 + ε)-approximation for the maximum matching interdiction problem on weighted planar graphs. The algorithm runs in pseudo-polynomial time for each fixed ε> 0. We also show that weighted maximum matching interdiction, budget-constrained flow improvement, directed shortest path interdiction, and minimum perfect matching interdiction are strongly NP-complete on planar graphs. To our knowledge, our budget-constrained flow improvement result is the first planar NP-completeness proof that uses a one-vertex crossing gadget.