Coloring, Clique and Independent set

Chromatic number

The graph coloring problem for an undirected graph G, is to assign a color to each summit so that the same color is not assigned to two adjacent vertices.

When the graph is planar, it comes down to the problem of coloring a map. The problem of coloring a graph arises in many practical areas such as pattern matching, sports scheduling, designing seating plans, exam timetabling, the scheduling of taxis, and solving Sudoku puzzles.

The minimum number of colors needed to color the graph G is called the chromatic number of G, and is denoted X(G).

The problem of finding the chromatic number of a graph is an Np-complete problem. The problem of coloring a graph with a limited number of colors – is it possible to color the graph with x colors, if so how? – is also an Np-complete problem.

Some rules (without demonstration):

  1. A planar graph is at most 4-chromatic.
  2. A path is 2-chromatic.
  3. A cycle is at most 3-chromatic.
  4. A n-clique (complete graph) is n-chromatic.

Example: A given set of jobs need to be assigned to time slots, each job requires one such slot. Jobs can be scheduled in any order, but pairs of jobs may be in conflict in the sense that they may not be assigned to the same time slot, for example because they both rely on a shared resource. The corresponding graph contains a vertex for every job and an edge for every conflicting pair of jobs. The chromatic number of the graph is exactly the minimum makespan, the optimal time to finish all jobs without conflicts.

Clique – Complete graph

Given an undirected graph G, a clique is a subset of vertices that are all connected in pairs by edges. In other words, it is a complete sub-graph.

Finding a click k of order k in a graph is an Np-complete problem.

The following graph has a clique of order 5:

grapheclique

Independent set

Given an undirected graph G, an independent set is a subset of vertices that are not connected in pairs by edges. Find an independent set is the same to find a clique in the inverse graph, ie it has an edge if it does not exist in the original graph, and vice versa.

To find an independent set a of order k in a graph is a Np-complete problem.

280px-independent_set_graph-svg

Relationship between the three problems and heuristics

An independent set S of G is said to be maximal by inclusion if there is no independent set S’ of G such that S is strictly contained in S’. A clique K is maximal by inclusion if there are no cliques K’ of G such that K is strictly contained in K’.

By this definition, we deduce that an independent set of maximum order is also a maximum stable by inclusion, the reciprocal is not true. We deduce the following heuristic (in french):

stable2

The Brélaz algorithm is a greedy algorithm that allows to know a maximum bound of the chromatic number of a graph. Its principle is simple and proceeds iteratively.

As long as there is an unicoloured vertex, we choose the unstained vertex with the largest number of neighbors colored with different colors. This vertex is then colored with the smallest possible color (the colors are sorted in an arbitrary increasing order). If all existing colors are already used by a neighbor, we add a new color to our palette (adding a color with a value greater than all existing ones).

The notion of independent set can also provide indications on the coloring of a graph. Indeed, we can assume that in an independent set, all the vertices have the same color. The coloration in k colors amounts to finding a partition of the set of vertices in a k independent set.

Welsh & Powell algorithm is based on this proposition:

  1. Classify the vertices of the graph in descending order of their degree
  2. Looking through the list in order, assign a color not used in the first non-colored vertex p, and assign that color to each non-colored vertices which are not adjacent to the summit p.
  3. Return to 2 if there are non-colored vertices in the list. Otherwise return the list.

 

Example

sudoku

To see the connection between Sudoku and graph coloring, we will first describe the Sudoku graph, which for convenience we will refer to as S. The graph S has 81 vertices, with each vertex representing a cell. When two cells cannot have the same number (either because they are in the same row, in the same column, or in the same box) we put an edge connecting the corresponding vertices of the Sudoku graph S. For example, since cells a3 and a7 are in the same row, there is an edge joining their corresponding vertices; there is also an edge connecting a1 and b3 (they are in the same box), and so on. When everything is said and done, each vertex of the Sudoku graph has degree 20, and the graph has a total of 810 edges. S is too large to draw, but we can get a sense of the structure of S by looking at a partial drawing. The drawing shows all 81 vertices of S, but only two (a1 and e5) have their full set of incident edges showing.

sudoku2

The second step in converting a Sudoku puzzle into a graph coloring problem is to assign colors to the numbers 1 through 9. This assignment is arbitrary, and is not a priority ordering of the colors as in the greedy algorithm, it’s just a simple correspondence between numbers and colors.

sudoku3

Once we have the Sudoku graph and an assignment of colors to the numbers 1 through 9, any Sudoku puzzle can be described by a Sudoku graph where some of the vertices are already colored (the ones corresponding to the givens). To solve the Sudoku puzzle all we have to do is color the rest of the vertices using the nine colors.

sudoku4

Publicités