Parameterized Complexity of Edge Interdiction Problems

DOI10.1007/978-3-319-08783-2_15MaRDI QIDQ2920456zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Yash Raj Shrestha

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Games involving graphs (91A43)

Abstract: We study the parameterized complexity of interdiction problems in graphs. For an optimization problem on graphs, one can formulate an interdiction problem as a game consisting of two players, namely, an interdictor and an evader, who compete on an objective with opposing interests. In edge interdiction problems, every edge of the input graph has an interdiction cost associated with it and the interdictor interdicts the graph by modifying the edges in the graph, and the number of such modifications is constrained by the interdictor's budget. The evader then solves the given optimization problem on the modified graph. The action of the interdictor must impede the evader as much as possible. We focus on edge interdiction problems related to minimum spanning tree, maximum matching and shortest paths. These problems arise in different real world scenarios. We derive several fixed-parameter tractability and W[1]-hardness results for these interdiction problems with respect to various parameters. Next, we show close relation between interdiction problems and partial cover problems on bipartite graphs where the goal is not to cover all elements but to minimize/maximize the number of covered elements with specific number of sets. Hereby, we investigate the parameterized complexity of several partial cover problems on bipartite graphs.

Recommendations

• On the parameterized complexity of edge-linked paths
• A survey of parameterized algorithms and the complexity of edge modification
• The parameterized complexity of the minimum shared edges problem
• The parameterized complexity of the minimum shared edges problem
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Extension of some edge graph problems: standard and parameterized complexity
• Parameterized algorithms for edge biclique and related problems
• On the parameterized complexity of the edge monitoring problem

Cited in

(12)

• On the hardness of covering-interdiction problems
• Critical edges for the assignment problem: complexity and exact resolution
• Parameterized algorithms for edge biclique and related problems
• Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
• Interdiction problems on planar graphs
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• A refined complexity analysis of finding the most vital edges for undirected shortest paths
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• Parameterized complexity of three edge contraction problems with degree constraints
• Matching interdiction
• Parametric matroid interdiction
• Budget and profit approximations for spanning tree interdiction

This page was built for publication: Parameterized Complexity of Edge Interdiction Problems

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