DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.30

Preventing Small Global Cuts by Protecting Edges

Authors: Christian Komusiewicz, Zhenwei Liu, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

The minimum cut problem is one of the oldest and most fundamental optimization problems in operations research. In this problem, we are given a connected edge-weighted graph (G,ω) and have to find an edge set A (called edge-cut) of smallest total weight such that the removal of the edges of A disconnects G. The problem thus takes the view of an attacker that wants to destroy the global connectivity of the network. Bienstock and Diaz [SICOMP '93] introduced Global Cut Prevention, a two-player version of the minimum cut problem where a defender aims to protect edges to increase the weight of the minimum cut of the resulting graph. More precisely, the input contains an additional edge cost function c that is independent of the attacker weight ω and the defender aims to protect an edge set of total cost at most d such that every edge-cut consisting of unprotected edges has weight at least a+1. We initiate the study of the parameterized complexity of Global Cut Prevention. Here, we consider the most natural parameters such as the budgets d and a of the players, the vertex cover number and treewidth of the input graph, and combinations of these parameters. We show, for example, that the encoding of the costs and weights of the edges has a considerable influence on the problem complexity: If each edge has unit defender cost and unit attacker weight, then Global Cut Prevention is FPT for the vertex cover number. If the attacker weights are arbitrary and encoded in unary, then the problem is W[1]-hard for the vertex cover number but still admits an XP-algorithm. Finally, if the defender cost and the attacker weight are encoded in binary, then the problem becomes NP-hard even on graphs with a vertex cover of size 2.

Cite as

Christian Komusiewicz, Zhenwei Liu, Nils Morawietz, and Frank Sommer. Preventing Small Global Cuts by Protecting Edges. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.WG.2026.30,
  author =	{Komusiewicz, Christian and Liu, Zhenwei and Morawietz, Nils and Sommer, Frank},
  title =	{{Preventing Small Global Cuts by Protecting Edges}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.30},
  URN =		{urn:nbn:de:0030-drops-261964},
  doi =		{10.4230/LIPIcs.WG.2026.30},
  annote =	{Keywords: Network interdiction, NP-hard problem, parameterized complexity, structural parameterization, edge-weighted graphs}
}

Document

DOI: 10.4230/LIPIcs.STACS.2025.51

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

Authors: Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the (p,q)-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains p-edge-connectivity between given terminal pairs against edge failures, assuming at most q unprotected edges can fail. We design polynomial-time exact algorithms for the cases where p and q are small and approximation algorithms for general values of p and q. Additionally, we show that when both p and q are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either p or q is constant, for which our new hardness result now provides justification.

Cite as

Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang. Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2025.51,
  author =	{Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
  title =	{{Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.51},
  URN =		{urn:nbn:de:0030-drops-228761},
  doi =		{10.4230/LIPIcs.STACS.2025.51},
  annote =	{Keywords: Network Design, Edge Failures, Graph Connectivity, Approximation Algorithms}
}

Search Results

Documents authored by Liu, Zhenwei

Preventing Small Global Cuts by Protecting Edges

Abstract

Cite as

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

Abstract

Cite as

Thanks for your feedback!

Could not send message