# Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and
Packing Problems

Serge Gaspers  UNSW Sydney, Australia<EMAIL_ADDRESS>Jerry Zirui
Li  James Ruse Agricultural High School. Sydney, Australia,
<EMAIL_ADDRESS>
###### Abstract

Let $U$ be a universe on $n$ elements, let $k$ be a positive integer, and let
$\mathcal{F}$ be a family of (implicitly defined) subsets of $U$. We consider
the problems of partitioning $U$ into $k$ sets from $\mathcal{F}$, covering
$U$ with $k$ sets from $\mathcal{F}$, and packing $k$ non-intersecting sets
from $\mathcal{F}$ into $U$. Classically, these problems can be solved via
inclusion–exclusion in $2^{n}n^{O(1)}$ time [BHK09]. Quantumly, there are
faster algorithms for graph coloring with running time $O(1.9140^{n})$ [SM22]
and for Set Cover with a small number of sets with running time
$O\left(1.7274^{n}|\mathcal{F}|^{O(1)}\right)$ [ABI+19]. In this paper, we
give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever
there is a classical enumeration algorithm that lends itself to a quadratic
quantum speedup, which, for any subinstance on a set $X\subseteq U$,
enumerates at least one member of a $k$-partition, $k$-cover, or $k$-packing
(if one exists) restricted to (or projected onto, in the case of $k$-cover)
the set $X$ in $c^{|X|}n^{O(1)}$ time with $c<2$. Our bounded-error quantum
algorithm runs in time $(2+c)^{n/2}n^{O(1)}$ for Set Partition, Set Cover, and
Set Packing. It is obtained by combining three algorithms that have the best
running time for some values of $c$. When $c\leq 1.147899$, our algorithm is
slightly faster than $(2+c)^{n/2}n^{O(1)}$; when $c$ approaches $1$, it
matches the $O\left(1.7274^{n}|\mathcal{F}|^{O(1)}\right)$ running time of
[ABI+19] for Set Cover when $|\mathcal{F}|$ is subexponential in $n$.

For covering, packing, and partitioning into maximal independent sets, maximal
cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free
graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect
graphs, maximal threshold graphs, maximal split graphs, maximal line graphs,
and maximal induced forests, we obtain bounded-error quantum algorithms with
running times ranging from $O(1.8554^{n})$ to $O(1.9629^{n})$. Packing and
covering by maximal induced matchings can be done quantumly in $O(1.8934^{n})$
time.

For Graph Coloring (covering with $k$ maximal independent sets), we further
improve the running time to $O(1.7956^{n})$ by leveraging faster algorithms
for coloring with a small number of colors to better balance our divide-and-
conquer steps. For Domatic Number (packing $k$ minimal dominating sets), we
obtain a $O((2-\varepsilon)^{n})$ running time for some $\varepsilon>0$.

Several of our results should be of interest to proponents of classical
computing:

  * •

We present an inclusion-exclusion algorithm with running time
$O^{*}\left(\sum_{i=0}^{\lfloor\alpha n\rfloor}\binom{n}{i}\right)$, which
determines, for each $X\subseteq U$ of size at most $\alpha n$,
$0\leq\alpha\leq 1$, whether $(X,\mathcal{F})$ has a $k$-cover, $k$-partition,
or $k$-packing. This running time is best-possible, up to polynomial factors.

  * •

We prove that for any linear-sized vertex subset $X\subseteq V$ of a graph
$G=(V,E)$, the number of minimal dominating sets of $G$ that are subsets of
$X$ is $O((2-\varepsilon)^{|X|})$ for some $\varepsilon>0$.

##  1 Introduction

Graph Coloring is an example of a problem requiring to partition an
$n$-element set $U$ into $k$ sets from a family $\mathcal{F}$. In this case
$U$ is the vertex set of a graph $G$ and $\mathcal{F}$ is implicitly defined
as the independent sets of $G$. We can also view Graph Coloring as a covering
problem where the vertex set needs to be covered with $k$ maximal independent
sets.

In 2006, [BH06] and [Koi06] independently solved Graph Coloring in
$O^{*}(2^{n})$ time via a new inclusion–exclusion approach, along with other
partitioning and covering problems. The approach has been used for packing
problems as well, and has been generalized to solve more generic subset
convolution problems [BHKK07, BHKK11, BHK09].

In this work, we give faster quantum algorithms for a range of partitioning,
covering, and packing problems, including Graph Coloring and Domatic Number.
To do this, we use the framework of [ABI+19] where a preprocessing step
computes solutions to small subinstances and stores them in QRAM. These
solutions are then accessed by a divide-and-conquer algorithm which enjoys a
quadratic speedup in quantum models of computation via techniques such as
Grover’s search [Gro96]. For the preprocessing step (Section 3), we adapt the
afore-mentioned inclusion-exclusion approach [BHK09] to compute the solutions
to all subinstances induced by a small subset of $U$ up to roughly $n/4$
elements. For the divide-and-conquer step (Section 4) one would ideally like
to divide $U$ into two halves; unfortunately, optimal partitions111For
conciseness, we will mainly discuss partitions in the introduction. The
treatment of covers and packings is similar. may not allow for such a balanced
split. However, we can restrict the divide-and-conquer step to divide $U$ into
two parts where in the larger part (equivalently, in both parts) the removal
of one set of an optimal partition results in at most $n/2$ elements. Finding
one set of the optimal partition is done via an algorithm that enumerates all
relevant candidate sets; for Graph Coloring, it enumerates the maximal
independent sets in the graph induced by the subset $X\subseteq U$ under
consideration. Importantly, we need that this enumeration can be done in
$O^{*}\left(c^{|X|}\right)$ time, for some $c<2$ by a classical algorithm that
has a quadratic quantum speedup, so that after two levels of divide-and-
conquer, the overall quadratic quantum speedup outperforms the classical
$O^{*}(2^{n})$ running time.

Our algorithm differs from the previously fastest quantum algorithm for Graph
Coloring [SM22] in both the preprocessing step and the divide-and-conquer
step. Our preprocessing step is deterministic and its running time is optimal,
matching the size of the output up to polynomial factors; the preprocessing
step of [SM22] is a bounded-error quantum algorithm whose running time is a
multiplicative factor of $3^{|X|/6}$ slower than ours for each small (up to
size roughly $n/4$) subset $X\subseteq U$. For the divide-and-conquer step,
our divide-then-enumerate strategy is described above; [SM22] employ an
enumerate-then-divide strategy, where the enumeration is done on the set to be
divided and the remainder is then divided into two sets of size at most half
the original set. It turns out that blending the the divide-then-enumerate and
the enumerate-then-divide strategy gives faster algorithms when $c\leq
1.147899$ (Section 5). For $c\leq 1.0872$ case, we also use a third level of
divide-and-conquer, and when $c$ approaches $1$, our $O(1.7274^{n})$ running
time matches the running time for Set Cover with a subexponential number of
sets of [ABI+19].

This gives improved algorithms for a range of partitioning, covering, and
packing problems (Section 6). We further improve the running time for Graph
Coloring (Section 7) to $O(1.7956^{n})$ by leveraging faster algorithms for a
small number of colors [SM22]. Our algorithm considers large subsets of
vertices ($\geq 0.48n$) an checks whether they are $5$-colorable,
$6$-colorable with no large $5$-colorable subset, and in some cases
$7$-colorable via a new $7$-Coloring algorithm that relies on the
preprocessing step. The advantage of excluding such cases from further
consideration is that we can make the divide-and-conquer steps more balanced.

For Domatic Number, at first glance it seems that our approach cannot be used.
The issue is that when considering a vertex subset $X$, even though there is
an algorithm that enumerates all minimal dominating sets of $G[X]$ in
$O(1.7159^{n})$ time [FGPS08], this is insufficient for our purposes: we need
to enumerate minimal vertex subsets of $X$ that dominate all of $G$, not just
$G[X]$, in $O^{*}\left(c^{|X|}\right)$ time for some $c<2$. In Section 8, we
show that such an enumeration algorithm (with a quadratic quantum speedup)
indeed exists provided that $|X|=\Omega(n)$. This then also gives a bounded-
error quantum algorithm for Domatic Number running in $O((2-\varepsilon)^{n})$
time.

##  2 Preliminaries

For a proposition $P$, the _Iverson bracket_ $[P]$ is a function that returns
$1$ if $P$ is true and $0$ otherwise.

### Asymptotic notation.

The $O^{*}$-notation is similar to the usual $O$-notation but allows to hide
polynomial factors in the input size. The $\tilde{O}$-notation hides
polylogarithmic factors. We make heavy use of Stirling’s approximation for
factorials, which implies that
$\binom{n}{k}=O^{*}\left(\left(\frac{n}{k}\right)^{k}\cdot\left(\frac{n}{n-k}\right)^{n-k}\right)$,
and of the binomial theorem,
$\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}=(x+y)^{n}$.

### Set Systems.

An implicit set system [FGLS19] is a function $\Phi$ that takes as input a
string $I\in\\{0,1\\}^{*}$ and outputs a set system $(U_{I},\mathcal{F}_{I})$,
where $U_{I}$ is a universe and $\mathcal{F}_{I}$ is a collection of subsets
of $U_{I}$. The string $I$ is referred to as an _instance_ and we denote by
$|U_{I}|=n$ the size of the universe and by $|I|=N$ the size of the instance.
We assume that $N\geq n$. The implicit set system $\Phi$ is said to be
_polynomial time computable_ if (a) there exists a polynomial time algorithm
that given $I$, produces $U_{I}$, and (b) there exists a polynomial time
algorithm that given $I$, $U_{I}$ and a subset $S$ of $U_{I}$, determines
whether $S\in\mathcal{F}_{I}$. Throughout this paper, we consider only
polynomial time computable implicit set systems. We define a _subset
polynomial time computable_ implicit set system $\Phi$ to be a polynomial time
computable set system, where (c) there exists a polynomial time algorithm that
given $I$, $U_{I}$ and a subset $S$ of $U_{I}$, determines whether $S\subseteq
S^{\prime}$ for some $S^{\prime}\in\mathcal{F}_{I}$. This is equivalent to
determining whether $S\in\mathcal{F}\downarrow$, where the downward closure
$\mathcal{F}\downarrow$ of $\mathcal{F}$ contains all sets in $\mathcal{F}$
and their subsets.

For any subset of elements $X\subseteq U$, an ordered tuple
$(S_{1},\dots,S_{k})$ of $k$ sets from $\mathcal{F}$ is a _$k$ -cover_ for $X$
if the union of these sets is $X$; it is a _$k$ -packing_ for $X$ if the
$S_{i}$’s are contained in $X$ and are pairwise non-intersecting; it is a _$k$
-partition_ for $X$ if it is both a $k$-cover and a $k$-packing for $X$.

For a subset polynomial time computable implicit set system $\Phi$, the input
of the $\Phi$-Set Cover problem is an instance $I$ and an integer $k$, and the
question is whether the set system $\Phi(I)=(U_{I},\mathcal{F}_{I})$ has a
$k$-cover. This is equivalent to asking whether
$(U_{I},\mathcal{F}_{I}\downarrow)$ has a $k$-cover and therefore, we assume
that $\mathcal{F}_{I}=\mathcal{F}_{I}\downarrow$ whenever discussing
$k$-covers. For a polynomial time computable implicit set system $\Phi$, the
input of the $\Phi$-Set Partition and $\Phi$-Set Packing problem is an
instance $I$ and an integer $k$, and the question is whether the set system
$\Phi(I)=(U_{I},\mathcal{F}_{I})$ has a $k$-partition or $k$-packing,
respectively. We generally omit $\Phi$ and the subscript $I$ when they are
clear from context.

### Graphs.

In a graph $G=(V,E)$, the _open neighborhood_ of a vertex $v$, denoted
$N_{G}(v)$ is the set containing all vertices adjacent to $v$ in $G$. The
_closed neighborhood_ of $v$ in $G$ also contains $v$ itself, and is denoted
$N_{G}[v]=\\{v\\}\cup N_{G}(v)$. Again, we may omit the subscript $G$. For a
vertex subset $X\subseteq V$, the graph $G-X$ is obtained from $G$ by removing
the vertices in $X$ and all their incident edges; the graph $G[X]$ induced on
$X$ is the graph $G-(V\setminus X)$.

### Quantum Algorithms.

It is known that most classical branching algorithms have a quadratic speedup
on quantum machines. As [SM22], we also rely on the following results.

######  Theorem 1 ([Gro96, BBHT98]).

Let $A:\\{1,2,\dots,N\\}\rightarrow\\{0,1\\}$ be a bounded-error quantum
algorithm with running time $T$. Then, there is a bounded-error quantum
algorithm computing $\bigvee_{x\in\\{1,\dots,N\\}}A(x)$ with running time
$\tilde{O}(\sqrt{N}T)$.

######  Theorem 2 ([DH96]).

Let $A:\\{1,2,\dots,N\\}\rightarrow\\{0,1\\}$ be a bounded-error quantum
algorithm with running time $T$. Then, there is a bounded-error quantum
algorithm computing $\min_{x\in\\{1,\dots,N\\}}A(x)$ with running time
$\tilde{O}(\sqrt{N}T)$.

In our context, $A$ is an algorithm exploring paths in superposition from the
root to the leaves of the search tree of a classical branching algorithm. The
amplitudes of this exploration depend on estimates of the sizes of the
subtrees, either by relying on an analysis of the classical branching
algorithm [Für08, SM22] or by on-the-fly estimations [AK17]. We speak of a
_simple_ branching algorithm when the exploration of one root-to-leaf path is
independent of the other paths; this excludes, for example, algorithms relying
on clause learning, re-use of computation done in earlier branches, and
branch-and-bound. For a simple branching algorithm with running time
$O^{*}(c^{n})$, one obtains a bounded-error quantum algorithm with running
time $O^{*}(c^{n/2})$ in this way; we simply say that we apply Grover’s search
to the branching algorithm.

##  3 Preprocessing small subsets

For $\alpha\in[0,1]$, a subset $X$ of $U$ is _$\alpha$ -small_ if
$|X|\leq\alpha n$. Denote by $s(n,\alpha)=\sum_{i=0}^{\lfloor\alpha
n\rfloor}\binom{n}{i}$ the number of $\alpha$-small subsets of $U$. In this
section, we consider the problem of counting the number of $k$-covers,
$k$-packings, and $k$-partitions for each $\alpha$-small subset of $U$. When
considering $k$-covers, we assume that $\mathcal{F}$ has been replaced by
$\mathcal{F}\downarrow$. This is because when we would like to cover a subset
of elements of $X$, we may use a set from $\mathcal{F}$ that also contains
elements outside of $X$. Since $\Phi$ is subset polynomial time computable in
the $\Phi$-Set Cover problem, we may as well replace $\mathcal{F}$ by
$\mathcal{F}\downarrow$; this makes the discussion of covering, partitioning,
and packing problems more uniform. Our algorithms run in
$O^{*}\left(s(n,\alpha)\right)$ time, which is best possible, since the output
is a list of $s(n,\alpha)$ integers.

This section heavily relies on previous $O^{*}(2^{n})$ inclusion-exclusion
approaches [BHKK11, BHK09] to compute the number of $k$-covers, $k$-packings,
and $k$-partitions for $U$ and these results are well-known when $\alpha=1$.

We start by defining the $\alpha$-small zeta transform, which is central to
this section.

######  Definition 1.

Let $f$ be a function from subsets of the universe $U$ to an algebraic ring
$R$. The _$\alpha$ -small zeta transform_ of $f$, denoted $f\zeta_{\alpha}$ is

$\displaystyle f\zeta_{\alpha}(X)=\sum_{Y\subseteq X}f(Y)$

for any $\alpha$-small $X\subseteq U$.

The $1$-small zeta transform is also called the _zeta transform_ and the
$\alpha$-small zeta transform is precisely the restriction of the zeta
transform to $\alpha$-small sets. Throughout this paper we assume that
arithmetic operations in the ring $R$ take $O^{*}(1)$ time and each ring
element is represented using $O^{*}(1)$ space.

######  Definition 2.

Let $f$ be a function from subsets of the universe $U$ to an algebraic ring
$R$. The _$\alpha$ -small Möbius transform_ of $f$, denoted $f\mu_{\alpha}$ is

$\displaystyle f\mu_{\alpha}(X)=\sum_{Y\subseteq X}(-1)^{|X\setminus Y|}f(Y)$

for any $\alpha$-small $X\subseteq U$.

It is well-known (see, e.g., [FK10]) that
$f\zeta_{\alpha}\mu_{\alpha}=f\mu_{\alpha}\zeta_{\alpha}=f$ when $\alpha=1$,
and the same is true when $\alpha\neq 1$.

######  Lemma 1.

The $\alpha$-small zeta transform $f\zeta_{\alpha}$ and the $\alpha$-small
Möbius transform $f\mu_{\alpha}$ can be computed in $O^{*}(s(n,\alpha))$ time.

###### Proof.

We start with $f\zeta_{\alpha}$ and proceed as in Yates’s method [Yat37].
Consider an arbitrary ordering of the elements of $U=\\{v_{1},\dots,v_{n}\\}$.
The algorithm considers each $\alpha$-small $X\subseteq U$ by increasing order
of cardinality.

Set $g_{0}(X)=f(X)$. Then, iterate over the elements of $U$ in the ordering
fixed above. When processing element $v_{i}$, set

$\displaystyle g_{i}(X)$ $\displaystyle=g_{i-1}(X)+[v_{i}\in X]\cdot
g_{i-1}(X\setminus\\{v_{i}\\}).$

Finally, set $f\zeta_{\alpha}(X)=g_{n}(X)$.

Correctness can be shown by induction on $i$ by observing that

$\displaystyle g_{i}(X)=\sum_{\\{v_{i+1},\dots,v_{n}\\}\cap X\subseteq
Y\subseteq X}f(Y).$

For each set $X$ the computation takes $O^{*}(1)$ time, and the number of sets
$X$ to be considered is $s(n,\alpha)$.

To compute $f\mu_{\alpha}$, we use the fact that
$\mu_{\alpha}=\sigma_{\alpha}\zeta_{\alpha}\sigma_{\alpha}$, where the
$\alpha$-small odd-negation transform is

$\displaystyle f\sigma_{\alpha}(X)=(-1)^{|X|}f(X),$

defined for any $\alpha$-small $X\subseteq U$. Indeed,

$\displaystyle f\sigma_{\alpha}\zeta_{\alpha}\sigma_{\alpha}(X)$
$\displaystyle=(-1)^{|X|}\cdot\sum_{Y\subseteq X}(-1)^{|Y|}\cdot f(Y)$
$\displaystyle=\sum_{Y\subseteq X}(-1)^{|X|+|Y|}f(Y)$
$\displaystyle=\sum_{Y\subseteq X}(-1)^{|X\setminus Y|}f(Y)$

since $|X|+|Y|$ and $|X|-|Y|=|X\setminus Y|$ have the same parity. The result
now follows, because, for a function $g$ and a set $X$, $g\sigma_{\alpha}(X)$
can be computed in $O^{*}(1)$ time. ∎

We refer to these algorithms as the _fast $\alpha$-small zeta transform_ and
the _fast $\alpha$-small Möbius transform_.

By inclusion-exclusion, the number of $k$-covers for a subset $X\subseteq U$
is

$\displaystyle c_{k}(\mathcal{F},X)=\sum_{Y\subseteq X}(-1)^{|X\setminus
Y|}a(Y)^{k},$ (1)

where $a(Y)$ is the number of subsets $Z\subseteq Y$ that belong to
$\mathcal{F}=\mathcal{F}\downarrow$.

For the number of $k$-partitions, we use an indeterminate $z$ in the ring $R$
that allows us to keep track of the sum of the cardinalities of the sets in
the cover. The number of $k$-partitions for a subset $X\subseteq U$ is given
by the coefficient of the monomial $z^{|X|}$ in the polynomial

$\displaystyle d_{k}(\mathcal{F},X)=\sum_{Y\subseteq X}(-1)^{|X\setminus
Y|}\left(\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}\right)^{k},$ (2)

where $a_{j}(Y)$ is the number of size-$j$ subsets $Z\subseteq Y$ that belong
to $\mathcal{F}$.

For the number of $k$-packings of $X$, we compute the number of
$(k+1)$-partitions where the first $k$ members of the $(k+1)$-tuple belong to
$\mathcal{F}$ and the last member is an arbitrary subset of $X$. Noting that
$(1+z)^{|Y|}=\sum_{i=0}^{|Y|}\binom{|Y|}{i}z^{i}$, the number of $k$-packings
for $X\subseteq U$ is the coefficient of $z^{|X|}$ in

$\displaystyle p_{k}(\mathcal{F},X)=\sum_{Y\subseteq X}(-1)^{|X\setminus
Y|}(1+z)^{|Y|}\left(\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}\right)^{k}.$ (3)

The first algorithmic step is to compute the values for $a(Y)$ in (1) and the
polynomials $\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}$ in (2) and (3). Observe that
$|Y|\leq|X|\leq\alpha n$. To compute the values $a(Y)$ for all $\alpha$-small
$Y\subseteq U$, observe that $a(Y)=\sum_{Z\subseteq Y}[Z\in\mathcal{F}]$ is
the $\alpha$-small zeta transform of the indicator function of $\mathcal{F}$.
Since the implicit set system is polynomial time computable, the indicator
function can be evaluated in polynomial time. Therefore, the fast
$\alpha$-small zeta transform allows us to compute all relevant values of
$a(\cdot)$ in $O^{*}(s(n,\alpha))$ time. Similarly, the polynomial
$\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}$ equals $h\zeta_{\alpha}(Y)$ where
$h(Z)=[Z\in\mathcal{F}]\cdot z^{|Z|}$ and can be computed in the same time
bound by the fast $\alpha$-small zeta transform.

The second algorithmic step is to to use the fast $\alpha$-small Möbius
transform and apply it to the functions that associate with each
$\alpha$-small $Y\subseteq U$ the values $a(Y)^{k}$;
$\left(\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}\right)^{k}$; and
$(1+z)^{|Y|}\left(\sum_{j=0}^{|Y|}a_{j}(Y)z^{j}\right)^{k}$, respectively.

We conclude that $c_{k}(\mathcal{F},X)$, $d_{k}(\mathcal{F},X)$, and
$p_{k}(\mathcal{F},X)$ for each $\alpha$-small $X\subseteq U$ can be computed
in $O^{*}(s(n,\alpha))$ time.

######  Theorem 3.

Given a polynomial time computable implicit set family
$\Phi(I)=(U,\mathcal{F})$ with $|U|=n$, there is a $O^{*}(s(n,\alpha))$ time
algorithm which determines, for all $k\leq\alpha n$ and all $\alpha$-small
$X\subseteq U$, whether $(X,\mathcal{F})$ has a $k$-cover (if we assume that
$\mathcal{F}$ is closed under subsets), $k$-partition, or $k$-packing.

##  4 Divide-and-conquer algorithm

Let $\Phi(I)=(U,\mathcal{F})$ be a polynomial time computable implicit set
family for which we would like to determine whether there is a $k$-cover
(assuming $\mathcal{F}=\mathcal{F}\downarrow$), $k$-partition, or $k$-packing.

We say that a simple branching algorithm _enumerates_ a family
$\mathcal{F}^{\prime}$ of subsets of $U$ if, at each leaf of its search tree
it finds at most one member of $\mathcal{F}^{\prime}$, and collectively the
leaves find all members of $\mathcal{F}^{\prime}$ (duplicates are allowed).

Our algorithm uses a divide-and-conquer strategy where the universe is twice
partitioned into two.

######  Definition 3.

For a family of subsets $\mathcal{F}$ of a universe $U$, and a subset
$X\subseteq U$, the _restriction_ of $\mathcal{F}$ to $X$ is
$r(\mathcal{F},X)=\\{S\subseteq X:S\in\mathcal{F}\\}$.

Observe that $(U,\mathcal{F})$ has a $k$-partition (resp., a $k$-packing or a
$k$-cover) for $k\geq 2$ iff there is a set $L\subseteq U$ and a positive
integer $k_{l}<k$ such that $(L,r(\mathcal{F},L))$ has a $k_{l}$-partition
(resp., a $k_{l}$-packing or a $k_{l}$-cover) and $(R,r(\mathcal{F},R))$ has a
$k_{r}$-partition (resp., a $k_{r}$-packing or a $k_{r}$-cover), where
$R=U\setminus L$ and $k_{r}=k-k_{l}$. We say that a $k$-partition,
$k$-packing, or $k$-cover $(S_{1},\dots,S_{k})$ does not _straddle_ $X$ if for
each $i\in\\{1,\dots,k\\}$, either $S_{i}\subseteq X$ or $S_{i}\cap
X=\emptyset$.

In this section we prove the following theorem.

######  Theorem 4.

Suppose there is a simple (classical) branching algorithm $A$, which, given an
instance $I$ and a subset $X\subseteq U$, enumerates a family $e(X,I)$ of
subsets of $X$ such that

  * •

if $(U,\mathcal{F})$ has a $k$-cover (resp., a $k$-partition or a $k$-packing)
that does not straddle $X$, then $(U,\mathcal{F})$ has a $k$-cover (resp., a
$k$-partition or a $k$-packing) $(S_{1},\dots,S_{k})$ with $S_{1}\in e(X,I)$,
and

  * •

the algorithm runs in $O^{*}(c^{|X|})$ time for some $c\leq 2$.

Then, there is a bounded-error quantum algorithm, which determines whether
$(U,\mathcal{F})$ has a $k$-cover (resp., a $k$-partition or a $k$-packing) in
$O^{*}\left(\binom{n}{n/4}+(2+c)^{n/2}\right)$ time, where $n=|U|$.

From now on, we focus on Set Cover; the discussion of Set Partition and Set
Packing is analogous. The first step is to use the algorithm from Theorem 3
with $\alpha=\frac{1}{4}$ and store the result in QRAM.

Ideally, we would want to divide the universe $U$ into equal sized sets $L$
and $R$ and compute a $k$-cover where each set of the cover is responsible for
covering elements of either $L$ or $R$. However, we cannot guarantee that such
a $k$-cover exists. Instead, we can focus on partitions of $U$ into $L$ and
$R$ with $|L|\geq n/2$ where the removal of one member of the $k$-cover
decreases the size of $L$ to at most $n/2$.

######  Lemma 2.

For any $x\in\\{0,\dots,n\\}$, $(U,\mathcal{F})$ has a $k$-cover, $k\geq 2$,
iff there is a partition of $U$ into $(L,R)$ with $|L|\geq x$ and integers
$k_{L},k_{R}\geq 1$ with $k=k_{L}+k_{R}$ such that $(L,r(\mathcal{F},L))$ has
a $k_{L}$-cover $(S_{1},\dots,S_{k_{L}})$ and $(R,r(\mathcal{F},R))$ has a
$k_{r}$-cover such that $|S_{i}|\geq|L|-x$ for every
$i\in\\{1,\dots,k_{L}\\}$.

In particular, this means that removing any member $S_{i}$ of the
$k_{L}$-cover gives a $(k_{L}-1)$-cover of $L\setminus S_{i}$ and $|L\setminus
S_{i}|\leq x$.

We use Grover’s search to divide the elements into two sets $(L,R)$ where
$|L|\geq n/2$ and $k$ into $k_{L}+k_{R}$. Then, we solve each of these two
instances independently, again using Grover’s search on $(L,r(\mathcal{F},L))$
(resp., on $(R,r(\mathcal{F},R))$), dividing it into $(LL,LR)$ where $|LL|\geq
n/4$ and $k_{LL}+k_{LR}=k_{L}$ (similar for $R$). For $(LL,r(\mathcal{F},LL))$
(and, similarly, on the corresponding instances for $LR$, $RL$, $RR$), we use
Grover’s search on the branching algorithm $A$ to enumerate candidate sets
$S_{1}\in e(LL,r(\mathcal{F},LL))$; if $|LL|-|S_{1}|>n/4$, then this branch is
unsuccessful; otherwise, look up whether $LL\setminus S_{1}$ has a
$(k_{LL}-1)$-cover in QRAM.

The running time of this algorithm is

$\displaystyle O^{*}\left(\binom{n}{n/4}\right)$

for the running the algorithm from Theorem 3; the steps using Grover’s search
take

$\displaystyle O^{*}\left(\sqrt{\sum_{l=\lceil
n/2\rceil}^{n}\binom{n}{l}\sum_{l^{\prime}=\lceil
n/4\rceil}^{l}\binom{l}{l^{\prime}}c^{l^{\prime}}}\right)=O^{*}\left((2+c)^{n/2}\right)$

time to achieve constant success probability. This proves Theorem 4.

### Discussion.

When $c\geq\frac{16}{3^{3/2}}-2\approx 1.079201$, then the running time is
$O^{*}\left((2+c)^{n/2}\right)$. When $c\leq\frac{16}{3^{3/2}}-2$, then the
running time is dominated by the term $\binom{n}{n/4}\approx 1.7548^{n}$. For
$c\leq 1.147899$, the next section gives faster algorithms.

##  5 Divide-and-conquer algorithms for small $c$

In this section, we again assume that there is an enumeration algorithm $A$,
as in Theorem 4, with running time $O^{*}\left(c^{|X|}\right)$. We present two
divide-and-conquer algorithms which are faster for small values of $c$.

Throughout this section, we focus on Set Cover; the discussion of Set
Partition and Set Packing is analogous.

######  Theorem 5.

There is a bounded-error quantum algorithm, which determines whether
$(U,\mathcal{F})$ has a $k$-cover (resp., a $k$-partition or a $k$-packing) in
$O^{*}\left(\binom{n}{n/4}+(1+c)^{\frac{3}{4}\cdot n}\right)$ time, where
$n=|U|$.

The first step is to use the algorithm from Theorem 3 with
$\alpha=\frac{1}{4}$ and store the result in QRAM. Our algorithm is similar to
the algorithm in Theorem 4, but we use the branching algorithm $A$ to remove a
subset from $L$ before dividing it into $(LL,LR)$. Again, Lemma 2 is central
to our algorithm.

We use Grover’s Search to divide the elements into two sets $(L,R)$ where
$|L|\geq n/2$ and $k$ into $k_{L}+k_{R}$. Then, we solve each of these two
instances independently, again using Grover’s search on
$(R,r(\mathcal{F},R))$, dividing it into $(RL,RR)$ where $|RL|\geq n/4$ and
$k_{RL}+k_{RR}=k_{R}$. For the instance $(L,r(\mathcal{F},L))$, we use
Grover’s search on the branching algorithm $A$ to enumerate candidate sets
$S_{1}\in e(L,r(\mathcal{F},L))$; if $|L|-|S_{1}|>n/2$ then this branch is
unsuccessful; otherwise, we use Grover’s search on the subinstance
$(L\setminus S_{1},r(\mathcal{F},L\setminus S_{1}))$, dividing it into
$(LL,LR)$ where $|LL|\geq n/4$ and $k_{LL}+k_{LR}=k_{L}-1$.

We process $(LL,r(\mathcal{F},LL))$ (and, similarly, the corresponding
instances for $LR$, $RL$, $RR$) as we did in Theorem 4 – we use Grover’s
search on the branching algorithm $A$ to enumerate candidate sets $S_{1}\in
e(LL,r(\mathcal{F},LL))$; if $|LL|-|S_{1}|>n/4$, then this branch is
unsuccessful; otherwise, look up whether $LL\setminus S_{1}$ has a
$(k_{LL}-1)$-cover in QRAM.

The running time of this algorithm is

$\displaystyle O^{*}\left(\binom{n}{n/4}\right)$

for the running the algorithm from Theorem 3; the steps using Grover’s search
take

$\displaystyle O^{*}\left(\sqrt{\sum_{l=\lceil
n/2\rceil}^{n}\binom{n}{l}c^{l}\sum_{l^{\prime}=\lceil n/4\rceil}^{\lfloor
n/2\rfloor}\binom{n/2}{l^{\prime}}c^{l^{\prime}}}\right)=O^{*}\left((1+c)^{\frac{3}{4}\cdot
n}\right)$

time to achieve constant success probability. This proves Theorem 5.

### Discussion.

When $c\geq\frac{2^{8/3}}{3}-1\approx 1.11653$, then the running time is
$O^{*}\left((1+c)^{\frac{3}{4}\cdot n}\right)$. When
$c\leq\frac{2^{8/3}}{3}-1$, then the running time is dominated by the term
$\binom{n}{n/4}\approx 1.7548^{n}$. When $c\leq 1.0872$, then the following
algorithm is faster.

######  Theorem 6.

If $c\leq 1.0872$, there is a bounded-error quantum algorithm, which
determines whether $(U,\mathcal{F})$ has a $k$-cover (resp., a $k$-partition
or a $k$-packing) in

$\displaystyle O^{*}\left(\left(\min_{0.1303\leq\alpha\leq
0.25}\left((1+c)^{3/4}c^{\alpha/2}\left(1-4\cdot\alpha\right)^{\frac{4\cdot\alpha-1}{8}}\left(4\cdot\alpha\right)^{-\frac{\alpha}{2}},\;\;\alpha^{-\alpha}\cdot(1-\alpha)^{\alpha-1}\right)\right)^{n}\right)\text{
time.}$

The first step is to use the algorithm from Theorem 3 with some
$0.1303\leq\alpha<0.25$ and store the result in QRAM. Our algorithm is
identical to the one presented in Theorem 5 except that we cannot directly
look up whether a subset $X\subseteq U$ has a $k$-cover in QRAM for $|X|\leq
n/4$. Instead, we use the following approach.

######  Lemma 3.

If $c\leq 1.0872$ and $0.1303\leq\alpha<0.25$, after running the algorithm
from Theorem 3, there exists a bounded-error quantum algorithm that checks for
a $k$-cover of a subset $X\subseteq U$ where $|X|\leq n/4$ in
$O^{*}\left(\sqrt{\binom{n/4}{\alpha\cdot n}\cdot c^{\alpha\cdot n}}\right)$
time.

###### Proof.

We use Grover’s search to divide the elements of $X$ into two sets $(XL,XR)$
where $|XL|\geq\alpha\cdot n$ and $k$ into $k_{XL}+k_{XR}$. We use Grover’s
search on the branching algorithm $A$ to enumerate candidate sets $S_{1}\in
e(XL,r(\mathcal{F},XL))$; if $|XL|-|S_{1}|>\alpha\cdot n$, then this branch is
unsuccessful; otherwise, look up whether $XL\setminus S_{1}$ has a
$(k_{XL}-1)$-cover and $XR$ has a $k_{XR}$-cover in QRAM. The correctness of
this approach follows from Lemma 2.

As the function $f(x)=\binom{n/4}{x}c^{x}$ is strictly decreasing for
$x>\frac{c}{c+1}\cdot\frac{n}{4}$ and

$\displaystyle\alpha\cdot n\geq 0.1303\cdot
n>\frac{1.0872\mathbin{/}4}{1.0872+1}\cdot
n\geq\frac{c}{c+1}\cdot\frac{n}{4},$

the running time of this algorithm is

$\displaystyle O^{*}\left(\sqrt{\sum_{i=\lceil\alpha\cdot n\rceil}^{\lfloor
n/4\rfloor}\binom{n/4}{i}c^{i}}\right)=O^{*}\left(\sqrt{\binom{n/4}{\alpha\cdot
n}c^{\alpha\cdot n}}\right)$

∎

Our algorithm is the same as the one in Theorem 3, except when we check for a
$(k_{LL}-1)$-cover for $LL\setminus S_{1}$ (resp., on $LR$, $RL$, $RR$) we use
Lemma 3 instead of a direct lookup in QRAM.

Running the algorithm from Theorem 3 takes

$\displaystyle O^{*}\left(\binom{n}{\alpha\cdot n}\right)$
$\displaystyle=O^{*}\left(\alpha^{-\alpha
n}\cdot(1-\alpha)^{(\alpha-1)n}\right)$

time. The steps using Grover’s search take

$\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil
n/2\rceil}^{n}\binom{n}{l}c^{l}\sum_{l^{\prime}=\lceil n/4\rceil}^{\lfloor
n/2\rfloor}\binom{n/2}{l^{\prime}}c^{l^{\prime}}}\sqrt{\binom{0.25\cdot
n}{\alpha\cdot n}c^{\alpha\cdot n}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(\left((1+c)^{3/4}c^{\alpha/2}\left(\frac{1}{1-4\cdot\alpha}\right)^{\frac{1-4\cdot\alpha}{8}}\left(\frac{1}{4\cdot\alpha}\right)^{\frac{\alpha}{2}}\right)^{n}\right)\text{
time.}$

The running time of the first part increases with $\alpha$ while the running
time of the second part decreases with $\alpha$. We can therefore optimise the
running time by balancing the value of $\alpha$ for a given $c$. To determine
when this approach is faster than $O^{*}\left(\binom{n}{n/4}\right)$ we
compute the value of $c$ when $\alpha$ is balanced at $0.25$:

$\displaystyle(1+c)^{3/4}c^{1/8}$ $\displaystyle=\frac{4}{3^{3/4}}$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle c$ $\displaystyle\approx
1.08724\enspace.$

Therefore, this algorithm outperforms the algorithms of Theorem 4 and Theorem
5 when $c\leq 1.08723$. The precise running time for certain values of $c$ and
the corresponding values of $\alpha$ are shown in the table below. We also
depict the best running times of all three algorithms for various values of
$c$.

$c$ | $\alpha$ | running time
---|---|---
1.0 | 0.236159 | $O^{*}(1.7274^{n})$
1.01 | 0.238036 | $O^{*}(1.7312^{n})$
1.02 | 0.239858 | $O^{*}(1.7349^{n})$
1.03 | 0.241622 | $O^{*}(1.7384^{n})$
1.04 | 0.243320 | $O^{*}(1.7418^{n})$
1.05 | 0.244946 | $O^{*}(1.7450^{n})$
1.06 | 0.246488 | $O^{*}(1.7480^{n})$
1.07 | 0.247928 | $O^{*}(1.7508^{n})$
1.08 | 0.249227 | $O^{*}(1.7533^{n})$
$1$$1.2$$1.4$$1.6$$1.8$$2$$1.7$$1.8$$1.9$$2$$c$Base $b$ of running time
$O^{*}(b^{n})$Running time for various values of $c$Theorem 4Theorem 5Theorem
6

Combining Theorem 4, Theorem 5, and Theorem 6, we obtain the following
corollary.

######  Corollary 1.

There is a bounded-error quantum algorithm, which determines whether
$(U,\mathcal{F})$ has a $k$-cover (resp., a $k$-partition or a $k$-packing) in
$O^{*}\left((2+c)^{n/2}\right)$ time, where $n=|U|$.

When $c\leq 1.147899$, then the running time provided by the best among
Theorem 5 and Theorem 6 is slightly faster. See Appendix A for details. At
$c=1$, the running time of Theorem 6 matches the running time of the Set Cover
algorithm of [ABI+19] when $|\mathcal{F}|$ is subexponential in $n$.

##  6 Applications

We can now use Corollary 1 in combination with simple branching algorithms
enumerating various vertex sets in graphs, in particular algorithms
enumerating maximal independent sets (equivalently, maximal cliques in the
complement graph) in $O^{*}(3^{n/3})$ time [FK10] (we note that the algorithm
of [JYP88] is not a _simple_ branching algorithm), maximal bicliques in
$O^{*}(3^{n/3})$ time, maximal induced matchings in $O^{*}(10^{n/5})$ time
[GRS12], maximal induced forests in $O(1.8527^{n})$ time [GL17], and minimal
$k$-hitting sets in $O^{*}((2-1/k)^{n})$ time [FGLS19]. The last result is
used to enumerate maximal $\mathcal{H}$-free subgraphs, which have no induced
subgraph isomorphic to any graph from the family $\mathcal{H}$ of graphs, all
of which have at most $k$ vertices. Some well-known $\mathcal{H}$-free graph
classes are

  * •

_cluster_ graphs with $\mathcal{H}=\left\\{P_{3}\right\\}$, where $P_{k}$
denotes the path on $k$ vertices,

  * •

_triangle-free_ graphs with $\mathcal{H}=\left\\{K_{3}\right\\}$, where
$K_{k}$ denotes the complete graph on $k$ vertices,

  * •

_cographs_ with $\mathcal{H}=\left\\{P_{4}\right\\}$ [CLB81],

  * •

_claw-free_ graphs with $\mathcal{H}=\left\\{K_{1,3}\right\\}$, where
$K_{k,\ell}$ denotes the complete bipartite graph with partite sets of size
$k$ and $\ell$,

  * •

_trivially-perfect_ graphs with $\mathcal{H}=\left\\{P_{4},C_{4}\right\\}$
[Gol78], where $C_{k}$ denotes the cycle on $k$ vertices,

  * •

_threshold_ graphs with
$\mathcal{H}=\left\\{P_{4},C_{4},\overline{C_{4}}\right\\}$ [CH73], where
$\overline{G}$ denotes the complement of $G$,

  * •

_split_ graphs with
$\mathcal{H}=\left\\{C_{4},\overline{C_{4}},C_{5}\right\\}$ [FH77], and

  * •

_line_ graphs, where $\mathcal{H}$ is a set of 9 graphs on at most 6 vertices
each [Bei70].

######  Theorem 7.

There are bounded-error quantum algorithms, which, for a graph on $n$ vertices
and integer $k$, determine whether there is a $k$-packing, $k$-partitioning,
or $k$-covering of $G$

  * •

with maximal independent sets, maximal cliques, or maximal bicliques in
$O(1.8554^{n})$ time,

  * •

with maximal cluster graphs or maximal triangle-free graphs in $O(1.9149^{n})$
time,

  * •

with maximal cographs, maximal claw-free graphs, maximal trivially-perfect
graphs, or maximal threshold graphs in $O(1.9365^{n})$ time,

  * •

with maximal split graphs in $O(1.9494^{n})$ time,

  * •

with maximal line graphs in $O(1.9579^{n})$ time, and

  * •

with maximal induced forests in $O(1.9629^{n})$ time.

There are bounded-error quantum algorithms, which, for a graph on $n$ vertices
and integer $k$, determine whether there is a $k$-packing or $k$-partitioning
of $G$

  * •

with maximal induced matchings in $O(1.8934^{n})$ time222Note that it is NP-
hard to determine, for a graph $G=(V,E)$ and vertex subset $X\subseteq V$,
whether there is a superset $Y\supseteq X$ that induces a 1-regular subgraph
of $G$. This can be seen by a simple reduction from Independent Set..

In particular, this leads to a bounded-error quantum algorithm computing the
chromatic number of an input graph in $O(1.8554^{n})$ time; a graph can be
covered with $k$ maximal independent sets iff it has chromatic number at most
$k$. In Section 7, we expedite this algorithm by exploiting fast algorithms
for coloring a graph with a small number of colors and this will enable us to
partition the vertex set in a more balanced way in the divide-and-conquer
steps.

Even though there is a simple branching algorithm that enumerates all minimal
dominating sets in $O(1.7159^{n})$ time [FGPS08], this algorithm cannot be
readily used for computing the domatic number using Theorem 4. This is because
when we consider a subset $X$ of the vertex set of $G=(V,E)$, we need to
enumerate vertex subsets from $X$ that are minimal dominating sets for $G$,
and not $G[X]$. In Section 8, we prove that such minimal dominating sets can
be enumerated in $O^{*}\left((2-\varepsilon)^{|X|}\right)$ time if $|X|$ is
linear in $|V|$.

##  7 Faster Computation of the Chromatic Number

Assume the vertex set of input graph $G=(V,E)$ can be partitioned into
independent sets $C=(I_{1},I_{2},\dots,I_{\chi})$ where $\chi$ is the
chromatic number of $G$. Denote by $n$ the number of vertices of $G$.

Using the algorithm from Theorem 4, we can compute the chromatic number of $G$
in $O(1.8554^{n})$ time. The family of subsets $\mathcal{F}$ corresponds to
the independent sets of $G$ and the family $e(X,r(\mathcal{F},X))$ corresponds
to the maximal independent sets of $G[X]$, which can be enumerated by a simple
branching algorithm $A$ in $O(3^{|X|/3})$ time [FK10]. We now prove a stronger
result.

######  Theorem 8.

There is a bounded-error quantum algorithm, which for a graph on $n$ vertices,
computes the chromatic number in $O(1.7956^{n})$ time.

Assume, w.l.o.g., that
$|I_{1}|\geq|I_{2}|\geq|I_{3}|\geq|I_{4}|\geq\dots\geq|I_{\chi}|$.

In the first step, we use the algorithm from Theorem 3 with $\alpha=0.27$ and
store the result in QRAM. That is, for each $\alpha$-small subset $X\subset
V$, we find the chromatic number of $X$ by finding the smallest $k$ such that
there exists a $k$-partition of $X$ into independent sets. This takes
$O^{*}(\binom{n}{0.27\cdot n})=O^{*}(1.79187^{n})$ time.

We then consider a few different possibilities for the large sets in $C$ and
present an algorithm which finds a partition into a smallest number of
independent sets for each of these cases. These possibilities cover all
configurations of $C$ so one result is guaranteed to find the chromatic number
by detecting the partition $C$ above, or an equivalent partition. The cases
are as follows:

  1. 1.

$G$ contains a vertex subset of size at least $0.48\cdot n$ that is the union
of at most five sets in $C$.

We check for $k$-coloring for all $1\leq k\leq n$ and take the minimum valid
value of $k$ as the chromatic number. To check for a certain $k$, we use
Grover’s search over all $Q\subset V$ where $|Q|\leq 0.52\cdot n$ and check
whether $G-Q$ is 5-colorable. If it is 5-colorable, we compute its chromatic
number by checking its $k^{\prime}$-colorability for $k^{\prime}<5$. We then
solve the instance $(Q,r(\mathcal{F},Q))$ to find a $k_{Q}$-coloring, where
$k_{Q}=k-\chi(G-Q)$, using Grover’s search to divide $Q$ into $(QL,QR)$ where
$|QL|\geq 0.27\cdot n$ and $k_{QL}+k_{QR}=k_{Q}$. For $(QL,r(\mathcal{F},QL))$
(and similarly for $QR$) we use Grover’s search on the branching algorithm $A$
to enumerate candidate sets $S_{1}\in e(QL,r(\mathcal{F},QL))$; if
$|QL|-|S_{1}|>0.27\cdot n$, then this branch is unsuccessful; otherwise, find
$\chi(QL\setminus S_{1})$ in QRAM.

The running time of this case with quantum 5-coloring in $O^{*}(1.4695^{n})$
[SM22] is

$\displaystyle\;O^{*}\left(\sum_{l=0}^{\lfloor 0.52\cdot
n\rfloor}\sqrt{\binom{n}{l}}\left(\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\sqrt{\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+1.4695^{n-l}\right)\right)$
$\displaystyle=$ $\displaystyle\;O^{*}\left(\sqrt{\sum_{l=0}^{\lfloor
0.52\cdot
n\rfloor}\binom{n}{l}\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+\sqrt{\sum_{l=\lceil
0.48\cdot n\rceil}^{n}\binom{n}{l}\left(1.4695^{l}\right)^{2}}\right)$
$\displaystyle=$ $\displaystyle\;O^{*}\left(\sqrt{\binom{n}{0.52\cdot
n}2.4423^{0.52\cdot n}}+\sqrt{(1+1.4695^{2})^{n}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(1.7831^{n}+1.7775^{n}\right)=O^{*}(1.7831^{n})$

  2. 2.

$G$ contains a vertex subset of size at least $0.48\cdot n$ that is the union
of six sets in $C$, but does not contain a vertex subset of size at least
$0.48\cdot n$ that is the union of at most five sets in $C$.

In this case we have

$\displaystyle|I_{1}|+|I_{2}|+\dots+|I_{5}|$ $\displaystyle<0.48\cdot n$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle 5\cdot|I_{6}|\leq
5\cdot|I_{5}|$ $\displaystyle<0.48\cdot n$ $\displaystyle\;\>\Longrightarrow$
$\displaystyle\;|I_{1}|+|I_{2}|+\dots+|I_{6}|$ $\displaystyle<0.576\cdot n,$

which, along with the condition $0.48\cdot n\leq|\bigcup_{i=1}^{6}I_{i}|$
gives

$\displaystyle 0.424\cdot n<|V\setminus\bigcup_{i=1}^{6}I_{i}|\leq 0.52\cdot
n.$

For this case we check for $k$-coloring for all $1\leq k\leq n$ and take the
minimum valid value of $k$ as the chromatic number. To check for a certain
$k$, we use Grover’s search over all $Q\subset V$ where $0.424\cdot n<|Q|\leq
0.52\cdot n$ and check whether $G-Q$ is 6-colorable. If so, we check whether
the instance $(Q,r(\mathcal{F},Q))$ is $(k-6)$-colorable in the same way as in
Case 1.

The running time of this case with quantum 6-coloring in $O^{*}(1.5261^{n})$
[SM22] is

$\displaystyle\;O^{*}\left(\sum_{l=\lceil 0.424\cdot n\rceil}^{\lfloor
0.52\cdot
n\rfloor}\sqrt{\binom{n}{l}}\left(\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\sqrt{\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+1.5261^{n-l}\right)\right)$
$\displaystyle=$ $\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil 0.424\cdot
n\rceil}^{\lfloor 0.52\cdot
n\rfloor}\binom{n}{l}\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+\sqrt{\sum_{l=\lceil
0.48\cdot n\rceil}^{\lfloor 0.576\cdot
n\rfloor}\binom{n}{l}\left(1.5261^{l}\right)^{2}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\binom{n}{0.52\cdot n}2.4423^{0.52\cdot
n}}+\sqrt{\binom{n}{0.576\cdot n}1.5261^{2\cdot 0.576\cdot n}}\right)$
$\displaystyle=$
$\displaystyle\;O^{*}\left(1.7831^{n}+1.7937^{n}\right)=O^{*}(1.7937^{n})$

  3. 3.

$G$ does not contain a vertex subset of size at least $0.48\cdot n$ that is
the union of at most six sets in $C$. That is
$|\bigcup_{i=1}^{6}I_{i}|<0.48\cdot n$.

Let $T=\bigcup_{i=1}^{q}I_{i}$ where $q$ is the maximum index such that
$|T|<\frac{n}{2}$. As $|\bigcup_{i=1}^{6}I_{i}|<0.48\cdot n$, we have $q\geq
6$. We consider two possibilities for the size of $T$ and present an algorithm
which finds a partition into a smallest number of independent sets for each
case. As a valid coloring is computed in each case, the smallest partition
gives the chromatic number if $|\bigcup_{i=1}^{6}I_{i}|<0.48\cdot n$.

    1. 3.1.

Consider the case where $|T|<\frac{6\cdot n}{13}$:

Let $L=\bigcup_{i=1}^{q+1}I_{i}$ and $R=\bigcup_{q+2}^{\chi}I_{i}$. We have

$\displaystyle|I_{1}|+|I_{2}|+\dots+|I_{q}|$ $\displaystyle<\frac{6\cdot
n}{13}$ $\displaystyle\;\>\Longrightarrow$ $\displaystyle 6\cdot|I_{q+1}|\leq
q\cdot|I_{q}|$ $\displaystyle<\frac{6\cdot n}{13}$
$\displaystyle\;\>\Longrightarrow$
$\displaystyle\;|I_{1}|+|I_{2}|+\dots+|I_{q+1}|$ $\displaystyle<\frac{7\cdot
n}{13}$ $\displaystyle\iff$ $\displaystyle|L|$ $\displaystyle<\frac{7\cdot
n}{13}$

and $0.5\cdot n\leq|L|$ from the definition of $q$.

Assume $L$ is not 7-colorable. There must be more than 7 independent set in
the construction of of $L$, which means

$\displaystyle q+1>7\iff q\geq 7$ $\displaystyle\;\>\Longrightarrow$
$\displaystyle 7\cdot|I_{q+1}|<\frac{6\cdot n}{13}$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle|L|<\frac{48\cdot n}{91}$

By contraposition, $|L|\geq\frac{48\cdot n}{91}$ implies that $L$ is
7-colorable.

######  Lemma 4.

After running the algorithm presented in Theorem 3, there exists a bounded-
error quantum algorithm to check the 7-colorability of a subset $X\subseteq U$
where $|X|\leq\frac{7}{3}\cdot\alpha\cdot n$ in $O^{*}(1.5622^{|X|})$ time.

###### Proof.

Assume that $X$ is 7-colorable and there is a partition
$D=(J_{1},J_{2},\dots,J_{7})$ of $X$ into independent sets. Assume, w.l.o.g.,
that $|J_{1}|\geq|J_{2}|\geq\dots\geq|J_{7}|$. Let $TL=J_{1}\cup J_{2}\cup
J_{3}$ and $TR=J_{4}\cup J_{5}\cup J_{6}\cup J_{7}$. We have

$\displaystyle\frac{|TL|}{3}\geq|J_{3}|\geq|J_{4}|\geq\frac{|TR|}{4}$
$\displaystyle\;\>\Longrightarrow$
$\displaystyle|TL|+\frac{4}{3}\cdot|TL|\geq|X|$ $\displaystyle\iff$
$\displaystyle|TL|\geq\frac{3}{7}\cdot|X|.$

Consider $TR\setminus J_{4}$,

$\displaystyle|TR|\leq\frac{4}{7}\cdot|X|\text{ and
}|J_{4}|\geq\frac{1}{4}\cdot|TR|$ $\displaystyle\;\>\Longrightarrow$
$\displaystyle|TR\setminus J_{4}|\leq\frac{3}{7}\cdot|X|\leq\alpha\cdot n.$

So there exists a subset $S_{1}\in e(TR,r(\mathcal{F},TR))$ such that
$|TR\setminus S_{1}|\leq\alpha\cdot n$.

We use Grover’s search to divide $X$ into two sets $(XL,XR)$ where
$|XL|\geq\frac{3\cdot|X|}{7}$. We check $XL$ for 3-colorability using a fast
quantum algorithm. If it is 3-colorable, we use Grover’s search on the
branching algorithm $A$ to enumerate candidate sets $S_{1}\in
e(XR,r(\mathcal{F},XR))$; if $|XR|-|S_{1}|>\alpha\cdot n$, then this branch is
unsuccessful; otherwise, check whether $\chi(XR\setminus S_{1})\leq 3$ in
QRAM. If $X$ is 7-colorable and $(XL,XR)=(TL,TR)$, we indeed detect
$7$-colorability.

The running time of this algorithm with quantum 3-coloring in
$O^{*}(1.1528^{n})$ time [Für08] is

$\displaystyle\;O^{*}\left(\sum_{l=\lceil\frac{3\cdot|X|}{7}\rceil}^{|X|}\sqrt{\binom{|X|}{l}}\left(1.1528^{l}+\sqrt{3^{(|X|-l)/3}}\right)\right)$
$\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil\frac{3\cdot|X|}{7}\rceil}^{|X|}\binom{|X|}{l}\left(1.1528^{l}\right)^{2}}+\sqrt{\sum_{l=0}^{\lfloor\frac{4\cdot|X|}{7}\rfloor}\binom{|X|}{l}1.4423^{l}}\right)$
$\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{(1+1.1528^{2})^{|X|}}+\sqrt{\binom{|X|}{\frac{4\cdot|X|}{7}}1.4423^{\frac{4\cdot|X|}{7}}}\right)$
$\displaystyle=$
$\displaystyle\;O^{*}(1.5261^{|X|}+1.5622^{|X|})=O^{*}(1.5622^{|X|})$

∎

We check for $k$-coloring for all $1\leq k\leq n$ and take the minimum valid
value of $k$ as the chromatic number. To check for a certain $k$, we use
Grover’s search to divide $V$ into two sets $(L,R)$ where $0.5\cdot
n\leq|L|<\frac{7\cdot n}{13}$ and $k$ into $k_{L}+k_{R}$. When
$|L|<\frac{48\cdot n}{91}$, we solve the subinstances $(L,r(\mathcal{F},L))$
and $(R,r(\mathcal{F},R))$ as in Theorem 4. When $|L|\geq\frac{48\cdot
n}{91}$, we solve the subinstance $(R,r(\mathcal{F},R))$ as in Theorem 4 and
run the algorithm in Lemma 4 on $L$; if $L$ isn’t 7-colorable, then this
branch is unsuccessful; otherwise the subinstance $(L,r(\mathcal{F},L))$ is
$k_{L}$-colorable for $k_{L}\geq 7$. This algorithm finds the chromatic number
of $G$ when $(L,R)$ are equal to the ones we constructed from $C$.

The running time of this algorithm is

$\displaystyle\;O^{*}\left(\sum_{l=\lceil 0.5\cdot
n\rceil}^{\lfloor\frac{7}{13}\cdot
n\rfloor}\sqrt{\binom{n}{l}}\left(\begin{cases}\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\sqrt{\binom{l}{l^{\prime}}3^{l^{\prime}/3}}&,\;l<\frac{48\cdot
n}{91}\\\ 1.5622^{l}&,\;l\geq\frac{48\cdot
n}{91}\end{cases}+\sum_{l^{\prime}=\lceil\frac{n-l}{2}\rceil}^{n-l}\sqrt{\binom{n-l}{l^{\prime}}3^{l^{\prime}/3}}\right)\right)$
$\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil\frac{6}{13}\cdot
n\rceil}^{\lfloor\frac{48}{91}\cdot
n\rfloor}\binom{n}{l}\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+\sqrt{\sum_{l=\lceil\frac{48}{91}\cdot
n\rceil}^{\lfloor\frac{7}{13}\cdot
n\rfloor}\binom{n}{l}\left(1.5622^{l}\right)^{2}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\binom{n}{\frac{48}{91}\cdot
n}2.4423^{\frac{48}{91}\cdot n}}+\sqrt{\binom{n}{\frac{7}{13}\cdot
n}1.5622^{2\cdot\frac{7}{13}\cdot n}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(1.7884^{n}+1.7956^{n}\right)=O^{*}(1.7956^{n})$

    2. 3.2.

Otherwise, consider the case where $\frac{6\cdot n}{13}\leq|T|<\frac{n}{2}$:

Let $L=T=\bigcup_{i=1}^{q}I_{i}$ and $R=\bigcup_{q+1}^{\chi}I_{i}$. We
partition $R$ into independent sets
$C^{\prime}=(I^{\prime}_{1},I^{\prime}_{2},\dots,I^{\prime}_{\chi^{\prime}})$
where $I^{\prime}_{i}=I_{q+i}$ for all $1\leq i\leq\chi^{\prime}$. By the
definition of $C$, this is an optimal partition of $R$. As $q\geq 6$, we get
$\frac{|L|}{6}\geq|I_{q}|\geq|I_{q+i}|=|I^{\prime}_{i}|$ for all $1\leq
i\leq\chi^{\prime}$.

######  Lemma 5.

Assume we have a partition $D=(J_{1},J_{2},\dots,J_{m})$ of a set $X$ where
$t\geq|J_{1}|\geq|J_{2}|\geq\dots\geq|J_{m}|$. Define
$p=\left\lceil\frac{|X|}{t}\right\rceil$ and $r=\frac{|X|}{p}$. For any non-
negative integer $a$, $1\leq a\leq p-2$, there exists an integer $k$ such that
$a\cdot r\leq|\bigcup_{i=1}^{k}J_{i}|\leq(a+1)\cdot r$.

###### Proof.

Let $k$ be the largest index such that $|\bigcup_{i=1}^{k}J_{i}|\leq(a+1)\cdot
r$. We will prove that $a\cdot r\leq|\bigcup_{i=1}^{k}J_{i}|$ and hence $k$
satisfies the constraints.

Assume that $|\bigcup_{i=1}^{k}J_{i}|<a\cdot r$. There are two cases:

      1. 1.

$k\geq a$. We have

$\displaystyle|J_{1}|+|J_{2}|+\dots+|J_{k}|$ $\displaystyle<a\cdot r$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle\;a\cdot|J_{k+1}|\leq
k\cdot|J_{k}|$ $\displaystyle<a\cdot r$ $\displaystyle\;\>\Longrightarrow$
$\displaystyle\;|J_{1}|+|J_{2}|+\dots+|J_{k+1}|$ $\displaystyle<a\cdot r+r$

which reaches a contradiction: $k$ is not the largest index such that
$|\bigcup_{i=1}^{k}J_{i}|\leq(a+1)\cdot r$.

      2. 2.

$k<a\implies k+1\leq a$. We have

$\displaystyle|\bigcup_{i=1}^{k+1}J_{i}|$ $\displaystyle>(a+1)\cdot r$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle\;(k+1)\cdot t$
$\displaystyle>(a+1)\cdot r$ $\displaystyle\;\>\Longrightarrow$ $\displaystyle
a\cdot t$ $\displaystyle>(a+1)\cdot r.$

From $p=\left\lceil\frac{|X|}{t}\right\rceil$,

$\displaystyle p-1$ $\displaystyle<\frac{|X|}{t}$ $\displaystyle\iff$
$\displaystyle\;(p-1)\cdot t$ $\displaystyle<|X|$ $\displaystyle\iff$
$\displaystyle(p-1)\cdot t$ $\displaystyle<p\cdot r.$

We also have

$\displaystyle a<p-1\text{ and
}t=\frac{|X|}{|X|\mathbin{/}t}\geq\frac{|X|}{\lceil|X|\mathbin{/}t\rceil}=r$
$\displaystyle\;\>\Longrightarrow$ $\displaystyle(a-(p-1))\cdot
t\leq(a-(p-1))\cdot r.$

Adding the last two results, we get

$\displaystyle a\cdot t$ $\displaystyle<(a+1)\cdot r$

which is a contradiction.

Therefore $a\cdot r\leq|\bigcup_{i=1}^{k}J_{i}|$ and the proof is complete. ∎

Let $T_{a}=\bigcup_{i=1}^{q^{\prime}}I^{\prime}_{i}$ and
$T_{b}=\bigcup_{i=1}^{q^{\prime}+1}I^{\prime}_{i}$ where $q^{\prime}$ is the
maximum index such that $|T_{a}|<\frac{|R|}{2}$. Note that
$\frac{|R|}{2}\leq|T_{b}|$. When we apply Lemma 5 with $X=R$, $D=C^{\prime}$
and $t=\frac{|L|}{6}$, we get

$\displaystyle\frac{|X|}{t}=\frac{6\cdot|R|}{|L|}\leq\frac{6\cdot\frac{7\cdot
n}{13}}{\frac{6\cdot n}{13}}$ $\displaystyle=7$
$\displaystyle\text{and\quad}\frac{6\cdot|R|}{|L|}>\frac{6\cdot\frac{n}{2}}{\frac{n}{2}}$
$\displaystyle=6$ $\displaystyle\;\>\Longrightarrow$ $\displaystyle
p=\left\lceil\frac{|X|}{t}\right\rceil$ $\displaystyle=7.$

If we let $a=3$, the lemma states that there exists a $k$ such that
$\frac{3\cdot|R|}{7}\leq|\bigcup_{i=1}^{k}I^{\prime}_{i}|\leq\frac{4\cdot|R|}{7}$.
As $q^{\prime}$ and $q^{\prime}+1$ differ by 1, it is not possible that
$|\bigcup_{i=1}^{q^{\prime}}I^{\prime}_{i}|<\frac{3\cdot|R|}{7}\leq|\bigcup_{i=1}^{k}I^{\prime}_{i}|\leq\frac{4\cdot|R|}{7}<|\bigcup_{i=1}^{q^{\prime}+1}I^{\prime}_{i}|$.
So, either $\frac{3\cdot|R|}{7}\leq|T_{a}|<\frac{|R|}{2}$ or
$\frac{|R|}{2}\leq|T_{b}|\leq\frac{4\cdot|R|}{7}$. We let $TL=T_{a}$ or
$TL=T_{b}$ such that $\frac{3\cdot|R|}{7}\leq|TL|\leq\frac{4\cdot|R|}{7}$ and
$TR=R\setminus TL$. Note that in both cases, removing the independent set
$I^{\prime}_{q^{\prime}+1}$ from either $TL$ or $TR$ would leave both subsets
with a size $\leq\frac{|R|}{2}$. Therefore, there exists a subset $S_{1}\in
e(TL,r(\mathcal{F},TL))$ (resp. for $TR$) such that $|TL\setminus
S_{1}|\leq\frac{|R|}{2}\leq 0.27$ (and similarly for $TR$).

We check for $k$-coloring for all $1\leq k\leq n$ and take the minimum valid
value of $k$ as the chromatic number. To check for a certain $k$, we use
Grover’s search to divide $V$ into two sets $(L,R)$ where $\frac{6\cdot
n}{13}\leq|L|<0.5\cdot n$ and $k$ into $k_{L}+k_{R}$. We solve the subinstance
$(L,r(\mathcal{F},L))$ as in Theorem 4. We also solve the subinstance
$(R,r(\mathcal{F},R))$ as in Theorem 4, except that $R$ is divided into
$(RL,RR)$ with $\frac{3\cdot|R|}{7}\leq|RL|\leq\frac{4\cdot|R|}{7}$ instead of
$|RL|>0.5\cdot|R|$. This algorithm finds the chromatic number of $G$ when
$(L,R)$ are equal to the ones we constructed from $C$ and $(RL,RR)=(TL,TR)$.

The running time of this algorithm is

$\displaystyle\;O^{*}\left(\sum_{l=\lceil\frac{6}{13}\cdot n\rceil}^{\lfloor
0.5\cdot
n\rfloor}\sqrt{\binom{n}{l}}\left(\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\sqrt{\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+\sum_{l^{\prime}=\lceil\frac{3\cdot(n-l)}{7}\rceil}^{\lfloor\frac{4\cdot(n-l)}{7}\rfloor}\sqrt{\binom{n-l}{l^{\prime}}3^{l^{\prime}/3}}\right)\right)$
$\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil\frac{6}{13}\cdot
n\rceil}^{\lfloor 0.5\cdot
n\rfloor}\binom{n}{l}\sum_{l^{\prime}=\lceil\frac{l}{2}\rceil}^{l}\binom{l}{l^{\prime}}3^{l^{\prime}/3}}+\sqrt{\sum_{l=\lceil
0.5\cdot n\rceil}^{\lfloor\frac{7}{13}\cdot
n\rfloor}\binom{n}{l}\sum_{l^{\prime}=\lceil\frac{3\cdot
l}{7}\rceil}^{\lfloor\frac{4\cdot
l}{7}\rfloor}\binom{l}{l^{\prime}}3^{l^{\prime}/3}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(\sqrt{\sum_{l=\lceil\frac{6}{13}\cdot
n\rceil}^{\lfloor 0.5\cdot
n\rfloor}\binom{n}{l}2.4423^{l}}+\sqrt{\sum_{l=\lceil 0.5\cdot
n\rceil}^{\lfloor\frac{7}{13}\cdot n\rfloor}\binom{n}{l}2.4405^{l}}\right)$
$\displaystyle=$ $\displaystyle\;O^{*}\left(\sqrt{\binom{n}{0.5\cdot
n}2.4423^{0.5\cdot n}}+\sqrt{\binom{n}{\frac{7}{13}\cdot
n}2.4405^{\frac{7}{13}\cdot n}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(1.7680^{n}+1.7956^{n}\right)=O^{*}(1.7956^{n})$

We observe that the overall running time of the algorithm is

$\displaystyle\;O^{*}\left(\sqrt{\binom{n}{\frac{7}{13}\cdot
n}\binom{\frac{7}{13}\cdot n}{\frac{4}{13}\cdot
n}3^{\frac{1}{3}\cdot\frac{4}{13}\cdot n}}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}\left(\left(\frac{\sqrt{13}}{2^{7/13}\cdot
3^{23/78}}\right)^{n}\right)$ $\displaystyle=$
$\displaystyle\;O^{*}(1.7956^{n})$

We reach this worst case when $\chi(G)=13$ and
$|I_{1}|=|I_{2}|=|I_{3}|=\dots=|I_{13}|$. An example of such a graph is the
disjoint union of $\frac{n}{13}$ complete graphs on 13 vertices. If the
universe is partitioned into 2, one part must have at least 7 independent sets
which is then partitioned into two parts where one part has at least 4
independent sets. Hence we cannot improve on the running time with a different
twice-partitioning strategy.

We also note that the current best known quantum algorithms for checking
13-colorability, 7-colorability and 4-colorability [SM22] do not improve our
running time. When iterating through $S_{1}\in(X,r(\mathcal{F},X))$, we only
need to consider $S_{1}$ with $|S_{1}|\geq|X|-\alpha\cdot n$ so we can use an
improved upper bound [Bys04] when we only need to consider
$|S_{1}|>|X|\mathbin{/}3$. However, this is only the case when
$|X|>\frac{3}{2}\cdot\alpha\cdot n$; so it does not affect our overall running
time as $|X|=\frac{4}{13}\cdot n$ in the worst case.

The pseudocode for the algorithm in this section can be found in Appendix B.

##  8 Enumeration of Minimal Subset Dominating Sets

In this section, we prove that the number of minimal dominating sets of a
graph that are subsets of some linear-sized subset of vertices $X$ is at most
$O^{*}\left((2-\varepsilon)^{|X|}\right)$. Moreover, they can be enumerated by
a simple branching algorithm whose running time is within a polynomial factor
of this bound.

######  Theorem 9.

There is a simple branching algorithm, which, given any graph $G=(V,E)$ and
any subset of vertices $X\subseteq V$ with $|X|\geq d\cdot|V|$ for some $d>0$,
enumerates all minimal dominating sets of $G$ that are subsets of $X$ in
$O^{*}\left((2-\varepsilon_{d})^{|X|}\right)$ time, for some
$\varepsilon_{d}>0$.

The theorem will follow from a slightly more general theorem about minimal set
covers of a set system. From a graph $G=(V,E)$ and a vertex subset $X\subseteq
V$, we obtain a set system $(U,\mathcal{F})$ where $U=V$ and a set
$S_{x}\in\mathcal{F}$ for each $x\in X$ that contains the closed neighborhood
of vertex $x$ in the graph $G$: $S_{x}=N_{G}[x]$. Then, there is a 1-to-1
correspondence between inclusion-wise minimal dominating sets in $G$ that are
subsets of $X$ and inclusion-wise minimal set covers of $(U,\mathcal{F})$.

######  Theorem 10.

There is a simple branching algorithm, which, given any set system
$(U,\mathcal{F})$ with $|U|\leq r\cdot|\mathcal{F}|$ for some $r>0$,
enumerates all minimal set covers of $(U,\mathcal{F})$ in
$O^{*}\left(2^{(1-\varepsilon_{r})\cdot|\mathcal{F}|}\right)$ time, for some
$\varepsilon_{r}>0$.

[FGPS08] proved Theorem 9 for $X=V$ and Theorem 10 for $r=1$. In particular,
their algorithm enumerates all minimal dominating sets of a graph on $n$
vertices in $O(1.7159^{n})$ time.

###### Proof.

Let $r>0$. Let $\varepsilon=\frac{3(r+1)-\log(2^{3(r+1)}-1)}{3(r+1)^{2}}$.
Consider the measure

$\displaystyle\mu(U,\mathcal{F})=(1-(r+1)\varepsilon)|\mathcal{F}|+\varepsilon|U|$

which associates a weight of $1-(r+1)\varepsilon>0$ to each set and a weight
of $\varepsilon>0$ to each element of a set system $(U,\mathcal{F})$. We will
show that every set system $(U,\mathcal{F})$ has at most
$2^{\mu(U,\mathcal{F})}$ minimal set covers by induction on $|\mathcal{F}|$.
For a set system with $|U|\leq r\cdot|\mathcal{F}|$, this number is
$2^{(1-(r+1)\varepsilon)|\mathcal{F}|+\varepsilon|U|}\leq
2^{(1-\varepsilon)\cdot|\mathcal{F}|}$. The proof can easily be turned into a
simple branching algorithm enumerating all minimal set covers whose search
tree is the induction tree of this proof.

The statement trivially holds when $|\mathcal{F}|=0$ since such an instance
has at most $1$ minimal set cover. For the induction, we consider three cases.

  1. 1.

$\mathcal{F}$ contains a set $S$ with $|S|\geq 3(r+1)$. Any minimal set cover
either contains $S$ or not. Those that do not contain $S$ are also minimal set
covers of $(U,\mathcal{F}\setminus\\{S\\})$ and those that contain $S$ are
made up of $S$ and a minimal set cover of $(U\setminus
S,\mathcal{F}\setminus\\{S\\})$. For the induction, we would like that

$\displaystyle 2^{\mu(U,\mathcal{F}\setminus\\{S\\})}+2^{\mu(U\setminus
S,\mathcal{F}\setminus\\{S\\})}$ $\displaystyle\leq 2^{\mu(U,\mathcal{F})}$
$\displaystyle\iff$ $\displaystyle
2^{\mu(U,\mathcal{F})-(1-(r+1)\varepsilon)}+2^{\mu(U,\mathcal{F})-(1-(r+1)\varepsilon)-|S|\cdot\varepsilon}$
$\displaystyle\leq 2^{\mu(U,\mathcal{F})}$ $\displaystyle\iff$ $\displaystyle
2^{-1+(r+1)\varepsilon}+2^{-1+(r+1)\varepsilon-|S|\cdot\varepsilon}$
$\displaystyle\leq 1$ $\displaystyle\;\Longleftarrow\;$ $\displaystyle
2^{-1+(r+1)\varepsilon}+2^{-1-2(r+1)\varepsilon}$ $\displaystyle\leq 1,$

and this inequality holds because
$\varepsilon\leq\frac{1}{r+1}\log\left(\frac{1+\sqrt{5}}{2}\right)$.

  2. 2.

There is an element $u\in U$ with frequency at most $3(r+1)$, i.e., $u$ occurs
in at most $3(r+1)$ sets of $\mathcal{F}$. Denote the sets that contain $u$ by
$\mathcal{S}=\\{S\in\mathcal{F}:u\in S\\}$. Since $u$ needs to be covered,
each set cover contains at least one set from $\mathcal{S}$. We use induction
on all $2^{|\mathcal{S}|}-1$ choices of including at least one set from
$\mathcal{S}$ into the set covers and excluding the remaining sets from
$\mathcal{S}$; each such choice leads to a set cover instance where we remove
all sets in $\mathcal{S}$, and we remove all elements covered by the sets that
are included in the set covers. Each such choice reduces the measure $\mu$ by
more than $|\mathcal{S}|\cdot(1-(r+1)\varepsilon)$. Now, we would therefore
like that

$\displaystyle(2^{|\mathcal{S}|}-1)\cdot
2^{\mu(U,\mathcal{F})-|\mathcal{S}|\cdot(1-(r+1)\varepsilon)}$
$\displaystyle\leq 2^{\mu(U,\mathcal{F})}$ $\displaystyle\iff$
$\displaystyle(2^{|\mathcal{S}|}-1)\cdot
2^{-|\mathcal{S}|\cdot(1-(r+1)\varepsilon)}$ $\displaystyle\leq 1$
$\displaystyle\iff$ $\displaystyle
2^{-|\mathcal{S}|\cdot(1-(r+1)\varepsilon)}$
$\displaystyle\leq(2^{|\mathcal{S}|}-1)^{-1}$ $\displaystyle\iff$
$\displaystyle-|\mathcal{S}|\cdot(1-(r+1)\varepsilon)$
$\displaystyle\leq-\log(2^{|\mathcal{S}|}-1)$ $\displaystyle\iff$
$\displaystyle(r+1)\varepsilon-1$
$\displaystyle\leq\frac{-\log(2^{|\mathcal{S}|}-1)}{|\mathcal{S}|}$
$\displaystyle\iff$ $\displaystyle\varepsilon$
$\displaystyle\leq\frac{|\mathcal{S}|-\log(2^{|\mathcal{S}|}-1)}{(r+1)|\mathcal{S}|}$

Note that $\frac{|\mathcal{S}|-\log(2^{|\mathcal{S}|}-1)}{(r+1)|\mathcal{S}|}$
decreases when $|\mathcal{S}|$ increases, and for the maximum possible value
of $|\mathcal{S}|$, which is $3(r+1)$, the inequality holds with equality for
the value of $\varepsilon$ given in the beginning of the proof.

  3. 3.

It remains to consider the case where all sets have size less than $3(r+1)$
and all elements have frequency more than $3(r+1)$. Since the sum of set sizes
equals the sum of element frequencies, we have that $|\mathcal{F}|\geq|U|$.
Here, we use the result of Fomin et al. [FGPS08] who proved that the number of
minimal set covers is at most $1.7159^{|\mathcal{F}|}$. For the induction, we
would like that

$\displaystyle 1.7159^{|\mathcal{F}|}$ $\displaystyle\leq
2^{\mu(U,\mathcal{F})}$ $\displaystyle\iff$ $\displaystyle
2^{|\mathcal{F}|\log 1.7159}$ $\displaystyle\leq
2^{(1-(r+1)\varepsilon)|\mathcal{F}|+\varepsilon|U|}$
$\displaystyle\;\Longleftarrow\;$ $\displaystyle 0.779|\mathcal{F}|$
$\displaystyle\leq(1-(r+1)\varepsilon)|\mathcal{F}|$ $\displaystyle\iff$
$\displaystyle\varepsilon\leq\frac{0.221}{r+1}$

and this inequality holds for the value of $\varepsilon$ given in the
beginning of the proof.

This concludes the proof of the theorem. ∎

Theorem 4 now lets us conclude the following.

######  Corollary 2.

There is a bounded-error quantum algorithm which computes the domatic number
of any graph on $n$ vertices in $O((2-\varepsilon)^{n})$ time for some
constant $\varepsilon>0$.

##  Appendix A A closer look at the running time for small $c$

$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$1.12$$1.13$$1.14$$1.15$$1.725$$1.730$$1.735$$1.740$$1.745$$1.750$$1.755$$1.760$$1.765$$1.770$$1.775$$c$Base
$b$ of running time $O^{*}(b^{n})$Running time for various values of
$c$$(2+c)^{n/2}$Theorem 5Theorem 6 Figure 1:  Visual presentation of running
times of Theorem 5 and Theorem 6.

When
$c<-\frac{2}{3}+\sqrt[3]{\frac{47}{54}-\frac{\sqrt{93}}{18}}+\sqrt[3]{\frac{47}{54}+\frac{\sqrt{93}}{18}}\approx
1.147899$, then choosing the best algorithm among Theorem 5 and Theorem 6
gives an algorithm running in $O^{*}(b^{n})$ time for some $b<\sqrt{c+2}$.
This can be seen visually in Figure 1 and proved rigorously, e.g., by
interleaving a stepwise function between the function $(c+2)^{n/2}$ and the
function from Theorem 6 when $c\leq 1.08$:

$\displaystyle\mathsf{steps}(c,n)$
$\displaystyle=\begin{cases}3^{n/2}&\text{if }c\leq 1.0123\\\
1.735595^{n}&\text{if }1.0123\leq c\leq 1.0221\\\ \dots\\\ 1.7533^{n}&\text{if
}1.0742\leq c\leq 1.08.\end{cases}$

When $1.08\leq c\leq 1.147899$, then Theorem 5 gives an algorithm with running
time $O^{*}(d^{n})$ for some $d<\sqrt{c+2}$.

##  Appendix B Pseudocode

Algorithm 1 Preprocessing for computing the chromatic number of $G$

1:function Precomp($G=(V,E)$)

2: $a[\emptyset],\chi[\emptyset]\leftarrow 0$

3: for $S\subseteq V$, $|S|\leq\lfloor 0.27\cdot n\rfloor$ do ($S$ is earlier
than $S^{\prime}$ if $S\subset S^{\prime}$)

4: if $S\neq\emptyset$ then

5: $v\leftarrow$ arbitrary vertex of $S$

6: $a[S]\leftarrow a[S\setminus\\{v\\}]+a[S\setminus N[v]]+1$ $\triangleright$
Number of independent sets in $S$

7: end if

8: end for

9: for $k=\lfloor 0.27\cdot n\rfloor,\lfloor 0.27\cdot n\rfloor-1,\ldots,1$ do

10: for $S\subseteq V$, $|S|\leq\lfloor 0.27\cdot n\rfloor$ do

11: $g_{0}[S]\leftarrow(-1)^{|S|}(a[S])^{k}$

12: end for

13: for $i=1,2,\ldots,n$ do

14: for $S\subseteq V$, $|S|\leq\lfloor 0.27\cdot n\rfloor$ do

15: if $v_{i}\in S$ then

16: $g_{i}[S]=g_{i-1}[S]+g_{i-1}[X\setminus\\{v_{i}\\}]$

17: else

18: $g_{i}[S]=g_{i-1}[S]$

19: end if

20: end for

21: end for

22: for $S\subseteq V$, $|S|\leq\lfloor 0.27\cdot n\rfloor$ do

23: if $(-1)^{|S|}g_{n}[S]>0$ then $\triangleright$ Number of $k$-covers of
$S$

24: $\chi[S]\leftarrow k$ $\triangleright$ Chromatic number of $S$

25: end if

26: end for

27: end for

28:end function

In this section, we present the pseudocode for Chromatic number algorithm of
Section 7. As checking for a $k$-partitioning of independent subsets is
equivalent to checking for a $k$-covering of maximal independent subsets, we
can use the algorithm for computing $c_{k}(\mathcal{F},X)$ in Theorem 3. As
the downward closure of the set of maximal independent subsets are independent
subsets, we can adapt the preprocessing to directly compute the number of
independent subsets of a set $X$.

In Algorithm 1, the input is the graph $G=(V,E)$ with vertex set
$V=\left\\{v_{1},\dots,v_{n}\right\\}$.

We now present the main portion of the algorithm in Algorithm 2. Grover’s
search is used to quadratically speed up the branching and is applied to every
for loop. Here, instead of iteratively updating $c$, all values $1\leq c\leq
n$ are considered and $c$ is set to the minimum possible. In Col, we use fast
quantum $k$-coloring algorithms presented in [Für08, SM22].

Algorithm 2 Main algorithm for computing the chromatic number of $G$

1:function Main($G$)

2: Precomp$(G)$

3: $c\leftarrow|V|$

4: for $S\subseteq V$, $0.48\cdot n\leq|S|$ do $\triangleright$ Case 1

5: if Col$(5,\,S)$ then

6:
$k\leftarrow\min_{x\in\left\\{1,2,3,4,5\right\\}}\left\\{\textsc{Col}(x,\,S)\right\\}$

7: $c\leftarrow\min\\{c,\,k+\textsc{Chr1a}(V\setminus S)\\}$

8: end if

9: end for

10: for $S\subseteq V$, $0.48\cdot n\leq|S|<0.576\cdot n$ do $\triangleright$
Case 2

11: if Col$(6,\,S)$ then

12: $c\leftarrow\min\\{c,\,6+\textsc{Chr1a}(V\setminus S)\\}$

13: end if

14: end for

15: for $S\subseteq V$, $0.5\cdot n\leq|S|<\frac{7\cdot n}{13}$ do
$\triangleright$ Case 33.1.

16: if $|S|<\frac{48\cdot n}{91}$ then

17: $c\leftarrow\min\\{c,\,\textsc{Chr1a}(S)+\textsc{Chr1a}(V\setminus S)\\}$

18: else

19: $c\leftarrow\min\\{c,\,\textsc{7Col}(S)+\textsc{Chr1a}(V\setminus S)\\}$

20: end if

21: end for

22: for $S\subseteq V$, $\frac{6\cdot n}{13}\leq|S|<0.5$ do $\triangleright$
Case 33.2.

23: $c\leftarrow\min\\{c,\,\textsc{Chr1a}(S)+\textsc{Chr1b}(V\setminus S)\\}$

24: end for

25: return $c$

26:end function

27:

28:function Col($k$, $S$)

29: return $k$-colorability of $S$ using [Für08, SM22]

30:end function

We now present the implementation for Chr1a, Chr1b and 7Col in Algorithm 3.
Similarly to above, Grover’s search is used to quadratically speed up the
branching and is applied to every for loop. In Chr2, Grover’s search is
applied to a classical branching algorithm that enumerates the maximal
independent sets of $G[S]$ in $O^{*}(3^{1/3})$ [FK10].

Algorithm 3 Implementations of Chr1a, Chr1b and 7Col

1:function Chr1a($S$)

2: $c\leftarrow|S|$

3: for $T\subseteq S$, $\frac{|S|}{2}\leq|T|$ do

4: $c\leftarrow\min\\{c,\textsc{Chr2}(T)+\textsc{Chr2}(S\setminus T)\\}$

5: end for

6: return $c$

7:end function

8:

9:function Chr1b($S$) $\triangleright$ Algorithm used for
$(R,r(\mathcal{F},R))$ in Case 33.2.

10: $c\leftarrow|S|$

11: for $T\subseteq S$, $\frac{3\cdot|S|}{7}\leq|T|\leq\frac{|4|\cdot|S|}{7}$
do

12: $c\leftarrow\min\\{c,\textsc{Chr2}(T)+\textsc{Chr2}(S\setminus T)\\}$

13: end for

14: return $c$

15:end function

16:

17:function 7Col($S$) $\triangleright$ Algorithm presented in Lemma 4

18: for $T\subseteq S$, $\frac{3\cdot|S|}{7}\leq|T|$ do

19: if Col$(3,\,T)$ and Chr2$(S\setminus T)\leq 4$ then

20: return $7$

21: end if

22: end for

23: return $|S|$

24:end function

25:

26:function Chr2($S$)

27: $c\leftarrow|S|$

28: for $T\in\textsc{Mis}(G[S])$, $|S\setminus T|\leq\lfloor 0.27\cdot
n\rfloor$ do

29: $c\leftarrow\min\\{c,1+\chi[S\setminus T]\\}$

30: end for

31: return $c$

32:end function

## References

  * [ABI+19] Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs.  Quantum speedups for exponential-time dynamic programming algorithms.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1783–1793. SIAM, 2019.  doi:10.1137/1.9781611975482.107.
  * [AK17] Andris Ambainis and Martins Kokainis.  Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 989–1002. ACM, 2017.  doi:10.1145/3055399.3055444.
  * [BBHT98] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998.  doi:10.1002/(SICI)1521-3978(199806)46:4/5\%3C493::AID-PROP493\%3E3.0.CO;2-P.
  * [Bei70] Lowell W. Beineke.  Characterizations of derived graphs.  Journal of Combinatorial Theory, Series B, 9:129–135, 1970.  doi:10.1016/S0021-9800(70)80019-9.
  * [BH06] Andreas Björklund and Thore Husfeldt.  Inclusion–exclusion algorithms for counting set partitions.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 575–582. IEEE Computer Society, 2006.  doi:10.1109/FOCS.2006.41.
  * [BHK09] Andreas Björklund, Thore Husfeldt, and Mikko Koivisto.  Set partitioning via inclusion-exclusion.  SIAM Journal on Computing, 39(2):546–563, 2009.  doi:10.1137/070683933.
  * [BHKK07] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Fourier meets möbius: fast subset convolution.  In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pages 67–74. ACM, 2007.  doi:10.1145/1250790.1250801.
  * [BHKK11] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Covering and packing in linear space.  Information Processing Letters, 111(21-22):1033–1036, 2011.  doi:10.1016/J.IPL.2011.08.002.
  * [Bys04] Jesper Makholm Byskov.  Enumerating maximal independent sets with applications to graph colouring.  Operations Research Letters, 32(6):547–556, 2004.  doi:10.1016/j.orl.2004.03.002.
  * [CH73] V. Chvátal and P. L. Hammer.  Set-packing problem and threshold graphs.  Technical report, University of Waterloo Research Report, 1973.  CORR 73-21.
  * [CLB81] D. G. Corneil, H. Lerchs, and L. Stewart Burlingham.  Complement reducible graphs.  Discrete Applied Mathematics, 3(3):163–174, 1981.  doi:10.1016/0166-218X(81)90013-5.
  * [DH96] Christoph Dürr and Peter Høyer.  A quantum algorithm for finding the minimum.  CoRR, quant-ph/9607014, 1996.  URL: http://arxiv.org/abs/quant-ph/9607014.
  * [FGLS19] Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh.  Exact algorithms via monotone local search.  Journal of the ACM, 66(2):8:1–8:23, 2019.  doi:10.1145/3284176.
  * [FGPS08] Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov.  Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.  ACM Transactions on Algorithms, 5(1):9:1–9:17, 2008.  doi:10.1145/1435375.1435384.
  * [FH77] Stephan Földes and Peter L. Hammer.  Split graphs.  In Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 311–315, 1977.
  * [FK10] Fedor V. Fomin and Dieter Kratsch.  Exact Exponential Algorithms.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010\.  doi:10.1007/978-3-642-16533-7.
  * [Für08] Martin Fürer.  Solving NP-complete problems with quantum search.  In Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN 2008), volume 4957 of Lecture Notes in Computer Science, pages 784–792. Springer, 2008.  doi:10.1007/978-3-540-78773-0_67.
  * [GL17] Serge Gaspers and Edward J. Lee.  Exact algorithms via multivariate subroutines.  In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of LIPIcs, pages 69:1–69:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.69.
  * [Gol78] Martin C. Golumbic.  Trivially perfect graphs.  Discrete Mathematics, 24(1):105–107, 1978.  doi:10.1016/0012-365X(78)90178-4.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Gary L. Miller, editor, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), pages 212–219. ACM, 1996\.  doi:10.1145/237814.237866.
  * [GRS12] Sushmita Gupta, Venkatesh Raman, and Saket Saurabh.  Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds.  SIAM Journal on Discrete Mathematics, 26(4):1758–1780, 2012.  doi:10.1137/09077850X.
  * [JYP88] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou.  On generating all maximal independent sets.  Information Processing Letters, 27(3):119–123, 1988.  doi:10.1016/0020-0190(88)90065-8.
  * [Koi06] Mikko Koivisto.  An $O^{*}(2^{n})$ algorithm for graph coloring and other partitioning problems via inclusion–exclusion.  In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 583–590. IEEE Computer Society, 2006.  doi:10.1109/FOCS.2006.11.
  * [SM22] Kazuya Shimizu and Ryuhei Mori.  Exponential-time quantum algorithms for graph coloring problems.  Algorithmica, 84(12):3603–3621, 2022.  doi:10.1007/S00453-022-00976-2.
  * [Yat37] F. Yates.  The design and analysis of factorial experiments.  Imperial Bureau of Soil Science, Harpenden, England, Technical Communication No. 35, 1937.