19.3.1. Deciding Whether A \(\boldsymbol{k}\)-Colouring Exists

To decide whether there exists a proper \(k\)-colouring of \(G\), we phrase the \(k\)-colouring problem as a set cover problem. A proper \(k\)-colouring of \(G\) defines a partition of the vertices into \(k\) independent sets \(I_1, \ldots, I_k\), each containing the vertices that have one of the \(k\) colours. These sets are independent because there is no edge whose endpoints have the same colour. These \(k\) independent sets cover \(V\): \(I_1 \cup \cdots \cup I_k = V\).

Conversely, given a covering of the vertices of \(G\) using \(k\) independent sets \(I_1, \ldots, I_k\), we can obtain a proper \(k\)-colouring by removing every vertex that occurs in more than one independent set from all but one of these sets: \(I_j' = I_j \setminus (I_1 \cup \cdots \cup I_{j-1})\) for all \(1 \le j \le k\). The resulting collection of sets \(I_1', \ldots, I_k'\) is a partition of \(V\) into \(k\) independent sets and thus defines a proper \(k\)-colouring by giving the colour \(j\) to all vertices in \(I_j'\), for all \(1 \le j \le k\).

Given a set cover instance \((U,\mathcal{S})\), a \(\boldsymbol{k}\)-cover is a set cover \(\mathcal{C} \subseteq \mathcal{S}\) of size \(|\mathcal{C}| = k\). By the above discussion, \(G\) has a proper \(k\)-colouring if and only if the set cover instance \((V,\mathcal{I})\), where \(\mathcal{I}\) is the collection of all independent sets of \(G\), has a \(k\)-cover. An interesting aspect of this problem is that the collection of sets \(\mathcal{I}\) has exponential size.

Again, to decide whether \((V,\mathcal{I})\) has a \(k\)-cover, we would like to count the number of \(k\)-covers and then check whether this count is positive. However, we can make our life much easier by counting what we call "covering \(k\)-tuples of independent sets" or simply "covering \(k\)-tuples":

A \(\boldsymbol{k}\)-tuple (of independent sets) is a tuple \((I_1, \ldots, I_k)\) such that \(I_1, \ldots, I_k \in \mathcal{I}\), that is, \(I_1, \ldots, I_k\) are independent sets in \(G\). Such a tuple is covering if \(I_1 \cup \cdots \cup I_k = V\).

The difference to a \(k\)-cover is that, being a set, a \(k\)-cover contains every set in \(\mathcal{I}\) at most once and there is no notion of an ordering of the sets in the \(k\)-cover. In contrast, the sets \(I_1, \ldots, I_k\) in a \(k\)-tuple have a well-defined order in the tuple, so \((I_1, \ldots, I_k)\) and \((I_k, \ldots, I_1)\), for example, are different tuples. We also allow a set to occur more than once in a tuple, that is, we allow \(I_h = I_j\) for some \(1 \le h < j \le k\). The key observation is that \(\mathcal{I}\) contains a \(k\)-cover of \(V\) if and only if there exists a covering \(k\)-tuple \((I_1, \ldots, I_k) \in \mathcal{I}^k\). Thus, it suffices to count the number of covering \(k\)-tuples in \(\mathcal{I}^k\).

Consider an arbitrary \(k\)-tuple \(T = (I_1, \ldots, I_k)\). We say that \(T\) has property \(P_v\) for some vertex \(v \in V\) if \(v \in I_1 \cup \cdots \cup I_k\). Let \(\mathcal{P} = \{ P_v \mid v \in V \}\). Then a \(k\)-tuple is covering if and only if it has all properties in \(\mathcal{P}\). If \(n_W\) is the number of \(k\)-tuples that have none of the properties in \(\mathcal{P}_W = \{ P_v \mid v \in W \}\), then Corollary 19.2 states that the number of covering \(k\)-tuples is

\[\sum_{W \subseteq V} (-1)^{|W|} n_W.\tag{19.1}\]

Observe that a tuple \(T = (I_1, \ldots, I_k)\) has none of the properties in \(\mathcal{P}_W\) if and only if \(I_j \cap W = \emptyset\) for all \(1 \le j \le k\). We say that the sets in \(T\) avoids \(W\). If \(m_W\) is the number of independent sets of \(G\) that avoid \(W\), then \(n_W = m_W^k\). Thus, the core of the problem is to compute all values \(m_W\).

Lemma 19.9: The set of values \(m_W\) for all \(W \subseteq V\) can be computed in \(O^*(2^n)\) time and space.

Proof: We use dynamic programming to compute all of these values in \(O^*(2^n)\) time. Specifically, we compute a table of values \(g_i(W)\) with \(W \subseteq V\) and \(0 \le i \le n\). For an arbitrary but fixed ordering \(\langle v_1, \ldots, v_n \rangle\) of the vertices in \(V\), \(g_i(W)\) is the number of all independent sets \(I\) in \(G\) that avoid \(W\) but contain all vertices in \(\{v_{i+1}, \ldots, v_n\} \setminus W\). In other words,

\[V \setminus (W \cup \{v_1, \ldots, v_i\}) \subseteq I \subseteq V \setminus W.\]

Then \(m_W = g_n(W)\) for all \(W \subseteq V\).

We compute these table entries by increasing index \(i\). For \(i = 0\), \(g_i(W)\) counts all independent sets \(I\) such that \(V \setminus W \subseteq I \subseteq V \setminus W\). Thus, \(g_0(W) = 1\) if \(V \setminus W\) is an independent set, and \(g_0(W) = 0\) otherwise.

For \(i > 0\), we distinguish two cases:

• If \(v_i \in W\), then \(V \setminus (W \cup \{v_1, \ldots, v_i\}) = V \setminus (W \cup \{v_1, \ldots, v_{i-1}\})\). Thus, an independent set \(I\) is a superset of \(V \setminus (W \cup \{v_1, \ldots, v_i\})\) if and only if it is a superset of \(V \setminus (W \cup \{v_1, \ldots, v_{i-1}\})\) and \(g_i(W) = g_{i-1}(W)\).

• If \(v_i \notin W\), then every independent set \(I\) such that

  \[V \setminus (W \cup \{v_1, \ldots, v_i\}) \subseteq I \subseteq V \setminus W\]

  either satisfies \(v_i \in I\) and, thus,

  \[V \setminus (W \cup \{v_1, \ldots, v_{i-1}\}) \subseteq I \subseteq V \setminus W\tag{19.2}\]

  or \(v_i \notin I\) and, thus,

  \[V \setminus ((W \cup \{v_i\}) \cup \{v_1, \ldots, v_{i-1}\}) \subseteq I \subseteq V \setminus (W \cup \{v_i\}).\tag{19.3}\]

  The number of independent sets satisfying (19.2) is \(g_{i-1}(W)\). The number of independent sets satisfying (19.3) is \(g_{i-1}(W \cup \{v_i\})\). Thus, \(g_i(W) = g_{i-1}(W) + g_{i-1}(W \cup \{v_i\})\).

  Since we compute \(g_i(W)\) after \(g_{i-1}(W)\) and \(g_{i-1}(W \cup \{v_i\})\), this shows that every table entry can be computed in constant time. Since there are \(2^n \cdot n\) table entries to be computed, the whole algorithm takes \(O(2^n \cdot n) = O^*(2^n)\) time and space. ▨

Corollary 19.10: It takes \(O^*(2^n)\) time and space to decide whether a graph \(G\) has a proper \(k\)-colouring.

Proof: By Lemma 19.9, we can compute all values \(m_W\), \(W \subseteq V\), in \(O^*(2^n)\) time and space. Evaluating (19.1) to count the number of covering \(k\)-tuples in \(\mathcal{I}^k\) then takes \(O^*(2^n)\) extra time. Since \(G\) has a proper \(k\)-colouring if and only if there exists at least one covering \(k\)-tuple, this solves the problem. ▨

Reducing the Space Requirements to Polynomial Space

The key to proving Corollary 19.10 was to produce all values \(m_W\), \(W \subseteq V\), in \(O^*(2^n)\) time, which we only know how to do using exponential space. If we are willing to spend more time to compute the values \(m_W\), \(W \subseteq V\), we can compute each value in turn using only linear space.

Lemma 19.11: Given any subset \(W \subseteq V\), \(m_W\) can be computed in \(O^*\bigl(2^{n-|W|}\bigr)\) time and linear space.

Proof: To compute \(m_W\), we need to count the independent sets in \(G[V \setminus W]\). Using linear time and space, we can construct \(G[V \setminus W]\). Then we enumerate all subsets of \(V \setminus W\) and test for each whether it is an independent set. We keep a running count of independent sets we have found so far and report its final value as \(m_W\). Testing, for each subset of \(V \setminus W\), whether it is an independent set takes linear time and space. Since there are \(2^{|V \setminus W|} = 2^{n - |W|}\) sets to be tested, the algorithm takes \(O^*\bigl(2^{n - |W|}\bigr)\) time and linear space. ▨

Corollary 19.12: It takes \(O^*(3^n)\) time and linear space to decide whether a graph \(G\) has a proper \(k\)-colouring.

Proof: We iterate over the subsets \(W \subseteq V\), compute \(m_W\) for each set such set \(W\), and add \((-1)^{|W|}m_W^k\) to the number of covering \(k\)-tuples of \(G\). Since computing each value \(m_W\) takes linear space, the whole algorithm takes linear space.

To bound the running time of the algorithm, observe that there are \(\binom{n}{j}\) subsets \(W \subseteq V\) of size \(|W| = j\). Thus, computing all values \(m_W\), \(W \subseteq V\) takes

\[\sum_{j=0}^n \binom{n}{j} O^*\bigl(2^{n-j}\bigr) = O^*(3^n)\]

time. ▨