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

Access Restriction
Subscribed

 Author Cygan, Marek ♦ Gabow, Harold N ♦ Sankowski, Piotr Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Maximum weight matchings ♦ Diameter and radius ♦ Matrix multiplication ♦ Shortest cycle 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 $\textit{Õ}(\textit{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 $\textit{Õ}(\textit{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 $\textit{Õ}(\textit{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 $\textit{Õ}(\textit{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 $\textit{t},$ for some given $\textit{t}.$ We give a simple $\textit{Õ}(\textit{Wnω})$ time algorithm for this problem that improves over the $\textit{Õ}(\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-09-11 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 4 Page Count 30 Starting Page 1 Ending Page 30

Open content in new tab

Source: ACM Digital Library