This blog is maintained by members of Algorithmic group at University of Warsaw:
- Krzysztof Ciebiera
- Marek Cygan
- Łukasz Kowalik
- Jakub ??cki
- Marcin Mucha
- Marcin Pilipczuk
- Piotr Sankowski
Finally, were able to show how to find minimum weight perfect matchings in non-bipartite graph using matrix multiplication. This was some years of trying after my paper from ICALP 2006, where the bipartite case was solved. However, with big help of Marek Cygan and Hal Gabow we have found rather elegant solution. The algorithm is very simple and given blow. Nevertheless, the proof of it correctness is not straight forward and requires some nontrivial structural properties.
Minimum weight perfect matching algorithm:
- Remove non-allowed edges from the graph, i.e., edges that do not belong to any minimum weight perfect matching,
- Compute M(v) minimum weight almost perfect matching that misses the vertex v,
- Define new weights of edges w’(uv) = w(uv) + w(M(u)) + w(M(v)),
- Connected components of E = {uv : w’(uv)<a}, for all a, encode the family of blossoms,
- Using algorithm for maximum cardinality matchings find a matching that crosses each blossom once.
This gives an algorithm working in time, where W is the maximal edge weight and ? is the matrix multiplication exponent. In the case of dense graphs with small integral weights our algorithm is faster than the O(n(m+n log n)) time algorithm of Gabow from 90 and the
time algorithm of Gabow and Tarjan from 91. Previously known algorithms for this problem were using augmenting paths. This algorithm is very different and is based on structural properties that give combinatorial relation between matchings weights and the dual solution. In particular, we show that there exists a canonical dual solution that is unique.
During the work we realized that the tools developed in the paper, i.e., usage of Baur-Strassen’s theorem for the computation of allowed edges, can be used to solve other problems as well. The framework appeared to be very powerful and we were able to solve the shortest cycle problem and the diameter problem in their full generality. Previous solutions for these problems that used matrix multiplication did not handle the case of undirected graphs with negative weights. Observe that in such case even detecting whether a graph has negative length cycle is nontrivial. The Bellman-Ford algorithm does not work here as it works only in the case of directed graphs. However, the problem can be solved by a reduction to the minimum weight perfect matching problem.
After the submission we realized that some other problems can be solved using this framework. One can compute the radius of the graph, as well as solve the single source shortest path problem in undirected graph with negative weights, but without negative weight cycles. Previously known algorithm for shortest paths worked only in the case of directed graphs with negative weights.
This was a rather interesting ICALP in Warwick. Actually, some people called it Polish ICALP ;). There was a visible number of participants who were from Poland as well as the ones who graduated from our universities. This includes the main organizer Artur Czumaj. During the event we realized to be the only university that had a PC member in every track:
- in Track A - Piotr Sankowski,
- in Track B - Bartek Klin and Andrzej Tarlecki,
- in Track C - Stefan Dziembowski.