research unit 1

Publication

Type of publication:Inproceedings
Entered by:PNP
TitleA Game Theoretic Approach for Efficient Graph Coloring
Bibtex cite IDRACTI-RU1-2008-28
Booktitle 19th International Symposium on Algorithms and Computation (ISAAC 2008)
Year published 2008
Month December
Pages 1-15
Location Gold Coast, Australia
Note To appear
URL http://www-or.amp.i.kyoto-u.ac.jp/isaac08/
Abstract
We give an efficient local search algorithm that computes a good vertex coloring of a graph $G$. In order to better illustrate this local search method, we view local moves as selfish moves in a suitably defined game. In particular, given a graph $G=(V,E)$ of $n$ vertices and $m$ edges, we define the \emphgraph coloring game $\Gamma(G)$ as a strategic game where the set of players is the set of vertices and the players share the same action set, which is a set of $n$ colors. The payoff that a vertex $v$ receives, given the actions chosen by all vertices, equals the total number of vertices that have chosen the same color as $v$, unless a neighbor of $v$ has also chosen the same color, in which case the payoff of $v$ is 0. We show: \beginitemize \item The game $\Gamma(G)$ has always pure Nash equilibria. Each pure equilibrium is a proper coloring of $G$. Furthermore, there exists a pure equilibrium that corresponds to an optimum coloring. \item We give a polynomial time algorithm $\mathcalA$ which computes a pure Nash equilibrium of $\Gamma(G)$. \item The total number, $k$, of colors used in \emphany pure Nash equilibrium (and thus achieved by $\mathcalA$) is $k\leq\min\\Delta_2+1, \fracn+ømega2, \frac1+\sqrt1+8m2, n-\alpha+1\$, where $ømega, \alpha$ are the clique number and the independence number of $G$ and $\Delta_2$ is the maximum degree that a vertex can have subject to the condition that it is adjacent to at least one vertex of equal or greater degree. ($\Delta_2$ is no more than the maximum degree $\Delta$ of $G$.) \item Thus, in fact, we propose here a \emphnew, \emphefficient coloring method that achieves a number of colors \emphsatisfying (together) the known general upper bounds on the chromatic number $\chi$. Our method is also an alternative general way of \emphproving, \emphconstructively, all these bounds. \item Finally, we show how to strengthen our method (staying in polynomial time) so that it avoids bad'' pure Nash equilibria (i.e. those admitting a number of colors $k$ far away from $\chi$). In particular, we show that our enhanced method colors \emphoptimally dense random $q$-partite graphs (of fixed $q$) with high probability. \enditemize
Authors
Topics
BibTeXBibTeX
RISRIS
Attachments
 coloring.pdf (main file) nash_color.zip

Publication ID476