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.