2
$\begingroup$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$.

Graph is not $k$ colorable iff $P(G,k)=0$.

The chromatic polynomial of clique $K_n$ is $x(x-1)(x-2)\ldots(x-(n-1))$

A graph is 3-colorable iff $P(G,x) \not \equiv 0 \pmod{x-3}$ (in other words 3 is not a root of $P(G,x)$.

The goal is to check 3-colorability by computing $P(G,x) \pmod{x-3}$.

For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added and the graph $G/uv$ is obtained by merging the two vertices.

According to wikipedia

$$P(G,k)= P(G+uv, k) + P(G/uv,k) \qquad (1) $$

And the terminating conditions are cliques.

So $G$ is not 3-colorable iff all terminal cliques are on more than $3$ vertices.

When computing (1) $\mod x-3$, we have the following terminal conditions.

(A) if $F$ contains $K_4$ as (induced) subgraph it is not 3-colorable and we return $P(F,k) \equiv 0 \pmod{x-3}$ without bothering to compute later.

(B) if $F$ is clique on 3 or less vertices, $G$ is 3-colorable since this a terminating clique.

Adding edges and merging vertices tends to induce $K_4$ and (A) is often hit, which makes computing $P(G,x) \pmod{x-3}$ strictly faster than the full $P(G,x)$ and this decides 3-colorability.

Consider the following naive algorithm for checking 3-colorability using $P(G,x) \pmod{x-3}$.

 function color3(G: connected graph)
 #returns 0 if G is not 3-colorable, otherwise reports it is and stops
 if G contains induced K_4 
     return 0
 if G is a clique on 3 or less vertices 
     report '3-colorable'. Stop.
 if we can add edge uv which induces K_4 in G 
     return color3(G/uv) #the induced K_4 contributes 0 to the sum
 #the above makes the problem strictly smaller
 #this might be greatly improved by trying to induce K_4-e
 [C] pick the lexicographic first non-adjacent u,v and return color3(G+uv)+color3(G/uv)

One call to color3 is polynomial, so the complexity depends on the number of double recursion in [C].

According to Wikipedia the worst case for computing (1) is $\phi^{n+m}$. 3-coloring 4-regular graphs is NP-complete, so for 4-regular it is $\phi^{3n}$.

Appears to me terminating by induced $K_4$ would greatly improve the running time.

Questions:

Q1 What is the complexity of color3?

$O(c^n)$ for small $c$ will be of practical interest. $2^{o(n)}$ might indicate complexity collapse.

Q2 How to improve [C]?

There might be other improvements like other 4-chromatic subgraph or $F$ being in a graph class where coloring is polynomial.

Experimental results:

For several 4-regular graphs on 246 vertices which are the line graphs of 3-regular graphs color3 found 3-coloring in less than a minute in sage 6.2 implementation. For several smaller graphs which are not 3-colorable it correctly returned 0. For reduction SAT to 3-color the running time was fast too.

Added Choosing the lexicographically first edge appears good choice. It adds high degree vertices and is experimentally much faster than choosing a random edge. (Another good choice is too add edge between the two highest degree vertices).

Q3 How to explain the fast experimental results, including 4-chromatic graph on 75 vertices and the reductions from SAT?

Sage implementation: https://gist.github.com/jor0/039127ab69dd8934c105

Q4 For 4-regular graph on 50 vertices, what is the current record for maximum number of steps of the above implementation?

$\endgroup$
9
  • $\begingroup$ Very related question on cstheory: cstheory.stackexchange.com/questions/25299/… $\endgroup$
    – joro
    Jul 21, 2014 at 11:49
  • $\begingroup$ Recursion to instances smaller by an additive constant is the standard technique for beating the obvious brute-force search algorithm for a wide variety of NP-hard problems. It normally leads to runtimes of the form $c^n$. Are you familiar with state-of-the-art 3-colouring algorithms such as sciencedirect.com/science/article/pii/S0020019010003595 , ics.uci.edu/~eppstein/pubs/Epp-SODA-01.pdf ? $\endgroup$ Jul 21, 2014 at 11:59
  • $\begingroup$ Errr, I missed that one sorry. $\endgroup$
    – Jernej
    Jul 22, 2014 at 10:30
  • $\begingroup$ @Jernej What is the fastest way say in Boost to find induced diamonds (K_4 minus edge)? $\endgroup$
    – joro
    Jul 22, 2014 at 10:55
  • $\begingroup$ @Joro, Btw, a way to speed up such recursion is to cache graphs, see how this is done for the chromatic polynomial to gain an extreme speedup trac.sagemath.org/ticket/14529 Though this introduces the isomorphism problem and breaks complexity analysis. $\endgroup$
    – Jernej
    Jul 22, 2014 at 11:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.