Abstract: We study the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We show hardness of obtaining strictly unicriterion approximations for this basic vertex interdiction problem. We also introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria -approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 4 times that in an optimal solution. WE accomplish this with an LP relaxation and round using a ball-growing algorithm based on the LP values. We further generalize the downgrading problem to one where each vertex can be downgraded to one of levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get -approximation for this case.
Recommendations
- scientific article; zbMATH DE number 7759273
- Optimal decremental connectivity in planar graphs
- Optimal decremental connectivity in planar graphs
- Vertex-minor reductions can simulate edge contractions
- Network-based vertex dissolution
- Reducing the maximum degree of a graph by deleting vertices
- Decreasing the maximum degree of a graph
- VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY
- Minimizing the diameter of a network using shortcut edges
Cites work
- A 2-approximation algorithm for the directed multiway cut problem
- A gentle introduction to optimization
- A problem in network interdiction
- An improved approximation algorithm of MULTIWAY CUT.
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Connectivity interdiction
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Deterministic network interdiction
- Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective
- Hardness and approximation for network flow interdiction
- scientific article; zbMATH DE number 2050722 (Why is no real title available?)
- Improved Algorithms for MST and Metric-TSP Interdiction
- Improved approximation for directed cut problems
- Improved region-growing and combinatorial algorithms for k-route cut problems (extended abstract)
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Matching interdiction
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Multiway cuts in node weighted graphs
- Network flow interdiction on planar graphs
- On the history of the transportation and maximum flow problems
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Shortest-path network interdiction
- Simple and fast rounding algorithms for directed and node-weighted multiway cut
- The network inhibition problem
This page was built for publication: Vertex downgrading to minimize connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038644)
