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

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?

• Usually we don't care about polynomial factors when discussing exponential time algorithms. The time bound should really be $\tilde{O}(\phi^{n+m})$ instead of $O(\phi^{n+m})$. Mar 24, 2018 at 15:29
• Of course, but still $\mathcal{O}(n \phi^{n + m}) \neq \mathcal{O}(\phi^{n + m})$ and this question explicitly asks for the case when caring about polynomial factors. Mar 24, 2018 at 15:39

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.

• That is what I am looking for. But how do you restore the original Union-Find structure after the recursive call? Passing the Union-Find structure as parameter requires $\mathcal{O}(n + m)$ time, right? So it is necessary to rollback the changes. Mar 24, 2018 at 21:50
• @neutron-byte, Good point. I added a discussion of that; see the 3rd paragraph. I guess that increases the running time but I'm not sure by how much. Look up persistent Union-Find and see what the best known data structures are; I don't know off the top of my head.
– D.W.
Mar 24, 2018 at 23:02