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 \emph{graph 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:
\begin{itemize}
\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 $\mathcal{A}$ which
computes a pure Nash equilibrium of $\Gamma(G)$. \item The total
number, $k$, of colors used in \emph{any} pure Nash equilibrium
(and thus achieved by $\mathcal{A}$) is $k\leq\min\{\Delta_2+1,
\frac{n+\omega}{2}, \frac{1+\sqrt{1+8m}}{2}, n-\alpha+1\}$, where
$\omega, \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 \emph{new}, \emph{efficient} coloring method that achieves
a number of colors \emph{satisfying (together) the known general
upper bounds on the chromaticnumber $\chi$}. Our method is also
an alternative general way of \emph{proving},
\emph{constructively}, 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 \emph{optimally} dense random
$q$-partite graphs (of fixed $q$) with high probability.
\end{itemize}
Abstract: For many random Constraint Satisfaction Problems, by now, we have asymptotically tight estimates of
the largest constraint density for which they have solutions. At the same time, all known polynomial-time algorithms
for many of these problems already completely fail to find solutions at much smaller densities. For example, it is
well-known that it is easy to color a random graph using twice as many colors as its chromaticnumber. Indeed, some
of the simplest possible coloring algorithms already achieve this goal. Given the simplicity of those algorithms, one
would expect there is a lot of room for improvement. Yet, to date, no algorithm is known that uses (2 - o)χ colors,
in spite of efforts by numerous researchers over the years.
In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we believe it is natural to
inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a
subset of {1, . . . , k}n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense
to a phase transition in the geometry of this set. Roughly, the set of k-colorings looks like a giant ball for k ? 2χ, but
like an error-correcting code for k ? (2 - o)χ. We prove that a completely analogous phase transition also occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each problem, its location corresponds precisely with the point were all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to prove rigorously much of the celebrated 1-step Replica-Symmetry-Breaking hypothesis
of statistical physics for random CSPs.
Abstract: An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge
when their label sets intersect. Random Intersection Graphs (RIGs) (as defined in [18, 31]) consider label sets formed by the following experiment:
each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex
succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes.
We study here the problem of efficiently coloring (and of finding upper bounds to the chromaticnumber) of RIGs. We concentrate in a range
of parameters not examined in the literature, namely: (a) m = n{\'a} for less than 1 (in this range, RIGs differ substantially from the Erd¨os- Renyi random graphs) and (b) the selection probability p is quite high
(e.g. at least ln2 n m in our algorithm) and disallows direct greedy colouring methods.
We manage to get the following results:
For the case mp ln n, for any constant < 1 − , we prove that np colours are enough to colour most of the vertices of the graph with high probability (whp). This means that even for quite dense
graphs, using the same number of colours as those needed to properly colour the clique induced by any label suffices to colour almost all of the vertices of the graph. Note also that this range of values of m, p
is quite wider than the one studied in [4].
� We propose and analyze an algorithm CliqueColour for finding a proper colouring of a random instance of Gn,m,p, for any mp >=ln2 n. The algorithm uses information of the label sets assigned to the
vertices of Gn,m,p and runs in O (n2mp2/ln n) time, which is polynomial in n and m. We also show by a reduction to the uniform random
intersection graphs model that the number of colours required by the algorithm are of the correct order of magnitude with the actual
chromaticnumber of Gn,m,p.
⋆ This work was partially supported by the ICT Programme of the European Union under contract number ICT-2008-215270 (FRONTS). Also supported by Research Training Group GK-693 of the Paderborn Institute for Scientific Computation
(PaSCo).
� We finally compare the problem of finding a proper colouring for Gn,m,p to that of colouring hypergraphs so that no edge is monochromatic.We show how one can find in polynomial time a k-colouring of the vertices of Gn,m,p, for any integer k, such that no clique induced by only one label in Gn,m,p is monochromatic. Our techniques are novel and try to exploit as much as possible the hidden structure of random intersection graphs in this interesting range.
Abstract: We exploit the game-theoretic ideas presented in [12] to
study the vertex coloring problem in a distributed setting. The vertices
of the graph are seen as players in a suitably defined strategic game,
where each player has to choose some color, and the payoff of a vertex is
the total number of players that have chosen the same color as its own.
We extend here the results of [12] by showing that, if any subset of nonneighboring
vertices perform a selfish step (i.e., change their colors in order
to increase their payoffs) in parallel, then a (Nash equilibrium) proper
coloring, using a number of colors within several known upper bounds
on the chromaticnumber, can still be reached in polynomial time. We
also present an implementation of the distributed algorithm in wireless
networks of tiny devices and evaluate the performance in simulated and
experimental environments. The performance analysis indicates that it
is the first practically implementable distributed algorithm.
Abstract: It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has chromaticnumber at most 4. Here, we show that the chromaticnumber of a random 5-regular graph is asymptotically almost surely equal to 3, provided a certain four-variable function has a unique maximum at a given point in
a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3-colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors.
Abstract: Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [0, 1]2 unit square. Each vertex i is assigned uniformly at random sector Si, of central angle {\'a}i, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. In this work, we study the value of the chromaticnumber {\^O}(Gn), directed clique number {\`u}(Gn), and undirected clique number {\`u}2 (Gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of {\'a} degrees with radius rn = \~{a}ln n/n. We prove that for values {\'a} < {\^I}, as n ¨ w.h.p., {\^O}(Gn) and {\`u}2 (Gn) are {\`E}(ln n/ln ln n), while {\`u}(Gn) is O(1), showing a clear difference with the random geometric graph model. For {\'a} > {\^I} w.h.p., {\^O}(Gn) and {\`u}2 (Gn) are {\`E} (ln n), being the same for random scaled sector and random geometric graphs, while {\`u}(Gn) is {\`E}(ln n/ln ln n).
