Abstract
We consider 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 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 sourcesink 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 (4,4)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 rounding using a ballgrowing algorithm based on the LP values. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k 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 a (4k,4k)approximation for this case.
BibTeX  Entry
@InProceedings{aissi_et_al:LIPIcs:2020:12252,
author = {Hassene Aissi and Da Qi Chen and R. Ravi},
title = {{Vertex Downgrading to Minimize Connectivity}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {5:15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12252},
URN = {urn:nbn:de:0030drops122527},
doi = {10.4230/LIPIcs.SWAT.2020.5},
annote = {Keywords: Vertex Interdiction, Vertex Downgrading, Network Interdiction, Approximation Algorithm}
}
Keywords: 

Vertex Interdiction, Vertex Downgrading, Network Interdiction, Approximation Algorithm 
Collection: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) 
Issue Date: 

2020 
Date of publication: 

12.06.2020 