Incrementing bipartite digraph edge-connectivity (Q1592842)

The authors solve the problem to increase the edge connectivity of a bipartite digraph by adding the smallest number of edges that keep the graph bipartite. This problem is motivated from statics where a square grid framework should be reinforced by cables. Actually, the more general problem of covering a crossing family of sets with the smallest number of directed edges is solved, where each edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula which has six infinite families of exceptional cases (blockers). Moreover, two other incrementation problems with a similar structure are solved: one concerns a problem on network flows which has three families of blockers. The other concerns spanning arborescences that has five families of blockers. For increasing the edge connectivity of a bipartite digraph with \(n\) vertices, \(m\) edges and the target connectivity \(k\), which keeps bipartiteness, the authors state an algorithm of time complexity \(O(km \log n)\) in the unweighted case and of \(O(nm \log (n^2/m))\) in the weighted case.