University of Bremen<EMAIL_ADDRESS>University of Bremen,
Germanysiebertz@uni-bremen.dehttps://orcid.org/0000-0002-6347-1198 University
of Bremen, Germanyvigny@uni-bremen.dehttps://orcid.org/0000-0002-4298-8876
Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny [500]Theory of computation
Graph algorithms analysis

# Distributed domination on graph classes with bounded expansion

Simeon Kublenz  Sebastian Siebertz  Alexandre Vigny

###### Abstract

We show that the dominating set problem admits a constant factor approximation
in a constant number of rounds in the LOCAL model of distributed computing on
graph classes with bounded expansion. This generalizes a result of Czygrinow
et al. for graphs with excluded topological minors.

###### keywords:

Dominating set, LOCAL algorithm, Bounded expansion graph classes.

##  1 Introduction

A dominating set in an undirected and simple graph $G$ is a set $D\subseteq
V(G)$ such that every vertex $v\in V(G)$ either belongs to $D$ or has a
neighbor in $D$. The Minimum Dominating Set problem takes as input a graph $G$
and the objective is to find a minimum size dominating set of $G$. The
decision problem whether a graph admits a dominating set of size $k$ is NP-
hard [22] and this even holds in very restricted settings, e.g. on planar
graphs of maximum degree $3$ [17].

Consequently, attention shifted from computing exact solutions to
approximating near optimal dominating sets. The simple greedy algorithm
computes an $\ln n$ approximation (where $n$ is number of vertices of the
input graph) of a minimum dominating set [20, 28], and for general graphs this
algorithm is near optimal – it is NP-hard to approximate minimum dominating
sets within factor $(1-\epsilon)\ln n$ for every $\epsilon>0$ [10].

Therefore, researchers tried to identify restricted graph classes where better
approximation are possible. The problem admits a PTAS on classes with
subexponential expansion [18]. Here, expansion refers to the edge density of
bounded depth minors and we will discuss the concept in detail below.
Important examples of classes with subexponential expansion include the class
of planar graphs and more generally classes that exclude some fixed graph as a
minor. The dominating set problem admits a constant factor approximation on
classes of bounded degeneracy (equivalently, of bounded arboricity) [5, 27]
and an $\mathcal{O}(\ln\gamma)$ approximation (where $\gamma$ denotes the size
of a minimum dominating set) on classes of bounded VC-dimension [7, 14]. In
fact, the greedy algorithm can be modified to yield a constant factor
approximation on graphs with bounded degeneracy [21] and an
$\mathcal{O}(\ln\gamma)$ approximation on biclique-free graphs (graphs that
exclude some fixed complete bipartite graph $K_{t,t}$ as a subgraph) [31].
However, it is unlikely that polynomial-time constant factor approximations
exist even on $K_{3,3}$-free graphs [31]. The general goal in this line of
research is to identify the broadest graph classes on which the dominating set
problem (or other important problems that are hard on general graphs) can be
approximated efficiently with a certain guarantee on the approximation factor.
These limits of tractability are often captured by abstract notions, such as
expansion, degeneracy or VC-dimension of graph classes.

In this paper we study the distributed time complexity of finding dominating
sets in the classic LOCAL model of distributed computing, which can be traced
back at least to the seminal work of Gallager, Humblet and Spira [16]. In this
model, a distributed system is modeled by an undirected (connected) graph $G$,
in which every vertex represents a computational entity of the network and
every edge represents a bidirectional communication channel. The vertices are
equipped with unique identifiers. In a distributed algorithm, initially, the
nodes have no knowledge about the network graph. They must then communicate
and coordinate their actions by passing messages to one another in order to
achieve a common goal, in our case, to compute a dominating set of the network
graph. The LOCAL model focuses on the aspects of communication complexity and
therefore the main measure for the efficiency of a distributed algorithm is
the number of communication rounds it needs until it returns its answer.

Kuhn et al. [24] proved that in $r$ rounds on an $n$-vertex graphs of maximum
degree $\Delta$ one can approximate minimum dominating sets only within a
factor $\Omega(n^{c/r^{2}}/r)$ and $\Omega(\Delta^{1/(r+1)}/r)$, respectively,
where $c$ is a constant. This implies that, in general, to achieve a constant
approximation ratio, we need at least $\Omega(\sqrt{\log n/\log\log n})$ and
$\Omega(\log\Delta/\log\log\Delta)$ communication rounds, respectively. Kuhn
et al. [24] also presented a $(1+\epsilon)\ln\Delta$-approximation in that
runs in $\mathcal{O}(\log(n)/\epsilon)$ rounds for any $\epsilon>0$, Barenboim
et al. [6] presented a deterministic $\mathcal{O}((\log n)^{k-1})$-time
algorithm that provides an $\mathcal{O}(n^{1/k})$-approximation, for any
integer parameter $k\geq 2$.

For graphs of degeneracy $a$ (equivalent to arboricity up to factor $2$),
Lenzen and Wattenhofer [27] provided an algorithm that achieves a factor
$\mathcal{O}(a^{2})$ approximation in randomized time $\mathcal{O}(\log n)$,
and a deterministic $\mathcal{O}(a\log\Delta)$ approximation algorithm with
$\mathcal{O}(\log\Delta)$ rounds. Graphs of bounded degeneracy include all
graphs that exclude a fixed graph as a (topological) minor and in particular,
all planar graphs and any class of bounded genus.

Amiri et al. [1] provided a deterministic $\mathcal{O}(\log n)$ time constant
factor approximation algorithm on classes of bounded expansion (which extends
also to connected dominating sets). Czygrinow et al. [8] showed that for any
given $\epsilon>0$, $(1+\epsilon)$-approximations of a maximum independent
set, a maximum matching, and a minimum dominating set, can be computed in
$\mathcal{O}(\log^{*}n)$ rounds in planar graphs, which is asymptotically
optimal [26].

Lenzen et al. [25] proposed a constant factor approximation on planar graphs
that can be computed in a constant number of communication rounds, see also
[33] for a finer analysis of the approximation factor. Wawrzyniak [32] showed
that message sizes of $\mathcal{O}(\log n)$ suffice to give a constant factor
approximation on planar graphs in a constant number of rounds. In terms of
lower bounds, Hilke et al. [19] showed that there is no deterministic local
algorithm (constant-time distributed graph algorithm) that finds a
$(7-\epsilon)$-approximation of a minimum dominating set on planar graphs, for
any positive constant $\epsilon$.

The results for planar graphs were gradually extended to classes with bounded
genus [2, 3], classes with sublogarithmic expansion [4] and eventually by
Czygrinow et al. [9] to classes with excluded topological minors. Again, one
of the main goals in this line of research is to find the most general graph
classes on which the dominating set problem admits a constant factor
approximation in a constant number of rounds.

bounded degreeexcludedtopologicalminorbounded expansionbounded
degeneracyplanarbounded genusexcluded minor Figure 1: Inclusion diagram of the
mentioned graph classes.

We take a step towards this goal and generalize the result of Czygrinow et al.
[9] to classes of bounded expansion. The notion of bounded expansion was
introduced by Nešetřil and Ossona de Mendez [29] and offers an abstract
definition of uniform sparseness in graphs. It is based on bounding the
density of shallow minors. Intuitively, while a minor is obtained by
contracting arbitrary connected subgraphs of a graph to new vertices, in an
$r$-shallow minor we are only allowed to contract connected subgraphs of
radius at most $r$.

A class of graphs has bounded expansion if for every radius $r$ the set of all
$r$-shallow minors has edge density bounded by a constant depending only on
$r$. We write $\nabla_{r}(G)$ for the maximal edge density of an $r$-shallow
minor of a graph $G$. Of course, every class $\mathscr{C}$ that excludes a
fixed graph $H$ as a minor has bounded expansion. For such classes there
exists an absolute constant $c$ such that for all $G\in\mathscr{C}$ and all
$r$ we have $\nabla_{r}(G)\leq c$. Special cases are the class of planar
graphs, every class of graphs that can be drawn with a bounded number of
crossings, see [30], and every class of graphs that embeds into a fixed
surface. Every class of intersection graphs of low density objects in low
dimensional Euclidean space has polynomial expansion [18], that is, the
function $\nabla_{r}$ is bounded polynomially in $r$ on $\mathscr{C}$. Also
every class $\mathscr{C}$ that excludes a fixed graph $H$ as a topological
minor has bounded expansion. Again, for such classes there exists an absolute
constant $c$ such that for all $G\in\mathscr{C}$ and all $r$ we have
$\nabla_{r}(G)\leq c$. Important special cases are classes of bounded degree
and classes of graphs that can be drawn with a linear number of crossings, see
[30]. Further examples include classes that can be drawn with a bounded number
of crossings per edge [30], classes with bounded queue-number, bounded stack-
number or bounded non-repetitive chromatic number [30] and the class of Erdös-
Rényi random graphs with constant average degree $d/n$, $G(n,d/n)$, has
asymptotically almost surely bounded expansion [30].

Hence, classes of bounded expansion are much more general than classes
excluding a topological minor. On the other hand, maybe not surprisingly, when
performing local computations, it is not properties of minors or topological
minors, but rather of shallow minors that allow the necessary combinatorial
arguments in the algorithms. This observation was already made in the study of
the kernelization complexity of dominating set on classes of sparse graphs
[11, 12, 13, 15, 23]. On the other hand, degenerate classes are those classes
where only $\nabla_{0}(G)$ is bounded. These classes are hence more general
than classes of bounded expansion.

The algorithm of Czygrinow et al. [9] is based on an quite complicated
iterative process of choosing dominating vertices from so called _pseudo-
covers_. Based on the fact that classes with excluded topological minors in
particular exclude some complete bipartite graph $K_{t,t}$ as a subgraph it is
proved that this iterative process terminates after at most $t$ rounds and
produces a good approximation of a minimum dominating set.

In this paper we make three contributions. First, we simplify the arguments
used by Czygrinow et al. and give a much more accessible description of their
algorithm. Second, we identify the property that $\nabla_{1}(G)$ is bounded by
a constant as the key property that makes the algorithm work. Classes with
only this restriction are even more general than bounded expansion classes,
hence, we generalize the algorithm to the most general classes on which it
(and similar approaches based on covers or pseudo-covers) can work. We
demonstrate that the pseudo-covering method cannot be extended e.g. to classes
of bounded degeneracy. Finally, Czygrinow et al. explicitly stated that they
did not aim to optimize any constants, and as presented, the constants in
their construction are enormous. We optimize the bounds that arise in the
algorithm in terms of $\nabla_{1}(G)$. Even though the constants are still
large, they are by magnitudes smaller than those in the original presentation.

The main open question that remains in this line of research is whether we can
compute constant factor approximations of minimum dominating sets in a
constant number of rounds in classes of bounded degeneracy.

##  2 Preliminaries

In this section we fix our notation and prove some basic lemmas required for
the algorithm. We use standard notation from graph theory and refer to the
literature for extensive background. For an undirected and simple graph $G$ we
denote by $V(G)$ the vertex set and by $E(G)$ the edge set of $G$. We also
refer to the literature, e.g. to [9] for the formal definition of the LOCAL
model of distributed computing.

A graph $H$ is a minor of a graph $G$, written $H\preceq G$, if there is a set
$\\{G_{v}\leavevmode\nobreak\ :\leavevmode\nobreak\ v\in V(H)\\}$ of pairwise
vertex disjoint and connected subgraphs $G_{v}\subseteq G$ such that if
$\\{u,v\\}\in E(H)$, then there is an edge between a vertex of $G_{u}$ and a
vertex of $G_{v}$. We call $V(G_{v})$ the _branch set_ of $v$ and say that it
is _contracted_ to the vertex $v$.

For a non-negative integer $r$, a graph $H$ is an _$r$ -shallow minor_ of $G$,
written $H\preceq_{r}G$, if there is a set $\\{G_{v}:v\in V(H)\\}$ of pairwise
vertex disjoint connected subgraphs $G_{v}\subseteq G$ of radius at most $r$
such that if $\\{u,v\\}\in E(H)$, then there is an edge between a vertex of
$G_{u}$ and a vertex of $G_{v}$. Observe that a $0$-shallow minor of $G$ is
just a subgraph of $G$.

We write $\nabla_{r}(G)$ for $\max_{H\preceq_{r}G}|E(H)|/|V(H)|$. Observe that
$\nabla_{0}(G)$ denotes the maximum average edge density of $G$ and
$2\nabla_{0}(G)$ bounds the degeneracy of $G$, which is defined as
$\max_{H\subseteq G}\delta(H)$. Here, $\delta(H)$ denotes the minimum degree
of $H$. A class $\mathscr{C}$ of graphs has _bounded expansion_ if there is a
function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $\nabla_{r}(G)\leq
f(r)$ for all graphs $G\in\mathscr{C}$. This is equivalent to demanding that
the degeneracy of each $r$-shallow minor of $G$ is functionally bounded by
$r$.

We write $K_{s,t}$ for the complete bipartite graph with partitions of size
$s$ and $t$, respectively. Observe that $K_{t,t}$ has $2t$ vertices and
$t^{2}$ edges, hence, if $\nabla_{0}(G)<t/2$, then $G$ excludes $K_{t,t}$ as a
subgraph.

For a graph $G$ and $v\in V(G)$ we write $N(v)=\\{w\leavevmode\nobreak\
:\leavevmode\nobreak\ \\{v,w\\}\in E(G)\\}$ for the _open neighborhood_ of $v$
and $N[v]=N(v)\cup\\{v\\}$ for the _closed neighborhood_ of $v$. For a set
$A\subseteq V(G)$ let $N[A]=\bigcup_{v\in A}N[v]$. We write $N_{r}[v]$ for the
set of vertices at distance at most $r$ from a vertex $v$. A dominating set in
a graph $G$ is a set $D\subseteq V(G)$ such that $N[D]=V(G)$. We write
$\gamma(G)$ for the size of a minimum dominating set of $G$. For $W\subseteq
V(G)$ we say that a set $Z\subseteq V(G)$ _dominates_ or _covers_ or is a
_cover_ of $W$ if $W\subseteq N[Z]$. Observe that we do not require $Z\cap
W=\emptyset$ as Czygrinow et al. do for covers.

The following lemma is one of the key lemmas used for the algorithm. It goes
back to [25].

######  Lemma 1.

Let $G$ be a graph. Then there are at most $2\gamma(G)$ vertices $v$ with the
property that $N(v)$ cannot be dominated by at most $2\nabla_{1}(G)$ vertices
different from $v$.

###### Proof.

Let $\gamma=\gamma(G)$ and assume that there are $2\gamma$ such vertices
$a_{1},\ldots,a_{2\gamma}$. We proceed towards a contradiction. Let
$\\{d_{1},\ldots,d_{\gamma}\\}$ be a minimum dominating set. At least $\gamma$
of the $a_{i}$’s are not in this dominating set. We can hence assume w.l.o.g.
that $\\{a_{1},\ldots,a_{\gamma}\\}$ and $\\{d_{1},\ldots,d_{\gamma}\\}$ are
two disjoint sets of vertices.

We build a $1$-shallow minor $H$ of the graph $G$ with the following $2\gamma$
branch sets. For every $i\leq\gamma$, we have a branch set $A_{i}=\\{a_{i}\\}$
and a branch set
$D_{i}=N[d_{i}]\setminus(\\{a_{1},\ldots,a_{\gamma}\\}\cup\bigcup_{j<i}N[d_{j}]\cup\\{d_{i+1},\ldots,d_{\gamma}\\})$.
We call the associated vertices of $H$
$a_{1}^{\prime},\ldots,a_{\gamma}^{\prime},d_{1}^{\prime},\ldots,d_{\gamma}^{\prime}$.

Since $\\{d_{1},\ldots,d_{\gamma}\\}$ is a dominating set of $G$ and by
assumption on $N(a_{i})$, we have that in $H$, every $a^{\prime}_{i}$ is
connected to at least $2\nabla_{1}(G)+1$ of the $d^{\prime}_{i}$. We therefore
have that $|V_{H}|=2\gamma$ and $|E_{H}|\geq\gamma(2\nabla_{1}+1)$, hence
$|E_{H}|>|V_{H}|\nabla_{1}$, a contradiction. ∎

Note that we cannot locally determine the number $\nabla_{1}(G)$. We must
hence assume that it is given with the input. Observe that similarly, the
algorithm of Czygrinow et al. works with the assumption that the input
excludes a complete graph with $t$ vertices as a topological minor. This
implies a bound on the edge density of topological minors in $G$, which can be
seen as being given with the input.

The algorithm proceeds in three phases. The first phase is based on Lemma 1 as
follows. In the LOCAL model we can learn the distance-$2$ neighborhood
$N_{2}[v]$ of every vertex $v$ in $2$ rounds, and then locally test whether
$N(v)$ can be dominated by at most $2\nabla_{1}(G)$ vertices. We let $D_{1}$
be the set of all vertices that do not have this property. By Lemma 1 we have
$|D_{1}|\leq 2\gamma(G)$. We remove $D_{1}$ from the graph and mark all its
neighbors as dominated in one additional round.

In the following we fix a graph $G$ and we assume that $N(v)$ can be
dominating by at most $2\nabla_{1}(G)$ vertices different from $v$ for all
$v\in V(G)$. We write $\nabla_{1}$ for $\nabla_{1}(G)$ and we let $t\leq
2\nabla_{0}(G)+1$ be minimal such that $G$ exclude $K_{t,t}$ as a subgraph.
Note that this number is not required as part of the input. We let $k\coloneq
2\nabla_{1}$. We also fix a minimum dominating set $D$ of $G$ of size
$\gamma$. In the following, when we speak of “almost all vertices”, we mean
all but at most $c\gamma$ vertices for some constant $c$. This is again
motivated by the argument that adding any $c\gamma$ vertices to the dominating
set will still give a constant factor approximation.

######  Example 1.

A planar $n$-vertex graph has at most $3n-6$ edges. A minor or a planar graph
is again planar, hence for planar graphs $G$ we have $\nabla_{r}(G)\leq\leq 3$
for all $r\geq 0$ and $k=2\nabla_{1}(G)\leq 6$.

The following lemma is proved exactly as Lemma 1.

######  Lemma 2.

There are at most $2\gamma$ many vertices $v$ with the property that $N(v)$
cannot be dominated by at most $2\nabla_{1}$ vertices from $D$ and different
from $v$.

Unfortunately, we cannot determine these vertices locally, as it requires
knowledge of $D$, however, this structural property is very useful for our
further argumentation. Denote by $\hat{D}$ the set of all vertices $v$ whose
neighborhood cannot be dominated by $2\nabla_{1}$ vertices of $D$ different
from $v$. Let $D^{\prime}=D\cup\hat{D}$. According to Lemma 2, $D^{\prime}$
contains at most $3\gamma$ vertices. Let us stress that $D^{\prime}$ will
never be computed by our LOCAL algorithm. We only use its existence in the
correctness proofs.

We can apply these lemmas to obtain a constant factor approximation for
dominating set only if $\nabla_{1}(G)$ is bounded by a constant. For example,
in general, in graphs of bounded degeneracy the number of vertices that
dominate the neighborhood of a vertex can only be bounded by $\gamma(G)$.
Hence, the approach based on covers and pseudo-covers that is employed in the
following cannot be extended to degenerate graph classes.

######  Example 2.

Let $G(\gamma,m)$ be the graph with vertices $v_{i}$ for $1\leq i\leq\gamma$,
$w^{j}$ for $1\leq j\leq m$ and $s_{i}^{j}$ for $1\leq i\leq\gamma,1\leq j\leq
m$. We have the edges $\\{v_{1},w^{j}\\}$ for $1\leq j\leq m$, hence $v_{1}$
dominates all $w^{j}$. We have the edges $\\{w^{j},s_{i}^{j}\\}$ for all
$1\leq i\leq\gamma,1\leq j\leq m$, hence, the $s_{i}^{j}$ are neighbors of
$w^{j}$. Finally, we have the edges $\\{v_{i},s_{i}^{j}\\}$, that is, $v_{i}$
dominates the $i$th neighbor of $w_{j}$. Hence, for $m>\gamma$, $G(\gamma,m)$
has a dominating set of size $\gamma$ and $m$ vertices whose neighborhood can
be dominated only by $\gamma(G)$ vertices. Lemma 1 implies that
$\gamma<2\nabla_{1}$, and as we can choose $m$ arbitrary large, we cannot
usefully apply Lemma 1. Furthermore, $G(\gamma,m)$ is $2$-degenerate, showing
that these methods cannot be applied on degenerate graph classes.

Figure 2:  A $2$ degenerate graph where for many $v\in V(G)$ the set $N(v)$
can only be dominated by at least $\gamma$ vertices different from $v$.

##  3 Covers and pseudo-covers

Intuitively, the vertices from a cover of a set $W$ can take different roles.
A few vertices of a cover may cover almost the complete set $W$, while a few
others are only there to cover what was left over. The key observation of
Czygrinow et al. is that in classes that exclude some $K_{t,t}$ as a subgraph,
there can only be few of such high degree covering vertices, while there can
be arbitrarily many vertices that cover at most $t-1$ vertices of $W$ (the
same vertices can be covered over and over again). This observation can be
applied recursively and is distilled into the following two definitions.
Recall that by the processing carried out in the first phase of the algorithm
we know that every neighborhood $N(v)$ can be covered by $k=2\nabla_{1}$
vertices different from $v$. For the rest of this article we fix
$\alpha\coloneqq 1/k$, $\ell=8\nabla_{1}/\alpha^{2}+1=4k^{3}+1$ and
$q=4k^{4}$.

######  Definition 1.

A vertex $z\in V(G)$ is _$\alpha$ -strong_ for a vertex set $W\subseteq V(G)$
if $|N[z]\cap W|\geq\alpha|W|$.

######  Definition 2.

A _pseudo-cover_ (with parameters $\alpha,\ell,q,k$) of a set $W\subseteq
V(G)$ is a sequence $(v_{1},\ldots,v_{m})$ of vertices such that for every $i$
we have

  * •

$|W\setminus\bigcup_{i\leq m}N[v_{i}]|\leq q$,

  * •

$v_{i}$ is $\alpha$-strong for $W\setminus\bigcup_{j<i}N[v_{j}]$,

  * •

$|N[v_{i}]\cap(W\setminus\bigcup_{j<i}N[v_{j}])|\geq\ell$,

  * •

$m\leq k$.

The next lemma shows how to derive the existence of pseudo-covers from the
existence of covers.

######  Lemma 3.

Let $W\subseteq V(G)$ be of size at least $q$ and let $Z$ be a cover of $W$
with $k$ elements. There exists an ordering of the vertices of $Z$ as
$z_{1},\ldots,z_{k}$ and $m\leq k$ such that $(z_{1},\ldots,z_{m})$ is a
pseudo-cover of $W$.

###### Proof.

We build the order by induction. Intuitively, we order the elements by
neighborhood size, while removing the neighborhoods of the previously ordered
vertices. More precisely, assume that $(z_{1},\ldots,z_{i})$ have been defined
for some $i\geq 0$. We then define $z_{i+1}$ as the element that maximizes
$|N[z]\cap(W\setminus\bigcup_{j\leq i}N[z_{j}])|$.

Once we have ordered all vertices of $Z$, we define $m$ as the maximal integer
not larger than $k$ such that for every $i\leq m$ we have:

  * •

$z_{i}$ is $\alpha$-strong for $W\setminus\bigcup_{j<i}N[z_{j}]$, and

  * •

$|N[z_{i}]\cap(W\setminus\bigcup_{j\leq i}N[z_{j}])|\geq\ell$.

We made sure that $(z_{1},\ldots,z_{m})$ satisfies the last 3 properties of a
pseudo-cover of $W$. It only remains to check the first one. To do so, we
define $W^{\prime}\coloneq W\setminus\bigcup_{i\leq m}N[z_{j}]$. We want to
prove that $|W^{\prime}|\leq q$. Note that because $Z$ covers $W$, if $m=k$ we
have $W^{\prime}=\emptyset$ and we are done. We can therefore assume that
$m<k$ and $W^{\prime}\neq\emptyset$. Since $Z$ is a cover of $W$, we also know
that $(z_{m+1},\ldots z_{k})$ is a cover of $W^{\prime}$, therefore there is
an element in $(z_{m+1},\ldots z_{k})$ that dominates at least a $1/k$
fraction of $W^{\prime}$. Thanks to the previously defined order, we know that
$z_{m+1}$ is such element. Since $\alpha=1/k$, it follows that $z_{m+1}$ is
$\alpha$-strong for $W^{\prime}$. This, together with the definition of $m$,
we have that $|N[z_{i}]\cap(W\setminus\bigcup_{j\leq i}N[z_{j}])|<\ell$
meaning that $|N[z_{m+1}]\cap W^{\prime}|<\ell$. This implies that
$|W^{\prime}|/k<\ell$. And since $\ell=q/k$, we have $|W^{\prime}|<q$. Hence,
$(z_{1},\ldots,z_{m})$ is a pseudo-cover of $W$. ∎

While there can exist unboundedly many covers for a set $W\subseteq V(G)$, the
nice observation of Czygrinow et al. was that the number of pseudo-covers is
bounded whenever the input graph excludes some biclique $K_{s,t}$ as a
subgraph. We do not state the result in this generality, as it leads to
enormous constants. Instead, we focus on the case where small covers exist,
that is, on the case where $\nabla_{1}(G)$ is bounded and optimize the
constants for this case.

######  Lemma 4.

Let $W\subseteq V(G)$ of size at least $8\nabla_{1}/\alpha^{2}$. Then there
are at most $4\nabla_{1}/\alpha$ vertices that are $\alpha$-strong for $W$.

###### Proof.

Assume that there is such a set $W$ with at least $c\coloneq
4\nabla_{1}/\alpha$ vertices that are $\alpha$-strong for $W$. We build a
$1$-shallow minor $H$ of the graph $G$ with $|W|$ branch sets. Each branch set
is either a single element of $W$, or a pair $\\{w,a\\}$, where $w$ is in $W$
and $a$ is an $\alpha$-strong vertex for $W$, connected to $w$, and that is
not in $W$. This is obtained by iteratively contracting one edge of an
$\alpha$-strong vertex with a vertex of $W$. This is possible because
$\alpha|W|>c$, so during the process and for any $\alpha$-strong vertex we can
find a connected vertex in $W$ that is not part of any contraction.

Once this is done, we have that $|V_{H}|=|W|$. For the edges, each of the
$\alpha$-strong vertices can account for $\alpha|W|$ many edges. We need to
subtract $c^{2}$ from the total as we do not count twice an edge between two
strong vertices. Therefore $|E_{H}|\geq c\alpha|W|-c^{2}$. Note also that
because $|W|\geq 8\nabla_{1}/\alpha^{2}$, we have that
$2\nabla_{1}\geq(4\nabla_{1})^{2}/(\alpha^{2}|W|)$. All of this together leads
to:

$\frac{|E_{H}|}{|V_{H}|}\geq\frac{c\alpha|W|-c^{2}}{|W|}\geq
4\nabla_{1}-\frac{(4\nabla_{1})^{2}}{\alpha^{2}|W|}\geq
4\nabla_{1}-2\nabla_{1}>\nabla_{1}$

This contradicts the definition of $\nabla_{1}$. ∎

This leads quickly to a bound on the number of pseudo-covers.

######  Lemma 5.

For every $W\subseteq V(G)$ of size at least $\ell$, the number of pseudo-
covers is bounded by $2(4\nabla_{1}(G)/\alpha)^{k}$.

The proof of the lemma is exactly as the proof of Lemma 7 in the presentation
of Czygrinow et al. [9], we therefore refrain from repeating it here.

We write $\mathcal{T}(v)$ for the set of all pseudo-covers of $N(v)$ and
$\mathcal{P}(v)$ the set of all elements that appear in a pseudo-cover of
$N(v)$.

######  Corollary 1.

For every $v\in V(G)$ with $|N(v)|>\ell$, we have $|\mathcal{T}(v)|\leq
2(2k^{2})^{k}$ and $|\mathcal{P}(v)|\leq 2k(2k^{2})^{k}\leq(2k)^{2k+1}$.

##  4 Finding dominators

Recall that by Lemma 2 for every $v\in V(G)$ we can cover $N(v)$ with at most
$k$ vertices from $D^{\prime}$. To first gain an intuitive understanding of
the second phase of the algorithm, where we construct a set $D_{2}\subseteq
V(G)$, let us consider the following iterative procedure.

Fix some $v\in V(G)$. Let $v_{1}=v$ and $B_{1}\coloneqq N(v)$ and assume
$|B_{1}|\geq k^{t-1}(2t{-}1)$. We consider $s$ vertices
$v_{1},v_{2}\ldots,v_{s}$ as follows. Choose as $v_{2}$ an arbitrary vertex
different from $v_{1}$ that dominates at least $k^{t-2}(2t-1)$ vertices of
$B_{1}$, that is, a vertex that satisfies $|N[v_{2}]\cap B_{1}|\geq
k^{t-2}(2t-1)$. Note that any vertex $v_{2}$ that dominate a $1/k$-fraction of
$B_{1}$ can be such vertex, i.e. it is enough for $v_{2}$ to be
$\alpha$-strong for $B_{1}$.

Let $B_{2}\coloneqq N(v_{2})\cap B_{1}$. Observe that we consider the open
neighborhood of $v_{2}$ here, hence $B_{2}$ does not contain $v_{2}$. Hence,
$|B_{2}|\geq k^{t-2}(2t-1)-1\geq k^{t-2}(2t-2)$. We continue to choose
vertices $v_{3},\ldots$ inductively just as above. That is, if the vertices
$v_{1},\ldots,v_{i}$ and sets $B_{1},\ldots,B_{i}\subseteq V(G)$ have been
defined, we choose the next vertex $v_{i+1}$ as an arbitrary vertex not in
$\\{v_{1},\ldots,v_{i}\\}$ that dominates at least $k^{t-i-1}(2t-i)$ vertices
of $B_{i}$, that is, a vertex with $|N[v_{i+1}]\cap B_{i}|\geq
k^{t-i-1}(2t-i)$ and let $B_{i+1}\coloneqq N(v_{i+1})\cap B_{i}$, of size at
least $k^{t-i-1}(2t-i-1)$.

######  Lemma 6.

Assume $|N(v)|\geq k^{t-1}\cdot(2t-1)$. Let $v_{1},\ldots,v_{s}$ be a maximal
sequence obtained as above. Then $s<t$ and
$D^{\prime}\cap\\{v_{1},\ldots,v_{s}\\}\neq\emptyset$.

###### Proof.

Assume that we can compute a sequence $v_{1},v_{2},\ldots,v_{t}$. By
definition, every $v_{i}$ is connected to every vertices of $B_{t}$. For every
$1\leq i\leq t$ we have $|B_{i}|\geq k^{t-i}(2t-i)$ and therefore $|B_{t}|\geq
t$. This shows that the two sets $\\{v_{1},\ldots,v_{t}\\}$ and $B_{t}$ form a
$K_{t,t}$ as a subgraph of $G$. Since this is not possible, the process must
stop having performed at most $t-1$ rounds.

We now turn to the second claim of the lemma. Assume that
$v_{1},v_{2},\ldots,v_{s}$ is a maximal sequence for some $s<t$. Because
$s<t$, we have that $B_{s}$ is not empty. Because $B_{s}\subseteq
B_{1}=N(v_{1})$, we have that $B_{s}$ can be dominated with at most $k$
elements of $D^{\prime}$. Therefore, there must be an element $v$ of
$D^{\prime}$ that dominates a $1/k$ fraction of $B_{s}$. If $v$ was not one of
the $v_{1},\ldots,v_{s}$, we could have continued the sequence by defining
$v_{s+1}\coloneqq v$. Since the sequence is maximal, $v$ must be one of the
$v_{1},\ldots,v_{s}$, which leads to
$D^{\prime}\cap\\{v_{1},\ldots,v_{s}\\}\neq\emptyset$. ∎

We aim to carry out this iterative process in parallel for all vertices $v\in
V(G)$ with a sufficiently large neighborhood. Of course, in the process we
cannot tell when we have encountered the element of $D^{\prime}$. Hence, from
the constructed vertices $v_{1},\ldots,v_{s}$ we will simply choose the
element $v_{s}$ into the dominating set. Unfortunately, this approach alone
can give us arbitrarily large dominating sets, as we can have many choices for
the vertices $v_{i}$, while already $v_{1}$ was possibly optimal. We address
this issue by restricting the possible choices for the vertices $v_{i}$.

######  Definition 3.

For any vertex $v\in V(G)$, a $k$-dominating-sequence of $v$ is a sequence
$(v_{1},\ldots,v_{s})$ for which we can define sets $B_{1},\ldots,B_{s}$ such
that:

  * •

$v_{1}=v$, $B_{1}\subseteq N(v_{1})$,

  * •

for every $i\leq s$ we have $B_{i}\subseteq N(v_{i})\cap B_{i-1}$,

  * •

$|B_{i}|\geq k^{t-i}(2t-i+(t-i)q)$

  * •

and for every $i\leq s$ we have $v_{i}\in\mathcal{P}(v_{i-1})$.

A $k$-dominating-sequence $(v_{1},\ldots,v_{s})$ is maximal if there is no
vertex $u$ such that $(v_{1},\ldots,v_{s},u)$ is a $k$-dominating-sequence.

Note that this definition requires $|N(v)|\geq k^{t-1}(2t-1+(t-1)q)$. For a
vertex $v$ with a not sufficiently large neighborhood, there are no
$k$-dominating-sequences of $v$.

######  Lemma 7.

Let $v$ be a vertex and let $(v_{1},\ldots,v_{s})$ be a maximal
$k$-dominating-sequence of $v$. Then $s<t$ and
$D^{\prime}\cap\\{v_{1},\ldots,v_{s}\\}\neq\emptyset$.

###### Proof.

The statement $s<t$ is proved exactly as for Lemma 6.
To prove the second statement we assume, in order to reach a contradiction,
that $D^{\prime}\cap\\{v_{1},\ldots,v_{s}\\}=\emptyset$. We have that
$B_{s}\subseteq N(v_{s})$, and remember that $N(v_{s})$ can be dominated by at
most $k$ elements of $D^{\prime}$. By Lemma 3, we can derive a pseudo-cover
$S=(u_{1},\ldots,u_{m})$ of $N(v_{s})$, where $m\leq k$ and every $u_{i}$ is
an element of $D^{\prime}$. Let $X$ denote the set (of size at most $q$) of
vertices not covered by $S$. As $S$ contains at most $k$ vertices there must
exist a vertex $u$ in $S$ that covers at least a $1/k$ fraction of
$B_{s}\setminus X$. By construction, we have that $|B_{s}|\geq
k^{t-s}\cdot(2t-s+(t-s)q)\geq k(t+q)$ because $s<t$. Therefore
$|B_{s}\setminus X|\geq k$ and we have

$|N[u]\cap B_{s}|\geq\frac{|B_{s}|-q}{k}\geq\frac{k^{t-s}(2t-s+(t-s)q)-q}{k},$

hence

$|N[u]\cap B_{s}|\geq\frac{k^{t-s}(2t-s+(t-s-1)q)}{k}\geq
k^{t-s-1}(2t-s+(t-s-1)q),$

and therefore

$|N(u)\cap B_{s}|\geq|N[u]\cap B_{s}|-1\geq k^{t-s-1}(2t-s-1+(t-s-1)q).$

So we can continue the sequence $(v_{1},\ldots,v_{s})$ by defining
$v_{s+1}\coloneqq u$. In conclusion if $(v_{1},\ldots,v_{s})$ is a maximal
sequence, it contains an element of $D^{\prime}$. ∎

The goal of this modified procedure is first to ensure that every maximal
sequence contains an element of $D^{\prime}$ and second, to make sure that
there are not to many possible $v_{s}$ (which are the elements that we pick
for the dominating set). This is illustrated in the following example and
formalized right after that.

######  Example 3.

Consider the case of planar graphs. Since these graph exclude $K_{3,3}$, i.e.
$t=3$, we have that every maximal sequence is of length 1 or 2. For every $v$
of sufficiently large neighborhood we consider every maximal $k$-dominating-
sequence $(v_{1},v_{s})$ of $v$. We then add $v_{s}$ to the set $D_{2}$. We
want to show that $|D_{2}|$ is linearly bounded by $|D^{\prime}|$ and hence by
$\gamma(G)$.

If $s=1$, then we have $v_{s}\in D^{\prime}$ and we are good.

If $s=2$, we have two possibilities. If $v_{2}$ is in $D^{\prime}$, we are
good. If however, $v_{2}$ is not in $D^{\prime}$, then $v_{1}$ is in
$D^{\prime}$. Additionally, $v_{2}$ is in some pseudo-cover $S$ of $v_{1}$,
i.e. $v_{2}\in\mathcal{P}(v_{1})$.

By Corollary 1, we have $|\mathcal{P}(v_{1})|\leq(2k)^{2k+1}$ (and in fact
this number is much smaller in the case of planar graphs). Therefore we have
$|D_{2}|\leq((2k)^{2k+1}+1)|D^{\prime}|$.

We generalize the ideas of Example 3, by explaining what “a few possible
picks” means.

######  Lemma 8.

For any maximal $k$-dominating-sequence $(v_{1},\ldots,v_{s})$, and for any
$i\leq s-1$, we have that

  * •

$v_{i+1}\in\mathcal{P}(v_{i})$,

  * •

$|N(v_{i})|\geq\ell$, and

  * •

$|\mathcal{P}(v_{i})|\leq(2k)^{2k+1}$.

###### Proof.

By construction $v_{i+1}\in\mathcal{P}(v_{i})$, furthermore, $v_{i}$ dominates
at least $B_{i}$, and $|B_{i}|\geq k^{t-i}(2t-i+(t-i)q)\geq q>\ell$. We
conclude with Corollary 1. ∎

We now for every $v\in V(G)$ compute all maximal $k$-dominating-sequences
starting with $v$. Obviously, as every $v_{i}$ in any $k$-dominating-sequences
of $v$ dominates some neighbors of $G$, we can locally compute these steps
after having learned the $2$-neighborhood $N_{2}[v]$ of every vertex in two
rounds in the LOCAL model of computation.

For a set $W\subseteq V(G)$ we write $\mathcal{P}(W)=\bigcup_{v\in
W}\mathcal{P}(v)$. Remember that the definition of $\mathcal{P}(v)$ requires
that $|N(v)|>\ell$. We simply extend the notation with
$\mathcal{P}(v)=\emptyset$ if $|N(v)|\leq\ell$. We now define

$\mathcal{P}^{(1)}(W)\coloneqq\mathcal{P}(W)$

additionally, for $1<i<t$

$\mathcal{P}^{(i)}(W)\coloneqq\mathcal{P}(\mathcal{P}^{(i-1)}(W))$

and finally, for every $1\leq i\leq t$

$\mathcal{P}^{(\leq i)}(W)\coloneqq\bigcup_{1\leq j\leq
i}\mathcal{P}^{(j)}(W).$

Using Lemma 8, for every $k$-dominating-sequence $(v_{1},\ldots,v_{s})$ we
have that $v_{s}\in\mathcal{P}^{(\leq k)}(v_{1})$. More generally, for every
$i\leq s$, we have that $v_{s}\in\mathcal{P}^{(\leq t)}(v_{i})$.

We define $D_{2}$ as the set of all $u\in V(G)$ such that there is some vertex
$v\in V(G)$, and some maximal $k$-dominating-sequence $(v_{1},\ldots,v_{s})$
of $v$ with $u=v_{s}$.

This leads to the following lemma.

######  Lemma 9.

$D_{2}\subseteq\mathcal{P}^{(\leq t)}(D^{\prime})$.

###### Proof.

This uses the observation made above the statement of this lemma, together
with Lemma 7. ∎

Note that while we don’t know how to compute $D^{\prime}$, this section
explained how to compute $D_{2}$ in 2 rounds with the LOCAL model of
computation.

######  Lemma 10.

$|D_{2}|\leq(2k)^{t(2k+1)}\cdot|D^{\prime}|$

###### Proof.

Corollary 1 gives us that $|\mathcal{P}(v)|\leq 2k(2k^{2})^{k}$ for every
$v\in V(G)$ with $|N(v)|>\ell$. As $\mathcal{P}(W)\leq\sum\limits_{v\in
W}|\mathcal{P}(v)|$, we have $P(W)\leq|W|\cdot(2k)^{2k+1}$. A naive induction
yields that for every $i\leq t$,

$|\mathcal{P}^{(\leq i)}(W)|\leq c^{i}|W|,$

where $c=(2k)^{2k+1}$. Hence with this and Lemma 9 we have

$|D_{2}|\leq(2k)^{t(2k+1)}\cdot|D^{\prime}|$

∎

##  5 Cleaning up

We now show that after defining and computing $D_{2}$ as explained in the
previous section, every neighborhood is almost entirely dominated by $D_{2}$.
More precisely, for every vertex $v$ of the graph $|\\{v^{\prime}\in
N(v)\leavevmode\nobreak\ :\leavevmode\nobreak\ v^{\prime}\not\in
N(D_{2})\\}|<k^{t-1}(2t-1+(t-1)q)$.

Before explaining why this holds, note that it implies that, in particular,
the vertices of $D$ have at most $k^{t-1}(2t-1+(t-1)q)$ non-dominated
neighbors. Since every vertex is either in $D$ or a neighbor of some element
in $D$, this implies that in the whole graph there are at most
$k^{t-1}(2t-1+(t-1)q)\cdot\gamma$ non-dominated vertices left.

We can therefore define $D_{3}\coloneqq\\{v\in V(G)\leavevmode\nobreak\
:\leavevmode\nobreak\ v\not\in N(D_{2})\\}$ and have that $|D_{3}|\leq
k^{t-1}(2t-1+(t-1)q)\cdot\gamma$, and that $D_{1}\cup D_{2}\cup D_{3}$ is a
dominating set of $G$. We are therefore done.

We now turn to the proof of the above claim.

######  Lemma 11.

For every vertex $v$ of the graph, we have:
$|\\{v^{\prime}\in N(v)\leavevmode\nobreak\ :\leavevmode\nobreak\
v^{\prime}\not\in N(D_{2})\\}|<k^{t-1}(2t-1+(t-1)q)$.

###### Proof.

Assume, for the sake of reaching a contradiction, that there is a vertex $v$
such that $|\\{v^{\prime}\in N(v)\leavevmode\nobreak\ :\leavevmode\nobreak\
v^{\prime}\not\in N(D_{2})\\}|\geq k^{t-1}(2t-1+(t-1)q)$.

We then define $B_{1}\coloneqq\\{v^{\prime}\in N(v)\leavevmode\nobreak\
:\leavevmode\nobreak\ v^{\prime}\not\in N(D_{2})\\}$.

Exactly as in the proof of Lemma 7, we have that $B_{1}$ can be dominated by
at most $k$ elements of $D^{\prime}$. Hence by Lemma 3, we can derive a
pseudo-cover $S=(u_{1},\ldots,u_{m})$ of $B_{1}$, where $m\leq k$ and every
$u_{i}$ is an element of $D^{\prime}$. This leads to the existence of some
vertex $u$ in $S$ that covers at least a $1/k$ fraction of $B_{1}\setminus X$.
This yields a vertex $v_{2}$, and a set $B_{2}$.

We can then continue and build a maximal $k$-dominating-sequence
$(v_{1},\ldots v_{s})$ of $v$. By construction, this sequence has the property
that every $v_{i}$ dominates some elements of $B_{1}$. This is true in
particular for $v_{s}$, but also we have that $v_{s}\in D_{2}$, hence a
contradiction. ∎

######  Corollary 2.

The graph contains at most $k^{t-1}(2t-1+(t-1)q)\cdot\gamma$ non-dominated
vertices. In particular, the set $D_{3}$ has at most this size.

##  6 The algorithm

In this final section we summarize the algorithm.

  1. 1.

Compute the set $D_{1}$ of all $v$ such that $N(v)$ cannot be dominated by
$2\nabla_{1}(G)$ vertices different from $v$. Remove $D_{1}$ from $G$ and mark
all its neighbors as dominated.

  2. 2.

In parallel for every vertex $v=v_{1}$ compute all $k$-domination sequences
$v_{1},\ldots,v_{s}$. Add all vertices $v_{s}$ to the set $D_{2}$. Remove
$D_{2}$ from $G$ and mark its neighbors as dominated. This is done as follows.

We can learn the neighborhood $N_{2}[v]$ for every vertex $v$ in $2$ rounds.
In the LOCAL model we can then compute the pseudo-covers without further
communication. In two additional rounds can compute the domination sequences
from the pseudo-covers (as we need to consider only elements from
$N_{2}[v_{1}]$). We report in $2$ additional rounds that $v_{s}$ belongs to
$D_{2}$ and one more round to mark the neighbors of $D_{2}$ as dominated.

  3. 3.

In the final round we add all non-dominated vertices to a set $D_{3}$ and
return the set $D_{1}\cup D_{2}\cup D_{3}$.

According to Lemma 1, Lemma 10 and Corollary 2 the algorithm computes a
$2+3(2k)^{t(2k+1)}+k^{t-1}(2t-1+(t-1)q)$ approximation. This is an absolute
constant in $\mathcal{O}(\nabla_{1}^{4t\nabla_{1}+t})$ depending only on
$\nabla_{1}(G)$, as also $t<2\nabla_{1}$.

##  7 Conclusion

We simplified the presentation and generalized the algorithm of Czygrinow et
al. [9] from graph classes that exclude some topological minor to graph
classes $\mathcal{C}$ where $\nabla_{1}(G)$ is bounded by an absolute constant
for all $G\in\mathcal{C}$. This is a property in particular possessed by
classes with bounded expansion, which include many commonly studied sparse
graph classes.

It is an interesting and important question to identify the most general graph
classes on which certain algorithmic techniques work. The key arguments of
Lemma 1 and Lemma 2 work only for classes with $\nabla_{1}(G)$ bounded by an
absolute constant. We need different methods to push towards classes with only
$\nabla_{0}(G)$ bounded, which are the degenerate classes.

The obtained bounds are still large, but by magnitudes smaller than those
obtained in the original work of Czygrinow et al.[9]. It will also be
interesting to optimize the algorithm for planar graphs, where additional
topological arguments can help to strongly optimize constants and potentially
beat the currently best known bound of 52 [25, 33].

## References

  * [1] Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz.  Distributed domination on graph classes of bounded expansion.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, pages 143–151, 2018.
  * [2] Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz.  A local constant factor mds approximation for bounded genus graphs.  In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 227–233, 2016.
  * [3] Saeed Akhoondian Amiri and Stefan Schmid.  Brief announcement: A log*-time local mds approximation scheme for bounded genus graphs.  In Proc. DISC, 2016.
  * [4] Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz.  Distributed dominating set approximations beyond planar graphs.  ACM Transactions on Algorithms (TALG), 15(3):1–18, 2019.
  * [5] Nikhil Bansal and Seeun William Umboh.  Tight approximation bounds for dominating set on graphs of bounded arboricity.  Information Processing Letters, 122:21–24, 2017.
  * [6] Leonid Barenboim, Michael Elkin, and Cyril Gavoille.  A fast network-decomposition algorithm and its applications to constant-time distributed computation.  Theoretical Computer Science, 751:2–23, 2018.
  * [7] Hervé Brönnimann and Michael T Goodrich.  Almost optimal set covers in finite vc-dimension.  Discrete & Computational Geometry, 14(4):463–479, 1995.
  * [8] Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak.  Fast distributed approximations in planar graphs.  In International Symposium on Distributed Computing, pages 78–92. Springer, 2008.
  * [9] Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak, and Marcin Witkowski.  Distributed approximation algorithms for the minimum dominating set in k_h-minor-free graphs.  In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [10] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624–633, 2014.
  * [11] Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar.  Kernelization and sparseness: the case of dominating set.  In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pages 31:1–31:14, 2016.
  * [12] Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, Fahad Panolan, and Sebastian Siebertz.  Lossy kernels for connected dominating set on sparse graphs.  SIAM Journal on Discrete Mathematics, 33(3):1743–1771, 2019.
  * [13] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz.  Neighborhood complexity and kernelization for nowhere dense classes of graphs.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 63:1–63:14, 2017.
  * [14] Guy Even, Dror Rawitz, and Shimon Moni Shahar.  Hitting sets when the vc-dimension is small.  Information Processing Letters, 95(2):358–362, 2005.
  * [15] Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk.  Progressive algorithms for domination and independence.  In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 27:1–27:16, 2019.
  * [16] Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira.  A distributed algorithm for minimum-weight spanning trees.  ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66–77, 1983.
  * [17] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [18] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  SIAM Journal on Computing, 46(6):1712–1744, 2017.
  * [19] Miikka Hilke, Christoph Lenzen, and Jukka Suomela.  Brief announcement: local approximability of minimum dominating set on planar graphs.  In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 344–346, 2014.
  * [20] David S Johnson.  Approximation algorithms for combinatorial problems.  Journal of computer and system sciences, 9(3):256–278, 1974.
  * [21] Mark Jones, Daniel Lokshtanov, MS Ramanujan, Saket Saurabh, and Ondřej Suchý.  Parameterized complexity of directed steiner tree on sparse graphs.  SIAM Journal on Discrete Mathematics, 31(2):1294–1327, 2017.
  * [22] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * [23] Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz.  Polynomial kernels and wideness properties of nowhere dense graph classes.  ACM Transactions on Algorithms (TALG), 15(2):1–19, 2018.
  * [24] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.  Local computation: Lower and upper bounds.  J. ACM, 63(2):17:1–17:44, 2016.
  * [25] Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.  Distributed minimum dominating set approximations in restricted families of graphs.  Distributed computing, 26(2):119 – 137, 2013.
  * [26] Christoph Lenzen and Roger Wattenhofer.  Leveraging linial’s locality limit.  In International Symposium on Distributed Computing, pages 394–407. Springer, 2008.
  * [27] Christoph Lenzen and Roger Wattenhofer.  Minimum dominating set approximation in graphs of bounded arboricity.  In International symposium on distributed computing, pages 510–524. Springer, 2010.
  * [28] László Lovász.  On the ratio of optimal integral and fractional covers.  Discrete mathematics, 13(4):383–390, 1975.
  * [29] Jaroslav Nešetřil and Patrice Ossona de Mendez.  Grad and classes with bounded expansion I. decompositions.  European Journal of Combinatorics, 29(3):760–776, 2008.
  * [30] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R Wood.  Characterisations and examples of graph classes with bounded expansion.  European Journal of Combinatorics, 33(3):350–373, 2012.
  * [31] Sebastian Siebertz.  Greedy domination on biclique-free graphs.  Information Processing Letters, 145:64–67, 2019.
  * [32] Wojciech Wawrzyniak.  Brief announcement: a local approximation algorithm for mds problem in anonymous planar networks.  In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 406–408, 2013.
  * [33] Wojciech Wawrzyniak.  A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs.  Information Processing Letters, 114(3):94–98, 2014.


* (6) J. Palacci, S. Sacanna, S. H. Kim, G. R. Yi, D. J. Pine, P. M. Chaikin, Light-activated self-propelled colloids, Philos. Trans. R. Soc. A 372, 20130372 (2014)
  * (7) W. F. Paxton, K. C. Kistler, C. C. Olmeda, A. Sen, S. K St Angelo, T. Cao, T. E. Mallouk, P. E. Lammert, V. H. Crespi, Catalytic nanomotors: autonomous movement of striped nanorods, J. Am. Chem. Soc. 126, 13424 (2004)
  * (8) L. Walsh, C. G. Wagner, S. Schlossberg, C. Olsen, A. Baskaran, N. Menon, Noise and diffusion of a vibrated self-propelled granular particle, Soft Matter, 13, 8964 (2017)
  * (9) I. Buttinoni, J. Bialké, F. Kümmel, H. Löwen, C. Bechinger, T. Speck, Dynamical Clustering and Phase Separation in Suspensions of Self-Propelled Colloidal Particles, Phys. Rev. Lett. 110, 238301 (2013)
  * (10) P. Galajda, J. Keymer, P. Chaikin, R. Austin, A Wall of Funnels Concentrates Swimming Bacteria, J. Bacterio. 189, 8704 (2007)
  * (11) A. Sokolov, M. M. Apodaca, B. A. Grzybowski, I. S. Aranson, Swimming bacteria power microscopic gears, Proc. Natl. Acad. Sci. 107, 969 (2010)
  * (12) R. Di Leonardo, L. Angelani, D. Dell’Arciprete, G. Ruocco, V. Lebba, S. Schippa, M. P. Conte, F. Mecarini, F. De Angelis, E. Di Fabrizio, Bacterial ratchet motors, Proc. Natl. Acad. Sci. 107, 9541 (2010)
  * (13) G. Volpe, I. Buttinoni, D. Vogt, H.-J. Kümmerer, C. Bechinger, Microswimmers in patterned environments, Soft Matter 7, 8810 (2011)
  * (14) G. Li, J. X. Tang, Accumulation of Microswimmers near a Surface Mediated by Collision and Rotational Brownian Motion, Phys. Rev. Lett. 103, 078101 (2009)
  * (15) C. F. Lee, Active particles under confinement: aggregation at the wall and gradient formation inside a channel, New J. Phys. 15, 055007 (2013)
  * (16) C. G. Wagner, M. F. Hagan, A. Baskaran, Steady-state distributions of active Brownian particles under confinement and forcing, J. Stat. Mech., 043203 (2017)
  * (17) B. Ezhilan, R. Alonso-Matilla, D. Saintillan, On the distribution and swim pressure of run-and-tumble particles in confinement, J. Fluid. Mech. 781, R4 (2015)
  * (18) N. J. Fisch, M. D. Kruskal, Separating variables in two-way diffusion equations, J. Math. Phys. 21, 740 (1980)
  * (19) R. Beals, Partial-range completeness and existence of solutions to two-way diffusion equation, J. Math. Phys. 22, 954 (1981)
  * (20) C. G. Wagner, R. Beals, Constructing solutions to two-way diffusion problems, J. Phys. A: Math Theor. 52, 115204 (2019)
  * (21) A. P. Solon, Y. Fily, M. E. Cates, Y. Kafri, M. Kardar, J. Tailleur, Pressure is not a state function for generic active fluids, Nat. Phys. 11, 673 (2015)
  * (22) L. Caprini, U. M. B. Marconi, Active particles under confinement and effective force generation among surfaces, Soft Matter 14, 9044 (2018)
  * (23) U. M. B. Marconi, A. Sarracino, C. Maggi, A. Puglisi, Self-propulsion against a moving membrane: Enhanced accumulation and drag force, Phys. Rev. E 96, 032601 (2017)
  * (24) C. Battle, C. P. Broedersz, N. Fakhri, V. F. Geyer, J. Howard, C. F. Schmidt, F. C. MacKintosh, Broken detailed balance at mesoscopic scales in active biological systems, Science 352, 604 (2016)
  * (25) R. Zakine, Y. Zhao, M. Knezevic, A. Daerr, Y. Kafri, J. Tailleur, F. van Wijland, Surface Tensions between Active Fluids and Solid Interfaces: Bare and Dressed, Phys. Rev. Lett. 124, 248003 (2020)
  * (26) A. Y. Grosberg, J.-F. Joanny, Nonequilibrium statistical mechanics of mixtures of particles in contact with different thermostats, Phys. Rev. E 92, 032118 (2015)
  * (27) A. Duzgan, J. V. Sellinger, Active Brownian particles near straight and curved walls: Pressure and boundary layers, Phys. Rev. E 97, 032606 (2018)
  * (28) A. P. Solon, J. Stenhammar, M. E. Cates, Y. Kafri, J. Tailleur, Generalized thermodynamics of motility-induced phase separation: phase equilibria, Laplace pressure, and change of ensembles, New. J. Phys. 20, 075001 (2018)
  * (29) R. Wittmann, F. Smallenburg, J. M. Brader, Pressure, surface tension, and curvature in active systems: a touch of equilibrium, J. Chem. Phys. 150, 174908 (2019)
  * (30) N. Nikola, A. P. Solon, Y. Kafri, M. Kardar, J. Tailleur, R. Voituriez, Active Particles with Soft and Curved Walls: Equation of State, Ratchets, and Instabilities, Phys. Rev. Lett. 117, 098001 (2016)
  * (31) C. Sandford, A. Y. Grosberg, J.-F. Joanny, Pressure and flow of exponentially self-correlated active particles, Phys. Rev. E 96, 052605 (2017)
  * (32) Y. Fily, A. Baskaran, M. F. Hagan, Dynamics of self-propelled particles under strong confinement, Soft Matter 10, 5609 (2014)
  * (33) A. Kaiser, H. H. Wensink, H. Löwen, How to capture active particles, Phys. Rev. Lett. 108, 268307 (2012)
  * (34) M. von Smoluchowski, Phys. Z. 17, 557 (1916); Z. Phys. Chem. 92, 129 (1917)
  * (35) G. F. Hubner, U. M. Titulaer, The Kinetic Boundary Layer for the Linearized Boltzmann Equation around an Absorbing Sphere, J. Stat. Phys. 59, 441 (1990)
  * (36) P. K. Ghosh, V. R. Misko, F. Marchesoni, F. Nori, Self-Propelled Janus Particles in a Ratchet: Numerical Simulations, Phys. Rev. Lett. 110, 268301 (2013)
  * (37) B. Ai, Ratchet transport powered by chiral active particles, Sci. Rep. 6, 18740 (2016)
  * (38) B. Ai, Y. He, W. Zhong, Entropic Ratchet transport of interacting active Brownian particles, J. Chem. Phys. 141, 194111 (2014)
  * (39) S. A. Mallory, C. Valeriani, A. Cacciuto, An Active Approach to Colloidal Self-Assembly, Annu. Rev. Phys. Chem. 69, 59 (2018)
  * (40) N. Figueroa-Morales, R. Soto, G. Junot, T. Darnige, C. Douarche, V. A. Martinez, A. Lindner, É. Clément, 3D Spacial Exploration by E. coli Echoes Motor Temporal Variability, Phys. Rev. X 10, 021004 (2020)
  * (41) F. Ginot, I. Theurkauff, D. Levis, C. Ybert, L. Bocquet, L. Berthier, C. Cottin-Bizonne, Nonequilibrium Equation of State in Suspensions of Active Colloids, Phys. Rev. X 5, 011004 (2015)
  * (42) M. J. Kontorovich, N. N. Lebedev, A method for the solution of problems in diffraction theory and related topics, Zh. Eksper. Teor. Fiz. 8, 1192 (1938)
  * (43) G. Z. Forristall, J. D. Ingram, Elastodynamics of a wedge, Bull. Seism. Soc. Amer. 61, 275 (1971)
  * (44) K. H. Kang, I. S. Kang, C. M. Lee, Geometry Dependence of Wetting Tension on Charge-Modified Surfaces, Langmuir 19, 6881 (2003)
  * (45) N. D. Fowkes, M. J. Hood, Surface Tension Effects in a Wedge, Q. J. Mech. Appl. Math. 51, 553 (1998)
  * (46) J. H. Smith, Solution of the Inhomogeneous Helmholtz Equation with Lebedev Transforms, J. Math. Phys. 47, 442 (1968)
  * (47) F. Oberhettinger, Tables of Bessel Transforms, Springer-Verlag (1972)
  * (48) F. Oberhettinger, Tables of Mellin Transforms, Springer-Verlag (1974)


Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for $k$-coloring of graphs on $n$ vertices has runtimes $\Omega(2^n)$ for $k\ge 5$. The list coloring problem asks the following more general question: given a list of available colors for each vertex in a graph, does it admit a proper coloring? We propose a quantum algorithm based on Grover search <cit.> to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases where the lists and graphs considered are arbitrary in nature.

§ INTRODUCTION

Graph coloring problems provide for a rich family of NP-complete problems in theoretical computer science.
While exhaustive search is believed to be the fastest classical approach for several NP-complete problems including satisfiability and hitting-set <cit.>, there are much better classical algorithms using dynamic programming, inclusion-exclusion and other structural approaches for problems such as graph coloring <cit.>, the traveling salesman problem <cit.>, set cover <cit.> etc.
Several authors have obtained quantum speedup on these classical algorithms <cit.>; however, all of these algorithms have the limitation that they cannot be easily generalized to the list coloring problem.

Given a finite graph $G=(V,E)$, a proper coloring of $G$ is a function $\chi:V\to\mathbb N$ such that for every edge $uv\in E$, $\chi(u)\neq \chi(v)$. The list coloring problem tries to determine a proper coloring $\chi$ of a graph $G=(V,E)$, given a list $L_v$ of available colors for each vertex $v$. In other words, it is forced that $\chi(v)\in L_v$. When $L_v=\{1,2,\ldots,k\}$ for every vertex $v$ this reduces to the well-studied $k$-coloring problem.
We propose a simple Grover search-based approach to obtain a quadratic speedup on exhaustive search for the list coloring problem.

Grover's algorithm <cit.> is known to speed up unstructured search quadratically using the technique of amplitude amplification. In its simplest form, to find some marked elements from a list of $N=2^n$ entries, the algorithm starts with a uniform quantum superposition of all $2^n$ basis states of an $n$-qubit register. It then amplifies the amplitudes of the searched state and reduces those of the other states, such that a measurement of the $n$ qubits leads to one of the searched states with high probability.

Grover's algorithm has been used to obtain quantum speedups for various problems in combinatorial optimization and computer science (see, for e.g., <cit.>). Needless to say, graph coloring problems are also not an exception in the literature, and have been attacked using quantum annealing <cit.>, hybrid approaches <cit.>, as well as using Grover search <cit.>.

In <cit.>, a qutrit-based approach has been used to demonstrate the cost-efficiency of ternary quantum logic; however, their main algorithm is not realizable right now on NISQ devices. The algorithm of <cit.> has the same issue as it requires quantum RAM which has not been realized at this moment.
On the other hand, the authors of <cit.> and <cit.> demonstrate a quantum algorithm solving the $k$-coloring problem on NISQ devices, comparing the efficiency of their algorithm against the reduction of 3-SAT to 3-coloring approach of Hu et. al. <cit.>.

All of these algorithms use an oracle design which uses binary comparators, and provide solutions where almost all binary strings have positive probabilities of being selected, including those that do not represent valid colorings. Our approach circumvents this problem via a modified initialization and diffusion operator that restricts the evolution of the quantum algorithm to the only $\prod_{v\in L_v}|L_v|$ plausible states. Note that this is the total number of valid colorings when the underlying graph is empty. We achieve this via the restricted version of Grover search <cit.>.

Let $S\subseteq \{1,2,\ldots, 2^n-1\}$, and suppose $S'\subsetneq S$ is a set of marked states. Let $O$ be an oracle that marks these states and requires $a$ ancillas. Then, there is a quantum circuit on $n+a+1$ qubits which makes $O(\sqrt{2^n/|S'|})$ queries, which when measured, gives one of the marked states with high probability. Further, states outside $S$ are never measured.

Additionally, we use an oracle design different from those in <cit.>, and give a classical algorithm in Section 3 that can reduce the complexity of this oracle in several special cases (such as for the $3$-coloring or $4$-coloring problems). As a corollary of Proposition <ref>, our main theorem provides an algorithm for the list coloring problem.

Given a graph $G=(V,E)$ on $n$ vertices and $m$ edges and lists of available colors $\{L_v: v\in V\}$, there exists a $(\sum_{v\in V}\lceil\log_2 \max L_v\rceil+m+1)$-qubit quantum algorithm with query complexity $O(\prod_{v\in V}(\max L_v)^{1/2})$ that returns a valid list coloring of $G$ with high probability.

This paper is organized as follows. In Section 2, we describe Grover's algorithm and a gate-level implementation. Section 3 is devoted to tackling the list coloring problem, and proves Theorem <ref>. In Section 4, we run experiments on classical simulators as well as real quantum machines, and compare the outcomes. We discuss applications and provide concluding remarks in Section 5.

§ GROVER'S ALGORITHM

In this section, we provide a concise exposition on Grover search.
The main idea behind Grover search is to amplify the amplitudes of some number of marked states (states which are being searched for), and consequentially decrease that of unmarked states.
Grover's Algorithm requires three different operators: Initialization, Oracle, and Diffusion. Below we present two formulations of the algorithm:

§.§ Unrestricted search space

When searching for a marked state among the full search space $S=\{0,1\}^n$, the initialization step of the algorithm creates a uniform superposition of all the possible states of an $n$-qubit system. This is achieved via appending Hadamard gates on each qubit:

\[H^{\otimes n}\lvert 0\rangle_n = \lvert +\rangle^{n} = \frac{1}{\sqrt{2^n}}\sum_{i=1}^n \lvert i\rangle_n.\]

Here we abuse notation and write $\lvert i\rangle_n$ to denote the state corresponding to an $n$-digit binary representation of $i$.

Next, Grover's Algorithm requires an oracle $O$ that, given a uniform superposition of all $2^n$ possible states, can change the sign of the marked states. Let $S'\subseteq \{0,1,\ldots 2^n-1\}$ be a set of marked states. The Oracle $O$ then switches the signs of the states in $S'$, i.e.

\[
O\lvert i\rangle_n = \left\{\begin{array}{cl} \lvert i\rangle_n, &i\not\in S \\ - \lvert i\rangle_n, & i\in S.\end{array}\right.
\]

The circuit implementation of the oracle $O$ usually is the most difficult (and computationally expensive) part of the algorithm, and one of the most basic implementations requires the usage of phase kickback <cit.>.

The final component of Grover's Algorithm is the diffusion operator $D$, which can be thought of as a reflection around the vector $\lvert 0\rangle^{n}$.
As an operator, we have

\[
D = 2\lvert 0\rangle_n\langle 0\rvert_n  - I.
\]

$D$ is usually implemented using phase kickback in the same fashion as the oracle $O$.

Grover's algorithm requires repeated usage of the operator $G = H^{\otimes n} D H^{\otimes n} O$ which has the net effect of reflecting around $\lvert +\rangle^n$, amplifying the amplitudes of marked states and decreases those of other states.
Measuring the state $G^rH^{\otimes n} \lvert 0\rangle_n$ ($r\ge 1$) gives one of the marked states with high probability, and this probability is maximum when $r = \lfloor\frac{\pi}{4}\sqrt{2^n/|S'|}\rfloor$.
Since $|S'|$ is not known in general, the $r$ is either randomly selected <cit.>, or is estimated using quantum counting algorithms <cit.>.

See Figure <ref> for an example of a circuit implementing unrestricted Grover search with $n=3$, $S'=\{\lvert 010\rangle_n, \lvert 011\rangle_n\}$, $S = \{0,1,\ldots, 7\}$.

\[
\Qcircuit @C=1em @R=1em {
&\qquad \mbox{Init} & & & &\ \ \ \mbox{Grover Operator} & & & & \\
\lstick{\ket{0}} & \gate{H} & \qw & \ctrlo{1} & \ctrlo{1}& \gate{H} & \ctrlo{1} & \gate{H}&\meter &\cw \\
\lstick{\ket{0}} & \gate{H}      & \qw   & \ctrl{1}       & \ctrl{1} & \gate{H} & \ctrlo{1} & \gate{H}&\meter&\cw \\
\lstick{\ket{0}} & \gate{H}      & \qw        & \ctrlo{1}  & \ctrl{1} & \gate{H} & \ctrlo{1} & \gate{H}&\meter &\cw \\
\lstick{\ket{0}} & \gate{H}      & \gate{Z}        & \targ       & \targ & \qw & \targ &\qw &\qw & \qw \gategroup{2}{2}{5}{3}{.7em}{.} \gategroup{2}{4}{5}{8}{.7em}{.}
\]

In a standard circuit implementation of Grover search, the initialization is achieved by the Hadamard operator $H^{\otimes 3}$. Phase kickback from the fourth qubit initialized to the state $\lvert -\rangle$ is used to negate the amplitudes of $\lvert 010\rangle$ and $\lvert 011\rangle$. Finally, diffusion is achieved via another phase kickback from the same qubit.

An example Grover search implementation

§.§ Restricted search space

Let us now consider a search space $S\subsetneq \{0,1\}^n$. In this case, the algorithm is designed to only evolve over the states of $S$, and this is achieved via an initialization operator $A$ such that

\[
A\lvert 0\rangle_n = \frac 1{\sqrt{|S|}}\sum_{i\in S}\lvert i\rangle_n,
\]

And the Grover operator is changed to a reflection around $A\lvert 0\rangle_n$ instead of $\lvert +\rangle^n$:

\[
G = ADA^{\dagger}O.
\]

The usage of $ADA^{\dagger}$ instead of $H^{\otimes n}DH^{\otimes n}$ makes sure that the evolution of the quantum states remains in the subspace spanned by $S$ instead of the entire space $\{0,1\}^n$, and this leads to probability distribution of the measured outcomes being supported on the state $S$.

The only detail missing in this formulation is the construction of the initialization operator $A$. As we shall see in Section 3, for graph coloring problems (and most applications in general), $A$ can be represented as a block matrix and can be implemented in time linear in the number of qubits.

We make a remark here that the graph coloring algorithm of <cit.> uses the unrestricted formulation of Grover's algorithm, but modifies the oracle to discard states that represent invalid colorings. On the other hand, they do not modify their diffusion operator, leading to states outside the search space having positive probabilities of being measured.

§ QUANTUM LIST COLORING ALGORITHM

Our goal in this section is to prove Theorem <ref>.
For the remainder of this section, assume that $G=(V,E)$ is an arbitrary graph with $|V|=n$, $|E|=m$.
Further, for every vertex $v$, let $L_v$ denote the list of admissible colors for vertex $v$.
As our algorithm is based on Grover search, we shall discuss the four basic steps of the algorithm: circuit setup, initialization, oracle and diffusion, each in their respective subsections.

§.§ Setup and qubit labels

Our algorithm design requires three different qubit registers:

* A vertex register to keep track of vertex colors. For each vertex $v$, we require the usage of $\lceil\log_2 \max L_v\rceil$ qubits to represent each color in $L_v$.
Let us denote $j_v := \lceil\log_2 \max L_v\rceil$, and let the qubits corresponding to vertex $v\in V$ be labeled by $q_{v}^{1},\ldots,q_v^{j_v}$.

* An edge register consisting of $m$ qubits, one corresponding to each edge.
Let $q'_{uv}$ denote the qubit corresponding to an edge $uv\in E$.

* A single qubit ancilla register, used for phase kickback in Grover's algorithm. Let $q^\ast$ denote this ancilla.

The total number of qubits required is $\sum\limits_{v\in V}j_v + m + 1$.
Now we take a closer look at our list coloring algorithm.

§.§ Initialization

For each $v\in V$, we initialize qubits $q_v^1,\ldots,q_v^{j_v}$ to a uniform superposition $\chi_v = \frac1{\sqrt{|L_v|}}\sum_{i\in L_v}\lvert i\rangle$. This can be achieved via a unitary operator $U_v$ such that

\[
U_v\lvert 0\rangle = \frac1{\sqrt{|L_v|}}\sum_{i\in L_v}\lvert i\rangle.
\]

We show one way of constructing the operator $U_v$. First, consider the standard basis $B = \{\lvert i\rangle: i\in \{0,1,\ldots,2^{v_j}-1\}\}$. We shall replace any one entry $\lvert i\rangle$ with $\chi_v$, where $i\in L_v$: let $B' = \{\chi_v\}\bigcup (B\setminus \{\lvert i\rangle\})$. It can be seen that $\text{Span}(B)=\text{Span}(B')$. We can now consider $B'$ as an ordered basis with its first entry as $\chi_v$, and apply the Gram-Schmidt process to turn $B'$ into an orthonormal basis $B''$ <cit.>. Note that as $\|\chi_v\|=1$, it remains unchanged in $B''$. The transpose of the coefficients of the vectors in $B''$ constitutes a change of basis operator that maps $\lvert 0\rangle$ to $\chi_v$, and this is how one can construct the matrix for $U_v$.
It can then be implemented with quantum gates using the results of <cit.> for example.

For the sake of clarity of the above procedure, let us consider an example with $j_v=2$ and $L_v=\{1,2,3\}$. Note that $\chi_v=\frac1{\sqrt3}(\lvert 1\rangle + \lvert 2\rangle + \lvert 3\rangle)$. Then, $B=\{\lvert 0\rangle, \lvert 1\rangle, \lvert 2\rangle, \lvert 3\rangle\}$, and we can take $B' = \{\chi_v, \lvert 0\rangle, \lvert 1\rangle, \lvert 2\rangle\}$. After the Gram-Schmidt process, we obtain

\[
\textstyle B'' = \left\{\frac1{\sqrt3}\lvert1\rangle+\frac1{\sqrt3}\lvert2\rangle+\frac1{\sqrt3}\lvert3\rangle,\ \lvert 0\rangle,\ \frac {\sqrt2}{\sqrt3}\lvert 1\rangle -\frac1{\sqrt6}\lvert 2\rangle -\frac 1{\sqrt6}\lvert3\rangle,\ \frac1{\sqrt2}\lvert2\rangle+\frac1{\sqrt2}\lvert3\rangle \right\}.
\]

Hence, in this case, we get

\[U_v = \begin{bmatrix}0 & \frac1{\sqrt3} & \frac 1{\sqrt3} & \frac1{\sqrt3}\\1&0&0&0\\0&\frac{\sqrt2}{\sqrt3}&-\frac1{\sqrt6}&-\frac1{\sqrt6}\\0&0&\frac1{\sqrt2}&\frac1{\sqrt2}\end{bmatrix}^\top.\]

Observe that by construction, $U_v\lvert 0\rangle = U_v\begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix}^\top = \begin{bmatrix}0 & \frac1{\sqrt3} & \frac 1{\sqrt3} & \frac1{\sqrt3}\end{bmatrix}^\top$, as desired.

Finally, let us denote $A = \bigotimes\limits_{v\in V}U_v$.

\begin{equation}
\label{eq:init-A}
A \otimes \bigotimes\limits_{e\in E} I\otimes ZH
\end{equation}

is the full initialization operator applied to the circuit starting from
$\lvert 0\rangle_{\sum_{v\in V}j_v}\otimes \lvert 0\rangle_m\otimes\lvert0\rangle$.
This creates the quantum state $\bigotimes\limits_{v\in V}\chi_v \otimes \lvert 0\rangle_m \otimes \lvert -\rangle$.

§.§ Oracle

Traditionally for the graph coloring problem, each vertex color is represented using the same number of qubits, and binary comparator circuits <cit.> are used to make sure that the two colors corresponding to two adjacent vertices are different.

While this approach is very efficient for the $k$-coloring problem where every vertex has the same set of admissible colors, the list coloring problem may sometimes require a large number of qubits. In fact, the total number of qubits required for implementing a comparator-based oracle would be $n\cdot\max_{v\in V}j_v + m + 1$, which can be much higher than our proposed oracle when the $j_v$'s are not all equal.

In short, for every edge $uv\in E$, we shall encode all possible colorings in $L_u\times L_v$ via flipping the amplitudes of the states corresponding to valid colorings $\{\lvert i_1\rangle_{j_u}\lvert i_2\rangle_{j_v}: i_1\in L_u, i_2\in L_v, i_1\neq i_2\}$. We propose a classical $O(|L_u|^2|L_v|^2)$-time algorithm to construct an efficient oracle $O_{u,v}$ for flipping these amplitudes. In short, $O_{u,v}$ should have the following net effect:

\begin{equation}
\label{eq:oracleReq}
O_{u,v}\left(\frac1{\sqrt{|L_u||L_v|}}\sum_{i_1\in L_u, i_2\in L_v}\lvert i_1\rangle \lvert i_2\rangle\lvert -\rangle\right) = \frac1{\sqrt{|L_u||L_v|}} \left(\sum_{\stackrel{i_1\in L_u, i_2\in L_v}{i_1\neq i_2}}-\lvert i_1\rangle \lvert i_2\rangle + \sum_{i\in L_u\cap L_v}\lvert i\rangle\lvert i\rangle\right)\lvert -\rangle
\end{equation}

Given a string $s$ of length $\ell$ and a subset $J=\{j_1,j_2,\ldots,j_r\}\subseteq \{1,2,\ldots,\ell\}$ we use $s_J$ to denote the substring $s_{j_1}s_{j_2}\ldots s_{j_r}$. $\bbF_2$ denotes the finite field of two elements. Our algorithm for implementing $O_{u,v}$ (Algorithm  <ref>) makes use of a subroutine called <ref> that can significantly simplify the complexity and the number of controlled not operations required in many cases.

Sets $L_u$, $L_v$ (denote $j_u = \lceil \log_2\max L_u\rceil$, $j_v = \lceil \log_2\max L_v\rceil$).
A $j_u+j_v+1$-qubit quantum circuit $O_{u,v}$ satisfying (<ref>).
Oracle $O_{u,v}$ for marking valid colorings.
Let $W'=\text{oracleReduction}(L_u, L_v)$
Create a circuit $C$ with quantum wires $q_1,\ldots, q_{j_u+j_v+1}$
every pair $(J,s)$ in $W'$
Add a multicontrolled NOT gate to $C$ with controls on wires $\{q_j: j\in J, s_j=1\}$, anticontrols on wires $\{q_j: j\in J, s_j=0\}$ and target $q_{j_u+j_v+1}$.

Sets $L_u$, $L_v$.
A set of pairs $W'$.
oracleReduction($L_u$, $L_v$)
Denote $j_u = \lceil \log_2\max L_u\rceil$, $j_v = \lceil \log_2\max L_v\rceil$
Convert each entry of $L_u$ and $L_v$ into $\{0,1\}$-strings of lengths $j_u$ and $j_v$, respectively
Let $X=\{ab: a\in L_u, b\in L_v, a\neq b\}$, where “ab" denotes concatenation
Let $Y=\{ab: a\in L_u. b\in L_v\}$, then $|Y|=|L_u||L_v|$
Set $W=\varnothing$
$k=1$ $j_u+j_v$
every $k$-element subset $J$ of $\{1,2,\ldots,j_u+j_v\}$
every $\{0,1\}$-string $s$ of length $k$
Add a $\{0,1\}$-variable $x_J^s$ to $W$

Create an empty linear system of equations $\mathcal L$ over $\bbF_2$ with variables $W$
every $\{0,1\}$-string $t\in Y$
Calculate the expression $f(W,t) = \sum \{x_J^s\in W: t_{J} = s\}$
$t\in X$
Add $f(W,t)=1$ to $\mathcal L$

Add $f(W,t)=0$ to $\mathcal L$

Solve the $|L_u||L_v|\times \sum_{j=1}^k\binom{j_u+j_v}{j}\cdot 2^j$ system $\mathcal L$ using Gaussian Elimination over $\bbF_2$
the system $\mathcal L$ is solvable
Solve the linear program minimizing $\sum_{x_J^s\in W} |J|\cdot x_J^s$ subject to $\mathcal L$
Let $W'=\{(J,s) : x_J^s\in W, x_J^s = 1\}$

We shall now demonstrate the correctness of Algorithm <ref>.

Algorithm <ref> gives a circuit $C$ satisfying (<ref>). Further, if the cost of implementing a $k$-controlled NOT operation is $k$, then the cost of $C$ is the smallest among all circuits that can be made using only controlled NOT operations onto the phase flip qubit.

It is sufficient to verify the action of $C$ on the states $\lvert i_1\rangle \lvert i_2\rangle \lvert -\rangle$, where $i_1\in L_u$ and $i_2\in L_v$.
Notice that a single controlled NOT gate corresponding to a pair $(J,s)$ in $C$ effectively flips the amplitudes of all basis states represented by $\{0,1\}$-strings $x$ of length $j_u+j_v$ for which $x_i=s_i$, $i\in J$.
In other words, all states of the following form are flipped (here $\ast$ denotes a wildcard, and $J=\{j_1,\ldots, j_k\}$, $s=s_1\cdots s_k$):

\[
\lvert \ast\cdots\ast \underset{j_1\text{'th}}{s_1} \ast\cdots \ast \underset{j_2\text{'th}}{s_2}\cdots \underset{\cdots}{\cdots}\cdots \underset{j_k\text{'th}}{s_{k}}\ast \cdots \ast\rangle
\]

Thus, after application of all the controlled NOT gates, only states which appeared in an odd number of $(J,s)$-pairs in $W'$ will survive, and those appearing an even number of times will not have their amplitudes flipped.

Let us now fix a string $t = t_1t_2\cdots t_{j_u+j_v}$, where $t_1\cdots t_{j_u}\in L_u$ and $t_{j_u+1}\cdots t_{j_u+j_v}\in L_v$, and analyze the function <ref> closely. Recall that $Y=\{ab: a\in L_u, b\in L_v\}$ and $X=\{ab:a\in L_u, b\in L_v, a\neq b\}$.
We now make a crucial observation: the number of times the amplitude of $\lvert t\rangle$ gets flipped by $C$ is

\[
\left|\left\{	(J,s)\in W': t_J=s	\right\}\right| = \left|\left\{	x_J^s\in W: x_J^s=1, t_J=s	\right\}\right| = f(W,t),
\]

As $x_J^s$ are all $\{0,1\}$-valued. Since the linear system $\mathcal L$ over $\bbF_2$ exactly contains the equations $f(W,t)=1$ if $t\in X$ and $f(W,t)=0$ if $t\in Y\setminus X$, any solution to the system $\mathcal L$ will give a correct circuit satisfying (<ref>).

Now we come to the second assertion of the theorem. Note that for each variable $x_J^s\in W$ with $x_J^s=1$, we require a $|J|$-controlled NOT operation onto the phase flip ancilla. This means that the cost of $C$ is exactly $\sum_{x_J^s\in W} |J|\cdot x_J^s$. As we have minimized this cost via a linear program in Step 19 of <ref>, this proves the second claim.

We now have all the ingredients required to implement our full oracle, which is presented as Algorithm <ref> below.
Graph $G=(V,E)$, lists $\{L_v:v\in V\}$, and a $\sum_{v\in V}j_v + m +1$-qubit quantum circuit $C$.
$C$ appended with a graph coloring oracle $O$.
Full oracle $O$ for marking valid list colorings
every edge $uv\in E$
Apply Oracle $O_{u,v}$ on qubits $q_u^1,\ldots, q_u^{j_u}$, $q_v^1,\ldots, q_v^{j_v}$, $q'_{uv}$ of $C$

Apply a controlled NOT operation with controls $q'_{\ast}$ and target $q^\ast$
every edge $uv\in E$
Apply Oracle $O_{u,v}$ on qubits $q_u^1,\ldots, q_u^{j_u}$, $q_v^1,\ldots, q_v^{j_v}$, $q'_{uv}$ to de-entangle the vertex register of $C$

§.§ Diffusion

Our diffusion operator is very straightforward, and is a direct application of the restricted search space diffusion mentioned in section 2.2. Let $A$ be the initialization operator we implemented in (<ref>), then a diffusion is achieved by $A D A^\dagger$, where $D=2\lvert 0\rangle\langle 0\rvert - I$ can be implemented by a controlled NOT with anticontrols on each of the vertex qubits and target the phase flip ancilla.

Refer to Figure <ref> for an illustration of the full list coloring algorithm.

\[
\Qcircuit @C=1em @R=.7em {
& &\mbox{\footnotesize Initialization  }\qquad & & & &\mbox{\footnotesize Grover Operator  } & & & & & \\
\lstick{} &\qw & \multigate{2}{U_{v_1}} &\qw &\multigate{10}{\mbox{Oracle O}} &\qw & \multigate{2}{U_{v_1}^\dagger}& \qw &\ctrlo{1}&\qw & \multigate{2}{U_{v_1}}&\qw&\meter&\cw \\
\lstick{} &\qw & \ghost{U_{v_1}}        &\qw &\ghost{\mbox{Oracle O}} &\qw & \ghost{U_{v_1}^\dagger}& \qw &\ctrlo{1} &\qw & \ghost{U_{v_1}}&\qw&\meter&\cw \\
\lstick{} &\qw & \ghost{U_{v_1}}        &\qw &\ghost{\mbox{Oracle O}} &\qw &\ghost{U_{v_1}^\dagger} &\qw &\ctrlo{0}&\qw &\ghost{U_{v_1}}&\qw&\meter&\cw \inputgroupv{2}{4}{.8em}{.8em}{\ket{0}_{j_1}} \\
\lstick{} & &\cdots               &    &\ghost{\mbox{Oracle O}} &\qw & \cdots & &\vdots& & & & &\qquad \inputgroup{4}{5}{1em}{\vdots\qquad} \\
\lstick{} &\qw & \multigate{2}{U_{v_n}} &\qw &\ghost{\mbox{Oracle O}} &\qw &\multigate{2}{U_{v_n}^\dagger} & \qw & \ctrlo{1}&\qw& \multigate{2}{U_{v_n}}&\qw &\meter&\cw \\
\lstick{} &\qw & \ghost{U_{v_n}}        &\qw &\ghost{\mbox{Oracle O}} &\qw &\ghost{U_{v_n}^\dagger} & \qw & \ctrlo{1}&\qw & \ghost{U_{v_n}}&\qw&\meter&\cw \\
\lstick{} &\qw & \ghost{U_{v_n}}        &\qw &\ghost{\mbox{Oracle O}} &\qw &\ghost{U_{v_n}^\dagger} & \qw & \ctrlo{4}&\qw& \ghost{U_{v_n}}&\qw&\meter&\cw\inputgroupv{6}{8}{.8em}{.8em}{\ket{0}_{j_n}} \\
\lstick{} &\qw & \qw                    &\qw &\ghost{\mbox{Oracle O}} &\qw &\qw &\qw &\qw&\qw& \qw&\qw & \qw&\qw \\
\lstick{} &\qw & \qw                    &\qw &\ghost{\mbox{Oracle O}} &\qw &\qw &\qw &\qw &\qw & \qw &\qw& \qw&\qw \\
\lstick{} &\qw & \qw                    &\qw &\ghost{\mbox{Oracle O}} &\qw &\qw &\qw &\qw &\qw & \qw&\qw& \qw&\qw \inputgroupv{9}{11}{.8em}{.8em}{\ket{0}_{m}} \\
\lstick{\ket{0}} &\gate{H} & \gate{Z}                    &\qw &\ghost{\mbox{Oracle O}} &\qw &\qw &\qw &\targ &\qw &\qw&\qw& \qw&\qw \gategroup{2}{2}{12}{3}{.7em}{^)} \gategroup{2}{5}{12}{11}{.7em}{^)} \\
\]

Outline of our list coloring circuit for a single Grover iteration.

§ RESULTS

We implement our list coloring algorithm in  using .
In order to gauge the efficiency of our result, we run experiments for the $3$ and $4$-coloring problems used in <cit.> on the the Amazon Statevector simulator.

§.§ 3-coloring $K_3$

$3$-coloring the triangle graph $G=(\{1,2,3\},\{12,23,13\})$ is equivalent to the list-coloring problem on $G$ with $L_1=L_2=L_3=\{\lvert01\rangle, \lvert10\rangle, \lvert11\rangle\}$. In this case, our initialization operator $U_v$ and oracle component $O_{uv}$ obtained from Algorithm <ref> are:

\[
\begin{array}{ccc}
U_v & = &  \Qcircuit @C=.7em @R=.7em {
\lstick{} & \gate{R_y(\arcsin\sqrt{2/3})} & \qw & \qw & \qw & \ctrl{1} & \qw & \qw & \qw & \qw &\qw \\
\lstick{} &\qw & \gate{S} & \gate{H} & \gate{T} & \targ & \gate{T^\dagger} & \gate{H} & \gate{S^\dagger} & \gate{X} & \qw \\
\end{array} \mbox{ ; }
\begin{array}{ccc}
O_{uv} & = &  \Qcircuit @C=.7em @R=.7em {
\lstick{} & \qw & \ctrl{3} & \qw & \qw \\
\lstick{} & \qw & \qw & \ctrl{1} & \qw \\
\lstick{} & \qw & \qw & \ctrl{2} & \qw \\
\lstick{} &\qw  & \ctrl{1} & \qw & \qw \\
\lstick{} & \qw & \targ  & \targ & \qw \\
\end{array}.
\]

Each Toffoli gate can be decomposed into two-qubit gates using the standard decomposition:

\[
\begin{array}{ccc}
\Qcircuit @C=.7em @R=1.7em {
\lstick{} & \ctrl{1} & \qw\\
\lstick{} & \ctrl{1} & \qw\\
\lstick{} & \targ    & \qw\\
}\qquad &\stackrel{\qquad}{=} \qquad
&\Qcircuit @C=.7em @R=.7em {
\lstick{} & \qw      & \qw     &\qw             &\ctrl{2}&\qw     &\qw      & \qw    &\ctrl{2}   & \qw             &\ctrl{1} & \qw & \ctrl{1} & \gate{T} & \qw \\
\lstick{} & \qw      & \ctrl{1}&\qw             &\qw     &\qw     &\ctrl{1} & \qw         &\qw   & \gate{T^\dagger}&\targ & \gate{T^\dagger} & \targ & \gate{S} & \qw\\
\lstick{} & \gate{H} & \targ   &\gate{T^\dagger}&\targ   &\gate{T}&\targ &\gate{T^\dagger}&\targ & \gate{T}        &\gate{H}& \qw & \qw & \qw  & \qw\\
\end{array}.
\]

To implement a  gate, we use a clean ancilla qubit to reduce circuit depth as demonstrated below:

\[
\begin{array}{ccc}
\Qcircuit @C=.7em @R=1.2em {
\lstick{} & \ctrl{1} & \qw\\
\lstick{} & \ctrl{1} & \qw\\
\lstick{} & \ctrl{1} & \qw\\
\lstick{} & \targ    & \qw\\
}\qquad &\stackrel{\qquad}{=} \qquad
&\Qcircuit @C=.7em @R=1.2em {
\lstick{}            & \ctrl{1} & \qw      &\ctrl{1}&\qw\\
\lstick{}            & \ctrl{3} & \qw      &\ctrl{3}&\qw\\
\lstick{}            & \qw      & \ctrl{1} & \qw    &\qw\\
\lstick{}            & \qw      & \targ    & \qw    &\qw\\
\lstick{\lvert 0\rangle} &\targ & \ctrl{-1}& \targ  &\qw
\end{array}
\]

Finally, we are able to run our circuit on the Amazon Statevector Simulator after decomposing into these elementary single and two-qubit operations. Our resulting histogram is shown in Figure <ref>.

[col sep=semicolon,]3coloringK3.csv
bar width=.3cm,
ymin = 0,
xticklabels from table=State,
x tick label style=font=, rotate=90, anchor=east,
ytick = 0,0.1,0.2,
ylabel=Observed Probability]
table [x expr=, y=Probability];

Observed frequencies for 2000 shots for 3-coloring $K_3$.

It is seen that the states $\lvert 011011\rangle, \lvert 011110\rangle, \lvert 100111\rangle, \lvert 101101\rangle, \lvert 110110\rangle, \lvert 111001\rangle$ are all massively amplified. A theoretical calculation of the statevector shows that each of these states have a probability of $0.165066$ of being measured, whereas states representing colorings outside $\{\lvert 01\rangle,\lvert 10\rangle, \lvert 11\rangle\}^3$ have probability $0$ of being measured. After a single Grover iteration, we therefore improve upon the results of <cit.>.

§.§ 4-coloring $K_4$

Let $G=\{\{1,2,3,4\},\{12,13,14,23,24,34,14\}$ be the complete graph on $4$ vertices, and suppose $L_1=L_2=L_3=L_4 = \{\lvert 00\rangle, \lvert 01\rangle, \lvert 10\rangle, \lvert 11\rangle\}$.
In this case the simple Hadamard operator $H^{\otimes 2}$ initializes each vertex register to a uniform superposition of its valid colors, and we can then run Algorithm <ref> to figure out the component $O_{uv}$. It turns out that one of the valid solutions minimizing the cost of gates used is the following circuit:

\[
\begin{array}{ccc}
O_{uv} & = &  \Qcircuit @C=.7em @R=.7em {
\lstick{} & \qw & \ctrl{3} & \qw & \ctrlo{1} & \qw     & \qw \\
\lstick{} & \qw & \qw & \ctrl{1} & \ctrlo{3} & \qw     & \qw \\
\lstick{} & \qw & \qw & \ctrl{2} & \qw       &\ctrlo{1}& \qw \\
\lstick{} &\qw  & \ctrl{1} & \qw & \qw       &\ctrlo{1}& \qw \\
\lstick{} & \qw & \targ  & \targ & \targ     &\targ    & \qw \\
\end{array}.
\]

Figure <ref> shows the results of running our circuit on the statevector simulator.

[col sep=semicolon]4coloringK4.csv
bar width=.3cm,
ymin = 0,
xticklabels from table=State,
x tick label style=font=, rotate=90, anchor=east,
ytick = 0,0.025,0.05,
ylabel=Observed Probability]
table [x expr=, y=Probability];

Observed frequencies for 2000 shots for 4-coloring $K_4$.

In this case, a statevector computation shows that each of the $4!=24$ states corresponding to valid colorings of $K_4$ has a theoretical probability of $0.041657$ of being measured, whereas the same for every unmarked state is approximately $10^{-6}$. The result of our experiment also follows this distribution.

We also ran our circuits on the IonQ physical device, however, reasonable results were not obtained due to the limitations of current quantum computers.

§ APPLICATIONS AND CONCLUDING REMARKS

The list coloring problem is ubiquitous in real life, as it not only generalizes an already well-appearing problem of graph coloring (scheduling, satisfiability etc.), but is also applicable to several other scenarios, such as:

* Wireless network Allocation <cit.>:  Consider a wireless network. Assume that due to hardware restrictions, each radio in the network has a limited set of frequencies through which it can communicate. Also assume radios within a certain distance of each other cannot operate on the same frequency without their transmissions interfering with each other. This problem can be modeled in terms of list-coloring by representing the radios by vertices, and joining them by edges if their corresponding radios are within a certain distance of each other. The lists for each vertex can be assigned according to the available frequencies for its corresponding radio.

* Register Allocation: In compiler optimization, register allocation is the process of assigning a large number of target program variables ($n$) onto a small number of CPU registers ($k$), which reduces to a $k$-coloring problem on an $n$-vertex graph.

* Sudoku: We can represent every cell in a sudoku problem with a vertex, and join two vertices with an edge if they are in same row or same column or same block. Given $x$ already filled cells, we can formulate the sudoku problem as a list-coloring problem on $81-x$ vertices and at most $9$ colors.

We proposed a Grover search-based quantum algorithm that achieves quadratic speedup in query complexity compared to a classical brute force search, and also proposed a classical algorithm that can simplify the oracle design for several special instances of the list coloring problem. We demonstrate the efficiency of our method in comparison with previous work by running our algorithm on the Amazon statevector simulator for the $3$ and $4$-coloring problems.

Unfortunately, the list coloring problem is difficult to solve both classically and using quantum algorithms, as for generic lists with no known structure, brute force seems to be the only way to attack the problem. As our algorithm is basically a brute force quantum search with some optimizations in the oracle, we perform better in general cases where the structure of the lists are unknown. However, the existence of clever hybrid algorithms exploiting specific structures for known lists cannot be ignored, and is a very promising future direction.

Finally, we note that one can obtain improvements on our algorithm by just changing a given list coloring problem to a reduced problem. For example, if $G=(V,E)$ has a vertex $v$ with $|L_v|=1$, we can color $v$ first and remove its color from each $L_u$ such that $uv\in E$. Secondly, we can remap admissible colors to ensure that the lists are as compactly represented as possible, leading to lower qubit requirement for our algorithm.

Part of this work was completed during a summer internship at Elyah Co. in 2020. The author is grateful to Sydney Andrews, Yūichirō Minato, Ryūtarō Nagai and Goutham Rajendran for several helpful discussions and comments.