Vertex downgrading to minimize connectivity
From MaRDI portal
Publication:6038644
DOI10.1007/S10107-022-01824-5zbMATH Open1517.90118arXiv1911.11229MaRDI QIDQ6038644FDOQ6038644
Authors: Hassene Aissi, Da Qi Chen, R. Ravi 
Publication date: 2 May 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1911.11229
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
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Multiway cuts in node weighted graphs
- Deterministic network interdiction
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Shortest-path network interdiction
- Matching interdiction
- A problem in network interdiction
- A gentle introduction to optimization
- On the history of the transportation and maximum flow problems
- Connectivity interdiction
- An improved approximation algorithm of MULTIWAY CUT.
- The network inhibition problem
- Improved approximation for directed cut problems
- Title not available (Why is that?)
- Network flow interdiction on planar graphs
- Multiway cut, pairwise realizable distributions, and descending thresholds
- A 2-approximation algorithm for the directed multiway cut problem
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Hardness and approximation for network flow interdiction
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective
- Simple and fast rounding algorithms for directed and node-weighted multiway cut
- Improved Algorithms for MST and Metric-TSP Interdiction
- Improved region-growing and combinatorial algorithms for \(k\)-route cut problems (extended abstract)
Cited In (1)
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)
