DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2020.5

Vertex Downgrading to Minimize Connectivity

Authors: Hassene Aissi, Da Qi Chen, and R. Ravi

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

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 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,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 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 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.

Cite as

Hassene Aissi, Da Qi Chen, and R. Ravi. Vertex Downgrading to Minimize Connectivity. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aissi_et_al:LIPIcs.SWAT.2020.5,
  author =	{Aissi, Hassene and Chen, Da Qi and Ravi, R.},
  title =	{{Vertex Downgrading to Minimize Connectivity}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.5},
  URN =		{urn:nbn:de:0030-drops-122527},
  doi =		{10.4230/LIPIcs.SWAT.2020.5},
  annote =	{Keywords: Vertex Interdiction, Vertex Downgrading, Network Interdiction, Approximation Algorithm}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.6

Randomized Contractions for Multiobjective Minimum Cuts

Authors: Hassene Aissi, Ali Ridha Mahjoub, and R. Ravi

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We show that Karger's randomized contraction method (SODA 93) can be adapted to multiobjective global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms. For global minimum cuts with a single edge-budget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an n-node graph improving upon the best-known randomized algorithm with running time tilde{O}(n^4) due to Armon and Zwick (Algorithmica 2006). Our analysis also gives a new upper bound of O(n^3) for the number of optimal solutions for a single edge-budget min cut problem. For the case of (k-1) edge-budget constraints, the extension of our algorithm saves a logarithmic factor from the best-known randomized running time of O(n^{2k} log^3 n). A main feature of our algorithms is to adaptively choose, at each step, the appropriate cost function used in the random selection of edges to be contracted. For the global min cut problem with a constant number of node budgets, we give a randomized algorithm with running time tilde{O}(n^2), improving the current best determinisitic running time of O(n^3) due to Goemans and Soto (SIAM Journal on Discrete Mathematics 2013). Our method also shows that the total number of distinct optimal solutions is bounded by O(n^2) as in the case of global min-cuts. Our algorithm extends to the node-budget constrained global min cut problem excluding a given sink with the same running time and bound on number of optimal solutions, again improving upon the best-known running time by a factor of O(n). For node-budget constrained problems, our improvements arise from incorporating the idea of merging any infeasible super-nodes that arise during the random contraction process. In contrast to cuts excluding a sink, we note that the node-cardinality constrained min-cut problem containing a given source is strongly NP-hard using a reduction from graph bisection.

Cite as

Hassene Aissi, Ali Ridha Mahjoub, and R. Ravi. Randomized Contractions for Multiobjective Minimum Cuts. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aissi_et_al:LIPIcs.ESA.2017.6,
  author =	{Aissi, Hassene and Mahjoub, Ali Ridha and Ravi, R.},
  title =	{{Randomized Contractions for Multiobjective Minimum Cuts}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.6},
  URN =		{urn:nbn:de:0030-drops-78686},
  doi =		{10.4230/LIPIcs.ESA.2017.6},
  annote =	{Keywords: minimum cut, multiobjective optimization, budget constraints, graph algorithms, randomized algorithms}
}

Search Results

Documents authored by Aissi, Hassene

Vertex Downgrading to Minimize Connectivity

Abstract

Cite as

Randomized Contractions for Multiobjective Minimum Cuts

Abstract

Cite as

Thanks for your feedback!

Could not send message