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)
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 -approximation for the maximum matching interdiction problem on weighted planar graphs. The algorithm runs in pseudo-polynomial time for each fixed . 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.
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
Cites work
- scientific article; zbMATH DE number 2050722 (Why is no real title available?)
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- A note on shortest path, assignment, and transportation problems
- Approximation algorithms for NP-complete problems on planar graphs
- Deterministic network interdiction
- Graph minors. III. Planar tree-width
- Graphs on surfaces
- Matching interdiction
- Network flow interdiction on planar graphs
- On budget-constrained flow improvement.
- On short paths interdiction problems: Total and node-wise limited interdiction
- Optimal interdiction policy for a flow network
- Packing interdiction and partial covering problems
- S-functions for graphs
- Shortest-path network interdiction
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The k most vital arcs in the shortest path problem
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- The network inhibition problem
Cited in
(20)- Interdicting facilities in tree networks
- Symmetric interdiction for matching problems
- On the \(p\)-hub interdiction problem
- On short paths interdiction problems: Total and node-wise limited interdiction
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Reformulations and complexity of the clique interdiction problem by graph mapping
- Network flow interdiction on planar graphs
- Packing interdiction and partial covering problems
- On the hardness of covering-interdiction problems
- A mixed-integer programming approach for locating jamming devices in a flow-jamming attack
- Connectivity interdiction
- Fractals for kernelization lower bounds
- Interdiction problems on planar graphs
- Assistance and interdiction problems on interval graphs
- The complexity of finding small separators in temporal graphs
- Matching interdiction
- The complexity of finding small separators in temporal graphs
- scientific article; zbMATH DE number 7758343 (Why is no real title available?)
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs
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)
