Interdiction problems on planar graphs

DOI10.1016/J.DAM.2015.05.036zbMATH Open1327.05234arXiv1305.1407OpenAlexW1835927266MaRDI QIDQ897609FDOQ897609

Aaron Schild, Feng Pan

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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+epsilon)$-approximation for the maximum matching interdiction problem on weighted planar graphs. The algorithm runs in pseudo-polynomial time for each fixed $epsilon>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.

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

Recommendations

• Interdiction problems on planar graphs
• Assistance and interdiction problems on interval graphs
• Network flow interdiction on planar graphs
• On planar intersection graphs with forbidden subgraphs
• Publication:5753968
• Planar and grid graph reachability problems
• On the \(p\)-hub interdiction problem
• Capacitated domination problems on planar graphs
• scientific article; zbMATH DE number 437535
• The Vertex-Disjoint Menger Problem in Planar Graphs

zbMATH Keywords

maximum flowplanar graphsapproximation schememaximum matchinginterdictioncrossing gadget

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The k most vital arcs in the shortest path problem
• Graphs on surfaces
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Deterministic network interdiction
• On budget-constrained flow improvement.
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Title not available (Why is that?)
• S-functions for graphs
• Graph minors. III. Planar tree-width
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• Shortest-path network interdiction
• A note on shortest path, assignment, and transportation problems
• Optimal interdiction policy for a flow network
• Matching interdiction
• On short paths interdiction problems: Total and node-wise limited interdiction
• The network inhibition problem
• Packing Interdiction and Partial Covering Problems
• Title not available (Why is that?)
• Network flow interdiction on planar graphs

Cited In (11)

• Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs
• Fractals for Kernelization Lower Bounds
• On the hardness of covering-interdiction problems
• A mixed-integer programming approach for locating jamming devices in a flow-jamming attack
• Interdicting facilities in tree networks
• Assistance and interdiction problems on interval graphs
• A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
• Title not available (Why is that?)
• The Complexity of Finding Small Separators in Temporal Graphs
• The complexity of finding small separators in temporal graphs
• On the \(p\)-hub interdiction problem

This page was built for publication: Interdiction problems on planar graphs

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