research-article

Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings

Authors:

Marek Cygan,

Harold N. Gabow,

Piotr SankowskiAuthors Info & Claims

Journal of the ACM (JACM), Volume 62, Issue 4

Article No.: 28, Pages 1 - 30

https://doi.org/10.1145/2736283

Published: 11 September 2015 Publication History

Get Access

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.

References

[1]

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, N.J.

Abstract

References

Cited By

Index Terms

Recommendations

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

A Decomposition Theorem for Maximum Weight Bipartite Matchings

Finding heaviest H-subgraphs in real weighted graphs, with applications

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations