Algorithmic Applications of Baur-Strassen’s Theorem

DOI10.1145/2736283zbMATH Open1426.05164arXiv1204.1616OpenAlexW2151827175MaRDI QIDQ3177733FDOQ3177733

Harold N. Gabow, Piotr Sankowski, Marek Cygan

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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 paper, 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 ilde{O}(Wn^{omega}) time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with non-negative weights) this matches the time bounds obtained in 2011 by Roditty and Vassilevska-Williams. On the other hand, no algorithm working in ilde{O}(Wn^{omega}) 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 ilde{O}(Wn^{omega}) 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 ilde{O}(Wn^{omega}) time algorithm for finding minimum weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski in 2006, who presented such an algorithm but only in the case of bipartite graphs. In order to solve minimum weight perfect matching problem we develop a novel combinatorial interpretation of the dual solution which sheds new light on this problem. Such a combinatorial interpretation was not know previously, and is of independent interest.

Full work available at URL: https://arxiv.org/abs/1204.1616

zbMATH Keywords

diametermatrix multiplicationradiusshortest cyclemaximum weight matchings

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (11)

• Improved distance queries and cycle counting by Frobenius normal form
• A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
• NC Algorithms for Weighted Planar Perfect Matching and Related Problems
• Temporal matching
• Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Two dimensional maximum weight matching using Manhattan topology
• Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
• Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors
• Temporal matching on geometric graph data
• Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey

This page was built for publication: Algorithmic Applications of Baur-Strassen’s Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177733)