Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T00:02:05.787Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

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.)

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