Király Tamás: An overview of BiCut and related cut problems in directed graphs

In the (s,t)-bicut problem, the input is an arc-weighted directed graph with two specified nodes s and t, and the goal is to find a minimum weight arc set whose removal ensures that s cannot reach t and t cannot reach s. The global bicut problem has no specified nodes in the input; instead, the goal is to find a minimum weight arc set whose removal ensures that there exist two nodes s and t such that s cannot reach t and t cannot reach s. In symmetric digraphs, these problems are equivalent to undirected (s,t)-mincut and global mincut, respectively; however, in general digraphs, they are much more difficult than (s,t)-mincut and global mincut. In this talk I review some recent results about bicuts and some related cut problems.