Beating the 2-approximation factor for global bicut

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu

Research output: Contribution to journalArticlepeer-review

Abstract

In the fixed-terminal bicut problem, the input is a directed graph with two specified nodes s and t and the goal is to find a smallest subset of edges whose removal ensures that s cannot reach tandt cannot reach s. In the global bicut problem, the input is a directed graph and the goal is to find a smallest subset of edges whose removal ensures that there exist two nodes s and t such that s cannot reach tandt cannot reach s. Fixed-terminal bicut and global bicut are natural extensions of { s, t} -min cut and global min-cut respectively, from undirected graphs to directed graphs. Fixed-terminal bicut is NP-hard, admits a simple 2-approximation, and does not admit a (2 - ϵ) -approximation for any constant ϵ> 0 assuming the unique games conjecture. In this work, we show that global bicut admits a (2 - 1 / 448) -approximation, thus improving on the approximability of the global variant in comparison to the fixed-terminal variant.

Original languageEnglish (US)
Pages (from-to)291-320
Number of pages30
JournalMathematical Programming
Volume177
Issue number1-2
DOIs
StatePublished - Sep 1 2019

Keywords

  • Bicut
  • Digraphs
  • Linear cut
  • k-cut

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Beating the 2-approximation factor for global bicut'. Together they form a unique fingerprint.

Cite this