Marek Cygan
Harold N. Gabow
Abstract
Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this article, we introduce a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the usage of Baur-Strassen’s theorem and of Strojohann’s determinant algorithm. It allows us to give new and simple solutions to the following problems:
Finding Shortest Cycles. We give a simple Õ(Wnω) time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with nonnegative weights), this matches the time bounds obtained in 2011 by Roditty and Williams. On the other hand, no algorithm working in Õ(Wn ω) time was previously known for undirected graphs with negative weights. Furthermore, our algorithm for a given directed or undirected graph detects whether it contains a negative weight cycle within the same running time.
Computing Diameter and Radius. We give a simple Õ(Wnω) time algorithm for computing a diameter and radius of an undirected or directed graphs. To the best of our knowledge, no algorithm with this running time was known for undirected graphs with negative weights.
Finding Minimum-Weight Perfect Matchings. We present an Õ(Wnω) time algorithm for finding minimum-weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski [2009] who presented such an algorithm but only in the case of bipartite graphs.
These three problems that are solved in the full generality demonstrate the utility of this framework. Hence, we believe that it can find applications for solving larger spectra of related problems. As an illustrative example, we apply it to the problem of computing a set of vertices that lie on cycles of length at most t, for some given t. We give a simple Õ(Wnω) time algorithm for this problem that improves over the Õ(Wnωt) time algorithm given by Yuster in 2011.
Besides giving this flexible framework, the other main contribution of this article is the development of a novel combinatorial interpretation of the dual solution for the minimum-weight perfect matching problem. Despite the long history of the matching problem, such a combinatorial interpretation was not known previously. This result sheds a new light on the problem, as there exist many structural theorems about unweighted matchings, but almost no results that could cope with the weighted case.
- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, N.J. Google Scholar
Digital Library
- Walter Baur and Volker Strassen. 1983. The complexity of partial derivatives. Theoret. Comput. Sci. 22, 3, 317--330. DOI: http://dx.doi.org/10.1016/0304-3975(83)90110-X.Google ScholarCross Ref
- Andreas Björklund. 2010. Determinant sums for undirected hamiltonicity. In Proceedings of FOCS’10. 173--182. Google ScholarDigital Library
- Timothy M. Chan. 2007. More algorithms for all-pairs shortest paths in weighted graphs. In Proceedings of STOC’07. 590--598. Google ScholarDigital Library
- Jack Edmonds. 1965. Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Stand. B 69B, 125--130.Google ScholarCross Ref
- Jack Edmonds. 1967. An introduction to matching. Mimeographed notes, Engineering Summer Conference, University of Michigan, Ann Arbor, MI.Google Scholar
- Harold N. Gabow. 1976. An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J. ACM 23, 2, 221--234. Google ScholarDigital Library
- Harold N. Gabow. 1983. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of STOC’83. 448--456. Google ScholarDigital Library
- Harold N. Gabow. 1985. A scaling algorithm for weighted matching on general graphs. In Proceedings of FOCS’85. 90--100. Google ScholarDigital Library
- Harold N. Gabow. 1990. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of SODA’90. 434--443. Google ScholarDigital Library
- Harold N. Gabow. 2012. A combinatoric interpretation of dual variables for weighted matching and f-factors. Theoret. Comput. Sci. 454, 136--163. http://dx.doi.org/10.1016/j.tcs.2012.06.024. Google ScholarDigital Library
- Harold N. Gabow, Z. Galil, and T.H. Spencer. 1989. Efficient implementation of graph algorithms using contraction. J. ACM 36, 3, 540--572. DOI: http://dx.doi.org/10.1145/65950.65954. Google ScholarDigital Library
- Harold N. Gabow and Robert E. Tarjan. 1991. Faster scaling algorithms for general graph matching problems. J. ACM 38, 4, 815--853. Google ScholarDigital Library
- Zvi Galil, Silvio Micali, and Harold N. Gabow. 1986. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 1, 120--130. Google ScholarDigital Library
- Nicholas J. A. Harvey. 2006. Algebraic structures and algorithms for matching and matroid problems. In Proceedings of FOCS’06. 531--542. Google ScholarDigital Library
- Chien-Chung Huang and Telikepalli Kavitha. 2012. Efficient algorithms for maximum weight matchings in general graphs with small edge weights. In Proceedings of SODA’12. 1400--1412. Google ScholarDigital Library
- Alon Itai and Michael Rodeh. 1977. Finding a minimum circuit in a graph. In Proceedings of STOC’77. 1--10. Google ScholarDigital Library
- Donald B. Johnson. 1977. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, 1, 1--13. DOI: http://dx.doi.org/10.1145/321992.321993. Google ScholarDigital Library
- Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, and Hing-Fung Ting. 1999. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Proceedings of ESA’99. 438--449. Google ScholarDigital Library
- Richard M. Karp, Eli Upfal, and Avi Wigderson. 1986. Constructing a perfect matching is in random NC. Combinatorica 6, 1, 35--48. Google ScholarDigital Library
- Anton Kotzig. 1959a. Z teorie konečỳch grafov s lineàrym faktorom I. Matematicko-Fyzikàlny Časopis SAV IX, 2, 73--91.Google Scholar
- Anton Kotzig. 1959b. Z teorie konečỳch grafov s lineàrym faktorom II. Matematicko-Fyzikàlny Časopis SAV IX, 3, 136-- 159.Google Scholar
- Anton Kotzig. 1960. Z teorie konečỳch grafov s lineàrym faktorom III. Matematicko-Fyzikàlny Časopis SAV IX, 4, 205--215.Google Scholar
- Eugene L. Lawler. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York.Google Scholar
- László Lovász and Michael D. Plummer. 1986. Matching Theory. Akadémiai Kiadó.Google Scholar
- Jacques Morgenstern. 1985. How to compute fast a function and all its derivatives: a variation on the theorem of Baur-strassen. SIGACT News 16, 4, 60--62. DOI: http://dx.doi.org/10.1145/382242.382836. Google ScholarDigital Library
- Marcin Mucha and Piotr Sankowski. 2004. Maximum matchings via Gaussian elimination. In Proceedings of FOCS’04. 248--255. Google ScholarDigital Library
- Seth Pettie. 2004. A new approach to all-pairs shortest paths on real-weighted graphs.Theoret. Comput. Sci. 312, 1, 47--74. Google ScholarDigital Library
- Liam Roditty and Virginia Vassilevska Williams. 2011. Minimum weight cycles and triangles: Equivalences and algorithms. In Proceedings of FOCS’11. 180--189. Google ScholarDigital Library
- Piotr Sankowski. 2005a. Processor efficient parallel matching. In Proceedings of SPAA’05. 165--170. Google ScholarDigital Library
- Piotr Sankowski. 2005b. Shortest paths in matrix multiplication time. In Proceedings of ESA’05. 770--778. Google ScholarDigital Library
- Piotr Sankowski. 2009. Maximum weight bipartite matching in matrix multiplication time. Theoret. Comput. Sci. 410, 44, 4480--4488. Google ScholarDigital Library
- A. Schrijver. 2003. Combinatorial Optimization -- Polyhedra and Efficiency. Springer-Verlag.Google Scholar
- Jacob T. Schwartz. 1980. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 701--717. Google ScholarDigital Library
- Avi Shoshan and Uri Zwick. 1999. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of FOCS’99. 605--614. Google ScholarDigital Library
- Arne Storjohann. 2003. High-order lifting and integrality certification. J. Symb. Computat. 36, 3--4, 613--648. DOI: http://dx.doi.org/10.1016/S0747-7171(03)00097-X. Google ScholarDigital Library
- J. W. Suurballe and Robert E. Tarjan. 1984. A quick method for finding shortest pairs of disjoint paths. Networks 14, 2, 325--336. DOI: http://dx.doi.org/10.1002/net.3230140209.Google ScholarCross Ref
- Raphael Yuster. 2011. A shortest cycle for each vertex of a graph. Inform. Process. Lett. 111, 21--22, 1057--1061. DOI: http://dx.doi.org/10.1016/j.ipl.2011.07.019. Google ScholarDigital Library
- Raphael Yuster and Uri Zwick. 2005. Answering distance queries in directed graphs using fast matrix multiplication. In Proceedings of FOCS’05. 389--396. Google ScholarDigital Library
- Richard Zippel. 1979. Probabilistic algorithms for sparse polynomials. In Proceedings of EUROSAM’79. 216--226. Google ScholarDigital Library
- Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3, 289--317. Google ScholarDigital Library
Index Terms
- Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings
Recommendations
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer ScienceConsider a directed or undirected graph with integral edge weights in [â'W, W ]. This paper introduces a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the Baur-Strassen Theorem and ...
A Decomposition Theorem for Maximum Weight Bipartite Matchings
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x / log (x2/y). We present a new decomposition ...
Finding heaviest H-subgraphs in real weighted graphs, with applications
For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. Our main results are new strongly polynomial algorithms for the MAX H-SUBGRAPH problem. ...
Comments