# Properties of nowhere dense graph classes related to independent set problem

Grzegorz Fabiański

###### Abstract.

A set is called $r$-independent, if every two vertices of it are in distance
greater then $r$. In the $r$-independent set problem with parameter $k$, we
ask whether in a given graph $G$ there exists an $r$-independent set of size
$k$. In this work we present an algorithm for this problem, which applied to a
graph from any fixed nowhere dense class, works in time bounded by
$f(k,r)|G|$, for some function $f$. We also present alternative algorithm,
with running time bounded by $g(k,r)|G|$, working on slightly more general
classes of graphs.

This work is supported by the NCN grant 2016/21/D/ST6/01485

###### Contents

  1. 1 Introduction
  2. 2 Witness existence
    1. 2.1 Notation
    2. 2.2 Preliminaries
    3. 2.3 Definitions
    4. 2.4 Proof of cowitness existence
    5. 2.5 Cowitness is already a witness
    6. 2.6 Existence of a small cowitness implies nowhere denseness
  3. 3 Algorithmic aspects
    1. 3.1 Algorithm for $r$-independent set by direct cowitness search
    2. 3.2 Ladder algorithm
  4. 4 Further work

##  1\. Introduction

#### Independent set.

An $r$-independent set is a subset of vertices of a given graph such that any
two different vertices in the set have mutual distance greater than $r$. We
focus on the following version of this problem: given a graph $G$ and integers
$r,k$ we are asked to decide whether the given graph has an $r$-independent
set of size $k$.

The unparametrized version of $r$-independent set is NP-hard, even in very
restricted settings — for example for $r=1$ and with restriction to planar
graphs of maximum vertex degree $3$, as shown in [6]. Despite this,
practically efficient algorithms are known. Examples include branching
algorithms [10] [11], and algorithms utilizing reductions [2]. Cases of planar
graphs and graphs of bounded degree are studied in detail, because branching
factors can be lifted from restricted to general settings [3].

Another line of research is focused on the parametrized version of the
independent set problem — we measure the running time not only by size of
input, but also in terms of $k$. Independent set admits a trivial algorithm
with running time $O(n^{f(k)})$ and it is believed that no quantitative
improvement is possible. In particular, the hypothesis (called
$\textit{W}[1]\not=$FPT) that there is no algorithm working in time
$f(k)n^{c}$ (where $c$ is a constant and $f$ is computable function) is widely
accepted in parametrized complexity theory and FPT-reduction to independent
set problem serves as a basic tool for showing hardness. Parametrized problems
solvable in time $f(k)n^{c}$, for some computable function $f$ and constant
$c$ are called fix-parameter trackable algorithm (FPT). In search for FPT-
algorithms, it is necessary to study this problem in more restricted settings,
where both graph the class and parameter $k$ are restricted.

The dual problem of $r$-dominating set is similarly hard and is well-studied
on restricted graph classes. Our work inherits basic concepts from the
corresponding study of $r$-dominating set on nowhere dense classes of graphs.

#### Nowhere dense graph classes.

Classes of nowhere dense graphs were introduced by Nešetřil and Ossona de
Mendez in [8] and generalize many known families of sparse graphs, for example
the following classes are nowhere dense: graphs with bounded treewidth, planar
graphs and classes defined by a forbidden (even topological) minor. Many
problems are effectively solvable on general classes of nowhere dense graphs,
allowing to replace complicated topological arguments, originating from
Robertson–Seymour graph structure theorem, by more general and simpler
combinatorial proofs.

######  Definition 1.

We say that a graph $H$ is an $r$-shallow minor of a graph $G$, if there is a
family $(B_{h})_{h\in H}$ of connected subgraphs of $G$ (called minor model)
such that the radius of each $B_{v}$ is at most $r$ and for each edge $uv$ in
the graph $H$ there are $u^{\prime}\in B_{u},v^{\prime}\in B_{v}$ such that
$u^{\prime}v^{\prime}$ is an edge in $G$. We write $H\preceq_{r}G$ to denote
that $H$ is a $r$-shallow minor of $G$.

######  Definition 2.

We say that a class of graphs $\mathcal{C}$ is nowhere dense if for every $r$
there is $t$ such that $K_{t}\not\preceq_{r}G$ for all $G\in\mathcal{C}$ (here
$K_{t}$ is a clique with $t$ vertices).

Nowhere denseness can be characterized by many other conditions (some of them
are described in [9]). In the scope of this work, a characterization in terms
of the splitter game will be used. Details will be provided in Section 2.3.

#### Dominating set.

A subset of vertices $X$ of a graph $G$ is called $r$-dominating if every
vertex in $G$ is at distance at most $r$ from some vertex of $X$. The
dominating set problem is the problem of determining if a given graph $G$ has
an $r$-dominating set of a given size $k$. The dominating set problem is a
natural dual to the independent set problem (dominating set is a covering
problem, while independent set is a packing problem).

In absence of restrictions on the class of graphs, parametrized
$1$-independent set can be fpt-reduced to $1$-dominating set. This shows that
on general graphs $1$-dominating set is at least as hard as independent set —
in fact it is believed that it is strictly harder (this hypothesis is called
$W[1]\not=W[2]$).

The computational complexity of dominating set on restricted graph classes is
well studied. FPT-algorithms were developed in bigger and bigger classes of
graphs, including classes of graphs defined by excluded minors. This line of
research culminates in showing that nowhere dense graph classes are the
largest subgraph-closed classes on which $r$-dominating set admits FPT
algorithm. More precisely, in [4] the following dichotomy was shown:

######  Theorem 1.

Let $\mathcal{C}$ be a class of graphs, closed under taking subgraphs. Then:

  * •

if $\mathcal{C}$ is nowhere dense, then for every $r$, the $r$-dominating set
problem is in FPT.

  * •

if $\mathcal{C}$ is not nowhere dense, then there is $r$ such that the
$r$-dominating set problem is as hard as on general graphs (it is
$W[2]$-hard).

The following notion of domination core is crucial for this work:

######  Definition 3.

Fix a graph $G$ and two subsets of vertices $X$ and $A$. We say that _$X$
$r$-dominates $A$_ whenever every vertex from $A$ is at distance at most $r$
from some vertex of $X$.

By this terminology, being an $r$-dominating set is equivalent to
$r$-dominating $V(G)$.

######  Definition 4.

Fix a graph $G$. We say that a set of vertices $A$ is a $(k,r)$-domination
core if for every set $X$ with $|X|\leqslant k$ (candidate for $r$-dominating
set), if $X$ $r$-dominates $A$, then $X$ $r$-dominates $G$.

The notion of domination core relaxes requirements posed on the set in
question by changing the global condition ($r$-domination of whole graph) to a
local one (domination of core). The main technical result of [13] can be
summarized as:

######  Theorem 2.

For every nowhere dense class $\mathcal{C}$ of graphs and integers
$k,r\in\mathbb{N}$ there is constant $C$ such that: for every graph
$G\in\mathcal{C}$ there exists a domination core (with parameters $k,r$) in
$G$ of size at most $C$. Moreover, it can computed in polynomial time.

#### Our results.

We prove the following:

######  Theorem 3.

Fix a nowhere dense class $\mathcal{C}$ of graphs. Then there is an algorithm
deciding the existence of an $r$-independent set of size $k$ in given graph
$G\in\mathcal{C}$ in time $f(k,r)|G|$, for some computable function $f$.
Moreover, if such an an independent set exists then the algorithm in question
will generate such a set.

This result is a strengthening of a result from [7], where an algorithm with
running in time $f(k,r)|V(G)|^{1+\epsilon}$ (for every $\epsilon>0$) is given.

We use the following definition, analogous to the definition of a domination
core.

######  Definition 5.

Fix a graph $G$. A _$(k,r)$ -witness_ (that $G$ does not have an
$r$-independent set of size $k$ in $A$) is a set $Q\subseteq G$ such that for
every $X\subseteq V(G)$ with $|X|=k$, there is a path, beginning and ending at
a vertex in $X$, that passes through $Q$ and has length at most $r$.

(Intuition: $X$ is not $r$-independent, and this fact is witnessed by $Q$.)

Our main technical result is the following:

######  Theorem 4 (Witness existence).

Fix $k,r\in\mathbb{N}$ and a nowhere dense class of graphs $\mathcal{C}$. Then
there is constant $C$ depending on $k,r$ and $\mathcal{C}$ such that for every
graph $G\in\mathcal{C}$ which does not have an $r$-independent set of size
$k$, there is a $(k,r)$-witness $Q\subseteq V(G)$ with $|Q|\leqslant C$.

In our proof, a key role is played by the notion of a cowitness defined below.

######  Definition 6.

Fix a graph $G$ with a set of vertices $A\subseteq V(G)$. A _$(k,r)$
-cowitness_ for the pair $(A,G)$ is a set $Q\subseteq V(G)$ such that for
every $X\subseteq A$ with $|X|=k$ and $A\subseteq N_{r}(X)$, for every $a\in
A$, there is a path beginning at $a$, ending at some vertex belonging to $X$,
passing through $Q$, and of length at most $r$. (Intuition: the fact that
$a\in N_{r}(X)$ is witnessed by $Q$ for every $X$ which covers all of $A$ —
not only $a$.)

As a side effect, in this work we found a new characterization of nowhere
dense graph classes — nowhere dense graph classes are exactly classes of
graphs which admit a _cowitness_ of constant size. We define the notion of
cowitness and state the characterization below:

######  Theorem 5 (Characterization by small cowitnesses).

Fix a class of graphs $\mathcal{C}$, closed under taking subgraphs. The the
following conditions are equivalent:

  1. (1)

$\mathcal{C}$ is nowhere dense,

  2. (2)

For all $r,k\in\mathbb{N}$ there is a constant $c$ such that for every
$G\in\mathcal{C}$ and every $A\subseteq G$ there is a $(k,r)$-cowitness for
the pair $(A,G)$ of size at most $c$,

  3. (3)

For all $r\in\mathbb{N}$ there is a constant $c$ such that for every
$G\in\mathcal{C}$ there is a $(1,r)$-cowitness for the pair $(V(G),G)$ of size
at most $c$.

#### My contribution.

In this work, two algorithms for the $r$-independent set problem are
described. The ladder algorithm is invented by Michał Pilipczuk, Szymon
Toruńczyk and Sebastian Siebertz. They originally developed an analogous
algorithm for $r$-dominating set and adopted for independent set. The proof of
correctness of the modified algorithm requires an analogous statement to
Theorem 2, which is given by Theorem 4. The statement dualizes easily, but the
known proof does not.

My contribution is the proof of Theorem 4. During the proof I developed the
definition of cowitness and found that it allows to characterize nowhere dense
graph classes. The proof is constructive and allows a direct construction of
an algorithm for $r$-independent set, which is the second algorithm presented
here.

I wish to thank Michał Pilipczuk and Szymon Toruńczyk, who guided me during
this work.

#### Organization of this work.

In Chapter 2 we recall some standard definitions and theorems from the theory
of nowhere dense graph classes and prove Theorems 4 and 5. In Chapter 3 we use
this result to construct two linear-time algorithms for the $r$-independent
set problem — the first is a direct consequence of the proof given, and the
second is the original ladder algorithm.

##  2\. Witness existence

###  2.1. Notation

Fix parameters $r\in\mathbb{N}$ (radius of independence), $k\in\mathbb{N}$
(size of an $r$-independent set to be found) and a graph $G$.

We write $A\subseteq G$ as a shortcut for $A$ being a subset of vertices of
$G$. Similarly $u\in G$ means that $u$ is a vertex of $G$. The subgraph
induced by a set of vertices $A$ will be denoted by $G[A]$. We measure the
size of the graph $G$ by $|G|:=|V(G)|+|E(G)|$.

The following definition implicitly depends on $r$ and $k$:

######  Definition 7.

_A short path_ is a path of length at most $r$.

We say that _a set $Q\subseteq G$ captures a set $Y\subseteq G$_ if and only
if there exists a short path connecting two different vertices in $Y$ that
passes through some vertex in $Q$ (intuition: the set $Q$ witnesses that $Y$
is not an $r$-independent set).

We say that _$Q\subseteq G$ captures a pair $(Y,z)$_, where $z\in G$ and
$Y\subseteq G$, if and only if there exists a short path connecting some $y\in
Y$ with $z$ passing through some vertex in $Q$ (intuition: the set $Q$
witnesses that $\operatorname{dist}(Y,z)<r$).

We will use the following simple fact, which is immediate from the definition:

######  Claim.

Capturing is a monotone property: if $X\subseteq Y,Q\subseteq W$ and $X$ is
captured by $Q$, then $Y$ is captured by $W$ as well.

Version for pairs: if $X\subseteq Y$, $Q\subseteq W$, $a\in G$ and $(X,a)$ is
captured by $Q$ then $(Y,a)$ is captured by $W$.

The notions of a witness and of a cowitness are key combinatorial properties
in this study. We repeat the definition, now using the terminology of
capturing:

######  Definition 8.

Fix a graph $G$. A _$(k,r)$ -witness_ (that $G$ does not have an
$r$-independent set of size $k$ in $A$) is a set $Q\subseteq G$ such that
every $X\subseteq G$, with $|X|=k$, is captured by $Q$ (intuition: $X$ is not
$r$-independent, and this fact is witnessed by $Q$).

######  Definition 9.

Fix a graph $G$ with a set of vertices $A\subseteq G$. A _$(k,r)$ -cowitness_
for $(G,A)$ is a set $Q\subseteq G$ such that for every $X\subseteq A$ with
$|X|=k$ and $A\subseteq N_{r}(X)$, for every $a\in A$, $(X,a)$ is captured by
$Q$ (intuition: the fact that $a\in N_{r}(X)$ is witnessed by $Q$ for every
$X$ which covers all of $A$ — not only $a$).

Being a witness also has the monotonicity property: if $Q$ is a witness with
parameters $k,r$, then it is also a witness with parameters $k^{\prime},r$ for
any $k^{\prime}>k$.

The goal of this section is to prove (we repeat the statements from the
introduction): See 4 This theorem follows from Theorems 5 and 6, given below:
See 5 We prove implication $(1)\rightarrow(2)$ in Section 2.4. Implication
$(2)\rightarrow(3)$ is immediate, while implication $(3)\rightarrow(1)$ will
be proved in Section 2.6.

The notion of a cowitness is much less intuitive than the notion of a witness
— a cowitness does not witness any property of a graph (in any $G$, the whole
vertex set is a cowitness for every $A\subseteq G$). Despite this, we have:

######  Theorem 6 (Cowitness is a witness (whenever possible)).

Fix a graph $G$ and a $(r,k-1)$-cowitness $Q$ for the pair $(V(G),G)$. If in
$G$ there is no $r$-independent set of size $k$, then $Q$ is a witness of
this.

We devote Section 2.5 to the proof of this theorem.

###### Proof of Theorem 4.

By Theorem 6, it is enough to show the existence of cowitness of size bounded
by $C$ (with modified parameter $k$). Such a cowitness exists by implication
$(1)\rightarrow(2)$ of Theorem 5. ∎

###  2.2. Preliminaries

In this section, we provide some definitions and results used in the proof of
Theorem 4 and 6.

Through this section we fix $r\in\mathbb{N}$.

###  2.3. Definitions

######  Definition 10.

By $\operatorname{dist}^{H}(v,w)$ we will denote distance between vertices $v$
and $w$ computed in graph a $H$, ie. the length of a shortest path in $H$,
connecting $v$ and $w$.

The $r$-neighborhood of a vertex $x$ in a graph $g$ is the set $\\{v\in
G|\operatorname{dist}^{H}(v,x)\leqslant r\\}$, denoted $N_{r}^{H}(x)$. We drop
the superscript, writing $\operatorname{dist}(v,w)$ and $N_{r}(v)$, when $H$
is clear from context.

We will be interested in distances from some vertex $v$ to a (small) set $S$,
but only up to some threshold. We call such functions distance profiles.
Formally, we define:

######  Definition 11.

A _profile on $S$_ is a function $S\rightarrow[0,1,\ldots,r,r+1]$ ($r+1$
should be seen as equivalent to $+\infty$). A set of profiles on $S$ will be
dentoes as $\mathcal{P}(S)$.

The _profile associated to a vertex_ $v\in G$ with respect to $S\subseteq G$
is the profile on $S$ such that for $s\in S$,
$\operatorname{profile}_{S}(v)(s)=\min(\operatorname{dist}(v,s),r+1)$.

The following straightforward claim shows the importance of profiles:

######  Claim.

Fix $X,Q\subseteq G$. For every $a\in G$, whether $Q$ captures $(X,a)$ depends
only on $\operatorname{profile}_{Q}(a)$. More precisly, if $a,b\in G$ are such
that $\operatorname{profile}_{Q}(a)=\operatorname{profile}_{Q}(b)$ then $Q$
captures $(X,a)$ if and only if $Q$ captures $(X,b)$.

We need a slightly stronger property — we have to understand the dependence on
the set $X$ as well as on $a$. This motivates the following notions:

######  Definition 12.

Fix $S\subseteq G$. The _profile associated to a subset $X\subseteq G$_ is the
following profile on $S$:

$\operatorname{profile}_{S}(X)(s):=\min_{x\in
X}\min(\operatorname{dist}(s,x),r+1)$

The _trace_ of a function $p:S\rightarrow\mathbb{N}$ in a graph $G$ is the set
defined as

$[p]:=\bigcup_{s\in S}N^{G}_{p(s)}(s)$

We can now state the stronger proposition:

######  Proposition 1.

Fix $Q\subseteq G$. Then for every $X\subseteq G$ and $a\in G$, $Q$ captures
$(X,a)$ if and only if the function
$\operatorname{profile}_{Q}(a)+\operatorname{profile}_{Q}(X)$ does not have
all values greater than $r$.

The set of such $a$ is equal to $[r-\operatorname{profile}_{Q}(X)]$ (where $r$
is considered as a constant function).

The proof is immediate from definitions. Note that if $p$ is a profile then
$r-p$ has range $\\{-1,0,\cdots,r\\}$ and that $N_{-1}(v)=\emptyset$.

#### Nowhere denseness.

We present a characterization of nowhere dense graph classes obtained in [1].
The following statements are slight reformulations of Theorem 4.2 and Remark
4.3 from that work.

######  Definition 13.

_(Splitter game)_ Let $G$ be a graph and let $l,r\in\mathbb{N}$. The
$(l,r)$-splitter game on $G$ is played by two players, Connector and Splitter,
as follows. We let $G_{0}:=G$. In round $i+1$ of the game, Connector chooses a
vertex $v_{i+1}\in G_{i}$ (further game play will be restricted to
$N_{r}(v_{i+1})$). Then Splitter picks a vertex $w_{i+1}\in
N_{r}^{G_{i}}(v_{i+1})$ — a vertex to be removed from arena. We let new arena
be $G_{i+1}:=G_{i}[N_{r}^{G_{i}}(v_{i+1})-\\{w_{i+1}\\}]$. Splitter wins if
$G_{i+1}=\emptyset$. Otherwise the game continues on $G_{i+1}$. If Splitter
has not won after $l$ rounds, then Connector wins.

######  Theorem 7.

Let $\mathcal{C}$ be a class of graphs. Then $\mathcal{C}$ is nowhere dense if
and only if for every $r\in\mathbb{N}^{+}$ there is $l\in\mathbb{N}^{+}$, such
that for every $G\in\mathcal{C}$, Splitter wins the $(l,r)$-splitter game on
$G$.

######  Theorem 8.

There is an algorithm $\mathcal{A}$ which given a graph $G$ and
$r\in\mathbb{N}$ plays a splitter game (interactively, playing as splitter)
such that: for every nowhere dense class $\mathcal{C}$ of graphs, there is
$d\in\mathbb{N}$ such that $\mathcal{A}$ wins in $d$ rounds.

Moreover, algorithm $\mathcal{A}$ works in linear time — given a move of the
opponent, a response in the game is generated in linear time.

We will use bounds on neighborhood complexity in nowhere dense graph classes.
In [5] the following result is proved.

######  Theorem 9.

Fix a class $\mathcal{C}$ of nowhere dense graphs. Then there is a function
$\mbox{nc}_{\mathcal{C}}$, such that for every
$\epsilon\in\mathbb{R},r\in\mathbb{N}$, every $G\in\mathcal{C}$ and every
$A\subseteq G$, the number of different profiles on set $A$ obtained by
vertices from $G$ is bounded by
$\mbox{nc}_{\mathcal{C}}(r,\epsilon)|A|^{1+\epsilon}$.

#### Greedy lemma.

We will use the following lemma:

######  Lemma 1 (Greedy lemma).

Fix a graph $G$, a set $X\subseteq G$ and $r,k\in\mathbb{N}$. Then either:

  1. (1)

There is $Y\subseteq X$ such that $|Y|>k$ and $Y$ is $2r$-independent in $G$
(equivalently: for $x\neq y$ and $x,y\in Y$, balls $N_{r}(x),N_{r}(y)$ are
disjoint).

  2. (2)

There is $Z\subseteq X$ such that $|Z|\leqslant k$ and $X\subseteq
N_{2r}^{G}(Z)$.

Moreover, there is an algorithm which for given $G,X,r,k$ computes $Y$ or $Z$
as above in time $O(k|G|)$.

###### Proof.

The lemma can be proved using a greedy algorithm, which aims at constructing
the set $Y$. Let us assume we have already constructed $Y\subseteq
X,|Y|\leqslant k$, which is $2r$-independent. There are two possibilities:

  * •

If $X\subseteq N_{2r}(Y)$, then we find $Z:=Y$ satisfying the second condition
and terminate.

  * •

Otherwise, there is $v\in X$ such that $v\not\in N_{2r}(Y)$, so $Y\cup\\{v\\}$
is $2r$-independent and larger than $Y$, hence we continue with
$Y:=Y\cup\\{v\\}$.

After $k+1$ repetitions of this procedure, we constructed a set $Y$ satisfying
the first condition. Testing whether there exists $v\not\in N_{2r}(Y)$ can be
easily done in linear time, so the final running time is $O(k|G|)$. ∎

###  2.4. Proof of cowitness existence

This section is devoted to the proof of the implication $(1)\rightarrow(2)$
from Theorem 5. By characterization of nowhere denseness in terms of the
splitter game (Theorem 7), it is sufficient to show the following theorem.

######  Theorem 10 (Cowitness existence).

For every $d,k,r\in\mathbb{N}$ there is $c\in\mathbb{N}$ such that for every
graph $G$ such that the $(d,3r)$-splitter game on $G$ is won by splitter, and
every $A\subseteq G$, there is a $(k,r)$-cowitness $Q$ for the pair $(A,G)$ of
size at most $c$.

We want to prove this theorem by induction on $d$. To do so, we must
strengthen the claim. We introduce a separator $S$ — a small set of vertices,
such that $G-S$ is simpler (in the sense that splitter can win in a smaller
number of rounds). Additionally, throughout the recursion we will maintain the
additional requirement that $S\subseteq Q$.

######  Theorem 11 (Cowitness existence — extended version).

For every $d,k,r,s\in\mathbb{N}$ there is a $c\in\mathbb{N}$ such that for
every graph $G$ and $S\subseteq G$ with $|S|=s$ such that the
$(d,3r)$-splitter game on $G^{\prime}:=G-S$ is won by splitter, and for every
$A\subseteq G$, there is a $(k,r)$-cowitness $Q$ for the pair $(A,G)$ of size
at most $c$, satisfying $S\subseteq Q$.

Obviously, Theorem 10 follows from Theorem 11 by considering $s:=0$. The
remainder of this section is devoted to the proof of Theorem 11.

Fix $d,r,s,G,A$. We want to find a $(k,r)$-cowitness $Q$ for the pair $(A,G)$.

We proceed by induction on $d$. The initial step is obvious: $d=0$ means that
$V(G)=S$ and we can take $Q:=V(G)$ and $c=s$.

Now we consider the induction step.

######  Lemma 2.

Take any $v\in G$. Define $w_{v}$ to be a wining splitter response for the
connector play at $v$ in the $(d,3r)$-splitter game and $G_{v}$ to be
$G[N_{3r}^{G^{\prime}}(v)\cup S]$. Then $(G_{v},S\cup\\{w_{z}\\},A^{*})$
satisfies the induction hypothesis, for every $A^{*}\subseteq G_{v}$.

###### Proof.

By definition of the splitter game, splitter win the $(d-1,3r)$ splitter game
in $G[N_{3r}(v)-\\{w_{v}\\}]=G_{v}-(S\cup\\{w_{v}\\})$. ∎

######  Lemma 3.

There is a set $Z$ of size bounded by a function of $k,r,s$, such that: For
every pair $(X,a)$ with $|X|\leqslant k$, $A\subseteq N_{r}^{G}(X)$ and $a\in
A$: if $(X,a)$ is not captured by $S$, then $a\in N^{G^{\prime}}_{2r}(Z)$

###### Proof.

Fix $G,S,A,r,k$ and $k$ as in the statement. For a profile $p$ on $S$, define

$T_{p}:=\\{x\in A|\operatorname{profile}_{S}(x)=p\\}$

We apply Lemma 1 in the graph $G^{\prime}$ to $T_{p}$. If the second case of
the lemma holds, say that the profile $p$ is covered, and define $Z_{p}$ to be
the outcome of the application of the lemma. Thus $T_{p}\subseteq
N_{2r}^{G^{\prime}}(Z_{p})$.

######  Claim.

If for some vertex $a\in T_{p}$ and set $X\subseteq G$ with $|X|\leqslant k$,
such that the pair $(X,a)$ is not captured by $S$, then the profile $p$ is
covered.

###### Proof.

We show that we are always in case $2$ of the lemma. Assume otherwise: there
is $Y_{p}$ such that $|Y_{p}|>k$ and balls $N_{r}^{G^{\prime}}(y)$, for all
$y\in Y_{p}$, are disjoint.

By assumption $|X|\leqslant k$, so for at least one $y\in Y_{p}$, the ball
$N_{r}^{G^{\prime}}(y)$ is disjoint with $X$.

We claim that $\operatorname{dist}^{G}(y,X)>r$. We already know that this fact
holds in $G^{\prime}$. The only remaining thing to show is the impossibility
of connecting $y$ with $X$ by a short path passing through $S$. But this is
impossible by the assumption that $S$ does not capture $(X,a)$, because $y$
and $a$ have the same profiles on $S$. ∎

Define $Z$ as $Z:=\bigcup_{p}Z_{p}$, where sum ranges over all profiles $p$
which are covered.

We claim that $X$ satisfies the required condition. Indeed, for every $a\in G$
and $X\subseteq G$ with $|X|\leqslant k$ such that $(X,a)$ is not captured by
$S$, the $\operatorname{profile}^{G}_{S}(a)$ is covered and so $a\in
T_{p}\subseteq N^{G^{\prime}}_{2r}(Z_{r})\subseteq N^{G^{\prime}}_{2r}(Z)$. ∎

######  Lemma 4.

For each $z\in Z$ and profile $p$ on $S$ there is a set $A_{z,p}$ such that
the following holds.

For every $(X,a)$ which is not captured by $S$ there is a pair $(z,l)$ such
that any cowitness $Q_{z,l}$ for $(G_{z},A_{z,l})$ captures $(X,a)$.

###### Proof of Lemma 4 $\rightarrow$ Theorem 11.

Define $Q=\bigcup_{z\in Z,p\in\mathcal{P}}Q_{z,p}$, where $Q_{z,p}$ is a
cowitnesses for the pair $(G_{z},A_{z,p})$, obtained by applying the induction
hypothesis to the $(G_{z},S\cup\\{w_{z}\\},A_{z,p})$.

Then $|Q|$ is bounded by induction hypothesis. ∎

It remains to prove the lemma.

###### Proof of lemma 4.

For $z\in Z$. Define $A_{z}:=A\cap N^{G^{\prime}}_{2r}(z)$ and let
$A_{z,p}:=A_{z}-[r-p]$, where $p$ is a profile on $S$.

Let $(X,a)$ ($X\subseteq G,a\in A$) be a pair which is not captured by $S$.

By Lemma 3, we can find $z\in Z$ such that $a\in N^{G^{\prime}}(z)$. Let
$l:=\operatorname{profile}_{S}(X)$. We show that $z,l$ satisfies the required
property.

Let $X_{z}=X\cap V(G_{z})$. Let $Q_{z,l}$ be a cowitness for
$(G_{z},A_{z,l})$.

We show that $Q_{z,l}$ captures $(X_{z},a)$, which implies that $Q_{z,l}$
captures $(X,a)$ since $X_{z}\subseteq X$.

As $Q_{z,l}$ is a cowitness for $(G_{z},A_{z,l})$, it is enough to show the
following properties:

  1. (1)

$A_{z,l}\subseteq N_{r}^{G^{\prime}}(X_{z})$

  2. (2)

$a\in A_{z,l}$

To prove these properties we define two subsets of $A_{z}$:

  * •

$A_{z}^{1}$ is the set of these vertices in $A_{z}$ that can be connected to a
vertex from $X$ by a short path passing through $S$,

  * •

$A_{z}^{2}$ is the set of these vertices in $A_{z}$ that can be connected to a
vertex from $X$ by a short path laying inside $G^{\prime}$.

By $A\subseteq N_{r}^{G}(X)$, any vertex from $A_{z}$ satisfies at least one
of these two conditions. The fact that $(X,a)$ is not captured by $S$ can be
equivalently expressed as $a\not\in A_{z}^{1}$.

By Proposition 1, $A_{z,l}=A_{z}-A^{1}_{z}$. As $a\not\in A_{z}^{1}$ and $a\in
A_{z}$ then $a\in A_{z,l}$, proving $(2)$.

######  Claim.

$A_{z}^{2}\subseteq N^{G_{z}}_{r}(X_{z})$

###### Proof.

Take $v\in A_{z}^{2}$ and fix a short path lying in $G^{\prime}$ that connects
vertex from $A$ with vertex $x\in X$. Since $A_{z}\subseteq
N_{2r}^{G^{\prime}}(z)$ and $\operatorname{dist}^{G^{\prime}}(v,x)\leqslant r$
then $x\in N_{3r}^{G^{\prime}}(z)$. So $x\in X_{z}$. ∎

In particular, $A_{z,l}=A_{z}-A_{z}^{1}\subseteq A_{z}^{2}\subseteq
N^{G^{\prime}}_{r}(X_{z})$ proving $(1)$.

By $(1)$ and $(2)$ and the fact that $Q_{z,p}$ is a cowitness for
$(G_{z},A_{z,l})$, we have that $Q_{z,l}$ captures $(X_{z},a)$, hence also
$(X,a)$. ∎

[p]
---
A
---
G’
---
S
---
z
---
distance from t:
---
2r
---
r
---
a
---
S
---
z
---
a
---
Figure 1. Left: $G_{t}$, two vertices from $X$ with $r$-neighborhoods (taken
in $G^{\prime}$) and two short paths. Note that a short path passing through
$S$ connects two vertices being apart in $G^{\prime}$. Right: visualization of
a profile and $A_{z,p}$

######  Corollary 1.

In Theorem 2.4 we can bound size of the cowitness $Q$ by
$|Q|\leqslant(rk)^{d(1+o(1))}$ for some constant $d$ depending only on class
$\mathcal{C}$ and $r$. Moreover, a cowitness of that size can be computed in
time $O(|G||Q|)$.

###### Proof.

Let $c(r,k,d,s)$ be the smallest number for which Theorem 11 holds.

From the proof given above we have that:

$c(r,k,d,s)\leqslant
c(r,k,d-1,s+1)|Z|(r+1)^{s}=(k+1)(r+1)^{2s}c(r,k,d-1,s+1);$
$c(r,k,0,s)\leqslant s.$

This gives upper bound:

$c(r,k,d,s)\leqslant(k+1)^{d}((r+1)^{2})^{s+(s+1)+\cdots(s+d-1)}c(r,k,0,s+d)=(d+s)(k+1)^{d}(r+1)^{2sd+d(d-1)}$

Which implies that:

$c(r,k,d,0)\leqslant d(k+1)^{d}(r+1)^{d(d-1)}$

The cowitness can be computed: the provided proof is not only constructive,
but effectively computable by a recursive algorithm:

  * •

Compute $Z$ using computability of greedy lemma — this phase is done in time
$O(k|G|)$

  * •

Compute pairs $(G_{z},A_{z,p})$ — each such pair can be found in linear time

  * •

For each each pair above we make a recursive subcall.

All steps are done in time (not counting execution of recursive subcalls)
$|G|(R+k)$ where $R$ is a number of recursive subcalls. Always $k\leqslant R$,
so running time is bounded by $|Q||G|$ (the fraction is the number of leaves
of recursion). ∎

###  2.5. Cowitness is already a witness

We repeat statement for convenience: See 6

###### Proof.

Assume otherwise — that $Q$ is a cowitness, but not a witness. Then there is
$X\subseteq G$ with $|X|=k$ such that $Q$ does not captures $X$. From all such
choices of $X$, fix one which minimizes the function:

$f(X)=\left|\\{w\in X|\exists v\in
X:v\not=w\land\operatorname{dist}(v,w)\leqslant r\\}\right|.$

There is no a $r$-independent set of size $k$ in $G$, so there are $w,v\in X$
such that $w\not=v$ and $\operatorname{dist}(w,v)\leqslant r$.

If $N_{r}(X-\\{w\\})=V(G)$ then, by applying the definition of cowitness to
the pair $(X-\\{w\\},w)$, we get that $Q$ captures $X$, a contradiction.

Assume otherwise, that $N_{r}(X-\\{w\\})\subsetneq V(G)$. Take any
$w^{\prime}\not\in N_{r}(X-\\{w\\})$. Define
$X^{\prime}:=X\cup\\{w^{\prime}\\}-\\{w\\}$. We claim that $X^{\prime}$ is a
smaller counterexample:

######  Claim.

$X^{\prime}$ is not captured by $Q$.

###### Proof.

Assume it is: then there is a short path between $x_{1},x_{2}\in
X^{\prime},x_{1}\neq x_{2}$ going through $Q$. As $w^{\prime}\not\in
N_{r}(X^{\prime}-\\{w\\})$, we have $x_{1},x_{2}\neq w$. The considered path
connects two vertices from $X$, so $Q$ captures $X$, a contradiction. ∎

It only remains to show that $f(X^{\prime})<f(X)$ — by construction
$f(X^{\prime})=f(X-\\{w\\})<f(X)$. This finishes the proof. ∎

The computational version of this problem can be solved efficiently:

######  Theorem 12.

Given is graph $G$, parameters $k,r$, set $Q$ promised to be
$(k-1,r)$-cowitness for pair $(V(G),G)$, and a set $X$ promised not to be
captured by $Q$. Then an $r$-independent set of size $k$ in $G$ can be
computed in time $O(k^{2}|G|)$.

###### Proof.

Such algorithm can be easily extracted from proof of Theorem 6 — it describes
a constructive procedure which from any $X$ not captured by $Q$ and not being
an $r$-independent set (this is equivalent to $f(X)>0$) generates $X^{\prime}$
such that $|X^{\prime}|=|X|=k,f(X^{\prime})<f(X)$ and $Q$ does not capture
$X^{\prime}$. This procedure computes $X^{\prime}$ in time $O(k|G|)$.

Iterating it at most $k$ times we get $X^{\prime}$ such that
$f(X^{\prime})=0$. This means that $X^{\prime}$ is an $r$-independent set. ∎

###  2.6. Existence of a small cowitness implies nowhere denseness

We now prove implication $(3)\rightarrow(1)$ from Theorem 5:

######  Theorem 13.

Fix a class $\mathcal{C}$ of graphs closed under taking subgraphs. Assume that
for every $r$ there is a constant $c$ such that for every $G\in\mathcal{C}$
there is a $(1,r)$-cowitness for the pair $(V(G),G)$ of size at most $c$. Then
$\mathcal{C}$ is nowhere dense.

We use following characterization of somewhere denseness (origins of this
statement are not clear, see Claim 6.1 with discussion from [4]):

######  Definition 14.

A $r$-subdivision of a graph $G$ is a graph constructed by replacing edges
from $G$ by paths of length $r+1$ (for every edge in $G$, new $r1$ vertices
are added in the middle of the edge).

######  Theorem 14.

Let $\mathcal{C}$ be closed under taking subgraphs. Then $\mathcal{C}$ is
somewhere dense if and only if there is $r$ such that $\mathcal{C}$ contains
the $r$-subdivision of every simple graph.

###### Proof of Theorem 2.6.

It is sufficient to prove that the $r$-subdivision of clique $K_{n}$ does not
have $(1,r+1+\lceil r/2\rceil)$-cowitness for pair $(V(G),G)$ of size smaller
than $\lfloor(n-1)/2\rfloor$. Assume there is such a cowitness $Q$.

Define $D$ to be the set of all vertices of degree $n-1$, then $|D|=n$. By
$|Q|\leqslant\lfloor(n-1)/2\rfloor$ we know that there is $v\in D$ such that
$D\not\in Q$. Take $X:=\\{v\\}$. Then $N_{r+1+\lceil r/2\rceil}(X)=V(G)$ and
$r+1+\lceil r/2\rceil$ is the smallest such constant.

Take $a,b\in D$ to be any two different vertices, different from $v$. Take $c$
to be one of two vertices in the middle of the subdivided edge between $a$ and
$b$ (in case when $r$ is even we choose the one that is nearer to $a$). We
consider paths of length $r+1+\lceil r/2\rceil$ connecting $v$ and $c$ — at
least one of such paths must has nonempty intersection with $Q$. When $r$ is
even, then there is exactly one such path, if $r$ is odd — exactly two.
Anyway, the union of all such paths is contained in the set $W_{a,b}$
consisting of subdivided edges $(v,a),(v,b),(a,b)$.

By $v\not\in Q$ we have that $W_{a,b}-\\{v\\}$ have nonempty intersection with
$Q$.

The sets $W_{a,b}-\\{v\\}$ and $W_{c,d}-\\{v\\}$ are disjoint whenever the
sets $\\{a,b\\}$ and $\\{c,d\\}$ are disjoint. By ranging over all possible
indices (from $D-\\{v\\}$) we can construct $\lfloor(n-1)/2\rfloor$ such
disjoint sets. All such sets contain element from $Q$, which contradicts that
$|Q|<\lfloor(n-1)/2\rfloor$. ∎

##  3\. Algorithmic aspects

In this section we apply the obtained results to construct two algorithms for
parametrized $r$-independent set in nowhere dense graph classes. The first
approach uses direct cowitness search, as established in Theorem 1. The second
one originates in stability theory and depends only on existence of small
witnesses (Theorem 4).

###  3.1. Algorithm for $r$-independent set by direct cowitness search

We want to prove the following Theorems.

######  Theorem 15.

The problem of checking, given a graph $G$ and subset $Q\subseteq G$, whether
$Q$ is a witness for $G$ can be done in time $O(|G||Q|+2^{k|Q|(1+o(1))})$ on
general graphs and (for every $\epsilon)$ in time
$O(|G||Q|+\mbox{nc}_{\mathcal{C}}(\epsilon,r)^{k}|Q|^{k(1+o(1))}$ on a nowhere
dense graph class $\mathcal{C}$.

######  Theorem 16.

On nowhere dense classes $\mathcal{C}$, the problem of finding an
$r$-independent set of size $k$ (or conclude that it does not exist) can be
solved in time
$O(|G|(rk)^{d(1+o(1))}+\mbox{nc}_{\mathcal{C}}(\epsilon,r)^{k}(kr)^{dk(1+\epsilon+o(1))})$
for some constant $d$ which depends only on the class $\mathcal{C}$.

###### Proof of Theorem 15.

We check if every $X\subseteq G$ with $|X|=k$ satisfies that there are
distinct vertices $x_{1},x_{2}\in X$ and $q\in Q$ such that
$\operatorname{dist}(x_{1},q)+\operatorname{dist}(q,x_{2})\leqslant r$.

Observe that whether given $X$ satisfies this property depends only on the
multiset of profiles $\\{\\{\operatorname{profile}^{Q}_{r}(x)|x\in X\\}\\}$.
So instead of considering all $X\subseteq G$ with $|X|=k$ it is sufficient to
consider all multisubsets of size $k$ of
$B:=\\{\\{\operatorname{profile}_{r}^{Q}(v)|v\in G\\}\\}$ — the multiset of
all realized profiles to $Q$ in $G$.

The set $B$ can be computed in time $|Q||G|$ by running $BFS$ from every
vertex from $Q$.

Despite $|B|=|G|$, the number of different elements in $B$ is bounded by
$(r+2)^{|Q|}$ — the number of profiles to the set $Q$. In case when $G$
belongs to some nowhere dense class of graphs, for every $\epsilon>0$ we have
the better bound by $\mbox{nc}_{\mathcal{C}}(\epsilon,r)|Q|^{1+\epsilon}$
(Theorem 9).

It follows that the number of different submultisets of $B$ of size $k$ is
bounded by $r^{|Q|k(1+o(1))}$ in case of general graphs, and by
$\mbox{nc}_{\mathcal{C}}(\epsilon,r)^{k}|Q|^{k(1+\epsilon)}$ in case of graphs
belonging to a nowhere dense class $\mathcal{C}$.

Checking each such submultiset is done in time $O(k|Q|)$ (for each $q\in Q$ we
search for two nearest vertices from $X$). ∎

###### Proof of Theorem 16.

We can compute a cowitness $Q$ of size $(kr)^{d(1+o(1))}$ in time $|Q||G|$.
Then, by Theorem 6, the problem of deciding whether there is an
$r$-independent set of size $k$ is equivalent to deciding whether $Q$ is a
witness. By Theorem 12, this reduction also holds for the computational
version of the independent set problem.

By applying the algorithm from Theorem 15 we are done. ∎

###  3.2. Ladder algorithm

In this section we describe an alternative algorithm to find an
$r$-independent set. It works correctly on any graph. When the input graphs
are restricted to some class of graphs which satisfies additional properties
(that are more general then the assumption of nowhere denseness), the
presented algorithm works in linear FPT time, otherwise there is no specific
time bound.

We will work with formulas of first order logic. For tuples
$\overline{x}=(x^{1},\ldots,x^{n})$ and $\overline{y}=(y^{1},\ldots,y^{m})$,
fix a formula $\phi(\overline{x},\overline{y})$ of first order logic with free
variables $x^{1},\ldots,x^{n}$ and $y^{1},\ldots,y^{m}$.

######  Definition 15.

A _ladder_ for formula $\phi(\overline{x},\overline{y})$ of length $d$ is a
family of tuples $\overline{x}_{i},\overline{y}_{j}$ (of length respectively
$n$ and $m$), defined for odd $i\in\\{1,\ldots,d\\}$ and even
$j\in\\{2,\ldots,d\\}$, such that $\phi(\overline{x}_{i},\overline{y}_{j})$
holds if and only if $i<j$.

######  Definition 16.

A class of graphs $\mathcal{C}$ is called _stable_ if and only if for any
formula $\phi(\overline{x},\overline{y})$ there is a constant $c$ such that
there is no ladder for $\phi$ of length $c$ in any $G\in\mathcal{C}$.

Adler and Adler proved in [1] that:

######  Theorem 17.

Fix a class $\mathcal{C}$ of graphs closed under taking subgraphs. Then
$\mathcal{C}$ is stable if and only if $\mathcal{C}$ is nowhere dense.

######  Definition 17.

Let $\operatorname{set}(\overline{x})$ be the set of elements appearing in the
tuple $\overline{x}$.

Define $\psi_{r,k;n,m}(\overline{x},\overline{y})$ to be the formula
describing the property that $\operatorname{set}(\overline{x})$ is not
captured by $\operatorname{set}(\overline{y})$. This property can be easily
expressed in first order logic.

######  Remark 1.

The formula $\psi_{r,k,n,m}$ is independent of the order of elements inside
the tuple. Therefore, in the ladder for $\psi$ we can use sets instead of
tuples if we additionally require that the sets $X_{i},Y_{j}$ have sizes at
most $n$ and $m$, respectively.

By generalized ladder we will mean ladder of sets not necessarily satisfying
that sets $X_{i},Y_{j}$ have sizes bounded by $n$ and $m$.

The goal of this section is to prove the following:

######  Theorem 18.

There is algorithm $A$ that given a graph $G$, and $k,r\in\mathbb{N}$ produces
either:

  1. (a)

an $r$-independent set of size $k$, or

  2. (b)

a witness that $G$ has no $r$-independent set of size $k$

On any class of graphs $\mathcal{C}$ satisfying both of the following
assumptions, the algorithm $A$ works in time $f(k,r)|G|$ and generates
witnesses of size bounded by a function of $r$ and $k$.

  1. (1)

There is a constant $c$ such that for any graph $G\in\mathcal{C}$ if $G$ does
not have an $r$-independent set of size $k$, then $G$ has a witness of this of
size at most $c$

  2. (2)

There is a constant $d$ such that there is no ladder for $\psi_{r,k;k,c}$ of
length $d$ in any graph from $\mathcal{C}$.

######  Remark 2.

Assumptions $1$ and $2$ are satisfied by every nowhere dense graph class, by
Theorems 5 and 17. Note that we do not require any computability of a witness
in our class $\mathcal{C}$, only its existence.

###### Proof of theorem 18.

Our algorithm tries to construct a generalized ladder for $\psi_{r,k,k,c}$
step by step. When it fails to enlarge the ladder then we get either $(a)$ or
$(b)$. The ladder in the construction will have the additional property that
$|X_{i}|=k$ and, in presence of $(2)$, $|Y_{i}|\leqslant c$.

Assume we have already constructed a ladder of length $d$. We have two steps:

####  $Y$-step: witness search.

Assume that $d$ is even. We want to find $Y_{d+1}$.

If any $X_{i}$ constructed so far is $r$-independent, we can terminate
concluding $(a)$. Assume otherwise. We aim at finding a set that witnesses
that $X_{i}$ is not $r$-independent for all odd $i\in\\{1,\ldots,d\\}$.
Assumption $(2)$, if present, guarantees the existence of such witness of size
at most $C$.

To find the witness we consider profiles. Whether $Q$ is a witness for all
$X_{i}$ depends only on the set $\\{\operatorname{profile}_{W}(x)|x\in Q\\}$,
where $W=\bigcup_{i}X_{i}$. The size of $W$ is bounded by $kd$ — so the number
of profiles and number of sets of profiles are also bounded.

We proceed as follows:

  1. (1)

We compute $\operatorname{profile}_{W}$ for all vertices in $G$. This can be
done by starting BFS from each vertex in $W$ — this procedure takes time
$O(|W||G|)$. Denote the set of all found profiles by $P$.

  2. (2)

We iterate over all subsets of $P$ and check whether the corresponding set
witnesses all $X_{i}$. As $Y_{i+1}$ we take the smallest witness.

The size of set $P$ is bounded by $r^{kd}$, thus the second step takes time
$O(kd2^{|P|})=O(2^{(r^{kd})}kd)$. By choosing the smallest possible witness,
we make the algorithm uniform: when $(2)$ holds, we do not need to know $c$ in
advance, as the found witness will be of size at most $c$.

####  $X$-step: finding candidate for an $r$-independent set.

Assume that $d$ is odd. We want to find a set $X_{i+1}$ such that none of
$Y_{i}$’s witnesses that $X_{i+1}$ is not an $r$-independent set.

We check if $A_{i}=\bigcup_{j}Y_{j}$ is a witness — by Theorem 15 this can be
done in time $f(|A_{i}|)|G|$ and in constructive way (if $A_{i}$ is not a
witness, then a set of size $k$ that is not witnessed is generated). Now we
can conclude:

  * •

If $A_{i}$ is a witness then we can conclude $(b)$ — note that the size of
$A_{i}$ is bounded by $dC$.

  * •

If $A_{i}$ is not a witness, take $X_{i+1}$ to be any set not witnessed by
$A_{i}$ — it will not be witnessed by any $Y_{i}$ and meets the stated
requirement.

#### Halting property.

On classes of graphs satisfying (1) and (2), we make at most $d$ rounds by
assumption, because at every step of the algorithm, sets
$X_{1},Y_{2},X_{3},\ldots,$ form a ladder. The algorithm is correct by
construction and we already argued that we produce a witness of size at most
$dc$.

To prove the halting property on general graphs we need to bound the length of
the ladder. Observe that $A_{l}$ is a strictly increasing family of sets (as a
function of $l$). After at most $n$ steps, $A_{l}=G$ ($l$ is the number of
steps up to that point). We prove that we terminate in at most two steps.

In the next step, the algorithm will be checking whether there exists set not
captured by $A_{l}=V(G)$ — this is equivalent to checking whether $G$ has an
$r$-independent set. If such a set is not found then the witness $V(G)$ is
returned. If such a set $B$ is found, then the ladder is enlarged by one step
and the $r$-independent set $B$ is returned in the subsequent step. ∎

##  4\. Further work

For the ladder algorithm we use the bound of ladder length obtained by general
argument of stability. For the particular $\psi$ that we used, maybe better
bounds can be obtained in restricted settings, for example on planar graphs or
graphs with bounded treewidth.

Practical evaluation of this algorithm is of independent interest. Various
heuristic improvements seem reasonable — including playing splitter game more
efficiently, using partial cowitnesses found in another branch of the
cowitness finding algorithm, identifying and pruning unimportant vertices
found during the ladder construction.

## References

  * [1] Hans Adler and Isolde Adler.  Interpreting nowhere dense graph classes as a classical notion of model theory.  Eur. J. Comb., 36:322–330, 2014.
  * [2] Takuya Akiba and Yoichi Iwata.  Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover.  Theor. Comput. Sci., 609:211–225, 2016.
  * [3] Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, and Johan M. M. van Rooij.  Fast algorithms for max independent set.  Algorithmica, 62(1-2):382–415, 2012.
  * [4] 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 Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 31:1–31:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  * [5] 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 Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 63:1–63:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  * [6] M. R. Garey, David S. Johnson, and Larry J. Stockmeyer.  Some simplified np-complete graph problems.  Theor. Comput. Sci., 1(3):237–267, 1976.
  * [7] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 89–98. ACM, 2014\.
  * [8] Jaroslav Nesetril and Patrice Ossona de Mendez.  First order properties on nowhere dense structures.  J. Symb. Log., 75(3):868–887, 2010.
  * [9] Jaroslav Nesetril and Patrice Ossona de Mendez.  Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics.  Springer, 2012.
  * [10] Etsuji Tomita, Yoichi Sutani, Takanori Higashi, and Mitsuo Wakatsuki.  A simple and faster branch-and-bound algorithm for finding a maximum clique with computational experiments.  IEICE Transactions, 96-D(6):1286–1298, 2013.
  * [11] Mingyu Xiao and Hiroshi Nagamochi.  Exact algorithms for maximum independent set.  In Leizhen Cai, Siu-Wing Cheng, and Tak Wah Lam, editors, Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, volume 8283 of Lecture Notes in Computer Science, pages 328–338. Springer, 2013.