A Matchless Result
A famous algorithm, a new paper, a full correctness proof
Vijay Vazirani is one of the world experts on algorithmic theory, and is especially known for his masterful book on approximation algorithms. Among many results in computational complexity, two have been Wikified: his theorem with Les Valiant on unique SAT, and the subsequent generalized Isolation Lemma with Ketan Mulmuley and his brother Umesh Vazirani. Lately his focus has been more on computational aspects of auctions, economic systems, and game theory.
Today Ken and I wish to discuss a recent paper by Vijay on matching.
His paper is quite unique—is “quite” redundant?—well it is an isolated case of a top researcher taking the time and energy to explain the correctness of one of his famous algorithms, originally in joint work with Silvio Micali. As our field matures we should see more of this.
Given an undirected graph 
has six different perfect matchings: the five “spokes” and others using just one spoke. Although matchings are often associated with bipartite graphs, it is important to note that the Petersen graph is not bipartite. This is important since the matching algorithm we will discuss works for general graphs, not just bipartite graphs.
The Importance Of Matching
Finding a maximum matching is one of the foundational problems at the intersection of graph theory and algorithmic theory. The reason for this is:
- The problem is useful in practice. Unlike many problems that are sometimes studied in theory, people really would like to be able to find matchings of general graphs. See this for a detailed list.
-
The problem is basic to the theory of graphs. László Lovász and Michael Plummer wrote an entire book called Matching Theory on—you guessed right—matchings. They shared the Niveau Prize of the Hungarian Academy of Sciences for this book in 1991. We especially like the Amazon review of the book:
The subject has obviously advanced a lot since the book was published, but the overview provided is still unmatched.
Cool pun.
- The problem is basic to the theory of algorithms. Euclid may have the first non-trivial algorithm, his algorithm for finding the gcd of two numbers, but algorithms for matching started over fifty years ago. This is not the place to trace out the long and complex history of who did what algorithm for finding matchings. Suffice it to say that much of the theory of algorithms can be traced to the history of matching algorithms: various tricks and methods that are used through computing often first appeared in matching algorithms. Andras Frank has written a wonderful piece called On Kuhn’s Hungarian Method—A tribute from Hungary about the bipartite case—see it for some interesting history.
Here is a picture of some of the applications of matching algorithms.
Let’s turn to look at Vijay’s new paper.
The Paper’s Tracks
Actually we need to first look at the original paper called An 
We will call this paper the MV paper, and its algorithm the MV algorithm. Note the running time is 
The title of Vijay’s original paper was created before these agreements, so it is understandable that they used the “old” style notation in the title. It is also less prone to the problem that if you write 
This paper presented the MV algorithm with the given running time. The major advance was that it efficiently found a maximum matching in general graphs. There is an interesting cliff that happens in the theory of algorithms for finding maximum matchings. Bipartite graphs are just much easier for matching algorithms. Of course they are easier for many other algorithms: it is trivial to find a 2-coloring of a bipartite graph, but NP-hard to find a 3-colring in a general graph. One of the achievements of the MV paper is that everything works for general graphs.
The new paper is solely authored by Vijay. It has several goals, but the main one is to give a clear but full proof of the correctness of the MV algorithm. The algorithm remains the same, but the correctness proof is new. The previous proof had a flawed case analysis. The new proof avails itself of information that the previous proof bypassed, to make the analysis tighter and more manageable.
We will not give the whole proof, but we will give an algorithmic idea highlighted also by Vijay, which has independent interest.
Dueling Depth-First Searches
Let 
-
there are vertex-disjoint paths from
and
, or
-
the set
every path from
is nonempty.
In the latter case, let 
The main puzzle is, how can we avoid searching past
- Whichever posse is on a higher-level node gets to move; if they are on the same level, Red moves.
-
If one posse’s depth-first search comes to an already-marked empty node
—it could have been marked by either posse on an earlier visit—it goes back and tries another down-edge from its previous node. If there are no more down-edges, it backtracks up from its previous node as in normal depth-first search.
- If the other posse is on node
|
|
By permission of ComicArtFans gallery owner Mark Geier: source commissioned from artist Terry Beatty |
The duel follows gentlemen’s rules. Red shoots in the air. Green takes the hint and backtracks looking for another node 
They can celebrate because they have met the time guarantee: Neither searched below 
Making a search posse on a lower level wait for the other ensures that nodes below a bottleneck don’t get searched. Many other parts of the algorithm similarly rely on co-ordination with delicate timing considerations; this is just a taste of them. The new paper also has many other figurative concepts, with illustrations.
Open Problems
Do read Vijay’s paper. It is one of the clearest expositions of a graph algorithm—a model for others. Also the idea that Vijay went back to an ancient paper—over thirty years old—solely to write the definitive proof of its correctness is something we all should applaud.
Of course the central problem in matching theory is still what is the best time for an algorithm that finds a maximum matching? Given the interest today in huge graphs that arise from social networks we will like a linear time algorithm. Is this possible? See this for some fast approximate algorithms.
[added words “on all paths” to DDFS time requirement, name and word fixes and adds, permission for vintage Green Hornet/Lone Ranger artwork]
“A matching M in an undirected graph G = (V;E) is a set of edges no two of which meet at
a vertex. Our problem is to find a matching of maximum cardinality in the given graph. All
definitions henceforth are w.r.t. a fixed matching M in G.
An alternating path is a simple path whose alternate edges are matched and unmatched. An alternating path that starts and ends at unmatched vertices is called an augmenting path.”
I can infer the definition of unmatched edges, but what the heck are unmatched vertices?
I shouldn’t be stuck on the definitions in a paper that supposedly has a “lot to be desired in terms of correctness, completeness and clarity”.
“VV” recently started blogging over at Turing invisible hand…. what is this cyberspace neighborhood coming to? 🙄
another interesting factoid about matching from john savage book “models of computation” notes p457, hopes about using monotone circuits to prove major lower bounds were somewhat dashed by the following:
How does this relate to
Norbert Blum: A New Approach to Maximum Matching in General Graphs. ICALP 1990: 586-597
and
Paul A. Peterson, Michael C. Loui: The General Maximum Matching Algorithm of Micali and Vazirani. Algorithmica 3: 511-533 (1988) ?
My outsider impression is that there were other works that had already fixed the issue, but I couldn’t find them cited in the new paper.
In a sense, every algorithm is an approximation algorithm since the notion of correctness lies on psychology, and therefore on probability at the bottom line. The same holds true for proofs. My theory consists in saying that the algorithms you can prove correct with a high degree of certainly, are precisely those you can’t prove efficient with a high certainty, and vice versa. The easy problems are those where this indetermination is hardly noticeable, while the hard problems are those where the notion of polynomial behavior doesn’t even make sense, because the algorithms are all galactic and can’t be run on any physical processor.
Of course this is a theory of physics, not of mathematics. I’m the first to regret, because I would otherwise have thus proved the undecidability of the very undecidability of P=NP. Indeed, by just setting the Planck constant either positive – implying P=NP is undecidable – or null – implying P=NP is decidable – you get the expected result. Nonetheless, I still feel that algorithms behave like particles under the analogy “proof of correctness”= “position measurement”, “proof of efficiency” = “speed measurement”, undecidability = indetermination.
In fact, the P versus NP problem looks like a logical Möbius strip.
On the one side, it’s purely mathematical and P!=NP appears to be the right hypothesis – though probably unprovable. Ladner’s theorem then explains why there are three distinct kinds of hardness in NP – polynomial, neither polynomial nor NP-complete, NP-complete.
On the other side, the opposite hypothesis P=NP can be described with arguments of pure physics, with quantum leaps between the discrete levels of hardness – e.g. between the hardness of SORTING, FACTORING and SAT. Unfortunately, these arguments are probably unfalsifiable as well.
My conclusion is that we should give up any hope of settling this problem. Blame it on the metaphysics…
The physics level represents the hardware of computer science, whereas the mathematics level represents its software. Making this distinction might lead to new progress. These two levels of computer science should indeed be named differently.
It’s the same distinction as that which is made between logic and mathematics – which is actually software developed upon logical hardware. But logic – the other name of theoretical computer science – lies on an intermediate level between physics and mathematics.
The third level is – in my humble opinion – “the third man” who passes unnoticed much too often…
I was very happy to see Vijay and Vijay’s beautiful paper featured here. I also share the compliments for this unique important endeavor. Making such an effort to give a clear, correct and inspiring proof for this classic algorithm (well it was a type of algorithm that became classic instantaneously but now it is also a few decades old) seems almost a thankless task. But in science often tasks that seems thankless turn out to lead to many fruits and recognition. And, of course, matching is such a great topic. A wonderful never-ending mine for beautiful mathematics, computer science, (and economics and more).