Bipartition-constrained edge-connectivity augmentation avoiding a prescribed perfect matching
(suggested by Jørgen Bang-Jensen)
Question: Is the following problem polynomial time solvable?
Let G = (U∪V,E) be a bipartite graph with bipartition U,V such that the bipartite complement of G (that is H=(U∪V,(U×V)-E)) has a perfect matching M. Suppose G is not k-edge-connected. Find a minimum set F of edges such that each edge in F is in (U×V)-E-M (parallel edges allowed) and G+F is k-edge-connected. That is, G+F is bipartite with the same bipartition (U,V) as G.
What is known?
If we do not have to avoid M, then the problem is in P . The motivation for this problem, besides being a natural restriction of the bipartition-constrained edge-connectivity augmentation problem comes from : the minimum size of F is equal to the minimum number of new arcs F we must add to a digraph D in order to be able to pack k arc-disjoint antistrong spanning digraphs in D+F.
 J. Bang-Jensen, H. Gabow, T. Jordán and Z. Szigeti, Edge-connectivity augmentation with partition constraints, Siam J. Disc. Math 12 (1999), 160-207.
 J. Bang-Jensen, S. Bessy, B. Jackson and M. Kriesell, Antistrong digraphs, (2015), submitted.