1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Yuval Filmus Mar 24 '18 at 15:29
  • $\begingroup$ 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. $\endgroup$ – neutron-byte Mar 24 '18 at 15:39
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – neutron-byte Mar 24 '18 at 21:50
  • $\begingroup$ @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. $\endgroup$ – D.W. Mar 24 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.