Finding maximum matchings in random regular graphs in linear expected time

DOI10.1002/RSA.20980MaRDI QIDQ6049997zbMATH OpenOpenAlexFDO

Authors Michael Anastos, Alan Frieze

Publication date 11 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Karp-Sipser algorithmmaximum matchingrandom regular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Abstract: In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results in cite{KS} suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random cubic graphs. We show that w.h.p. the first algorithm will find a matching of size $n/2-O(logn)$ on a random cubic graph (indeed on a random graph with degrees in $3,4$). We also show that the algorithm can be adapted to find a perfect matching w.h.p. in $O(n)$ time, as opposed to $O(n^{3/2})$ time for the worst-case.

Recommendations

• scientific article; zbMATH DE number 1139976
• scientific article; zbMATH DE number 1512672
• Matching algorithms are fast in sparse random graphs
• Small maximal matchings in random graphs.
• STACS 2004

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• Controllability and matchings in random bipartite graphs
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• scientific article; zbMATH DE number 2127722 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• Karp-Sipser on random graphs with a fixed degree sequence
• On tail probabilities for martingales
• Probability Inequalities for Sums of Bounded Random Variables
• The rank of diluted random graphs

Cited in

(12)

• Maximum matching in regular and almost regular graphs
• Matching algorithms are fast in sparse random graphs
• Karp-Sipser on random graphs with a fixed degree sequence
• Computing large matchings fast
• A Fast Perfect-Matching Algorithm in Random Graphs
• Average-case analysis of algorithms for matchings and related problems
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• scientific article; zbMATH DE number 1512672 (Why is no real title available?)
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• scientific article; zbMATH DE number 1929931 (Why is no real title available?)
• The time complexity of maximum matching by simulated annealing
• STACS 2004

This page was built for publication: Finding maximum matchings in random regular graphs in linear expected time

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