Using Cut Queries in \(\gamma\)-Balanced Graphs

Abstract

The classic graph mincut problem has been much studied in the traditional sequential model of computing. In the cut-query oracle model, the mincut problem is a special case of submodular function minimization via an evaluation oracle, a problem for which there is a significant gap between the known upper and lower bounds. Prior work by Rubinstein, Schramm, and Weinberg surprisingly found that the mincut of an undirected graph can be found using only (\tilde O(n)) undirected cut queries, while (\tilde O(n^2)) are necessary to learn the graph in the general case. A past Princeton thesis by Mon attempted to generalize this work on undirected graphs to the directed case, making progress but not formulating a complete algorithm. This thesis picks up where Mon’s left off, examining several novel approaches to the directed mincut problem that attempt to find the mincut using (\tilde o(n^2)) queries. Each of these approaches, however, is not correct in often subtle ways, revealing some of the difficulties when considering directed graphs in the cut-oracle model.