Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

DOI10.1137/20M1330415MaRDI QIDQ4990395zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe

Publication date 28 May 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsgirthweighted graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Abstract: Given an $n$-vertex $m$-edge graph $G$ with non negative edge-weights, the girth of $G$ is the weight of a shortest cycle in $G$. For any graph $G$ with polynomially bounded integer weights, we present a deterministic algorithm that computes, in $ildecalO(n^{5/3}+m)$-time, a cycle of weight at most twice the girth of $G$. Our approach combines some new insights on the previous approximation algorithms for this problem (Lingas and Lundell, IPL'09; Roditty and Tov, TALG'13) with Hitting Set based methods that are used for approximate distance oracles and date back from (Thorup and Zwick, JACM'05). Then, we turn our algorithm into a deterministic $(2+varepsilon)$-approximation for graphs with arbitrary non negative edge-weights, at the price of a slightly worse running-time in $ildecalO(n^{5/3}lo{g}^{calO(1)}(1/varepsilon)+m)$. Finally, if we insist in removing the dependency in the number $m$ of edges, we can transform our algorithms into an $ildecalO(n^{5/3})$-time randomized $4$-approximation for the graphs with non negative edge-weights -- assuming the adjacency lists are sorted. Combined with the aforementioned Hitting Set based methods, this algorithm can be derandomized, thereby yielding an $ildecalO(n^{5/3})$-time deterministic $4$-approximation for the graphs with polynomially bounded integer weights, and an $ildecalO(n^{5/3}lo{g}^{calO(1)}(1/varepsilon))$-time deterministic $(4+varepsilon)$-approximation for the graphs with non negative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs.

Recommendations

• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Approximate shortest paths in weighted graphs
• Finding shorter cycles in a weighted graph
• Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• scientific article; zbMATH DE number 1215999
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 7561542 (Why is no real title available?)
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Approximate distance oracles
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Approximate distance oracles with constant query time
• Approximate distance oracles with improved preprocessing time
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Approximating the girth
• Automata, Languages and Programming
• Better approximation algorithms for the graph diameter
• Constant girth approximation for directed graphs in subquadratic time
• Distance oracles beyond the Thorup-Zwick bound
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding Even Cycles Even Faster
• Finding a Minimum Circuit in a Graph
• Graph theory
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• On Graphs that do not Contain a Thomsen Graph
• Subcubic equivalences between path, matrix, and triangle problems

Cited in

(8)

• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Approximating the girth
• Approximating the girth
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• The summation and bottleneck minimization for single-step searching on weighted graphs

This page was built for publication: Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

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