Unique Maximum Matching Algorithms

doi:10.1006/jagm.2001.1167

Journal of Algorithms

Volume 40, Issue 2, August 2001, Pages 159-183

https://doi.org/10.1006/jagm.2001.1167 Get rights and content

Abstract

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log⁴ n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of planar graphs, we improve the algorithm to run in O(n log n) time. Second, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. A generalization of Kotzig's theorem proved by Jackson and Whitty allows us to give a modification of the first algorithm that tests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f-factor is unique. Both extensions have the same time bounds as their perfect matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds' algorithm for computing such a matching. The method is an extension of our algorithm for the unweighted case.

References (31)

H.N. Gabow
Algorithmic proofs of two relations between connectivity and the 1-factors of a graph
Discrete Math.
(1979)
H.N. Gabow et al.
A linear time algorithm for a special case of disjoint set union
J. Comput. System Sci.
(1985)
D.D. Sleator et al.
A data structure for dynamic trees
J. Comput. System Sci.
(1983)
Mikkel Thorup
Decremental dynamic connectivity
J. Algorithms
(1999)
S. Alstrup et al.
Minimizing diameters of dynamic trees
Proc. 24th International Colloquium on Automata, Languages, and Programming (ICALP)
(1997)
S. Alstrup et al.
Maintaining center and median in dynamic trees
Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT)
(2000)
M.O. Ball et al.
An analysis of alternative strategies for implementing matching algorithms
Networks
(1983)
T.C. Biedl et al.
Efficient algorithms for Petersen's matching theorem
Proc. 10th Annual ACM–SIAM Symposium on Discrete Algorithms
(1999)
R.B. Carey et al.
Graph-theoretic approach to RNA modeling using comparative data
Proc. 3rd International Conference on Intelligent Systems for Molecular Biology
(1995)
J. Edmonds
Maximum matching and a polyhedron with 0, 1-vertices
J. Res. Nat. Bur. Standards
(1965)

J. Edmonds

Paths, trees, and flowers

Canad. J. Math.

(1965)

G.N. Frederickson

Data structures for on-line updating of minimum spanning trees, with applications

SIAM J. Comput.

(1985)

H.N. Gabow

An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems

Proc. 15th Annual ACM Symposium on Theory of Computing

(1983)

H.N. Gabow et al.