NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings
Dexter C. Kozen, Umesh V. Vazirani, Vijay V. Vazirani · 1986
Laszlo Lovasz recently posed the following problem: "Is there an NC algorithm for testing if a given graph has a unique perfect matching ?" We present such an algorithm for bipartite graphs. We also give NC algorithms for obtaining a transitive orientation of a comparability graph, and an interval representation of an interval graph. These enable us to obtain an NC algorithm for finding a maximum matching in an incomparability graph. 1 Introduction Karp, Upfal and Wigderson [9] have recently shown that the maximum matching problem is in Random NC 3 (RNC 3 ). This result has since been improved to RNC 2 by Mulmuley, Vazirani, and Vazirani [16]. It remains open whether there is a deterministic NC algorithm for this problem. A first step might be to obtain an NC algorithm for testing if a graph has a perfect matching. An RNC algorithm for this problem exists, based on a method of Lovasz [13] (see [1]). Rabin and Vazirani [18] give an NC algorithm for obtaining perfect matchings in...