Beating the 2-approximation factor for global bicut

• 成果类型: Article
• 署名作者: Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Lee, Euiwoong; Xu, Chao
• 署名单位: Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1270-8
• 发表日期: 2019
• 页码: 291-320
• 关键词: cut; algorithm

摘要

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-E)-approximation for any constant E>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.