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:

- Given an undirected graph, construct its block-cutpoint graph.
- Solve the 3-coloring problem for each of the blocks.
- 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

- Partition given graph G into blocks B1, B2, ..., Bm.
- Color each of the blocks independently.
**The reconciliation step**: two blocks, say B1 and B2, can share only 1 vertex (the cut vertex), say X.- If X is colored with the same color, then we simply merge the colorings for B1 and B2.
- If X is colored differently in B1 and B2, say c1 and c2, respectively, then:
- we make X's color in B2 as c1 (its color in B1)
- All vertices in B2 colored as c2 are now colored as c1 and
- all vertices in B2 colored as c1 are now colored as c2.
- So in essence, we swapped colors c1 and c2 in B2.
- 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.

## No comments:

## Post a Comment