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 : 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.. 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 . In contrast, Penso, Rautenbach, and dos Santos Souza gave a characterization and a polynomial-time recognition algorithm for graphs that have a uniquely restricted maximum matching.