Experiments in graph 3-coloring - block-cutpoint graph

Introduction
One way to reduce the runtime complexity of an algorithm is to partition the problem into smaller sub-problems, solve the sub-problems and combine these solutions to solve the original, bigger problem. This approach can be used when coloring a graph.

I investigated an approach that uses a block-cutpoint representation of the given graph. On a high level, here is the solution:

1. Given an undirected graph, construct its block-cutpoint graph.
2. Solve the 3-coloring problem for each of the blocks.
3. Combine the solution for each of the blocks to 3-color the original graph.

Definitions
Bi-connected graph
An undirected graph is bi-connected if any two vertices lie on a cycle. In other words, there are at least 2 distinct, disjoint paths between any two vertices. This concept is similar to that of a strongly connected component in a directed graph.

Block (aka Bi-connected component)
A bi-connected subgraph of a graph is called a block.

Cutpoint (aka cut vertex)
A vertex whose removal disconnects a graph is called a cut point or a cut vertex. Such vertices are "on the boundary" of a block. In Figure 1, they are shown in red color.

Block-Cutpoint graph

• A graph where a block is collapsed into a vertex,
• a cut vertex is represented as a vertex in this graph,
• there is an edge between a block vertex and a cut vertex only if the cut vertex is part of the block,
• there is an edge between two cut vertices only if there are adjacent in the original graph.

Interesting point to note is that any undirected graph can be represented as a tree of blocks and cutpoints, as shown in the figure above.

Coloring algorithm

1. Partition given graph G into blocks B1, B2, ..., Bm.
2. Color each of the blocks independently.
3. The reconciliation step: two blocks, say B1 and B2, can share only 1 vertex (the cut vertex), say X.
1. If X is colored with the same color, then we simply merge the colorings for B1 and B2.
2. If X is colored differently in B1 and B2, say c1 and c2, respectively, then:
1. we make X's color in B2 as c1 (its color in B1)
2. All vertices in B2 colored as c2 are now colored as c1 and
3. all vertices in B2 colored as c1 are now colored as c2.
3. So in essence, we swapped colors c1 and c2 in B2.
4. If we perform the reconciliation step in breadth first search order (BFS) of the block-cutpoint tree, we have a valid coloring for the original graph, provided each of the blocks has a valid coloring.

Runtime complexity

• Let the size of G be n.
• Let the sizes of the blocks B1, B2, ..., Bm be n1, n2, ..., nm, respectively.

Since the worst case running time is exponential in the number of nodes, say a^n for G, the runtime complexity of the above algorithm is a^n1 + a^n2 + ... + a^nm + O(n). This translates to O(a^max(n1, n2, ..., nm)) asymptotically.

In closing
This algorithm can be applied to n-coloring, not just 3-coloring. It reduces the time complexity if there are cut vertices in the graph. The more even the size of the blocks, the more the speed-up in run time.

Experiments in graph 3-coloring

3-coloring using independent sets

• By definition, vertices in an independent set (IS) share no edges. So these vertices can all be colored with one color.
• If after the removal of these vertices (and incident edges), the graph is 2-colorable, then we have a valid 3-coloring.

Fig 1: An independent set (red vertices)

Fig 2: Graph without independent set

Fig 3: Graph without independent set is 2-colorable

Fig 4: Fully colored graph with 3 colors

Interesting points about this approach

• Not all independent sets work, since G - IS may not be 2-colorable.
• Enumerating all independent sets is equivalent to enumerating the power set of the vertices and determining if they form an independent set. This has 2^v iterations, each taking about v^2 time. This is asymptotically better than 3^v iterations required for a brute force 3-coloring.
• If a graph is 3-colorable, then we can always find one color in a valid 3-coloring that is applied to at most floor(v/3) vertices. This implies that when enumerating all independent sets, we need to only find independent sets of size floor(v/3) or less. This is still O(2^n), by the way.

Optimization for this approach

• We start with brute force enumeration, as below, where 1 implies inclusion of the vertex and 0 its exclusion from the independent set.
• {1, 0, 0, ..., 0} - start by choosing v0
• {1, 1, 0, ...., 0} - after we choose v0 and v1 in the independent set.
• {1, 0, 1, ...., 0} - if we decide that v0 and v1 cannot be in an independent set (because they share an edge) and move on to v0 and v2.
• In general, if current selection is an independent set, keep the latest added vertex and include the next available vertex.
• In general, if current selection is not an independent set (because the latest vertex has one or more edges with previous vertices in the independent set), drop the latest added vertex and choose the next available one.

3-coloring with brute force

• This is exhaustive, brute force approach. We try each combination, till we find a valid coloring.
• Let the colors be 0, 1 and 2. Each color combination is an n-tuple. E.g. {0, 2, 1, 0, 0, 1, 1, 2, ...}. This colors vertex v0 with color 0, v1 with color 2, v2 with color 1 and so on.
• This is O(3^n), but seems to run faster in practice. Perhaps it has a tighter bound than O(3^n).

Optimization for this approach

• We order vertices arbitrarily as v0, v1, v2, ..., vn.
• We enumerate current color selection lexicographically. E.g.
1. 0
2. 0, 0, if the previous selection is a valid coloring
3. 0, 0, 0 if the previous selection is a valid coloring
4. 0, 0, 1 if the previous selection is not a valid coloring
5. 0, 0, 2 if the previous selection is not a valid coloring
6. 0, 1 if the previous selection is not a valid coloring
7. 0, 1, 0 if the previous selection is a valid coloring
8. and so on.

3-coloring greedily

• This is a simple approach, very fast in practice, but cannot color all colorable graphs.
• Order vertices by descending order of degree.
• Greedily choose the lowest color that is valid.
• Repeat above step till all vertices are colored.
• Runs in O(v^2) time.