skip to main content


Title: Finding maximum matchings in random regular graphs in linear expected time
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 by Karp and Sipser suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for randomk‐regular graphs. We show that w.h.p. the first algorithm will find a matching of sizein a randomk‐regular graph,k = O(1). We also show that the algorithm can be adapted to find a maximum matching inO(n)time w.h.p. This is to be compared withO(n3/2)time for the worst‐case.

 
more » « less
PAR ID:
10240191
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
58
Issue:
3
ISSN:
1042-9832
Page Range / eLocation ID:
p. 390-429
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that, whereis the maximal degree andmis the number of edges, the algorithm runs in expected timeO(m). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected timefor the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power‐law degree sequences in cases where the previous best wasO(n4.081), and (ii)O(nd + d4) ford‐regular graphs when, where the previous best wasO(nd3).

     
    more » « less
  2. Let Ωqq(H) denote the set of proper [q]‐colorings of the hypergraphH. Let Γqbe the graph with vertex set Ωqwhere two coloringsσ,τare adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH=Hn,m;k, k ≥ 2, the randomk‐uniform hypergraph withV=[n] andm=dn/khyperedges then w.h.p. Γqis connected ifdis sufficiently large and. This is optimal up to the first order ind. Furthermore, with a few more colors, we find that the diameter of ΓqisO(n) w.h.p., where the hidden constant depends ond. So, with this choice ofd,q, the natural Glauber dynamics Markov Chain on Ωqis ergodic w.h.p.

     
    more » « less
  3. We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in(n, p) for nearly optimalp(up to afactor). In particular, we show that givent = (1 − o(1))npHamilton cyclesC1,…,Ct, each of which is oriented arbitrarily, a digraph(n, p) w.h.p. contains edge disjoint copies ofC1,…,Ct, provided. We also show that given an arbitrarily orientedn‐vertex cycleC, a random digraph(n, p) w.h.p. contains (1 ± o(1))n!pncopies ofC, provided.

     
    more » « less
  4. Abstract

    Consider the upper tail probability that the homomorphism count of a fixed graphHwithin a large sparse random graphGnexceeds its expected value by a fixed factor. Going beyond the Erdős–Rényi model, we establish here explicit, sharp upper tail decay rates for sparse randomdn‐regular graphs (providedHhas a regular 2‐core), and for sparse uniform random graphs. We further deal with joint upper tail probabilities for homomorphism counts of multiple graphs(extending the known results for), and for inhomogeneous graph ensembles (such as the stochastic block model), we bound the upper tail probability by a variational problem analogous to the one that determines its decay rate in the case of sparse Erdős–Rényi graphs.

     
    more » « less
  5. Abstract

    Given ak‐vertex graphHand an integern, what are then‐vertex graphs with the maximum number of induced copies ofH? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction ofk‐vertex subsets of ann‐vertex graph that induce a copy ofH. Huang, Lee, and the first author proved that for a randomk‐vertex graphH, almost surely then‐vertex graphs maximizing the number of induced copies ofHare the balanced iterated blow‐ups ofH. In this article, we consider the case where the graphHis obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely alln‐vertex graphs maximizing the number of induced copies ofHare balanced iterated blow‐ups of.

     
    more » « less