TR-2017-09

Beating the 2-approximation factor for Global Bicut

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



Abstract

In the fixed-terminal bicut problem, the input is a directed graph with two specified nodes and the goal is to find a smallest subset of edges whose removal ensures that the two specified nodes cannot reach each other. 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 \emph{there exist} two nodes that cannot reach each other. 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-\epsilon)$-approximation for any constant $\epsilon>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.


Bibtex entry:

@techreport{egres-17-09,
AUTHOR = {B{\'e}rczi, Krist{\'o}f and Chandrasekaran, Karthekeyan and Kir{\'a}ly, Tam{\'a}s and Lee, Euiwoong and Xu, Chao},
TITLE = {Beating the 2-approximation factor for Global Bicut},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-09}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!