# Bipartition-constrained edge-connectivity augmentation avoiding a prescribed perfect matching

(suggested by Jørgen Bang-Jensen)

# Problem Statement

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 [1]. The motivation for this problem, besides being a natural restriction of the bipartition-constrained edge-connectivity augmentation problem comes from [2]: 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.

# References

[1] 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.

[2] J. Bang-Jensen, S. Bessy, B. Jackson and M. Kriesell, Antistrong digraphs, (2015), submitted.