Breaking the Barrier for Minimum Bipartite Dijoin via Dynamic and Local Graph AlgorithmsResearch Paper
A dijoin of a digraph is a set of arcs whose contraction makes the digraph strongly connected; equivalently, a set of arcs meeting every dicut, the nonempty set of arcs crossing a vertex bipartition when all crossing arcs point the same way. Lucchesi and Younger proved in 1978 that the minimum size of a dijoin equals the maximum number of pairwise…