Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T11:01:34.014Z Has data issue: false hasContentIssue false

Max Cut for Random Graphs with a Planted Partition

Published online by Cambridge University Press:  24 September 2004

B. BOLLOBÁS
Affiliation:
Trinity College, Cambridge CB2 1TQ and Department of Mathematical Sciences, University of Memphis, Memphis TN38152, USA (e-mail: [email protected])
A. D. SCOTT
Affiliation:
Department of Mathematics, University College London, Gower Street, London WC1E 6BT, UK (e-mail: [email protected])

Abstract

We give an algorithm that, with high probability, recovers a planted $k$-partition in a random graph, where edges within vertex classes occur with probability $p$ and edges between vertex classes occur with probability $r\ge p+c\sqrt{p\log n/n}$. The algorithm can handle vertex classes of different sizes and, for fixed $k$, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.

Type
Research Article
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)