Karp–Sipser heuristic:

On the degree-1 and degree-2 reduction rules

Karp–Sipser (KS) [5] heuristic is a well-known method to obtain high quality matchings in undirected graphs, bipartite graphs, and hypergraphs.  This heuristic is based on two reduction rules. The first rule says that if there is a vertex with degree one, then we can match that vertex with its unique neighbor and remove both from the graph without any loss.  The second rule says that if there is a vertex v with degree two, then its neighbors can be coalesced, and the vertex v can be discarded. A maximum matching on the reduced graph can be extended to a maximum matching on the original graph. If there is no degree-1 or degree-2 vertices, then a randomly selected edge is used to match two vertices, upon which both of them are removed.

The (full) heuristic with the degree-2 reduction rule turns out to be difficult to analyse. That is why most studies are conserved with the variant with the degree-1 reduction rule. This variant has excellent practical performance [6,7], good theoretical guarantees for certain classes of random graphs [2,5], and can be made to have an approximation ratio around 0.866 [3] for bipartite graphs and a close-by ratio on general graphs [4]. There are graphs for which KS with only the degree-1 reduction can obtain worse results. The following is an example and a table from [3].

The bipartite graph instances giving hard time to KS with the degree-1 rule correspond to the following matrices (rows form one part, and the columns form the other part) . The rows and columns are split into two sets in the middle, yielding a 2\times 2 structure. The (1,1)-block is full, the (2,2)-block is empty, and there is an identity matrix at the other two blocks. In order to hide the perfect matching composed of those two identity matrices, additional nonzeros are added to the last t rows in the first row block, and the last t columns in the first column block so that those rows and columns become dense. For n=3200, and with different thickness t\in \{2,4,8,16, 32\} in the full rows, KS with only the degree-1 rule obtains the performance shown in the table.

ks1wcase

t Performance
2 0.782
4 0.704
8 0.707
16 0.685
32 0.670

We want to now turn attention to the full KS (that is with the degree-1 and degree-2 reduction rules). Anastos and Frieze [1] state in the abstract of a recent arXiv paper:

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser (FOCS 1981) proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results in the orignal paper suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random cubic graphs. We show that w.h.p. the first algorithm will find a matching of size n/2-O(\log n) on a random cubic graph (indeed on a random graph with degrees in \{3, 4\}). We also show that the algorithm can be adapted to find a perfect matching w.h.p. in O(n) time, as opposed to O(n^{3/2}) time for the worst-case.

This wonderful result shows improvement with the degree-2 reductions (over using only degree-1 reductions): instead of leaving out O(n^{1/5}) vertices as KS with the degree-1 rule only, it leaves out only \log n vertices. We can also create instances for which KS with both reduction rules obtains perfect matchings, whereas that with the degree-1 reduction obtains inferior results. These instances are upper (or lower) Hessenberg matrices, or more sparser versions of it (for example if we discard all but the first and the last subdiagonal nonzeros). A figure is shown below with only two subdiagonal nonzeros. On these instances, an immediate application of the degree-2 reduction triggers a chain of degree-1 reductions, until we have a 2\times 2 matrix, whose perfect matching is obtained by a degree-2 and then a degree-1 reduction. On the other hand, KS with only the degree-1 rule obtains the performance shown in the table for different n (the performance reported in the table is average of 10 different random runs on the same instance).

ks1vs2case

n Performance
500 0.828
1000 0.790
5000 0.754

There is a catch though. While there is a linear time, straightforward implementation of the degree-1 rule, the straightforward implementation of the degree-2 rule can be quadratic in the worst case; consider repetitive merges with the same vertex which will happen with an Hessenberg matrix. We can perhaps assume that the worst cases are rare in practice, but nonetheless a worst-case quadratic run time complexity is a lot!

References

  1. Michael Anastos and Alan Frieze, Finding perfect matchings in random cubic graphs in linear time, arXiv preprint arXiv:1808.00825, Nov., 2018. (url)
  2. Jonathan Aronson, Alan Frieze, and Boris G. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures & Algorithms, 12 (1998), pp. 111-177.
  3. Fanny Dufossé, Kamer Kaya, and Bora Uçar, Two approximation algorithms for bipartite matching on multicore architectures, Journal of Parallel and Distributed Computing, 85 (2015), pp. 62–78. (doi)
  4. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, and Bora Uçar, Approximation algorithms for maximum matchings in undirected graphs, Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, Bergen, Norway, 2018, pp. 56–65. (doi)
  5. Richard M. Karp and Michael Sipser, Maximum matching in sparse random graphs, 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1981, pp. 364–375. (doi)
  6. Johannes Langguth, Fredrik Manne, and Peter Sanders, Heuristic initialization for bipartite matching problems, Journal of Experimental Algorithmics, 15 (2010), pp. 1.1–1.22. (doi)
  7. Jakob Magun, Greedy matching algorithms, an experimental study, Journal of Experimental Algorithmics, 3 (1998). (doi)

9 November 2018

Today was a great day at the school. There were two remarkable events. The first one is the 30th anniversary of the lab LIP at ENS Lyon (here is the program). The second was that the ENS Lyon awarded Marc Snir with an honorary doctorate degree (Docteur Honoris Causa). The page announcing this event is in French and google translate does a good job in translating it to English. Yves Robert had slides for introducing Marc during the event.

Marc Snir
Marc Snir

Many of us know Marc (ever heard of the MPI standard and the book “MPI: The complete reference“). His work span complexity theory, to MPI standard, to parallel computing systems. And oh, he speaks French.

I was lucky to see his talk during the 30th anniversary of the LIP (but unlucky to miss the ceremony of Docteur Honoris Causa). He gave an overview of his involvement with building parallel machines: BlueGene, Blue Waters, SP/Vulcan, and others. His talk has many whimsical observations. Here are some:

  • A supercomputer research prototype is an oxymoron.
  • A supercomputer research design is either boring or unpractical.
  • The main contribution [of all the supercomputer design projects]: The projects educated a generation of researchers.
  • Theory informs practice, but should not be taken literally.

After stating

Often theory follows practice, rather than practice following theory

he discussed how his paper with Upfal and Felperin was motivated by Vulcan’s practically well behaving design of \log N + O(1) stages. Back then, the theory demonstrated 2\log N stages to avoid worst cases. The cited paper shows \log N + \log\log N, where the extra term is O(1) for practical purposes.

After the talk, I wondered which computer he helped to build was his favorite. He said, more or less,

I created them, so all are my favorite !

References

Eli Upfal, Sergio Felperin, and Marc Snir, Randomized routing with shorter paths, IEEE Transactions on Parallel and Distributed Systems, 7(4), pp. 356–362, 1996. (doi)