Vertex downgrading to minimize connectivity
Chen, da Qi; Ravi, R.; Aissi, Hassene (2022), Vertex downgrading to minimize connectivity, Mathematical programming. 10.1007/s10107-022-01824-5
TypeArticle accepté pour publication ou publié
Journal nameMathematical programming
Springer International Publishing
MetadataShow full item record
Author(s)Chen, da Qi
Carnegie Mellon University [Pittsburgh] [CMU]
Tepper School of Business
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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 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 (4, 2)-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 2 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. Furthermore, we show that other bicriteria approximations exist where one can worsen the approximation factor for one of the costs in order to improve the other. 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. Trade-offs between the two approximation ratios similar to the two-level case also exist for the generalized problem. By transferring node values to edge values, we also derive new bicriteria approximation results for the vertex interdiction versions of the multiway cut problem in digraphs and multicut problems in undirected graphs.
Subjects / KeywordsVertex interdiction, Vertex downgrading, Network interdiction, Approximation algorithm
Showing items related by title and author.
Weighted sum model with partial preference information: application to Multi-Objective Optimization Kaddani, Sami; Vanderpooten, Daniel; Vanpeperstraete, Jean-Michel; Aissi, Hassene (2017) Article accepté pour publication ou publié