Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-05T23:10:39.579Z Has data issue: false hasContentIssue false
  • English
  • Français

Colouring Semirandom Graphs

Published online by Cambridge University Press:  01 July 2007

AMIN COJA-OGHLAN
AMIN COJA-OGHLAN*
Affiliation:
Humboldt-Universität zu Berlin, Institut für Informatik, Unter den Linden 6, 10099 Berlin, Germany (e-mail: coja@informatik.hu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study semirandom k-colourable graphs made up as follows. Partition the vertex set V = {1, . . ., n} randomly into k classes V1, . . ., Vk of equal size and include each Vi–Vj-edge with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may add further Vi–Vj-edges (i≠j) to G0, thereby completing the semirandom graph G = G*n,p,k. We show that if np ≥ max{(1 + ϵ)klnn, C0k2} for a certain constant C0>0 and an arbitrarily small but constant ϵ>0, an optimal colouring of G*n,p,k can be found in polynomial time with high probability. Furthermore, if np ≥ C0max{klnn, k2}, a k-colouring of G*n,p,k can be computed in polynomial expected time. Moreover, an optimal colouring of G*n,p,k can be computed in expected polynomial time if k ≤ ln1/3n and np ≥ C0klnn. By contrast, it is NP-hard to k-colour G*n,p,k With high probability if .

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 4 , July 2007 , pp. 515 - 552
Copyright
Copyright © Cambridge University Press 2006

References

[1]Achlioptas, D. and Naor, A. (2004) The two possible values of the chromatic number of a random graph. In Proc. 36th STOC, pp. 587–593.CrossRefGoogle Scholar
[2]Alon, N. and Kahale, N. (1997) A spectral technique for coloring random 3-colorable graphs. SJCOM 26 1733–1748.Google Scholar
[3]Alon, N. and Kahale, N. (1998) Approximating the independence number via the ϑ-function. MATHPROG 80 253–264.Google Scholar
[4]Blum, A. and Spencer, J. (1995) Coloring random and semirandom k-colorable graphs. JALGO 19 203–234.Google Scholar
[5]Bollobás, B. (1988) The chromatic number of random graphs. COMB 8 49–55.Google Scholar
[6]Bollobás, B. (2001) Random Graphs, 2nd edn, Cambridge University Press.CrossRefGoogle Scholar
[7]Bollobás, B. and Scott, A. D. (2004) Max cut for random graphs with a planted partition. CPC 13 451–474.Google Scholar
[8]Boppana, R. (1987) Eigenvalues and graph bisection: an average-case analysis. In Proc. 28th FOCS, pp. 280–285.CrossRefGoogle Scholar
[9]Böttcher, J. (2005) Coloring sparse random k-colorable graphs in polynomial expected time. In Proc. 30th MFCS, pp. 156–167.Google Scholar
[10]Charikar, M. (2002) On semidefinite programming relaxations for graph coloring and vertex cover. In Proc. 13th SODA, pp. 616–620.Google Scholar
[11]Coja-Oghlan, A. Solving NP-hard semirandom graph problems in polynomial expected time. JALGO, to appear.Google Scholar
[12]Coja-Oghlan, A. (2006) Finding large independent sets in polynomial expected time. CPC 15 XXX–XXX.Google Scholar
[13]Coja-Oghlan, A., Moore, C. and Sanwalani, V. (2006) MAX k-CUT and approximating the chromatic number of random graphs. RSA 28 289–322.Google Scholar
[14]Dyer, M. and Frieze, A. (1989) The solution of some NP-hard problems in polynomial expected time. JALGO 10 451–489.Google Scholar
[15]Feige, U. and Kilian, J. (1998) Zero knowledge and the chromatic number. JCSS 57 187–199.Google Scholar
[16]Feige, U. and Kilian, J. (2001) Heuristics for semirandom graph problems. JCSS 63 639–671.Google Scholar
[17]Feige, U. and Krauthgamer, R. (2000) Finding and certifying a large hidden clique in a semirandom graph. RSA 16 195–208.Google Scholar
[18]Feige, U. and Ofek, E. (2005) Spectral techniques applied to sparse random graphs. RSA 27 251–275.Google Scholar
[19]Frieze, A. and Jerrum, M. (1997) Improved approximation algorithms for MAX k-CUT and MAX BISECTION. ALGORITH 18 61–77.CrossRefGoogle Scholar
[20]Frieze, A. and McDiarmid, C. (1997) Algorithmic theory of random graphs. RSA 10 5–42.Google Scholar
[21]Goemans, M. X. and Kleinberg, J. (1998) The Lovasz theta function and a semidefinite programming relaxation of vertex cover. SJDM 11 1–48.Google Scholar
[22]Goemans, M. X. and Williamson, D. P. (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM 42 1115–1145.Google Scholar
[23]Grötschel, M., Lovász, L. and Schrijver, A. (1988) Geometric Algorithms and Combinatorial Optimization, Springer.CrossRefGoogle Scholar
[24]Helmberg, C. (2000) Semidefinite programming for combinatorial optimization. Habilitationsschrift; Report ZR-00-34, Zuse Institute Berlin.Google Scholar
[25]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.Google Scholar
[26]Karger, D., Motwani, R. and Sudan, M. (1998) Approximate graph coloring by semidefinite programming. JACM 45 246–265.CrossRefGoogle Scholar
[27]Khanna, S., Linial, N. and Safra, S. (2000) On the hardness of approximating the chromatic number. COMB 20 393–415.Google Scholar
[28]Krivelevich, M. (2002) Coloring random graphs: An algorithmic perspective. In Proc. 2nd Colloquium on Mathematics and Computer Science, pp. 175–195.CrossRefGoogle Scholar
[29]Krivelevich, M. and Vilenchik, D. (2006) Semirandom models as benchmarks for coloring algorithms. In Proc. 8th ANALCO, pp. 211–221.CrossRefGoogle Scholar
[30]Kučera, L. (1989) Graphs with small chromatic number are easy to color. IPL 30 233–236.Google Scholar
[31]Lawler, E. L. (1976) A note on the complexity of the chromatic number problem. IPL 5 66–67.Google Scholar
[32]Łuczak, T. (1991) The chromatic number of random graphs. COMB 11 45–54.Google Scholar
[33]McSherry, F. (2001) Spectral partitioning of random graphs. In Proc. 42nd FOCS, pp. 529–537.Google Scholar
[34]Subramanian, C. R. (1999) Minimum coloring random and semirandom graphs in polynomial average time. JALGO 33 112–123.Google Scholar
[35]Subramanian, C. R., Fürer, M. and Veni Madhavan, C. E (1998) Algorithms for coloring semi-random graphs. RSA 13 125–158.Google Scholar
[36]Subramanian, C. R. and Veni Madhavan, C. E. (2002) General partitioning on random graphs. JALGO 42 153–172.Google Scholar
[37]Szegedy, M. (1994) A note on the θ number of Lovasz and the generalized Delsarte bound. In Proc. 35th FOCS, pp. 36–39.CrossRefGoogle Scholar