Ex - K-Coloring Editorial by en_translator
This problem asks to count \(K\)-coloring of a graph.
First of all, we describe a solution when \(N\) is small.
- See also wata’s slides for more detailed explanation.
Let \(s(k)\) be the number of ways to paint the vertices in exactly \(K\) colors in total; then the answer equals
\[\sum_{i=1}^N \binom{K}{i} s(i),\]
Thus, it is sufficient to enumerate \(s(1), \dots, s(N)\). This can be computed in a total of \(\mathrm{O}(N 3^N)\) time using subset DP (Dynamic Programming). (See also: ABC213-G editorial.)
This DP can be optimized using an algorithm called Subset Convolution. Given function \(f(S)\) and \(g(S)\) whose domains are the subsets this algorithm computes
\[(f \ast g)(S) = \sum_{T \subseteq S} f(T) g(S \setminus T).\]
This costs \(\mathrm{O}(3^N)\) naively, and the subset DP solution calls this convolution \(N\) times.
In fact, this convolution can be optimized to \(\mathrm{O}(N^2 2^N)\) time.
- We omit the details. For Japanese speakers, see the chapter “Subset Convolution” in an article by hos, which is very easy to understand. For English speakers, see an article in CodeForces by adamant.
With this convolution, one can enumerate \(s(1), s(2), \dots, s(N)\) in a total of \(\mathrm{O}(N^3 2^N)\) time.
Moreover this convolution can be optimized to \(\mathrm{O}(N^2 2^N)\) time. Let \(F(S)\) be a function that takes \(1\) if \(S\) is a non-empty independent set, and \(0\) otherwise. Let \(f^K\) be the \(K\)-time convolution of \(F(S)\), then the answer is
\[\left(\sum_{i=1}^{\min(K, N)} \binom{K}{i} f^K\right)(V),\]
where \(V\) is the vertex set. Considering the meaning of \(f^n\), we can see that \(f^{n}(S)\) is always \(0\) if \(n=0\) or \(n \geq N\), so we can set the lower bound of the sigma to \(0\) and upper to \(K\) to obtain:
\[\left(\sum_{i=0}^K \binom{K}{i} f^K\right)(V).\]
Then, if we let \(g(S)\) be a function that returns \(1\) if \(S\) is a (possibly empty) independent set, then the expression above equals \(g^K(V)\). (We can also derive it with combinatoric interpretation.)
Thus, it is sufficient to find the powers of Subset Convolution. Actually, the power can be found by evaluating, instead of evaluating the pointwise product, the \(K\)-th power of the pointwise product. The powers up to the \(N\)-th degree can be found in a total of \(\mathrm{O}(N^2)\) or \(\mathrm{O}(N \log N)\) time, so the overall time complexity remains \(\mathrm{O}(N^2 2^N)\), which is same to that of Subset Convolution. (The latter part of hos’s article include a little more detailed explanation of a similar example in the latter half).
Next, we briefly explain a solution when \(M\) is small.
We adopt the inclusion-exclusion principle against the sets of edges. That is, we compute for each subset \(P\) of the edge set \(E\), “the number of ways to paint vertices such that, for all \(e \in P\) at least, the vertices adjacent to \(e\) are painted in the same color,” and find their sum weighted by \((-1)^{|P|}\). Then we have the following expression:
\[\sum_{P \subseteq E} (-1)^{|P|} K^{k(V, P)}.\]
(Here, \(k(V, P)\) is the number of connected components of a graph whose vertex set is \(\lbrace 1,2,\dots,N\rbrace\) and edge set is \(P\).)
Using this expression, we can compute the answer in a total of \(\mathrm{O}(N 2^M)\) time with brute forcing, or \(\mathrm{O}(2^M \log N)\) time with DFS (Depth-First Search) and rollback Union-Find.
The expression above can also be considered as a DP where edges are removed one by one. Let \(F(G)\) be the number of \(K\)-colorings of a graph \(G\). Then, taking an edge \(e\) of \(G\), we have
\[F(G) = F(G - e) - F(G \setminus e),\]
where \(-\) is a removal of an edge, and \(\setminus\) is a contraction of an edge. Also, if \(G\) has an isolated vertex \(v\), we have
\[F(G) = K F(G - v),\]
where \(-\) denotes a removal of an edge.
The writer’s solution uses this expression. That is, we consider how we can compute the number of colorings recursively of a graph after removing or contracting several edges.
Specifically, let \(v\) be a vertex of \(G\) with the minimum degree. If the degree of \(v\) is \(0\),
\[F(G) = K F(G - v).\]
If the degree of \(v\) is \(1\), we have
\[F(G) = (K - 1) F(G')\]
where \(e\) is the edge adjacent to \(v\), and graph \(G' = (V \setminus \lbrace v \rbrace, E \setminus \lbrace e \rbrace)\), so it can be recursively processed too.
Now we assume that the degree of \(v\) is \(2\). Let \(e_1\) and \(e_2\) be the edges adjacent to \(v\). We consider removing or contracting the two edges, for a total of four cases. Let us call them
\[G_1 = (G-e_1)-e_2, G_2 = (G-e_1)\setminus e_2,\]
\[G_3 = (G\setminus e_1)-e_2, G_4 = (G\setminus e_1) \setminus e_2.\]
Then \(G_2\) and \(G_3\) are isomorphic, and \(G_1\) is a graph obtained by adding an isolated vertex \(v\) to \(G_2\). Therefore,
\[ \begin{aligned} &F(G) \\ &= F(G_1) - F(G_2) - F(G_3) + F(G_4) \\ &= (K - 2) F(G_2) + F(G_4) \end{aligned} \]
Thus, we have a recurrence relation of finding the number of colorings of a graph with two graphs with two less edges.
In general, we need to count the colorings of \((2^{\deg(v)} - \deg(v))\) subgraphs, for any degree of \(v\).
We adopt this with the solution we introduced before. If the degree of \(v\) is \(3\) or greater, the number of vertices is bounded by \(\mathrm{ceil}(2M/3)\), so it can be computed in an \(\mathrm{O}(2^{2M/3} M^2)\) time, for a total of \(\mathrm{O}(\max(2^{M/2} , M^2 2^{2M/3})) = \mathrm{O}(M^2 1.59^M)\) time.
Alternatively, when we use subset DP instead of Subset Convolution, it is optimal to consider up to degree \(3\) (that boils down to five subgraphs); this requires \(\mathrm{O}(\max(5^{M/3}, M 3^{M/2})) = \mathrm{O}(M 1.74^M)\) time. While the base is greater than the solution before, this works fast enough too.
posted:
last update: