Approximating the independence number and the chromatic number in expected polynomial time
type: Item
instance of: scholarly article
title: Approximating the independence number and the chromatic number in expected polynomial time
zbMATH Open document ID: 0995.05055
DOI: 10.1023/A:1013899527204
author: Michael Krivelevich
author: Van Vu
published in: Journal of Combinatorial Optimization
publication date: 2002-05-28T00:00:00Z
review text: For a number \(f\geq 1\), we say that an algorithm \(A\) approximates the independence number within factor \(f\) over graphs on \(n\) vertices, if for every such graph \(G\) the algorithm \(A\) outputs an independent set \(I\), whose size satisfies \(|I|\geq \frac{\alpha(G)}{f}\). Similarly, \(A\) approximates the chromatic number within factor \(f\) for graphs on \(n\) vertices if for every such a graph it outputs a colouring with the number of colours \(k\) satisfying \(k\leq f\cdot \chi(G)\). Recent results have shown that in general there is no polynomial time algorithm which approximates these two parameters within a satisfactory factor. In this paper it is shown that the situation is significantly better than in the average case. For an integer \(n\) and a function \(0\leq p=p(n)\leq 1\), the random graph \(G(n,p)\) is a graph with \(n\) labeled vertices \(1,2,\dots, n\), where each pair of vertices \((i,j)\) is chosen to be an edge of \(G\) independently with probability \(p\). Given an algorithm \(A\), whose domain is the set of all graphs on \(n\) vertices, and a probability space \(G(n,p)\), the expected running time of \(A\) over \(G(n,p)\) is defined as \(\sum_{G} Pr[G] R_{A}(G)\) where the sum runs over all labeled graphs on \(n\) vertices, \(Pr[G]\) is the probability that \(G\) is chosen according to the distribution \(G(n,p)\) and \(R_{A}(G)\) stands for the running time of \(A\) on \(G\). It is shown that for \(p=p(n)\) in the range \(n^{\frac{-1}2+\epsilon}\leq p \leq \frac{3}4\) the independence and chromatic number can be approximated by deterministic algorithms whose expected running times are polynomial and their approximation factor is \(O(\frac{(np)^{\frac{1}2}}{\log n})\) and \(O((np)^{\frac{1}2}\log n)\) respectively. The obtained algorithms are based on the greedy colouring algorithm and an application of Talagrand's inequality.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1746304
zbMATH Keywords: approximating algorithm
zbMATH Keywords: chromatic number
zbMATH Keywords: independence number
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: a:1013899527204
OpenAlex ID: W1492831324
description: scientific article; zbMATH DE number 1746304