# Graphs extendable to a uniquely matchable bipartite graph

Can we characterize bipartite graphs that can be extended (by adding edges) to a bipartite graph with a unique perfect matching?

The problem is NP-complete. A related problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk ^{[1]}: given a bipartite graph *G* and an integer *k*, decide if *G* has an induced subgraph on *2k* nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the present problem if we add *n-k* isolated nodes to both classes. This means that the input parameter *k* is redundant, it can be simply *n*, the number of vertices of *G*, in which case it becomes equivalent to our problem.

A very short summary of the reduction: The reduction is from the Largest Balanced Independent Set problem, where the input is a bipartite graph *G* and a *k* and the question is whether it contains an empty [math]K_{k,k}[/math] (where the *k-k* vertices must be from different classes).
We will call the two classes of G top and bottom. Take *k+1* copies of *G*, denoted by *(1,G),...,(k+1,G)* and connect a vertex of the top i-th copy, *(i,u)*, to a vertex of the bottom j-th copy, *(j,v)*, if (1) i<j or (2) *u* and *v* are connected in *G*. In this new graph, *G'*, there is a uniquely matchable subgraph on [math]2k^2+2k[/math] vertices if and only if *G* has a balanced independent set with *2k* vertices. Proof:

If *G* has a balanced independent set with *2k* vertices, then trivially *G'* has a a uniquely matchable subgraph on [math]2k^2+2k[/math] vertices.

Now suppose that *G'* has a a uniquely matchable subgraph on [math]2k^2+2k[/math] vertices. Order this subgraph such that no edge goes from top-right to bottom-left.
Take the vertex from the right of the top with the *k.* different second coordinate, *w*, and denote by *m* the lowest first coordinate occurred until that vertex. Notice that bottom-left from *w* the first coordinates are at most *m* (unless there is a balanced independent set with *2k* vertices in *G*) and use the pigeon hole principle:
|Vertices Top-right from *w*| + |*w*| + |Vertices Bottom-left from *w*| [math]\le (k-1)(k-m+2)+1+(k-1)m=k^2+k-1[/math],
so there must be one more vertex, contradiction.

## Remarks

This problem was proposed by Günter Rote. It is easy to decide in an arbitrary graph if a perfect matching *M* is unique, by checking for every [math]e \in M[/math] if *M-e* is a maximum matching in *G-e* . For bipartite graphs, the following characterization theorem holds:

**Theorem.** A perfect matching *M* in a bipartite graph *G=(A,B;E)* is unique if and only if the vertices of *A* and *B* can be ordered such that [math]a_ib_i \in M[/math] (*i=1,...,n*) and [math]a_ib_j \notin E[/math] if [math]1 \leq i \ltj \leq n[/math].

It follows that if a bipartite graph on *2n* nodes can be extended to a bipartite graph with a unique perfect matching, then it cannot contain a complete bipartite subgraph of size *n+2*. Another (obvious) necessary condition is that the graph cannot contain two perfect matchings. However, as the following example shows, these conditions are not sufficient:

A related problem was considered by Golumbic et al.^{[2]}. They showed that in a bipartite graph it is NP-complete to find a matching of maximum size with the property that it is the unique perfect matching of the subgraph induced by its nodes (a *uniquely restricted matching*). The problem is polynomial-time solvable for interval graphs ^{[3]}. In contrast, Penso, Rautenbach, and dos Santos Souza ^{[4]} gave a characterization and a polynomial-time recognition algorithm for graphs that have a uniquely restricted maximum matching.

## References

- ↑ B. Dasgupta, T. Jiang, S. Kannan, M. Li, E Sweedyk,
*On the complexity and approximation of syntenic distance*, Discrete Applied Mathematics 88 (1998), 59-82, DOI link author link - ↑ M. C. Golumbic, T. Hirst, M. Lewenstein,
*Uniquely Restricted Matchings*, Algorithmica 31 (2001), 139-154. DOI link. author link - ↑ M.C. Francis, D. Jacob, S. Jana,
*Uniquely Restricted Matchings in Interval Graphs*, arXiv link - ↑ L.D. Penso, D. Rautenbach, U. dos Santos Souza,
*Graphs in which some and every maximum matching is uniquely restricted*, arXiv link