<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Department of Computer Science & Mathematics<br class="">Combinatorics & Theoretical Seminar<br class=""><br class=""><b class="">Karthik Chandrasekaran</b><br class="">(University of Illinois@Urbana-Champaign)<br class=""> <div class="">Tuesday, November 7, 2017<br class="">Ryerson 251 @ 3:30 pm<br class=""><br class="">Title: Beating the 2-factor for Global Bicut<br class=""><br class="">Abstract:<br class=""><br class="">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 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 and admits a simple 2-approximation, which is also the best possible approximation factor assuming the unique games conjecture. In contrast, we show that global bicut admits a (2-eps)-approximation for eps>0. In this talk, I will highlight the techniques behind the (2-eps)-approximation. I will also mention some related cut problems and open questions.<br class="">Based on joint work with Kristof Berczi, Tamas Kiraly, Euiwoong Lee and Chao Xu.<br class=""><br class="">Host: Prof. Yury Makarychev<br class="">(Refreshments will be served prior to the talk in Ry. 255 @ 3pm)</div></body></html>