Polynomial Growth Observed in a New Graph Coloring Algorithm: Insight or Oversight?

Question

Hello MathExchange community,

I have developed a graph coloring algorithm that has demonstrated impressive results in initial tests. However, before drawing any concrete conclusions, I'm looking for insights from experts in the field.

Brief Overview of the Algorithm:

Unique Permutation Coloring (UPC): This technique ensures that we don't evaluate multiple equivalent colorings, thus drastically reducing the number of possibilities.

Biggest Possible Clique (BPC): By calculating the largest clique that could exist given the number of edges in the graph, we can set a color lower bound.

Neighbour Count Constraint (NCC): This utilizes the count of a node's neighbors to limit the maximum number of colors that need to be considered for that node. These techniques work synergistically. For instance, if a node has a high neighbor count but the determined chromatic number is low, we wouldn't need to compute higher color numbers for that node.

Results: I was able to solve graphs with up to 12,000 nodes in less than 2 minutes. As the number of nodes increased, the growth factor of the worst-case scenario seemed to suggest a polynomial growth.

Concern: While the results are promising, the polynomial nature of the growth has led me to doubt the underlying logic of my algorithm. Given the NP-hard nature of the problem, I'm wondering if there's a potential glitch or oversight in my approach that I might be missing.

I would greatly appreciate any feedback, especially if anyone can point out potential flaws or provide insights into the observed behavior. The complete documentation and code are available https://github.com/khreibi/GraphColoring/tree/main.

Thank you for your time and assistance!

Answer 1

Let's first compare this algorithm to a simple greedy algorithm: it goes through the vertices in the order that they are given, and for each vertex, it chooses the first color that does not conflict with already-colored vertices.

The greedy algorithm can produce suboptimal colorings when the vertices are not given in the optimal order. For example, suppose we have a path graph on $4$ vertices, numbered in the order shown below:

1 --- 3 --- 4 --- 2

The greedy algorithm will give vertex $1$ the first color. Then, it will give vertex $2$ the first color. Then, it will give vertex $3$ the second color (since it is adjacent to vertex $1$, which has the first color). Finally, it will give vertex $4$ the third color (since it is adjacent to vertices $2$ and $3$, which have the first two colors). So the greedy algorithm ends up $3$-coloring the path, even though a $2$-coloring exists (give vertices $1$ and $4$ the first color, and give vertices $2$ and $3$ the second color).

---

The graph coloring algorithm in the question modifies the greedy algorithm by putting some limits on it, and then adding some backtracking:

if (IsSafe(v, c))
{
   colors[v] = c;
   if (GraphColoringUtil(m, v + 1))
      return true;
   colors[v] = 0;
}

Here, we provisionally agree with the greedy algorithm to give vertex v the first color c we can - and call GraphColoringUtil recursively to continue on the rest of the graph. However, if the algorithm ever uses a color that exceeds the limit from the BPC and NCC rules, then it will refuse to accept that! The GraphColoringUtil call returns false, and we try the next color c+1 instead, and repeat until every vertex stays under the limits.

This seems like a great idea, but I have bad news.

Fact 1. Even left to itself, the greedy algorithm will never exceed the BPC limit: in a graph with less than $\binom{m+1}2$ edges, it will never give a vertex a color greater than $m$.

Proof. We prove the contrapositive. Suppose that the greedy algorithm uses color $m+1$ at some point. In particular, the vertex that received color $m+1$ must have had neighbors already given colors $1$ through $m$, or else it would have used those colors. Therefore colors $1, 2, \dots, m+1$ all appear in the output on at least one vertex.

More generally, a vertex given color $k \le m+1$ must have had neighbors already given colors $1$ through $k-1$. In particular, for each pair $(j,k)$ with $1 \le j < k \le m+1$, the vertex given color $k$ must have a neighbor given color $j$. So for every such pair of colors $(j,k)$, the graph must have an edge with those colors on its endpoints. There are $\binom{m+1}{2}$ such pairs $(j,k)$, so the graph must have at least $\binom{m+1}{2}$ edges.

Fact 2. Even left to itself, the greedy algorithm will never exceed the NCC limit: a vertex with $d$ neighbors will never be given a color greater than $d+1$.

Proof. A vertex with $d$ neighbors will be given the first color that does not appear on its already-colored neighbors. This eliminates at most $d$ options, so at least one of the colors $1, 2, \dots, d+1$ will be valid.

---

As a result, the BPC and NCC computations do not affect the algorithm: they place upper bounds on the greedy algorithm that the greedy algorithm is already incapable of violating. Therefore the backtracking in the code snippet quoted above will never occur: GraphColoringUtil simply never returns false.

As a result, the algorithm is equivalent to the greedy algorithm, and suffers from the same problems: sometimes it gives a suboptimal coloring.