Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution

Question

Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, how many $k$-colorings of $G$ exist? A $k$-coloring is a function $c: V \to \{ 1, 2, \dots, k \}$ such that $c(u) \neq c(v)$ for all edges $\{ u, v \} \in E$. Let $f(G, k)$ denote the number of $k$-colorings of $G$.

There is a well-known formula, sometimes called Fundamental Reduction Theorem:

$\displaystyle f(G, k) = f(G - e, k) - f(G\,/\, e, k)$ for all $e \in E$.

Note that $G - e$ is $G$ without edge $e$ and $G\,/\,e$ is $G$ with edge $e$ contracted.

Using this formula, it is easy to figure out a recursive algorithm. We just need to choose an arbitrary edge and recurse on $G - e$ and $G\,/\, e$. The base case is a graph without edges. If $T(n + m)$ denotes the time complexity, we have $T(n + m) \le T(n + m - 1) + T(n + m - 2)$ which is just fibonacci recurrence and establishes a time complexity of $\mathcal{O}(\phi^{n + m})$ where $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ denotes the golden ratio. So far, so good.

But we made an assumption: Can $G - e$ and $G\,/\,e$ really be obtained from $G$ in $\mathcal{O}(1)$ time? It seems like we cannot avoid a polynomial factor:

• If $G$ is represented by an adjacency matrix, vertex removal (needed for contraction) does not shrink the matrix and we always need $\mathcal{O}(n)$ time to access the edges of a single vertex. And another problem: How to select an arbitrary edge fast?

• If $G$ is represented by adjacency lists, edge removal is fast. But edge contraction requires moving/copying neighbour vertices to another adjacency lists which is expensive.

• If $G$ is represented by an edge list, edge selecting is fast. Edge removal is also fast, because the edge is arbitrary and we can always take the first edge in the list. But again, edge contraction causes many edges to be updated (i.e. assigned another endpoint)...

Is there a way to really achieve $\mathcal{O}(\phi^{n + m})$ without a factor of $n$, $m$ or $n + m$ using an appropiate data structure or modification of the algorithm?

Answer 1

Use an adjacency list representation, together with a Union-Find data structure on the vertices. Augment the Union-Find data structure so you can quickly enumerate the list of all edges incident on any vertex within a particular partition (you can keep track of them with a doubly linked list, and splice the lists together whenever you do a Union operation). Now edge contraction can be done in $O(\alpha(n))$ time, by simply doing a Union operation on the two vertices. Edge removal can be done in $O(1)$ time, due to the adjacency list representation. You can also find an arbitrary edge in $O(1)$ time, thanks to the augmentation of the Union-Find data structure.

This avoids the factor of $n$. You still pay a factor of $O(\alpha(n))$ instead of $O(1)$, but $O(\alpha(n))$ is so small that it might as well be $O(1)$ for all practical purposes, and in any case it is far smaller than $n$.

Actually, I think you pay more than that, because you'll need to undo the Union operations after returning from the recursive call. To deal with that, you can use a persistent Union-Find data structure. I'm not familiar with the asymptotic running time for those data structures, but I think given how it is used here it will be pretty close to as efficient as the plain Union-Find.

Usually we don't worry too much about polynomial factors when analyzing exponential-time algorithms, because the polynomial factor is tiny compared to the exponential factor, so a polynomial speedup won't change much in practice. But here is a case where the polynomial speedup you desired can be achieved.