On the max-cut of sparse random graphs

DOI10.1002/RSA.20738MaRDI QIDQ4564857zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Quan Li

Publication date 7 June 2018

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

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

zbMATH Keywords

large deviationslocal optimalitymaximum cutsmoment methodsrandom graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random ErdH{o}s-R'{e}nyi graph on $n$ nodes and $lfloorcnfloor$ edges. It is shown in Coppersmith et al. ~cite{Coppersmith2004} that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region $[c/2+0.37613sqrtc,c/2+0.58870sqrtc]$ with high probability (w.h.p.) as $n$ increases, for all sufficiently large $c$. In this paper we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval $[c/2+0.47523sqrtc,c/2+0.55909sqrtc]$ w.h.p. as $n$ increases, for all sufficiently large $c$. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as $c$ increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value $c/2+0.47523sqrtc$. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of $1.36000n$ on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of $1.33773n$.

Recommendations

• The MAX-CUT of sparse random graphs
• A probabilistic result for the max-cut problem on random graphs
• Extremal cuts of sparse random graphs
• On the maximal cut in a random hypergraph
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances

Cited in

(25)

• Balanced cut approximation in random geometric graphs
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• On the maximal cut in a random hypergraph
• Extremal cuts of sparse random graphs
• Suboptimality of local algorithms for a class of max-cut problems
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• Optimization on sparse random hypergraphs and spin glasses
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• The MAX-CUT of sparse random graphs
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• (Dis)assortative partitions on random regular graphs
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Local approximation of the maximum cut in regular graphs
• A probabilistic result for the max-cut problem on random graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Friendly bisections of random graphs
• MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• On the minimum bisection of random 3-regular graphs
• New results for MaxCut in H$H$‐free graphs
• On perfectly friendly bisections of random graphs
• Partitioning problems via random processes
• Maximum chordal subgraphs of random graphs
• Triangles improve 0.878 approximation for Maxcut

This page was built for publication: On the max-cut of sparse random graphs

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