Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time
Journal of Combinatorial OptimizationPublished 1 June 2002
Michael Krivelevich, Van H. Vu
Citations45
SJR quartileQ2
SJR score0.43
SNIP0.84
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An approximation algorithm is presented for the independence number of graphs on n vertices, whose approximation ratio is O((np)1/2/log n) and whose expected running time over the probability space G(n, p) is polynomial.
Abstract
Abstract The independence number of a graph and its chromatic number are known to be hard to approximate. Due to recent complexity results, unless coRP = NP, there is no polynomial time algorithm which approximates any of these quantities within a factor of n 1−∈ for graphs on n vertices. We show that the situation is significantly better for the average case. For every edge probability p = p(n) in the range n −1/2+∈ ≤ p ≤ 3/4, we present an approximation algorithm for the independence number of graphs on n vertices, whose approximation ratio is O((np)1/2/log n) and whose expected running time over the probability space G(n, p) is polynomial. An algorithm with similar features is described also for the chromatic number. A key ingredient in the analysis of both algorithms is a new large deviation inequality for eigenvalues of random matrices, obtained through an application of Talagrand's inequality.
Keywords
Computer ScienceMathematics
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems
3,133 Citations1997Dorit S. Hochba
This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.
IEEE Transactions on Information TheoryOn the Shannon capacity of a graph
1,658 Citations1979László Lovász
It is proved that the Shannon zero-error capacity of the pentagon is \sqrt{5} and a well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases.
COMBINATORICAThe eigenvalues of random symmetric matrices
673 Citations1981Zoltán Füredi, János Komlós
It is shown that with probability 1-o(1)all eigenvalues belong to the above intervalI if μ=0, while in case μ>0 only the largest eigenvalueλ1 is outsideI, and λ1 asymptotically has a normal distribution with expectation (n−1)μ+v+(σ2/μ) and variance 2σ2 (bounded variance!).
BIT Numerical MathematicsApproximating maximum independent sets by excluding subgraphs
363 Citations1992Ravi B. Boppana, Magnús M. Halldórsson
COMBINATORICAThe chromatic number of random graphs
362 Citations1988B Bollobás
It is shown that for a fixed probabilityp, 0<p<1, almost every random graphGn,p has chromatic number log (1/(1 - p) + o(1) + 1 + o (1)log n, where n is the number of random graphs.
Eigenvalues and graph bisection: An average-case analysis
323 Citations1987Ravi B. Boppana
This paper presents an algorithm that will, for almost all graphs in a certain class, output the minimum-size bisection and will yield a proof that the bisection is optimal.
Information Processing LettersA still better performance guarantee for approximate graph coloring
223 Citations1993Magnús M. Halldórsson
An approximation algorithm for graph coloring is presented which achieves a performance guarantee of O(n( log log n) 2 (log n) 3 ) , a factor oflog log n improvement.
Random Structures and AlgorithmsFinding and certifying a large hidden clique in a semirandom graph
200 Citations2000Uriel Feige, Robert Krauthgamer
This work shows that a different algorithm, based on the Lovasz theta function, almost surely both finds the hidden clique and certifies its optimality and has an additional advantage of being more robust: it also works in a semirandomhidden clique model, in which an adversary can remove edges from the random portion of the graph.
Journal of AlgorithmsThe solution of some random NP-hard problems in polynomial expected time
197 Citations1989Martin Dyer, Alan Frieze
The average-case complexity of recognising some NP-complete properties is examined, when the instances are randomly selected from those which have the property.
COMBINATORICAThe chromatic number of random graphs
189 Citations1991Tomasz Łuczak
It is proved that there exists a constantd0 such that fornp (n)>d0, p(n)→0, the probability that the chromatic number of the random graph G(n, p) tends to 1 asn→∞.
SIAM Journal on ComputingA Spectral Technique for Coloring Random 3-Colorable Graphs
187 Citations1997Noga Alon, Nabil Kahalé
A polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p $\geq$ c/n, where c is a sufficiently large absolute constant.
Finding a large hidden clique in a random graph
116 Citations1998Noga Alon, Michael Krivelevich +1 more
Zero knowledge and the chromatic number
112 Citations2002Uriel Feige, Joe Kilian
A new technique, inspired by zero-knowledge proof systems, is presented for proving lower bounds on approximating the chromatic number of a graph, and the result matches (up to low order terms) the known gap for approximation the size of the largest independent set.
Lecture notes in computer scienceSpectral techniques in graph algorithms
55 Citations1998Noga Alon
In this survey, several algorithms based on spectral techniques focusing on their performance for randomly generated input graphs are described.
Journal of AlgorithmsThe greedy coloring is a bad probabilistic algorithm
53 Citations1991Luděk Kučera
It is proved that for each n there is a graph G n such that the chromatic number of G n is at most n e, but the probability that A(G n, p) (1 − ϑ)n log 2 n for a randomly chosen ordering p is O ( n − Δ ).
Geometric and Functional AnalysisA new isoperimetric inequality for product measure and the tails of sums of independent random variables
19 Citations1991Michel Talagrand
Lecture notes in computer scienceColoring random graphs in polynomial expected time
8 Citations1993Martin Fürer, C. R. Subramanian +1 more
The results improve the current results for this problem of vertex coloring random k-colorable graphs using k colors by removing the assumption of constant edge probability used in these models.