TY - JOUR

T1 - Beating the 2-approximation factor for global bicut

AU - Bérczi, Kristóf

AU - Chandrasekaran, Karthekeyan

AU - Király, Tamás

AU - Lee, Euiwoong

AU - Xu, Chao

N1 - Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2019/9/1

Y1 - 2019/9/1

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

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

KW - Bicut

KW - Digraphs

KW - Linear cut

KW - k-cut

UR - http://www.scopus.com/inward/record.url?scp=85044616948&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044616948&partnerID=8YFLogxK

U2 - 10.1007/s10107-018-1270-8

DO - 10.1007/s10107-018-1270-8

M3 - Article

AN - SCOPUS:85044616948

SN - 0025-5610

VL - 177

SP - 291

EP - 320

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -