#  Linear kernels for $k$-tuple and liar’s domination
in bounded genus graphs

Arijit Bishnu
ACM Unit
Indian Statistical Institute
Kolkata, INDIA
<EMAIL_ADDRESS>Arijit Ghosh 111 Supported by the Indo-German Max Planck
Center for Computer Science (IMPECS).
D1: Algorithms & Complexity
Max-Planck-Institut für Informatik
Saarbrücken, Germany
<EMAIL_ADDRESS>Part of this work was done when the author was a visiting
scientist in ACM Unit, Indian Statistical Institute, Kolkata. Subhabrata Paul
ACM Unit
Indian Statistical Institute
Kolkata, INDIA
<EMAIL_ADDRESS>
###### Abstract

A set $D\subseteq V$ is called a _$k$ -tuple dominating set_ of a graph
$G=(V,E)$ if $\left|N_{G}[v]\cap D\right|\geq k$ for all $v\in V$, where
$N_{G}[v]$ denotes the closed neighborhood of $v$. A set $D\subseteq V$ is
called a _liar’s dominating set_ of a graph $G=(V,E)$ if

  * (i) $\left|N_{G}[v]\cap D\right|\geq 2$ for all $v\in V$, and

  * (ii) for every pair of distinct vertices $u,v\in V$, $\left|(N_{G}[u]\cup N_{G}[v])\cap D\right|\geq 3$.

Given a graph $G$, the decision versions of $k$-Tuple Domination Problem and
the Liar’s Domination Problem are to check whether there exists a $k$-tuple
dominating set and a liar’s dominating set of $G$ of a given cardinality,
respectively. These two problems are known to be NP-complete [LC03, Sla09]. In
this paper, we study the parameterized complexity of these problems. We show
that the $k$-Tuple Domination Problem and the Liar’s Domination Problem are
W[2]-hard for general graphs but they admit linear kernels for graphs with
bounded genus.

##### Keywords.

$k$-tuple domination, liar’s domination, planar graphs, bounded genus graphs,
kernelization, and W[2]-hard

##  1 Introduction

Let $G=(V,E)$ be a graph. For a vertex $v\in V$, let $N_{G}(v)=\\{u\in V|uv\in
E\\}$ and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ denote the open and closed
neighborhoods of $v$, respectively. A set $D\subseteq V$ is called a
_dominating set_ of a graph $G=(V,E)$ if $|N_{G}[v]\cap D|\geq 1$ for all
$v\in V$. The _domination number_ of a graph $G$, denoted by $\gamma(G)$, is
the minimum cardinality of a dominating set of $G$. The concept of domination
has been well studied. Depending upon various applications, different
variations of domination have appeared in the literature [HHS98a, HHS98b].

Among different variations of domination, $k$-tuple domination and liar’s
domination are two important and well studied type of domination [HH00, LC02,
LC03, RS09, Sla09]. A set $D\subseteq V$ is called a _$k$ -tuple dominating
set_ of a graph $G=(V,E)$ if each vertex $v\in V$ is dominated by at least $k$
number of vertices in $D$, that is, $|N_{G}[v]\cap D|\geq k$ for all $v\in V$.
The concept of $k$-tuple domination in graphs was introduced in [HH00]. For
$k=2$ and $3$, it is called _double domination_ and _triple domination_
respectively. The _$k$ -tuple domination number_ of a graph $G$, denoted by
$\gamma_{k}(G)$, is the minimum cardinality of a $k$-tuple dominating set of
$G$. It is a simple observation that for the existence of a $k$-tuple
dominating set, we need $\delta(G)\geq k-1$, where $\delta(G)$ is the minimum
degree of $G$. On the other hand, liar’s domination is a new variation of
domination and was introduced in 2009 by Slater [Sla09]. A set $D\subseteq V$
is called a _liar’s dominating set_ of a graph $G=(V,E)$ if the following two
conditions are met:

condition (i)

$|N_{G}[v]\cap D|\geq 2$ for all $v\in V$

condition (ii)

for every pair of distinct vertices $u,v\in V$, $|(N_{G}[u]\cup N_{G}[v])\cap
D|\geq 3$

In a network guarding scenario, if sentinels are placed in the vertices of the
dominating set, then the graph (network) is guarded. Consider the situation
where a single sentinel is unreliable or lies and we do not know the exact
sentinel that lies. We then need a liar’s dominating set to guard the network.
The _liar’s domination number_ of a graph $G$, denoted by $\gamma_{LR}(G)$, is
the minimum cardinality of a liar’s dominating set of $G$. Formally, the
decision versions of $k$-Tuple Domination Problem and Liar’s Domination
Problem are defined as follows.

$k$-Tuple Domination Problem

_Instance:_ A graph $G=(V,E)$ and a nonnegative integer $p$.

_Question:_ Does there exist a $k$-tuple dominating set of cardinality at most
$p$?

Liar’s Domination Problem

_Instance:_ A graph $G=(V,E)$ and a nonnegative integer $p$.

_Question:_ Does there exist a liar’s dominating set of cardinality at most
$p$?

Note that, every liar’s dominating set is a double dominating set and every
triple dominating set is a liar’s dominating set. Hence, liar’s domination
number lies between double and triple domination number, that is,
$\gamma_{2}(G)\leq\gamma_{LR}(G)\leq\gamma_{3}(G)$.

The rest of the paper is organized as follows. Section $2$ introduces some
pertinent definitions and preliminary results that are used in the rest of the
paper and a brief review on the progress in the study of parametrization for
domination problems. Section $3$ deals with the hardness results of both
$k$-tuple domination problem and liar’s domination problem. In Section $4$, we
show that both $k$-Tuple Domination Problem and Liar’s Domination Problem
admit linear kernel in planar graphs. In Section $5$, we extend the results
for bounded genus graphs. Finally, Section $6$ concludes the paper.

##  2 Preliminaries

Let $G=(V,E)$ be a graph. Let $G[S]$, $S\subseteq V$ denote the induced
subgraph of $G$ on the vertex set $S$. The _distance_ between two vertices $u$
and $v$ in a graph $G$ is the number of edges in a shortest path connecting
them and is denoted as $d_{G}(u,v)$. The degree of a vertex $v\in V(G)$,
denoted by $deg_{G}(v)$, is the number of neighbors of $v$.

###  2.1 Graphs on surfaces

In this subsection, we recall some basic facts about graphs on surfaces
following the discussion in [FT04]. The readers are referred to [MT01] for
more details. A _surface_ $\Sigma$ is a compact $2$-manifold without boundary.
Let $\Sigma_{0}$ denote the sphere $\\{(x,y,z)|~{}x^{2}+y^{2}+z^{2}=1\\}$. A
_line_ and _O-arc_ are subsets of $\Sigma$ that are homeomorphic to $[0,1]$
and a circle respectively. A subset of $\Sigma$ meeting the drawing only in
vertices of $G$ is called _$G$ -normal_. If an O-arc is G-normal, then it is
called a _noose_. The length of a noose is the number of its vertices. The
_representativity_ of $G$ embedded in $\Sigma\neq\Sigma_{0}$ is the smallest
length of a non-contractible noose in $\Sigma$ and it is denoted by _rep
$(G)$_.

The classification theorem for surfaces states that, any surface $\Sigma$ is
homeomorphic to either a surface $\Sigma^{h}$ which is obtained from a sphere
by adding $h$ handles (orientable surface), or a surface $\Sigma^{k}$ which is
obtained from a sphere by adding $k$ crosscaps (non-orientable surface)
[MT01]. The _Euler genus_ of a non-orientable surface $\Sigma$, denoted by _eg
$(\Sigma)$_, is the number of crosscaps $k$ such that $\Sigma\cong\Sigma^{k}$
and for an orientable surface, _eg $(\Sigma)$_ is twice the number of handles
$h$ such that $\Sigma\cong\Sigma^{h}$. Given a graph $G$, Euler genus of $G$,
denoted by eg$(G)$, is the minimum eg$(\Sigma)$, where $\Sigma$ is a surface
in which $G$ can be embedded. The _Euler characteristic_ of a surface $\Sigma$
is defined as $\chi(\Sigma)=2-\textup{eg}(\Sigma)$. For a graph $G$, $\chi(G)$
denotes the largest number $t$ for which $G$ can be embedded on a surface
$\Sigma$ with $\chi(\Sigma)=t$. Let $G=(V,E)$ be a $2$-cell embedded graph in
$\Sigma$, that is, all the faces of $G$ is homeomorphic to an open disk. If
$F$ is the set of all faces, then _Euler’s formula_ tells that
$V-E+F=\chi(\Sigma)=2-\textup{eg}(\Sigma)$.

Next we define a process called _cutting along a noose $N$_. Although the
formal defi is given in [MT01], we follow a more intuitive defi given in
[FT04]. Let $N$ be a noose in a $\Sigma$-embedded graph $G=(V,E)$. Suppose for
any $v\in N\cap V$, there exists an open disk $\Delta$ such that $\Delta$
contains $v$ and for every edge $e$ adjacent to $v$, $e\cap\Delta$ is
connected. We also assume that $\Delta-N$ has two connected components
$\Delta_{1}$ and $\Delta_{2}$. Thus we can define partition of
$N_{G}(v)=N_{G}^{1}(v)\cup N_{G}^{2}(v)$, where $N_{G}^{1}(v)=\\{u\in
N_{G}(v)|uv\cap\Delta_{1}\neq\emptyset\\}$ and $N_{G}^{2}(v)=\\{u\in
N_{G}(v)|uv\cap\Delta_{2}\neq\emptyset\\}$. Now for each $v\in N\cap V$ we do
the following:

  1. 1.

remove $v$ and its incident edges

  2. 2.

introduce two new vertices $v^{1},v^{2}$ and

  3. 3.

connect $v^{i}$ with the vertices in $N_{G}^{i}$, $i=1,2$.

The resulting graph $\mathcal{G}$ is obtained from $\Sigma$-embedded graph $G$
by cutting along $N$. The following lemma is very useful in the proofs by
induction on the genus.

###### Lemma 1

[FT04] Let $G$ be a $\Sigma$-embedded graph and let $\mathcal{G}$ be a graph
obtained from $G$ by cutting along a non-contractible noose $N$. Then one of
the following holds

  * •

$\mathcal{G}$ is the disjoint union of graphs $G_{1}$ and $G_{2}$ that can be
embedded in surfaces $\Sigma_{1}$ and $\Sigma_{2}$ such that
$eg(\Sigma)=eg(\Sigma_{1})+eg(\Sigma_{2})$ and $eg(\Sigma_{i})>0,i=1,2$.

  * •

$\mathcal{G}$ can be embedded in a surface with Euler genus strictly smaller
than eg$(\Sigma)$.

A _planar graph_ $G=(V,E)$ is a graph that can be embedded in the plane. We
term such an embedding as a _plane graph_.

###  2.2 Parameterization and domination

A _parameterized problem_ is a language
$L\subseteq\Sigma^{*}\times\mathds{N}$, where $\Sigma^{*}$ denotes the set of
all finite strings over a finite alphabet $\Sigma$. A parameterized problem
$L$ is _fixed-parameter tractable_ if the question “$(x,p)\in L$” can be
decided in time $f(p)\cdot|x|^{O(1)}$, where $f$ is a computable function on
nonnegative integers, $x$ is the instance of the problem and $p$ is the
parameter. The corresponding complexity class is called FPT. Next we define a
reducibility concept between two parameterized problems.

###### Definition 2

[DF99, Nie06] Let $L,L^{\prime}\subseteq\Sigma^{*}\times\mathds{N}$ be two
parameterized problems. We say that $L$ reduces to $L^{\prime}$ by a _standard
parameterized m-reduction_ if there are functions $p\mapsto p^{\prime}$ and
$p\mapsto p^{\prime\prime}$ from $\mathds{N}$ to $\mathds{N}$ and a function
$(x,p)\mapsto x^{\prime}$ from $\Sigma^{*}\times\mathds{N}$ to $\Sigma^{*}$
such that

  1. 1.

$(x,p)\mapsto x^{\prime}$ is computable in time $p^{\prime\prime}|x|^{c}$ for
some constant $c$ and

  2. 2.

$(x,p)\in L$ if and only if $(x^{\prime},p^{\prime})\in L^{\prime}$.

A parameterized problem is in the class W[i], if every instance $(x,p)$ can be
transformed (in fpt-time) to a combinatorial circuit that has height at most
$i$, such that $(x,p)\in L$ if and only if there is a satisfying assignment to
the inputs, which assigns $1$ to at most $p$ inputs. A problem $L$ is said to
be W[i]_-hard_ if there exists a standard parameterized m-reduction from all
the problems in W[i] to $L$ and in addition, if the problem is in W[i], then
it is called W[i]_-complete_.

Next we define the reduction to problem kernel, also simply referred to as
_kernelization_.

###### Definition 3

[Nie06] Let $L$ be a parameterized problem. By reduction to problem kernel, we
mean to replace instance $I$ and the parameter $p$ of $L$ by a “reduced”
instance $I^{\prime}$ and by another parameter $p^{\prime}$ in polynomial time
such that

  * •

$p^{\prime}\leq c\cdot p$, where $c$ is a constant,

  * •

$I^{\prime}\leq g(p)$, where $g$ is a function that depends only on $p$, and

  * •

$(I,p)\in L$ if and only if $(I^{\prime},p^{\prime})\in L$.

The reduced instance $I^{\prime}$ is called the _problem kernel_ and the size
of the problem kernel is said to be bounded by $g(p)$.

In parameterized complexity, domination and its variations are well studied
problems. The decision version of domination problem is W[2]-complete for
general graphs [DF99]. But this problem is FPT when restricted to planar
graphs [AFN04a] though it is still NP-complete for this graph class [GJ79].
Furthermore, for bounded genus graphs, which is a super class of planar
graphs, domination problem remains FPT [FT04]. It was proved that dominating
set problem possesses a linear kernel in planar graphs [AFN04a] and in bounded
genus graphs [FT04]. Also domination problem admits polynomial kernel on
graphs excluding a fixed graph $H$ as a minor [Gut09] and on $d$-degenerated
graphs [PRS12]. A search tree based algorithm for domination problem on planar
graphs, which runs in $O(8^{p}n)$ time, is proposed in [AFF+05]. For bounded
genus graphs, similar search tree based algorithm is proposed in [EFF04] and
has a time complexity of $O((4g+40)^{p}n^{2})$, where $g$ is the genus of the
graph. Algorithms with running time of $O(c^{\sqrt{p}}n)$ for domination
problem on planar graphs have been devised in [ABF+02, AFN04b, FT03, FT04].
Like domination problem, $k$-Tuple Domination Problem and Liar’s Domination
Problem are both NP-complete [LC03, Sla09] for general graphs. However, these
problems have been polynomially solved for different graph classes [LC02,
LC03, PP13a, PP13b]. But for planar graphs and hence for graphs with bounded
genus, $k$-Tuple Domination Problem remains NP-complete [LC08]. In [Sla09],
though the NP-completeness proof is given for general graphs, it can be
verified that using the same construction one can find the NP-completeness of
Liar’s Domination Problem in planar graphs, see Lemma 26 in Appendix 7.

Some generalization of classical domination problem have been studied in the
literature from parameterized point of view. Among those problems,
$k$-dominating threshold set problem, $[\sigma,\rho]$-dominating set problem
(also known as generalized domination) are generalized version of $k$-tuple
dominating set problem. In [GV08], it is proved that $k$-dominating threshold
set problem is FPT in $d$-degenerated graphs. $[\sigma,\rho]$-domination is
studied in [CP14, TP97, vRBR09]. A set $D$ of vertices of a graph $G$ is
$[\sigma,\rho]$-dominating set if for any $v\in D,|N(v)\cap D|\in\sigma$ and
for any $v\notin D,|N(v)\cap D|\in\rho$ for any two sets $\sigma$ and $\rho$.
It is known that $[\sigma,\rho]$-domination is FPT when parameterized by
treewidth [vRBR09]. By Theorem 32 of [ABF+02], it follows that $k$-tuple
domination is FPT on planar graphs. But there is no explicit kernel for both
$k$-tuple domination and liar’s domination problem in the literature.

There have been successful efforts in developing meta-theorems like the
celebrated Courcelle’s theorem [Cou92] which states that all graph properties
definable in monadic second order logic can be decided in linear time on
graphs of bounded tree-width. This also implies FPT algorithms for bounded
tree-width graph for these problems. In case of kernelization in bounded genus
graphs, Bodlaender et al. give two meta-theorems [BFL+09]. The first theorem
says that all problems expressible in counting monadic second order (CMSO)
logic and satisfying a coverability property admit a polynomial kernel on
graphs of bounded genus and the second theorem says that all problems that
have a finite integer index and satisfy a weaker coverability property admit a
linear kernel on graphs of bounded genus. It is easy to see that both
$k$-tuple and liar’s domination problems can be expressed in CMSO logic. Let
$G=(V,E)$ be an instance of a graph problem $\Pi$ such that $G$ is embeddable
in a surface of Euler genus at most $r$. The basic idea of quasi-coverable
property for $\Pi$ is that there exists a set $S\subseteq V$ satisfying the
conditions of $\Pi$ such that the tree-width of $G\setminus R^{r}_{G}(S)$ is
at most $r$ where $R^{r}_{G}(S)$ is a special type of reachability set from
$S$. In domination type of problems, this reachability set is actually the
whole graph and hence these problems satisfy the quasi-coverable property. The
basic idea of strong monotonicity for a graph problem $\Pi$ is roughly as
follows: Let $\mathcal{F}_{i}$ be a class of graphs $G$ having a specific set
of vertices $S$ termed as the boundary of $G$ such that $|S|=i$. The glued
graph $G=G_{1}\oplus G_{2}$ of $G_{1}$ and $G_{2}$ is the graph which is
obtained by taking the disjoint union of $G_{1}$ and $G_{2}$ and joining $i$
edges between the vertices of the boundary sets. A problem $\Pi$ is said to
satisfy the strong monotonicity if for every boundaried graph
$G=(V,E)\in\mathcal{F}_{i}$, there exists a set $W\subseteq V$ of a specific
cardinality which satisfy the property of $\Pi$ such that for every boundaried
graph $G^{\prime}=(V^{\prime},E^{\prime})\in\mathcal{F}_{i}$ with a set
$W^{\prime}\subseteq V^{\prime}$, satisfying the property of $\Pi$, the vertex
set $W\cup W^{\prime}$ satisfies the property of $\Pi$ for the glued graph
$G=G\oplus G^{\prime}$. It can be verified easily that both $k$-tuple
domination and liar’s domination problems satisfy the strongly monotone
property. The strongly monotone property implies the finite integer index for
these problems. Hence, by the second meta-theorem in [BFL+09], both $k$-tuple
and liar’s domination problems admit linear kernels for graphs on bounded
genus. Though these meta-theorems provide simple criteria to decide whether a
problem admits a linear or polynomial kernel, finding a linear kernel with
reasonably small constants for a specific problem is a worthy topic of further
research [BFL+09]. In this paper, we have obtained linear kernels with small
constants for both the problems on bounded genus graphs. We have also proved
the W[2]-hardness for $k$-tuple and liar’s domination for general graphs.

##  3 Hardness results in general graphs

In this section, we show that $k$-tuple Domination Problem and Liar’s
Domination Problem are W[2]-hard. In [CP14], it is proved that
$[\sigma,\rho]$-domination problem for any recursive sets $\sigma$ and $\rho$
is W[2]-hard. This implies the hardness for $k$-tuple domination in general
graphs. But in this paper, we have come up with a simple W[2]-hardness proof
for $k$-tuple domination in general graphs. To prove this, we show standard
parameterized m-reductions from Domination Problem, which is known to be
W[2]-complete [DF99], to $k$-Tuple Domination Problem and Liar’s Domination
Problem, respectively.

###### Theorem 4

$k$-Tuple Domination Problem is $\mathsf{W[2]}$-hard.

###### Proof.

We show a standard parameterized m-reduction from Domination Problem to
$k$-Tuple Domination Problem. Let $<G=(V,E),p>$ be an instance of Domination
Problem. We construct an instance
$<G^{\prime}=(V^{\prime},E^{\prime}),p^{\prime}>$ of the $k$-Tuple Domination
Problem as follows: $V^{\prime}=V\cup V_{k}$ where
$V_{k}=\\{u_{1},u_{2},\ldots,u_{k}\\}$ and
$E^{\prime}=E\cup\\{v_{i}u_{j}|v_{i}\in V\mbox{ and }u_{j}\in V_{k}\setminus
u_{k}\\}\cup\\{u_{i}u_{j}|u_{i},u_{j}\in V_{k},i\not=j\\}$. Also set
$p^{\prime}=p+k$. The construction of $G^{\prime}$ from $G$ in case of triple
domination is illustrated in Figure 1.

Figure 1: Construction of $G^{\prime}$ from $G$ for triple domination

###### Claim 5

$G$ has a dominating set of size at most $p$ if and only if $G^{\prime}$ has a
$k$-tuple dominating set of size at most $p^{\prime}$.

###### Proof.

Let $D$ be a dominating set of $G$ of cardinality at most $p$ and
$D^{\prime}=D\cup V_{k}$. Each $v_{i}\in V$ is dominated by at least one
vertex from $D$ and by $k-1$ vertices from $V_{k}$. Each $u_{i}\in V_{k}$ is
dominated by $k$ vertices of $V_{k}$. Thus, $D^{\prime}$ is a $k$-tuple
dominating set of $G^{\prime}$ of cardinality at most $p^{\prime}$.

Conversely, let $D^{\prime}$ be a $k$-tuple dominating set of $G^{\prime}$ of
cardinality at most $p^{\prime}$. Note that each $k$-tuple dominating set
contains the set $V_{k}$ because to dominate $u_{k}$ by $k$ vertices we must
select all the vertices of $V_{k}$. Let $D=D^{\prime}\setminus V_{k}$. Clearly
$D\subseteq V$ and $|D|\leq p$. Now for each $v\in V$, $|N_{G}[v]\cap D|\geq
1$ because otherwise, there exists a vertex $v\in V$ such that
$|N_{G^{\prime}}[v]\cap D^{\prime}|=k-1$. This is a contradiction because
$D^{\prime}$ is a $k$-tuple dominating set of $G^{\prime}$. Thus $D$ is a
dominating set of $G$ of cardinality at most $p$.

Hence, $G$ has a dominating set of size at most $p$ if and only if
$G^{\prime}$ has a $k$-tuple dominating set of size at most $p^{\prime}$. ∎

Thus, $k$-Tuple Domination Problem is W[2]-hard. ∎

Next we show the W[2]-hardness of Liar’s Domination Problem.

###### Theorem 6

Liar’s Domination Problem is $\mathsf{W[2]}$-hard.

###### Proof.

We show a standard parameterized m-reduction from Domination Problem to Liar’s
Domination Problem. Let $<G=(V,E),p>$ be an instance of Domination Problem. We
construct an instance $<G^{\prime}=(V^{\prime},E^{\prime}),p^{\prime}>$ of the
Liar’s Domination Problem as follows:
$V^{\prime}=V\cup\\{u,u^{\prime},v,v^{\prime},w\\}$ and
$E^{\prime}=E\cup\\{v_{i}u|v_{i}\in V\\}\cup\\{v_{i}v|v_{i}\in
V\\}\cup\\{uu^{\prime},vv^{\prime},wu,wv\\}$. Also $p^{\prime}=p+4$. The
construction of $G^{\prime}$ from $G$ is illustrated in Figure 2.

Figure 2: Construction of $G^{\prime}$ from $G$

###### Claim 7

$G$ has a dominating set of size at most $p$ if and only if $G^{\prime}$ has a
liar’s dominating set of size at most $p^{\prime}$.

###### Proof.

Let $D$ be a dominating set of $G$ of cardinality at most $p$ and
$D^{\prime}=D\cup\\{u,u^{\prime},v,v^{\prime}\\}$. It is easy to verify that
for each vertex $x\in V^{\prime}$, $|N_{G^{\prime}}[x]\cap D^{\prime}|\geq 2$
and for every pair of vertices $x,y\in V^{\prime}$, $|(N_{G^{\prime}}[x]\cup
N_{G^{\prime}}[y])\cap D^{\prime}|\geq 3$. Hence $D^{\prime}$ is a liar’s
dominating set of $G^{\prime}$ of cardinality at most $p+4=p^{\prime}$.

Conversely, let $D^{\prime}$ be a liar’s dominating set of $G^{\prime}$ of
cardinality at most $p^{\prime}$. Each liar’s dominating set must contain the
set $\\{u,u^{\prime},v,v^{\prime}\\}$ because to doubly dominate $u^{\prime}$
and $v^{\prime}$ we must select the vertices
$\\{u,u^{\prime},v,v^{\prime}\\}$.

Let $X\subseteq V$ denote the set of vertices that are dominated by exactly
two vertices ($u$ and $v$) from $D^{\prime}$. We claim $|X|\leq 1$. If there
exists two such vertices $x,y\in V$, then $|(N_{G^{\prime}}[x]\cup
N_{G^{\prime}}[y])\cap D^{\prime}|=2$ which violates condition (ii) of liar’s
domination. We now deal with two cases:

$|X|=1$:

Let $X=\\{x\\}$. Here $|N_{G^{\prime}}[x]\cap D^{\prime}|=2$. This implies
$w\in D^{\prime}$, otherwise the pair $x$ and $w$ violates condition (ii) of
liar’s domination. We set
$D^{\prime\prime}=(D^{\prime}\setminus\\{w\\})\cup\\{x\\}$. $D^{\prime\prime}$
is also a liar’s dominating set of $G^{\prime}$ of cardinality at most
$p^{\prime}$. Note that all vertices in $V$ is triply dominated by
$D^{\prime\prime}$ and it does not contain $w$.

$|X|=0$:

In this case each vertex of $V$ is triply dominated by $D^{\prime}$. Now if
$w\notin D^{\prime}$, we are done. Otherwise the set
$D^{\prime}\setminus\\{w\\}$ forms a liar’s dominating set of $G^{\prime}$ of
cardinality at most $p^{\prime}$ such that each vertex of $V$ is triply
dominated by $D^{\prime}\setminus\\{w\\}$.

Hence without loss of generality, we assume that there is a liar’s dominating
set $D^{\prime}$ of $G^{\prime}$ of cardinality at most $p^{\prime}$ such that
every vertex in $V$ is triply dominated by $D^{\prime}$ and $w\notin
D^{\prime}$. Let $D=D^{\prime}\setminus\\{u,u^{\prime},v,v^{\prime}\\}$.
Clearly $D\subseteq V$ and $|D|\leq p$. Now for each $x\in V$, $|N_{G}[x]\cap
D|\geq 1$ because otherwise, there exists a vertex $x\in V$ such that for the
pair $x$ and $w$, condition (ii) of liar’s domination is violated. This is a
contradiction because $D^{\prime}$ is a liar’s dominating set of $G^{\prime}$.
Thus $D$ is a dominating set of $G$ of cardinality at most $p$.

Hence, $G$ has a dominating set of size at most $p$ if and only if
$G^{\prime}$ has a liar’s dominating set of size at most $p^{\prime}$. ∎

Thus, Liar’s Domination Problem is W[2]-hard. ∎

##  4 Linear kernels for planar graphs

Having seen that $k$-tuple and liar’s domination are W[2]-hard in general
graphs, we focus on planar graphs in this section and show that they are FPT.

###  4.1 Double domination

In this subsection we show that Double Domination Problem in planar graphs
possesses a linear kernel. Our proof technique uses the region decomposition
idea of Alber et al. [AFN04a]. First we describe the reduction rules for
kernelization.

####  4.1.1 Reduction rule

Let $G=(V,E)$ be the instance for Double Domination Problem. Consider a pair
of vertices $u,v\in V$. Let $N_{G}(u,v)=N_{G}(u)\cap N_{G}(v)$. We partition
the vertices of $N_{G}(u,v)$ in to three parts as follows:

$\displaystyle N^{1}_{G}(u,v)$ $\displaystyle=$ $\displaystyle\\{x\in
N_{G}(u,v)|N_{G}(x)\setminus\\{N_{G}(u,v)\cup\\{u,v\\}\\}\neq\emptyset\\};$
$\displaystyle N^{2}_{G}(u,v)$ $\displaystyle=$ $\displaystyle\\{x\in
N_{G}(u,v)\setminus N^{1}_{G}(u,v)|N_{G}(x)\cap
N^{1}_{G}(u,v)\neq\emptyset\\};$ $\displaystyle N^{3}_{G}(u,v)$
$\displaystyle=$ $\displaystyle N_{G}(u,v)\setminus(N^{1}_{G}(u,v)\cup
N^{2}_{G}(u,v)).$

Reduction Rule: For every pair of distinct vertices $u,v\in V$, if
$N^{3}_{G}(u,v)\neq\emptyset$, then

  * •

delete all the vertices of $N^{2}_{G}(u,v)$ and

  * •

delete all vertices of $N^{3}_{G}(u,v)$ except one vertex.

###### Lemma 8

Let $G=(V,E)$ be a graph and $G^{\prime}=(V^{\prime},E^{\prime})$ be the
resulting graph after having applied the reduction rule to $G$. Then
$\gamma_{2}(G)=\gamma_{2}(G^{\prime})$.

###### Proof.

Let $u,v\in V$ such that $N^{3}_{G}(u,v)\neq\emptyset$. Now if
$N^{2}_{G}(u,v)=\emptyset$ and $|N^{3}_{G}(u,v)|=1$, then $G^{\prime}$ is same
as $G$. So, without loss of generality, assume that
$\left|N^{3}_{G}(u,v)\right|>1$ and $N^{2}_{G}(u,v)\neq\emptyset$. Note that a
vertex $x$ of $N^{3}_{G}(u,v)$ can be doubly dominated by any two vertices
from $N_{G}[x]\subseteq\\{N^{2}_{G}(u,v)\cup N^{3}_{G}(u,v)\cup\\{u,v\\}\\}$.
Again for any two vertices $x,y\in N^{2}_{G}(u,v)\cup
N^{3}_{G}(u,v)\cup\\{u,v\\}$, $N_{G}[x]\cup N_{G}[y]\subseteq N_{G}[u]\cup
N_{G}[v]$. This shows that we can double dominate each vertex of
$N^{3}_{G}(u,v)$ in an optimal way by selecting $u$ and $v$ only. This
selection of $u$ and $v$ was forced by the only vertex $w\in N^{3}_{G}(u,v)$
that remained in $G^{\prime}$. We claim that $G$ contains a minimum double
dominating set $D$ which does not contain any vertex from $N^{2}_{G}(u,v)\cup
N^{3}_{G}(u,v)$. First observe that there can not be three or more vertices
from $N^{2}_{G}(u,v)\cup N^{3}_{G}(u,v)$ in $D$. If it were, then we could
replace those three or more vertices by $u$ and $v$, thus contradicting the
minimality of $D$. Now for those two (or one) vertices from
$N^{2}_{G}(u,v)\cup N^{3}_{G}(u,v)$ in $D$, we can replace them by $u$ and
(or) $v$. Therefore, $G$ contains a minimum double dominating set $D$ which
does not contain any vertex from $N^{2}_{G}(u,v)\cup N^{3}_{G}(u,v)$. Clearly,
this set $D$ also forms a minimum double dominating set of $G^{\prime}$.
Hence, $\gamma_{2}(G)=\gamma_{2}(G^{\prime})$. ∎

In this reduction, for a pair of distinct vertices $u,v\in V$, we have
actually deleted at most $\min\\{deg_{G}(u),deg_{G}(v)\\}$ vertices. So, the
time taken is $\sum_{u,v\in V}\min\\{deg_{G}(u),deg_{G}(v)\\}$ for the whole
reduction process. Since for a planar graph $\sum_{v\in V}deg_{G}(v)=O(n)$,
where $n$ is the number of vertices, we have the following lemma.

###### Lemma 9

For a planar graph having $n$ vertices, the reduction rule can be carried out
in $O(n^{3})$ time.

####  4.1.2 A linear kernel

In this subsection, we show that the reduction rule given in the previous
section yields a linear kernel for Double Domination Problem in planar graphs.
For this proof, first we find a “maximal region decomposition” of the vertices
$V^{\prime}$ of the reduced graph $G^{\prime}=(V^{\prime},E^{\prime})$ and
then we show that $|V^{\prime}|=O(\gamma_{2}(G^{\prime}))$. We start with some
definitions regarding maximal region decomposition following Alber et al.
[AFN04a].

###### Definition 10

Let $G=(V,E)$ be a plane graph. A closed subset of the plane is called a
region $R(u,v)$ between two vertices $u,v$ if the following properties are
met:

  1. 1.

the boundary of $R(u,v)$ is formed by two simple paths $P$ and $Q$ between $u$
and $v$ of length at most two edges, and

  2. 2.

all the vertices which are strictly inside the region $R(u,v)$ are from
$N_{G}(u)\cap N_{G}(v)$.

The definition of a region is slightly different from the definition given in
[AFN04a], where all the vertices which are strictly inside the region $R(u,v)$
are from $N_{G}(u)\cup N_{G}(v)$. Note that by the above definition, paths of
length one or two between $u$ and $v$ can form a region $R(u,v)$. For a region
$R=R(u,v)$, let $\partial(R)$ denote the boundary of $R$ and $V(R)$ denote the
vertices inside or on the boundary of $R$, i.e., $V(R)=\\{u\in V|~{}u~{}\mbox{
is inside }R\mbox{ or on }\partial(R)\\}$.

###### Definition 11

Let $G=(V,E)$ be a plane graph and $D\subseteq V$. A $D$-region decomposition
of $G$ is a set $\mathcal{R}$ of regions between pairs of vertices in $D$ such
that

  1. 1.

for $R(u,v)\in\mathcal{R}$ no vertices of $D$ (except $u$ and $v$) lies in
$V(R(u,v))$, and

  2. 2.

for two regions $R_{1},R_{2}\in\mathcal{R}$, $(R_{1}\cap
R_{2})\subseteq(\partial(R_{1})\cup\partial(R_{2}))$, i.e., they can intersect
only at the vertices on the boundary.

For a $D$-region decomposition $\mathcal{R}$, we define
$V(\mathcal{R})=\cup_{R\in\mathcal{R}}V(R)$. A $D$-region decomposition
$\mathcal{R}$ is called maximal if there is no region $R$ such that
$\mathcal{R^{\prime}}=\mathcal{R}\cup R$ is a $D$-region decomposition, where
$V(\mathcal{R})$ is a strict subset of $V(\mathcal{R^{\prime}})$.

First we observe an important property of a maximal $D$-region decomposition.

###### Lemma 12

Let $G=(V,E)$ be a plane graph with a double dominating set $D$ and let
$\mathcal{R}$ be a maximal $D$-region decomposition. Then $V=V(\mathcal{R})$.

###### Proof.

Let $v\in V$ be a vertex such that $v\notin V(\mathcal{R})$. There can be two
cases – $v\in D$ and $v\notin D$. First, let us assume that $v\in D$. Since
$D$ is a double dominating set of $G$, there exists another vertex $x\in D$
such that $vx\in E$. Now, the path $P=(x,v)$ forms a region $R$. Clearly
$\mathcal{R}\cup R$ forms a $D$-region decomposition of $G$ which contradicts
the maximality of $\mathcal{R}$. Let us now consider the other case $v\notin
D$. Since $D$ is a double dominating set of $G$, there exists $x,y\in D$ such
that $vx,vy\in E$. In this case, the path $P=(x,v,y)$ forms a region $R$. Here
also, $\mathcal{R}\cup R$ forms a $D$-region decomposition of $G$ which
contradicts the maximality of $\mathcal{R}$. Thus each vertex of $V$ is in
$V(\mathcal{R})$, that is, $V\subseteq V(\mathcal{R})$. Thus
$V=V(\mathcal{R})$. ∎

It is obvious that, for a plane graph $G=(V,E)$ with a double dominating set
$D$, there exists a maximal $D$-region decomposition $\mathcal{R}$. Based on
Lemma 12, we propose a greedy algorithm to compute a maximal $D$-region
decomposition, which is given in Algorithm 1. The algorithm basically ensures
the properties of the region decomposition mentioned in Definitions 10 and 11.

Input: A plane graph $G=(V,E)$ and a double dominating set $D\subseteq V$.

Output: A maximal $D$-region decomposition $\mathcal{R}$ of $G$.

begin

$V_{used}\leftarrow\emptyset$, $\mathcal{R}\leftarrow\emptyset$;

while  _$V_{used}\neq V$_ do

Select a vertex $x$ from $V\setminus V_{used}$;

Consider the set $\mathcal{R}_{x}$ of all regions $S$ with the following
properties:

  1. 1.

$S$ is a region between $u$ and $v$, where $u,v\in D$.

  2. 2.

$S$ contains $x$.

  3. 3.

no vertex from $D\setminus\\{u,v\\}$ is in $V(S)$.

  4. 4.

$(S\cup R)\subseteq(\partial(S)\cup\partial(R))$ for all $R\in\mathcal{R}$.

Choose a region $S_{x}\in\mathcal{R}_{x}$ which is maximal in terms of
vertices;

$\mathcal{R}\leftarrow\mathcal{R}\cup\\{S_{x}\\}$;

$V_{used}\leftarrow V_{used}\cup V(S_{x})$;

$\textnormal{{return}}(\mathcal{R})$;

Algorithm 1 REGION$\\_$DECOMPOSITION$(G,D)$

Clearly Algorithm 1 output a maximal $D$-region decomposition in polynomial
time. Next, we show that for a given plane graph $G$ with a double dominating
set $D$, every maximal $D$-region decomposition contains at most $O(|D|)$ many
regions. For that purpose, we observe that a $D$-region decomposition induces
a graph in a very natural way.

###### Definition 13

The induced graph $G_{\mathcal{R}}=(V_{\mathcal{R}},E_{\mathcal{R}})$ of a
$D$-region decomposition $\mathcal{R}$ of $G$ is the graph with possible
multiple edges which is defined as follows: $V_{\mathcal{R}}=D$ and
$E_{\mathcal{R}}=\\{(u,v)|$there is a region $R(u,v)\in\mathcal{R}$ between
$u,v\in D\\}$.

Note that, since by Definition 11 the regions of a $D$-region decomposition do
not intersect, the induced graph $G_{\mathcal{R}}$ of a $D$-region
decomposition $\mathcal{R}$ is a planar graph with multiple edges. Next we
bound the number of regions in a maximal $D$-region decomposition using the
concept of _thin planar graph_ following Alber et al. [AFN04a].

###### Definition 14

A planar graph $G=(V,E)$ with multiple edges is thin if there exists a planar
embedding such that if there are two edges $e_{1},e_{2}$ between a pair of
distinct vertices $v,w\in V$, then there must be two further vertices
$u_{1},u_{2}\in V$ which sit inside the two disjoint areas of the plane that
are enclosed by $e_{1}$ and $e_{2}$.

###### Lemma 15

Let $D$ be a double dominating set of a planar graph $G=(V,E)$. Then the
induced graph $G_{\mathcal{R}}=(V_{\mathcal{R}},E_{\mathcal{R}})$ of a maximal
$D$-region decomposition $\mathcal{R}$ of $G$ is a thin planar graph.

###### Proof.

Let $R_{1}$ and $R_{2}$ be two regions between two vertices $v,w\in D$ and
$e_{1}$ and $e_{2}$ be the corresponding multiple edges between two vertices
$v,w\in V_{\mathcal{R}}$. Let $A$ be an area enclosed by $e_{1}$ and $e_{2}$.
If $A$ contains a vertex $u\in D$, we are done. Suppose there is no vertex of
$D$ in $A$. Now consider the following cases:

There is no vertex from $V\setminus D$ in $A$:

In this case, by combining the regions $R_{1}$ and $R_{2}$, we can form a
bigger region which is a contradiction to the maximality of $\mathcal{R}$.

There is a vertex $x\in(V\setminus D)$ in $A$:

In this case, if $x$ is double dominated by $v$ and $w$, then again we can
combine the two regions $R_{1}$ and $R_{2}$ to get a bigger region. So, assume
that $x$ is dominated by some vertex $u$ other than $v$ and $w$. Since $G$ is
planar, $u$ must be in $A$ which contradicts the fact that $A$ does not
contain any vertex from $D$.

Hence, combining both the cases we see that $G_{\mathcal{R}}$ is a thin planar
graph. ∎

In [AFN04a], it is proved that for a thin planar graph $G=(V,E)$, we have
$|E|\leq 3|V|-6$. Hence we have the following lemma.

###### Lemma 16

For a plane graph $G$ with a double dominating set $D$, every maximal
$D$-region decomposition $\mathcal{R}$ contains at most $3|D|$ many regions.

Now, if we can bound the number of vertices that belongs to any region
$R(u,v)$ of a maximal $D$-region decomposition $\mathcal{R}$ by some constant
factor, we are done. However, achieving this constant factor bound is not
possible for any plane graph $G$. But in a reduced plane graph, we can obtain
this bound, as shown in the following lemma.

###### Lemma 17

A region $R$ of a plane reduced graph contains at most $6$ vertices, that is,
$|V(R)|\leq 6$.

###### Proof.

Let $R$ be the region between $u$ and $v$ and $\partial(R)=\\{u,x,v,y\\}$.
First note that $R$ contains at most two vertices from
$N_{G^{\prime}}^{1}(u,v)$ and the only possibility of such vertices are $x$
and $y$. If there exists a vertex $w\in N_{G^{\prime}}^{1}(u,v)$, apart from
$x$ and $y$, then $w$ has to have a neighbor $z\notin N_{G^{\prime}}(u,v)$.
$z$ should be inside the region $R$ and hence, cannot be double dominated.
Now, because of the reduction rule, we can say that
$\left|N_{G^{\prime}}^{3}(u,v)\right|\leq 1$. We consider the two cases:

Case I ($\left|N_{G^{\prime}}^{3}(u,v)\right|=1$):

In this case, $\left|N_{G^{\prime}}^{2}(u,v)\right|=\emptyset$ by the
reduction rule. Hence, $|V(R)|\leq 5$.

Case II ($\left|N_{G^{\prime}}^{3}(u,v)\right|=0$):

In this case, we claim that there can be at most two vertices from
$N_{G^{\prime}}^{2}(u,v)$. If possible, let $p,q,r\in
N_{G^{\prime}}^{2}(u,v)$. Now all these three vertices must be adjacent to
either $x$ or $y$, which is not possible because of planarity. Hence, in this
case $|V(R)|\leq 6$.

∎

First observe that, for a reduced graph $G^{\prime}$ with a minimum double
dominating set $D$, by Lemma 16, there exists a maximal $D$-region
decomposition $\mathcal{R}$ with at most $3\cdot\gamma_{2}(G^{\prime})$
regions. Also by Lemma 12, we have $V^{\prime}=V(\mathcal{R})$ and by Lemma
17, we have for each region $|V(R)|\leq 6$. Thus we have
$|V^{\prime}|=|V(\mathcal{R})|=|\cup_{R\in\mathcal{R}}V(R)|\leq\sum_{R\in\mathcal{R}}\left|V(R)\right|\leq
6\cdot|\mathcal{R}|\leq 18\cdot\gamma_{2}(G^{\prime})$. Hence, we have the
following theorem.

###### Theorem 18

For a reduced planar graph $G^{\prime}=(V^{\prime},E^{\prime})$, we have
$|V^{\prime}|\leq 18\cdot\gamma_{2}(G^{\prime})$, that is, Double Domination
Problem on planar graph admits a linear kernel.

###  4.2 Liar’s and $k$-tuple domination

We first show that the number of vertices in a plane graph,
$|V|=O(\gamma_{LR}(G))$. In this respect, first we note that both the results
in Lemma 12 and Lemma 16 are valid for any plane graph $G$ and any double
dominating set $D$. Since every liar’s dominating set is also a double
dominating set, similar type of results hold for any plane graph $G$ and any
liar’s dominating set $L$. We claim that the number of vertices in a region
$R$ of a $L$-region decomposition is bounded above by a constant. Let $R$ be a
region between $u$ and $v$ and $\partial(R)=\\{u,x,v,y\\}$. Note that in
$V(R)$ there are two vertices ($u$ and $v$) from $L$. Now, if there exists two
vertices $p,q\in V(R)\setminus\partial(R)$, then for the pair $p$ and $q$
condition (ii) of liar’s domination is violated. Hence, there is at most one
vertex in $V(R)\setminus\partial(R)$. Therefore, $|V(R)|\leq 5$. Thus we have
$|V|=|V(\mathcal{R})|=|\cup_{R\in\mathcal{R}}V(R)|\leq\sum_{R\in\mathcal{R}}|V(R)|\leq
5\cdot|\mathcal{R}|\leq 15\cdot|L|\leq 15\cdot\gamma_{LR}(G).$ Hence, we have
the following theorem

###### Theorem 19

For a planar graph $G=(V,E)$, $|V|\leq 15\cdot\gamma_{LR}(G)$.

Since every $k$-tuple dominating set for $k\geq 3$ is a liar’s dominating set,
we can use Theorem 19. But, we can improve the constant a little bit.

###### Theorem 20

For a planar graph $G=(V,E)$, $|V|\leq 12\cdot\gamma_{k}(G)$, where $k\geq 3$.

###### Proof.

Let $D$ be a minimum $k$-tuple dominating set of $G=(V,E)$. Since every
$k$-tuple dominating set is a double dominating set, by Lemma 16 we can form a
maximal $D$-region decomposition $\mathcal{R}$ of $G$ containing at most
$3\cdot|D|$ many regions. Again by Lemma 12, we have $V=V(\mathcal{R})$. Since
each region contains only two vertices of $D$, we have $|V(R)|\leq 4$.
Otherwise there exists one vertex in $V(R)$ which is not dominated by $k$
vertices of $D$. Hence $|V|\leq 4\cdot|\mathcal{R}|\leq 12\cdot|D|\leq
12\cdot\gamma_{k}(G)$. ∎

##  5 Linear kernels for bounded genus graphs

In this section, we extend our results to bounded genus graphs to show that
$k$-Tuple Domination Problem and Liar’s Domination Problem admit a linear
kernel. The notations in this section follow Section 2.1.

For double domination problem, we apply the same reduction rule on a graph $G$
with bounded genus $g$ to obtain the reduced graph $G^{\prime}$. Note that the
reduced graph $G^{\prime}$ is also of bounded genus $g$. Let $G=(V,E)$ be an
$n$-vertex $\Sigma$-embedded graph. It is easy to observe that, since
$\sum_{v\in V}deg_{G}(v)=O(n+\textup{eg}(\Sigma))$, the reduced graph
$G^{\prime}=(V^{\prime},E^{\prime})$ can be computed in
$O(n^{3}+n^{2}\cdot\textup{eg}(\Sigma))$ time, where $|V|=n$. Next we show
that $|V^{\prime}|=O(\gamma_{2}(G^{\prime})+g)$ which implies Double
Domination Problem admits a linear kernel in bounded genus graphs.

To prove the above, we consider two cases. In the first case, we assume that
the reduced $\Sigma$-embedded graph has representativity strictly greater than
$4$. In the case when $rep(G)\leq 4$, we go by induction on the Euler genus of
surface $\Sigma$. In the first case, the graphs are locally planar, i.e., all
the contractable noose are of length less or equal to $4$. Since the boundary
of the regions in planar case is less than or equal to $4$, the boundary
$\partial(R)$ of any region $R$ of a $D$-region decomposition $\mathcal{R}$ is
contractible. Hence the proof in the planar case can be extended in this case.
Hence we have the following lemma.

###### Lemma 21

Let $G^{\prime}=(V^{\prime},E^{\prime})$ be a reduced $\Sigma$-embedded graph
where $\textup{rep}(G^{\prime})>4$. Then $|V^{\prime}|\leq
18(\gamma_{2}(G^{\prime})+\textup{eg}(\Sigma))$.

###### Proof.

Let $D$ be a double dominating set of $G^{\prime}$ and $\mathcal{R}$ is a
maximal $D$-region decomposition of $G^{\prime}$. Forming a induced graph,
$G_{\mathcal{R}}$ as in case of double domination problem in planar graphs
(Section 4.1.2), we have $|\mathcal{R}|\leq 3\cdot(|D|+eg(\Sigma))$. Also, in
this case, every vertex of $V^{\prime}$ belongs to at least one region of
$\mathcal{R}$ and for a region $R$, $|V(R)|\leq 6$. Hence, we have
$|V^{\prime}|\leq 18(\gamma_{2}(G^{\prime})+\textup{eg}(\Sigma))$. ∎

Next consider the case where $3\leq\textup{rep}(G^{\prime})\leq 4$. For a
noose $N$ in $\Sigma$, we define the graph $G_{N}=(V_{N},E_{N})$ as follows.
First we consider the graph $\mathcal{G}$ obtained from
$G^{\prime}=(V^{\prime},E^{\prime})$ by cutting along $N$. Then for every
$v\in N\cap V^{\prime}$ if $v^{i}$, $i=1,2$, is not adjacent to a pendant
vertex, then we add a pendant vertex $u^{i}$ adjacent to $v^{i}$ to form
$G_{N}$. Clearly $G_{N}$ has genus less than that of $G^{\prime}$. If we add
all the vertices of $V_{N}\setminus V^{\prime}$ to a double dominating set $D$
of $G^{\prime}$, then we clearly obtain a double dominating set of $G_{N}$ and
as, $\textup{rep}(G^{\prime})\leq 4$, $|V_{N}\setminus V^{\prime}|\leq 16$.
Hence, $\gamma_{2}(G_{N})\leq\gamma_{2}(G^{\prime})+|N\cap
V^{\prime}|\leq\gamma_{2}(G^{\prime})+16$. Also note that if $G^{\prime}$ is a
reduced graph, then so is $G_{N}$. Using these facts, we prove that Double
Domination Problem possesses a linear kernel when restricted to graphs with
bounded genus.

###### Lemma 22

For any reduced $\Sigma$-embedded graph $G^{\prime}=(V^{\prime},E^{\prime})$
with eg$(\Sigma)\geq 1$, $|V^{\prime}|\leq
18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-16)$.

###### Proof.

We prove this result by induction on $\textup{eg}(\Sigma)$. Suppose
$\textup{eg}(\Sigma)=1$. If $\textup{rep}(G^{\prime})>4$, then the result
follows from Lemma 21. Otherwise Lemma 1 implies that the graph $G_{N}$,
described above, is planar. Hence by Theorem 18, we have $|V_{N}|\leq
18\cdot\gamma_{2}(G_{N})$. Thus $|V^{\prime}|\leq|V_{N}|\leq
18(\gamma_{2}(G^{\prime})+16)$.

Assume that $|V^{\prime}|\leq
18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-16)$ for any
$\Sigma$-embedded reduced graph $G^{\prime}$ with eg$(\Sigma)\leq g-1$.
Consider a reduced $\Sigma$-embedded graph $G^{\prime}$ with eg$(\Sigma)=g$.
Now if rep$(G^{\prime})>4$, then again by Lemma 21, we are done. Hence assume
that rep$(G^{\prime})\leq 4$. By Lemma 1, either $G_{N}$ is the disjoint union
of graphs $G_{1}$ and $G_{2}$ that can be embedded in surfaces $\Sigma_{1}$
and $\Sigma_{2}$ such that eg$(\Sigma)=$ eg$(\Sigma_{1})+$ eg$(\Sigma_{2})$
and eg$(\Sigma_{i})>0$, $i=1,2$ (this is the case when $N$ is surface
separating curve), or $G_{N}$ can be embedded in a surface with Euler genus
strictly smaller than eg$(\Sigma)$ (this holds when N is not surface
separating).

Let us consider the case where $G_{N}$ is the disjoint union of graphs
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ that can be embedded in
surfaces $\Sigma_{1}$ and $\Sigma_{2}$. Since eg$(\Sigma_{i})\leq g-1$ for
$i=1,2$, we can apply the induction hypothesis on $G_{i}$. Thus we have,

$\displaystyle|V^{\prime}|\leq|V_{N}|$ $\displaystyle=|V_{1}|+|V_{2}|$
$\displaystyle\leq\sum_{i=1}^{2}18(\gamma_{2}(G_{i})+32\cdot\textup{eg}(\Sigma_{i})-16)$
$\displaystyle\leq 18(\gamma_{2}(G_{N})+32\cdot\textup{eg}(\Sigma)-32)$ as
$G_{1}$ and $G_{2}$ are disjoint $\displaystyle\leq
18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-16).$

Next we consider the case where $G_{N}$ can be embedded in a surface
$\Sigma^{\prime}$ with Euler genus strictly smaller than $g$. In this case
too, we can apply induction hypothesis on $G_{N}$. Thus we have,

$\displaystyle|V^{\prime}|\leq|V_{N}|$ $\displaystyle\leq
18(\gamma_{2}(G_{N})+32\cdot\textup{eg}(\Sigma^{\prime})-16)$
$\displaystyle\leq 18(\gamma_{2}(G_{N})+32\cdot(\textup{eg}(\Sigma)-1)-16)$
$\displaystyle\leq 18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-32)$
as $\gamma_{2}(G_{N})\leq\gamma_{2}(G^{\prime})+16$ $\displaystyle\leq
18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-16).$

Thus we have proved that, $|V^{\prime}|\leq
18(\gamma_{2}(G^{\prime})+32\cdot\textup{eg}(\Sigma)-16)$ for every
$\Sigma$-embedded graph $G^{\prime}=(V^{\prime},E^{\prime})$. ∎

Hence by Lemma 21 and Lemma 22, we have the main result of this subsection.

###### Theorem 23

Double Domination Problem admits a linear kernel for bounded genus graphs.

For liar’s domination problem, by Theorem 19, we have $|V|\leq
15\cdot\gamma_{LR}(G)$ in case of a planar graph $G=(V,E)$. Proceeding exactly
in the same way as in the case of double domination, we can have the following
theorem for a $\Sigma$-embedded graph $G$.

###### Theorem 24

Let $G=(V,E)$ be a $\Sigma$-embedded graph. Then $|V|\leq
15(\gamma_{LR}(G)+32\cdot\textup{eg}(\Sigma))$.

Since for any graph that admits a $k$-tuple dominating set ($k\geq 3$),
$\gamma_{LR}(G)\leq\gamma_{k}(G)$, we have the following corollary of Theorem
24.

###### Corollary 25

For a $\Sigma$-embedded graph $G=(V,E)$, $|V|\leq
15(\gamma_{k}(G)+32\cdot\textup{eg}(\Sigma))$.

##  6 Conclusion

In this paper, we first have proved that $k$-Tuple Domination Problem and
Liar’s Domination Problem are W[2]-hard for general graphs. Then we have shown
that these two problems admit linear kernel for planar graphs and also for
bounded genus graphs. It would be interesting to look for other graph classes
where these problems admit efficient parameterized algorithms.

## Acknowledgements

The authors want to thank Venkatesh Raman and Saket Saurabh for some of their
nice introductory expositions to parametrization.

##  7 Appendix

###### Lemma 26

Liar’s Domination Problem is NP-complete for planar graphs.

###### Proof.

The reduction is from Domination Problem in planar graphs, which is known to
be NP-complete[GJ79]. Let $G=(V,E)$ be a planar graph with
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and $k$ be an integer. We construct an
instance $G^{\prime}=(V^{\prime},E^{\prime})$ and $k^{\prime}$ of Liar’s
Domination Problem as follows: We add a set of $3n$ new vertices
$S=\\{x_{i},y_{i},z_{i}|1\leq i\leq n\\}$ to the vertex set of $V$, i.e.,
$V^{\prime}=V\cup S$ and the edge set of $G^{\prime}$ is given by
$E^{\prime}=E\cup\\{v_{i}x_{i},x_{i}y_{i},y_{i}z_{i}|1\leq i\leq n\\}$. Note
that, since $G$ is planar, so is $G^{\prime}$. Also assume that
$k^{\prime}=k+3n$. In [Sla09], it is proved that $G$ has a dominating set of
cardinality at most $k$ if and only if $G^{\prime}$ has a liar’s dominating
set of cardinality at most $k^{\prime}=k+3n$.

Thus, Liar’s Domination Problem is NP-complete for planar graphs. ∎

## References

  * [ABF+02] J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier.  Fixed parameter algorithms for dominating set and related problems on planar graphs.  Algorithmica, 33(4):461–493, 2002.
  * [AFF+05] J. Alber, H. Fan, M. R. Fellows, H. Fernau, R. Niedermeier, F. A. Rosamond, and U. Stege.  A refined search tree technique for dominating set on planar graphs.  J. Comput. Syst. Sci., 71(4):385–405, 2005.
  * [AFN04a] J. Alber, M. R. Fellows, and R. Niedermeier.  Polynomial-time data reduction for dominating set.  J. ACM, 51(3):363–384, 2004.
  * [AFN04b] J. Alber, H. Fernau, and R. Niedermeier.  Parameterized complexity: exponential speed-up for planar graph problems.  J. Algorithms, 52(1):26–56, 2004.
  * [BFL+09] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos.  (Meta) Kernelization.  In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, pages 629–638, Washington, DC, USA, 2009. IEEE Computer Society.
  * [Cou92] B. Courcelle.  The monadic second-order logic of graphs iii: tree-decompositions, minor and complexity issues.  Inform. Théor. Appl., 26:257–286, 1992.
  * [CP14] D. Cattanéo and S. Perdrix.  The parameterized complexity of domination-type problems and application to linear codes.  In T. V. Gopal, M. Agrawal, A. Li, and S. B. Cooper, editors, Theory and Applications of Models of Computation, volume 8402 of Lecture Notes in Computer Science, pages 86–103. Springer International Publishing, 2014.
  * [DF99] R. G. Downey and M. R. Fellows.  Parameterized Complexity.  Springer-Verlag, 1999.  530 pp.
  * [EFF04] J. A. Ellis, H. Fan, and M. R. Fellows.  The dominating set problem is fixed parameter tractable for graphs of bounded genus.  J. Algorithms, 52(2):152–168, 2004.
  * [FT03] F. V. Fomin and D. M. Thilikos.  Dominating sets in planar graphs: branch-width and exponential speed-up.  In SODA, pages 168–177, 2003.
  * [FT04] F. V. Fomin and D. M. Thilikos.  Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up.  In ICALP, pages 581–592, 2004.
  * [GJ79] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [Gut09] S. Gutner.  Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor.  In J. Chen and F. V. Fomin, editors, Parameterized and Exact Computation, volume 5917 of Lecture Notes in Computer Science, pages 246–257. Springer Berlin Heidelberg, 2009.
  * [GV08] P. A. Golovach and Y. Villanger.  Parameterized complexity for domination problems on degenerate graphs.  In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniel Paulusma, editors, Graph-Theoretic Concepts in Computer Science, volume 5344 of Lecture Notes in Computer Science, pages 195–205. Springer Berlin Heidelberg, 2008.
  * [HH00] Frank Harary and Teresa W. Haynes.  Double domination in graphs.  Ars Comb., 55, 2000.
  * [HHS98a] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater.  Fundamentals of Domination in Graphs.  Marcel Dekker, 1998.
  * [HHS98b] T.W. Haynes, S.T. Hedetniemi, and P.J.B. Slater.  Domination in Graphs: Advanced Topics.  Marcel Dekker, Incorporated, 1998.
  * [LC02] C.-S. Liao and G. J. Chang.  Algorithmic aspects of $k$-tuple domination in graphs.  Taiwanese Journal of Mathematics, 6(3):415–420, 2002.
  * [LC03] C.-S. Liao and G. J. Chang.  k-tuple domination in graphs.  Inf. Process. Lett., 87(1):45–50, 2003.
  * [LC08] C.-M. Lee and M.-S. Chang.  Variations of $y$-dominating functions on graphs.  Discrete Mathematics, 308(18):4185 – 4204, 2008.
  * [MT01] B. Mohar and C. Thomassen.  Graphs on Surfaces.  Johns Hopkins series in the mathematical sciences. Johns Hopkins University Press, 2001.
  * [Nie06] R. Niedermeier.  Invitation to Fixed-Parameter Algorithms.  Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, 2006.
  * [PP13a] B. S. Panda and S. Paul.  Liar’s domination in graphs: Complexity and algorithm.  Discrete Applied Mathematics, 161(7-8):1085–1092, 2013.
  * [PP13b] B. S. Panda and S. Paul.  A linear time algorithm for liar’s domination problem in proper interval graphs.  Information Processing Letters, 113:815–822, 2013.
  * [PRS12] G. Philip, V. Raman, and S. Sikdar.  Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond.  ACM Trans. Algorithms, 9(1):11:1–11:23, Dec 2012.
  * [RS09] M. L. Roden and P. J. Slater.  Liar’s domination in graphs.  Discrete Mathematics, 309(19):5884–5890, 2009.
  * [Sla09] Peter J. Slater.  Liar’s domination.  Networks, 54(2):70–74, 2009.
  * [TP97] J. A. Telle and A. Proskurowski.  Algorithms for vertex partitioning problems on partial $k$-trees.  SIAM J. Disc. Math, 10(4):529–550, 1997.
  * [vRBR09] J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith.  Dynamic programming on tree decompositions using generalised fast subset convolution.  In A. Fiat and P. Sanders, editors, Algorithms - ESA 2009, volume 5757 of Lecture Notes in Computer Science, pages 566–577. Springer Berlin Heidelberg, 2009.


[a]Andreas Risch

# The influence of gauge field smearing on discretisation effects

Stefan Schaefer  Rainer Sommer

###### Abstract

When designing lattice actions, gauge field smearing is frequently used to
define the lattice Dirac operator. Since the smearing procedure removes
effects of ultraviolet fluctuations, the fermions effectively see a larger
lattice spacing than the gauge fields. Creutz ratios, formed from ratios of
rectangular Wilson loops, based on smeared gauge fields are adequate
observables to investigate the effect of smearing since they do not need
renormalisation and provide a measure of the physical forces felt by the
fermions. We study their behaviour at various smearing radii (fixed in lattice
units) and in particular how the smearing influences the scaling towards the
continuum limit. Since we employ the Wilson gradient flow as smearing, the
same Creutz ratios have another, well defined continuum limit, when the flow
time is fixed in physical units. That continuum limit is reached with smaller
corrections at finite $a$.

##  1 Introduction

Four-dimensional smearing is a common method used in lattice gauge theories to
smooth a gauge field. During the years, several smearing algorithms have been
developed, e.g. HYP [1], Stout [2], HEX [3] and gradient flow [4, 5] smearing.
Considering a smearing transformation $\mathcal{S}:U\mapsto\mathcal{S}[U]$
there are two main types of application: Observable smearing

$\displaystyle\langle O_{\mathcal{S}}[U]\rangle=\langle
O[\mathcal{S}[U]]\rangle,$ (1)

where a new observable is defined by evaluating a given observable on the
smeared gauge field, and smearing in the lattice fermion action

$\displaystyle
S[U]=S_{\mathrm{g}}[U]+\overline{\psi}\,D[\mathcal{S}[U]]\,\psi,$ (2)

where the Dirac operator is evaluated on the smeared gauge field. Concerning
observable smearing the main motivation is noise reduction, whereas smearing
in the fermion action improves the algorithmic stability, e.g. with regard to
exceptional configurations. In Ref. [6] even at very coarse lattice spacings
the Wilson Dirac operator defined with nHYP gauge links could be shown to
exhibit a spectrum with a well-defined spectral gap. The same was shown for
stout smearing in Ref. [7].

In this work we are going to focus on two questions: How does the smearing
strength influence lattice artefacts? What smearing strengths allow for a
controlled continuum extrapolation? We will discuss these issues using the
example of Creutz ratios, which provide a measure of the physical111As opposed
to the forces present in the molecular dynamics evolution of the HMC. forces
felt by the fermions caused by the gauge field. A somewhat related discussion
for thermal correlation functions and the energy-momentum tensor can be found
in [8]. Creutz ratios in combination with APE smearing and the Wilson flow
were also studied in a determination of the string tension in [9].

##  2 The gradient flow formalism, gradient flow smearing and physical
gradient flow

We make use of the continuum four-dimensional Yang-Mills action which is
defined as
$S_{\mathrm{YM}}=-\frac{1}{2g_{0}^{2}}\int\mathrm{d}^{4}x\operatorname{tr}(F_{\mu\nu}(x)F_{\mu\nu}(x))$,
where
$F_{\mu\nu}=\partial_{\mu}A_{\nu}-\partial_{\nu}A_{\mu}+[A_{\mu},A_{\nu}]$
denotes the field strength tensor and $A_{\mu}(x)$ the corresponding gauge
field. In the Yang-Mills continuum gradient flow formalism [5] a gauge field
$B_{\mu}(x,t_{\mathrm{fl}})$ is introduced, which is defined on
$\mathds{R}^{4}\times[0,\infty)$ and where $t_{\mathrm{fl}}$ is the so called
gradient flow time. At $t_{\mathrm{fl}}=0$ the usual four-dimensional gauge
field is an initial condition in the flow time evolution, i.e.

$\displaystyle B_{\mu}(x,0)=A_{\mu}(x).$ (3)

The dynamics in the flow time direction is driven by the gauge-covariant flow
equation

$\displaystyle\frac{\partial}{\partial
t_{\mathrm{fl}}}B_{\mu}(x,t_{\mathrm{fl}})=-\frac{\delta
S_{\mathrm{YM}}[B]}{\delta
B_{\mu}(x,t_{\mathrm{fl}})}=D_{\nu}G_{\nu\mu}(x,t_{\mathrm{fl}}),$ (4)

where
$G_{\mu\nu}=\partial_{\mu}B_{\nu}-\partial_{\nu}B_{\mu}+[B_{\mu},B_{\nu}]$
denotes the generalised field strength tensor on
$\mathds{R}^{4}\times[0,\infty)$ and $D_{\mu}=\partial_{\mu}+[B_{\mu},\cdot]$
the generalised covariant derivative. The gradient flow possesses a smoothing
property in the direction of positive flow time: From a leading-order
perturbative expansion one may deduce that the gauge field
$B_{\mu}(x,t_{\mathrm{fl}})$ is a spherically smoothed version of $A_{\mu}(x)$
with mean-square radius $r_{\mathrm{sm}}=\sqrt{8t_{\mathrm{fl}}}$ [5]. In [10]
it has been shown perturbatively to all loop orders that any functional of the
flowed fields $B_{\mu}(x,t_{\mathrm{fl}})$ at strictly positive
$t_{\mathrm{fl}}$ is finite, i.e. no additional renormalisation is required,
assuming that the four-dimensional theory has been renormalised.

We discretise the Yang-Mills gradient flow by means of the Wilson gradient
flow [5] and integrate the flow equation numerically by means of an explicit
3rd-order Runge-Kutta integration scheme with a step size $\frac{\Delta
t_{\mathrm{fl}}}{a^{2}}\leq$ which never exceeds $0.01$.

We consider two scenarios in which we apply the gradient flow to the gauge
field: For gradient flow smearing the gradient flow time is fixed in lattice
units when varying the lattice spacing,
$\frac{8t_{\mathrm{fl}}}{a^{2}}=\mathrm{const}$, i.e. in physical units it
shrinks when the lattice spacing is reduced and therefore vanishes in the
continuum limit. Hence, the continuum theory is unaltered. Smearing strengths
up to $\frac{8t_{\mathrm{fl}}}{a^{2}}=8$ have been used in practice, e.g. in
[11]. The second scenario we refer to as a physical gradient flow. In this
case the gradient flow time is fixed in physical units, i.e.
$t_{\mathrm{fl}}/t_{0}=\mathrm{const}$, where $t_{0}$ may be any physical
length scale of the theory, in particular the scale defined in [5].
Consequently, the flow time in lattice units grows with shrinking lattice
spacing $\frac{8t_{\mathrm{fl}}}{a^{2}}\propto\frac{8t_{0}}{a^{2}}$ and hence
the continuum theory / observables are altered. One motivation for a physical
gradient flow is the possibility to define and access new observables.

##  3 Lattice setup

ensemble | $\beta$ | $T/a$ | $L/a$ | $a\,[\text{fm}]$ | $L\,[\text{fm}]$ | $t_{0}/a^{2}$
---|---|---|---|---|---|---
sft1 | 6.0662 | 80 | 24 | 0.0834(4) | 2.00(1) | 3.990(9)
sft2 | 6.2556 | 96 | 32 | 0.0624(4) | 2.00(1) | 7.070(17)
sft3 | 6.5619 | 96 | 48 | 0.0411(2) | 1.97(1) | 16.52(6)
sft4 | 6.7859 | 192 | 64 | 0.0312(2) | 2.00(1) | 29.60(10)
sft5 | 7.1146 | 320 | 96 | 0.0206(2) | 1.98(2) | 67.94(23)
Table 1: Parameters of the SU(3) gauge ensembles [12] and computed reference
flow time $t_{0}/a^{2}$ in lattice units.

We make use of $\mathrm{SU}(3)$ Yang Mills theory gauge ensembles [12] based
on the Wilson plaquette action. Temporal open boundary conditions [13] are
imposed to alleviate topology freezing. The scale is set by means of the force
parameter $r_{0}$ [14], where for illustration a value of
$r_{0}=0.5\,\text{fm}$ is used. An overview of the gauge ensembles is given in
table 1. The lattice spacing varies between $0.08\,\text{fm}$ and
$0.02\,\text{fm}$ and the spatial extent is kept constant at $L=2\,\text{fm}$.

Instead of the force parameter $r_{0}$ we will in the following use the
already mentioned reference flow time $t_{0}$ [5] to construct dimensionless
quantities. To define $t_{0}$ we make use of the action density
$E(x,t_{\mathrm{fl}})=-\frac{1}{2}\sum_{\mu,\nu}\operatorname{tr}\big{(}G^{\mathrm{clv}}_{\mu\nu}(x,t_{\mathrm{fl}})\,G_{\mu\nu}^{\mathrm{clv}}(x,t_{\mathrm{fl}})\big{)}$,
where $G^{\mathrm{clv}}$ denotes the field strength tensor in the clover
discretisation [15]. The reference flow time $t_{0}$ is then implicitly
defined by $t^{2}_{0}\,\langle E(x,t_{0})\rangle=0.3$ [5]. Numerical values
are listed in table 1.

In our measurements we implement the two scenarios for scaling the flow time
via

$\frac{8t_{\mathrm{fl}}}{a^{2}}=\begin{cases}0,\;0.25,\;0.5,\;\ldots,\;2,\;2.5,\ldots,\;3.5,\;4,\;5,\;6,\;7,\;8&\text{smearing}\\\
\frac{8t_{0}}{a^{2}}\times 0.0146\times
j\,,\;\;j\in\\{0,\;1,\;\ldots,\;4\\}&\text{physical flow}\end{cases}$ (5)

##  4 Creutz ratios and gradient flow

In this work we study the influence of smearing on the continuum extrapolation
of Creutz ratios. In order to define the latter we introduce planar
rectangular Wilson loops of size $r\times t$,

$\displaystyle
W(r,t)\equiv\Big{\langle}\operatorname{tr}\Big{(}P\exp\Big{(}\oint_{\gamma(r,t)}\mathrm{d}x_{\mu}A_{\mu}(x)\Big{)}\Big{)}\Big{\rangle},$
(6)

which are obtained from the gauge field by a path-ordered integral along a
rectangular closed path $\gamma(r,t)$. The Creutz ratios are then obtained
from dual logarithmic derivatives:

$\displaystyle\chi(r,t)\equiv-\frac{\partial}{\partial
t}\frac{\partial}{\partial r}\ln(W(r,t)).$ (7)

It can be shown that in the limit of an infinite time extent the static quark
anti-quark force can be extracted, i.e. $\chi(r,t)\rightarrow
F_{\mathrm{\overline{q}q}}(r)\text{ for }t\rightarrow\infty$ [9]. In order to
define Creutz ratios on the lattice [16] we construct planar rectangular
Wilson loops from closed paths of gauge links:

$\displaystyle
W^{\mathrm{lat}}(r,t)\equiv\Big{\langle}\operatorname{tr}\Big{(}\prod_{(x,\mu)\in\gamma(r,t)}U_{\mu}(x)\Big{)}\Big{\rangle}.$
(8)

We discretise eq. 7 making use of central differences [9],

$\displaystyle\chi\Big{(}t+\frac{a}{2},r+\frac{a}{2}\Big{)}\equiv\frac{1}{a^{2}}\ln\Big{(}\frac{W(t+a,r)\cdot
W(t,r+a)}{W(t,r)\cdot W(t+a,r+a)}\Big{)},$ (9)

such that only $O(a^{2})$ lattice artefacts remain. Note that Creutz ratios
renormalise trivially, i.e. no extra renormalisation factors are required to
obtain a renormalised $\chi(r,t)$. This important property entails that the
small flow time limit is smooth, as opposed to e.g. the one of $\langle
E(x,t_{\mathrm{fl}})\rangle$. For our observables, we can interchange
continuum limit and small flow time limit. The two scenarios eq. 5 therefore
have a common limit where both $a=0$ and $t_{\mathrm{fl}}=0$.

In the following discussion, we will only focus on diagonal Creutz ratios
$\chi(r,t)$ with $r=t$, which we abbreviate as $\chi(r)\equiv\chi(r,r)$. We
compute the latter in lattice units $(\chi\cdot a^{2})(\frac{r}{a})$ for
various half integer distances $\frac{r}{a}=1.5,2.5,\ldots$ on gauge
configurations on which the gradient flow was applied. We use $t_{0}$ to
define dimensionless Creutz ratios, i.e. we analyse $\hat{\chi}\equiv\chi\cdot
8t_{0}$ as a function of $\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}$. The
computation is based on the openQCD [17] package and utilizes B. Leder’s
program for measuring Wilson loops [18, 19]. For the data analysis the python3
package pyobs [20] is used, which implements the $\Gamma$-method [21] for
Monte Carlo error estimation.

Figure 1: Dimensionless Creutz ratios $\hat{\chi}\equiv\chi\cdot 8t_{0}$ as
functions of the distance $\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}$ on different
ensembles and for different gradient flow times
$\frac{8t_{\mathrm{fl}}}{a^{2}}$.

In fig. 1 the dimensionless diagonal Creutz ratio $\hat{\chi}$ is displayed as
a function of the distance $\hat{r}$ evaluated on the five gauge ensembles.
For larger distances the statistical signal deteriorates. Comparing both
figures, which only differ in the size of the applied gradient flow time
$\frac{8t_{\mathrm{fl}}}{a^{2}}$, we confirm that the gradient flow reduces
statistical errors drastically [9]. The $\sim\frac{1}{r^{2}}$ short distance
behaviour is smoothed at distances $r\lessapprox\sqrt{8t_{\mathrm{fl}}}$.
Already from this qualitative picture we see that in the smearing scenario the
path to continuum and hence lattice artefacts are altered. This effect becomes
smaller at larger distances which is coherent with the finiteness of the
smearing radius.

##  5 Interpolation of Creutz ratios

We want to extrapolate $\hat{\chi}(\hat{r})$ to the continuum at a fixed value
of $\hat{r}$. This requires the knowledge of $(\chi\cdot
a^{2})\big{(}\frac{r}{a}\big{)}$ at arbitrary values of $\frac{r}{a}$, i.e.
also at locations $\frac{r}{a}\neq 1.5,2.5,\ldots$, where the values are not
determined by the measurements. We therefore interpolate $\chi\cdot a^{2}$ as
a function of $\frac{r}{a}$. A first class of considered interpolation models
is constructed from linear combinations of $m$ monomials
$\big{(}\frac{r}{a}\big{)}^{n_{j}}$, where $n_{j}\in\mathbb{Z}$, with
coefficients $c_{n_{j}}\in\mathbb{R}$: The function
$\mathrm{Pol}_{n_{1},\ldots,n_{m}}\big{(}\frac{r}{a}\big{)}=\sum_{j=1}^{m}c_{n_{j}}\big{(}\frac{r}{a}\big{)}^{n_{j}}$
is then used to locally interpolate between $m$ adjacent nodes. For $m>2$
several locally defined interpolation functions possess overlapping regions.
In order to obtain a smoothing effect for the global interpolation and to
resolve the interpolation ambiguity we average over all contributing
interpolations in an overlapping region between two adjacent nodes. In
particular, we make use of the interpolation models $\mathrm{Pol}_{2,1,0}$ and
$\mathrm{Pol}_{0,-2,-4}$. In addition, we use a cubic natural spline
$\mathrm{CSpl}$, which is defined as a piecewise cubic polynomial with
continuous second derivative and vanishing second derivative at the
boundaries, as well as the combination $\mathrm{CSpl}\cdot\mathrm{Pol}_{-2}$.

Figure 2: Dimensionless Creutz ratio $\hat{\chi}\equiv\chi\cdot 8t_{0}$ as a
function of the distance $\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}$ on the
ensemble sft3 with a gradient flow time $\frac{8t_{\mathrm{fl}}}{a^{2}}=4$ for
various interpolation models.

In order to account for the interpolation model ambiguities we average over
all $n=4$ considered interpolation models $(\chi\cdot
a^{2})_{\mathrm{av}}\big{(}\frac{r}{a}\big{)}\equiv\frac{1}{n}\sum_{i=1}^{n}(\chi\cdot
a^{2})_{i}\big{(}\frac{r}{a}\big{)}$ and add a systematic error, which is
given by half the spread of all interpolation models:
$\Delta_{\mathrm{sys}}(\chi\cdot
a^{2})_{\mathrm{av}}\big{(}\frac{r}{a}\big{)}\equiv\frac{1}{2}\big{(}\max_{i=1,\ldots,n}\big{\\{}(\chi\cdot
a^{2})_{i}\big{(}\frac{r}{a}\big{)}\big{\\}}-\min_{i=1,\ldots,n}\big{\\{}(\chi\cdot
a^{2})_{i}\big{(}\frac{r}{a}\big{)}\big{\\}}\big{)}$. In fig. 2 several
interpolation models are shown for a given value of the smearing strength on
one ensemble. The interpolations begin to differ at short distances in the
region where the Creutz ratios vary rapidly between nodes. In the following we
are going to focus on the region $0.3\leq\hat{r}\leq 0.6$, in which lattice
artefacts are not uncontrollably large and the statistical signal is
sufficiently good.

##  6 Continuum extrapolation

At fixed distance $\hat{r}$ we perform a global continuum extrapolation making
use of the Symanzik expansion222Our investigation has an intermediate
precision. At this level we neglect logarithmic effects both in the lattice
spacing [22] and in the flow time [5]. and the small flow time expansion of
$\hat{\chi}$. For this purpose we define the dimensionless lattice spacing
parameter $\hat{a}\equiv\frac{a}{\sqrt{8t_{0}}}$ and the flow time parameter
$\varepsilon=\frac{t_{\mathrm{fl}}}{t_{0}}$. The double expansion is then
given by

$\displaystyle\hat{\chi}$
$\displaystyle=\sum_{i=0}^{n}c_{i}\hat{a}^{i}+O(\hat{a}^{n+1}),$
$\displaystyle c_{i}$
$\displaystyle=\sum_{i=0}^{m}c_{ij}\varepsilon^{j}+O(y^{m+1}).$ (10)

To define the fit ansatz for the extrapolation we truncate the latter
expansion, obtaining

$\displaystyle\hat{\chi}_{\mathrm{tr}}(\hat{a},y)$
$\displaystyle=c_{00}+c_{20}\hat{a}^{2}+c_{40}\hat{a}^{4}+c_{01}\varepsilon+c_{21}\hat{a}^{2}\varepsilon+c_{02}\varepsilon^{2}.$
(11)

In order to demonstrate that this fit ansatz also describes the $a$-dependence
for fixed smearing, we observe that the smearing strength is parametrised by
$\frac{\varepsilon}{\hat{a}^{2}}=\frac{8t_{\mathrm{fl}}}{a^{2}}$ and

$\displaystyle\hat{\chi}_{\mathrm{tr}}$
$\displaystyle=d_{0}+d_{2}\hat{a}^{2}+d_{4}\hat{a}^{4}$ (12)

with coefficients

$\displaystyle d_{0}=c_{00},\quad
d_{2}=c_{20}\Big{(}1+\frac{c_{01}}{c_{20}}\frac{8t_{\mathrm{fl}}}{a^{2}}\Big{)},\quad
d_{4}=c_{40}\Big{(}1+\frac{c_{21}}{c_{40}}\frac{8t_{\mathrm{fl}}}{a^{2}}+\frac{c_{02}}{c_{40}}\frac{64t_{\mathrm{fl}}^{2}}{a^{4}}\Big{)}.$
(13)

Figure 3: Dimensionless Creutz ratio $\hat{\chi}\equiv\chi\cdot 8t_{0}$ as a
function of the lattice spacing $\hat{a}\equiv\frac{a}{\sqrt{8t_{0}}}$ at a
distance of $\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}=0.3$ (top) and $0.4$
(bottom). Extrapolations for several gradient flow smearing strengths
$\frac{8t_{\mathrm{fl}}}{a^{2}}$ (solid) and for several physical gradient
flows $\frac{t_{\mathrm{fl}}}{t_{0}}$ (dashed). Solid lines and circles belong
to gradient flow smearing, whereas dashed lines and squares represent a
physical gradient flow. Data points have been shifted for better visibility.

In fig. 3 the continuum extrapolations for the distances $\hat{r}=0.3$ and
$0.4$ are shown. We consider both smearing and the physical gradient flow,
c.f. eq. 5. An inclusion of data from too large smearing strengths
$\frac{8t_{\mathrm{fl}}}{a^{2}}$ and too large physical gradient flow
strengths $\frac{t_{0}}{t_{\mathrm{fl}}}$ led to fits with a bad $p$-value,
which is an indication of the breakdown of the Symanzik expansion and the
small flow time expansion. This depends however on the $\hat{r}$: at larger
distances larger values of $\frac{8t_{\mathrm{fl}}}{a^{2}}$ and
$\frac{t_{0}}{t_{\mathrm{fl}}}$ can be fitted with the low-order expansion. By
construction of the fit model the continuum limit is independent of the
smearing strength $\frac{8t_{\mathrm{fl}}}{a^{2}}$ as in the limit
$\hat{a}\rightarrow 0$ only the fit coefficient $d_{0}=c_{00}$ in eq. 12
contributes. In the figures all continuum extrapolations depicted by solid
lines, which differ in their smearing strengths, therefore share a common
continuum limit.

In contrast, the physical gradient flow, constant
$\varepsilon=\frac{t_{\mathrm{fl}}}{t_{0}}$, leads to a flow time dependent
continuum limit $c_{00}+c_{01}\varepsilon+c_{02}\varepsilon^{2}$ which turns
out to be below the $c_{00}$ attained with the smearing. This dependence is
more pronounced at shorter distances. In contrast to the rather steep bending
smearing curves, we observe rather flat extrapolations with the physical flow
at constant $t_{\mathrm{fl}}/t_{0}$ (dashed). Since the raw data is the same
in both cases, the flat behaviour for the physical flow and the increasing
difference between the continuum limits for shorter distances directly lead to
the non-monotonic and relatively strong dependence of the smearing curves on
the lattice spacing.

##  7 Influence of the smearing strength on the continuum extrapolation

Figure 4: Relative contributions to the Symanzik expansion of
$\hat{\chi}\equiv\chi\cdot 8t_{0}$ evaluated at $a=0.062\,\text{fm}$ (sft2) as
a function of the smearing strength $\frac{8t_{\mathrm{fl}}}{a^{2}}$ at
various distances $\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}$.

In order to investigate whether we are able to perform a controlled continuum
extrapolation we consider relative contributions to the Symanzik expansion. We
choose an intermediate lattice spacing (for some contemporary lattice
computations this is a small one) of $a=0.062\,\text{fm}$ . The relative total
lattice artefacts $(d_{2}\hat{a}^{2}+d_{4}\hat{a}^{4})/d_{0}$ and the $a^{4}$
contributions relative to the $a^{2}$ ones, $d_{4}\hat{a}^{2}/d_{2}$, are
depicted in fig. 4 as functions of the smearing strength
$\frac{8t_{\mathrm{fl}}}{a^{2}}$ for several distances $\hat{r}$. At smaller
distances we find larger overall and smearing dependent lattice artefacts
whereas at larger distances smaller overall lattice artefacts are present. In
order to define a maximally allowed smearing strength we demand that the
relative overall lattice artefacts are bounded by
$|(d_{2}\hat{a}^{2}+d_{4}\hat{a}^{4})/d_{0}|\leq 0.25$ and that the curvature
is limited by $|d_{4}\hat{a}^{2}/d_{2}|\leq 0.5$, i.e. that lattice artefacts
add up to less than $25\%$ and that the $a^{4}$-contribution is somewhat
suppressed by the $a^{2}$ term. Note that with the signs of the coefficients
found for the Creutz ratios, the second condition means that we are to the
left side of the peak of the curves, i.e. in the region where lattice
artefacts are monotonic. Clearly these conditions are not very stringent; one
may want to insist on sharper bounds. From fig. 4 we can deduce that our loose
condition means $\frac{8t_{\mathrm{fl}}}{a^{2}}\lessapprox 1$ for
$\hat{r}=0.3$ while $\frac{8t_{\mathrm{fl}}}{a^{2}}\approx 3$ is tolerated by
the loose criteria at the upper end of the investigated distances,
$\hat{r}=0.6$. At such distances the main restriction comes from the bound on
the curvature.

Figure 5: Location of the maximum of $\hat{\chi}(\hat{a})$ as a function of
the smearing strength $\frac{8t_{\mathrm{fl}}}{a^{2}}$ for several distances
$\hat{r}\equiv\frac{r}{\sqrt{8t_{0}}}$.

The location of the peak $\hat{a}_{\mathrm{peak}}^{2}$ is plotted as a
function of the smearing radius for various distances $\hat{r}$ in fig. 5.
Given a certain distance that one wants to cover adequately in the sense that
cutoff-effects are monotonic, one has to be below the plotted curve. E.g. with
$t_{\mathrm{fl}}/a^{2}=1$ and for distances $\hat{r}\geq 0.4$, lattice
spacings up to $0.08$ fm lead to a monotonic dependence on $a$. In order to
cover smaller distances one needs either smaller lattice spacings or less
smearing.

##  8 Conclusion and Outlook

We have studied the influence of gradient flow smearing on diagonal Creutz
ratios $\chi(r,r)$ evaluated at various distances. We have found that the
maximum tolerable smearing radius that still allows for a controlled continuum
extrapolation depends on the distance. As expected, for short distance
observables less smearing is tolerable. The main result of our numerical
investigation is summarised in fig. 5. Each curve yields the upper boundary of
the region where discretisation effects are monotonic, which is a minimum
requirement for extrapolating data reliably to the continuum. Obviously, non-
monotonic behaviour would not be an issue if we knew that a simple form as in
eq. 12 was correct. But even the asymptotic small $a$ behaviour is complicated
with log-corrections [12] and higher orders in $a$, making a simple functional
form essential for a controlled extrapolation.

Of course, we have only considered one specific observable in our study, but
it is a measure of the force between quarks. This observable allows to probe
different distances and we expect that physical observables with propagating
quarks will be affected by how close it is to the continuum limit. We remind
the reader that quark propagation with a smeared Dirac operator (smearing in
the action) is related to smeared Wilson loops (smeared observables) through
the hopping parameter expansion. Creutz ratios are just the finite version of
Wilson loops.

A further restriction of our study is in principle that we use gradient flow
smearing with a continuous evolution in $t_{\mathrm{fl}}$ while in an
application one will rather use stout smearing [2], which corresponds to a
very coarse discretisation in $t_{\mathrm{fl}}$. We do not expect the
behaviour in fig. 3 to change much but will check this explicitly in the near
future.

Computations for this project have been performed on the HPC cluster PAX at
DESY Zeuthen. The authors gratefully acknowledge the support of DV-Zeuthen.

## References

  * [1] A. Hasenfratz and F. Knechtli, _Phys. Rev. D_ 64 (2001) 034504 [hep-lat/0103029].
  * [2] C. Morningstar and M. J. Peardon, _Phys. Rev. D_ 69 (2004) 054501 [hep-lat/0311018].
  * [3] S. Capitani, S. Durr and C. Hoelbling, _JHEP_ 11 (2006) 028 [hep-lat/0607006].
  * [4] R. Narayanan and H. Neuberger, _JHEP_ 03 (2006) 064 [hep-th/0601210].
  * [5] M. Lüscher, _JHEP_ 08 (2010) 071 [1006.4518].
  * [6] A. Hasenfratz, R. Hoffmann and S. Schaefer, _JHEP_ 05 (2007) 029 [hep-lat/0702028].
  * [7] S. Dürr, Z. Fodor, C. Hoelbling et al., _Phys. Rev. D_ 79 (2009) 014501 [0802.2706].
  * [8] A. M. Eller and G. D. Moore, _Phys. Rev. D_ 97 (2018) 114507 [1802.04562].
  * [9] M. Okawa and A. Gonzalez-Arroyo, _PoS_ LATTICE2014 (2014) 327 [1410.7862].
  * [10] M. Lüscher and P. Weisz, _JHEP_ 02 (2011) 051 [1101.0963].
  * [11] E. Berkowitz, C. Bouchard, C. C. Chang et al., _Phys. Rev. D_ 96 (2017) 054513 [1701.07559].
  * [12] N. Husung, M. Koren, P. Krah et al., _EPJ Web Conf._ 175 (2018) 14024 [1711.01860].
  * [13] M. Lüscher and S. Schaefer, _JHEP_ 07 (2011) 036 [1105.4749].
  * [14] R. Sommer, _Nucl. Phys. B_ 411 (1994) 839 [hep-lat/9310022].
  * [15] B. Sheikholeslami and R. Wohlert, _Nucl. Phys. B_ 259 (1985) 572.
  * [16] M. Creutz, _Phys. Rev. Lett._ 45 (1980) 313.
  * [17] _http://cern.ch/luscher/openQCD/_ .
  * [18] _https://github.com/bjoern-leder/wloop_ .
  * [19] M. Donnellan, F. Knechtli, B. Leder et al., _Nucl. Phys. B_ 849 (2011) 45 [1012.3037].
  * [20] _https://mbruno46.github.io/pyobs/_ .
  * [21] U. Wolff, _Comput. Phys. Commun._ 156 (2004) 143 [hep-lat/0306017].
  * [22] N. Husung, P. Marquard and R. Sommer, _Phys. Lett. B_ 829 (2022) 137069 [2111.02347].