tcb@breakable

# An improved kernelization algorithm for Trivially Perfect Editing

Maël Dumas  Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067
Orléans, France  Anthony Perez  Univ. Orléans, INSA Centre Val de Loire, LIFO
EA 4022, F-45067 Orléans, France

###### Abstract

In the Trivially Perfect Editing problem one is given an undirected graph
$G=(V,E)$ and an integer $k$ and seeks to add or delete at most $k$ edges in
$G$ to obtain a trivially perfect graph. In a recent work, Dumas et al. [16]
proved that this problem admits a kernel with $O(k^{3})$ vertices. This result
heavily relies on the fact that the size of trivially perfect modules can be
bounded by $O(k^{2})$ as shown by Drange and Pilipczuk [14]. To obtain their
cubic vertex-kernel, Dumas et al. [16] then showed that a more intricate
structure, so-called _comb_ , can be reduced to $O(k^{2})$ vertices. In this
work we show that the bound can be improved to $O(k)$ for both aforementioned
structures and thus obtain a kernel with $O(k^{2})$ vertices. Our approach
relies on the straightforward yet powerful observation that any large enough
structure contains unaffected vertices whose neighborhood remains unchanged by
an editing of size $k$, implying strong structural properties.

##  1 Introduction

In the Trivially Perfect Editing problem one is given an undirected graph
$G=(V,E)$ and an integer $k$ and seeks to _edit_ (add or delete) at most $k$
edges in $G$ so that the resulting graph is trivially perfect (i.e. does not
contain any cycle on four vertices nor path on four vertices as an induced
subgraph). More formally we consider the following problem:

Trivially Perfect Editing Input: A graph $G=(V,E)$, a _parameter_
$k\in\mathbb{N}$ Question: Does there exist a set $F\subseteq(V\times V)$ of
size at most $k$ such that the graph $H=(V,E\triangle F)$ is trivially perfect
?

Here $E\triangle F=(E\cup F)\setminus(E\cap F)$ denotes the symmetric
difference between sets $E$ and $F$. We define similarly the deletion (resp.
completion) variant of the problem by only allowing to delete (resp. add)
edges. Graph modification covers a broad range of well-studied problems that
find applications in various areas. For instance, Trivially Perfect Editing
has been used to define the community structure of complex networks by Nastos
and Gao [30] and is closely related to the well-studied graph parameter tree-
depth [20, 32]. Theoretically, some of the earliest NP-Complete problems are
graph modification problems [25, 19]. Regarding edge (graph) modification
problems, one of the most notable one is the Minimum Fill-in problem which
aims at adding edges to a given graph to obtain a chordal graph (i.e. a graph
that does not contain any induced cycle of length at least $4$). In a seminal
result, Kaplan et al. [24] proved that Mininum Fill-in admits a parameterized
algorithm as well as a kernel containing $O(k^{3})$ vertices. This result was
later improved to $O(k^{2})$ vertices by Natanzon et al. [31]. Parameterized
complexity and kernelization algorithms provide a powerful theoretical
framework to cope with decision problems.

#### Parameterized complexity

A parameterized problem $\Pi$ is a language of $\Sigma^{*}\times\mathbb{N}$,
where $\Sigma$ is a finite alphabet. An instance of a parameterized problem is
a pair $(I,k)$ with $I\subseteq\Sigma^{*}$ and $k\in\mathbb{N}$, called the
_parameter_. A parameterized problem is said to be _fixed-parameter tractable_
if it can be decided in time $f(k)\cdot|I|^{O(1)}$. An equivalent definition
of fixed-parameter tractability is the notion of _kernelization_. Given an
instance $(I,k)$ of a parameterized problem $\Pi$, a _kernelization algorithm_
for $\Pi$ (kernel for short) is a polynomial-time algorithm that outputs an
equivalent instance $(I^{\prime},k^{\prime})$ of $\Pi$ such that
$|I^{\prime}|\leqslant h(k)$ for some function $h$ depending on the parameter
only and $k^{\prime}\leqslant k$. It is well-known that a parameterized
problem is fixed-parameter tractable if and only if it admits a kernelization
algorithm (see e.g. [18]). Problem $\Pi$ is said to admit a _polynomial
kernel_ whenever $h$ is a polynomial.

#### Related work

Since the work of Kaplan et al. [24] many polynomial kernels for edge
modification problems have been devised (see e.g. [3, 2, 12, 23, 1, 14, 26,
15, 11]). There is also evidence that under some reasonable theoretical
complexity assumptions, some graph modification problems do not admit
polynomial kernels [27, 22, 8, 29]. We refer the reader to a recent
comprehensive survey on kernelization for edge modification problems by
Crespelle et al. [9]. The Trivially Perfect Editing problem has been well-
studied in the literature [5, 21, 4, 1, 14, 16, 28, 30]. Recall that trivially
perfect graphs are a subclass of chordal graphs that additionally do not
contain any path on four vertices as an induced subgraph. These graphs are
also known as _quasi-threshold_ graphs. We note here that while the NP-
Completeness of completion and deletion toward trivially perfect graphs has
been known for some time [33, 6], the NP-Completeness of Trivially Perfect
Editing remained opened until the work of Nastos and Gao [30]. Thanks to a
result of Cai [7] stating that graph modification toward _any_ graph class
characterized by a finite set of forbidden induced subgraphs is fixed-
parameter tractable, Trivially Perfect Editing is fixed-parameter tractable.
Regarding kernelization algorithms, Drange and Pilipczuk [14] provided a
kernel containing $O(k^{7})$ vertices, a result that was recently improved to
$O(k^{3})$ vertices by Dumas et al. [16]. These results also work for the
deletion and completion variants. For the latter problem, a recent result by
Bathie et al. [1] improves the bound to $O(k^{2})$ vertices.

As part of the proof for the size of their cubic vertex-kernel, Dumas et al.
[16] subsequently showed the following result. The structures used in Theorem
1 shall be defined later.

######  Theorem 1 ([16]).

Let $(G,k)$ be an instance111As we shall see Section 3.1 the instance also
needs to be further reduced under standard reduction rules. of Trivially
Perfect Editing such that the sizes of its _trivially perfect modules_ and
_combs_ are bounded by $p(k)$ and $c(k)$, respectively. If $(G,k)$ is a Yes-
instance then $G$ has $O(k\cdot(p(k)+c(k))$ vertices.

The cubic vertex-kernel of Dumas et al. [16] relied on a result of Drange and
Pilipczuk [14] that proved that $p\in O(k^{2})$ and then used new reduction
rules implying that $c\in O(k^{2})$.

#### Our contribution

We provide reduction rules and structural properties on trivially perfect
graphs that will imply an $O(k)$ bound for both functions $p$ and $c$ of
Theorem 1. These new reduction rules allow us to prove the existence a
quadratic vertex-kernel for Trivially Perfect Editing. To bound the size of
trivially perfect modules by $O(k)$, we first reduce the ones that contain a
large matching of non-edges with the use of a simple reduction rule. To bound
the ones that do not contain such structures, we will rely on so-called
_combs_ , introduced by Dumas et al. [16]. Combs correspond to parts of the
graph that induce trivially perfect graphs (but not necessarily modules) with
strong properties on their neighborhoods. They are composed of two main parts,
called the _shaft_ and the _teeth_ , that will be independently reduced to a
size linear in $k$. The reduction rule dealing with shafts will ultimately
allow us to bound the size of trivially perfect modules with no large matching
of non-edges. Our approach relies on the straightforward yet powerful
observation that any large enough structure contains unaffected vertices whose
neighborhood remains unchanged by an editing of size $k$. Finally, we note
that our kernel works for both the deletion and completion variants of the
problem.

#### Outline

Section 2 presents some preliminary notions and structural properties on
(trivially perfect) graphs. Section 3 describes known as well as our
additional reduction rules to obtain the claimed kernelization algorithm while
Section 4 explain why our kernel is safe for the deletion variant of the
problem. We conclude with some perspectives in Section 5.

##  2 Preliminaries

We consider simple, undirected graphs $G=(V,E)$ where $V$ denotes the vertex
set of $G$ and $E\subseteq(V\times V)$ its edge set. We will sometimes use
$V(G)$ and $E(G)$ to clarify the context. The open (respectively closed)
neighborhood of a vertex $u\in V$ is denoted by $N_{G}(u)=\\{v\in
V\mid\\{u,v\\}\in E\\}$ (respectively $N_{G}[u]=N_{G}(u)\cup\\{u\\}$). Given a
subset of vertices $S\subseteq V$ the neighborhood of $S$ is defined as
$N_{G}(S)=\\{v\in V(G)\setminus S\mid\\{u,v\\}\in E\\}$. Similarly, given a
vertex $u\in V$ and $S\subseteq V$ we let $N_{S}(u)=N_{G}(u)\cap S$. In all
aforementioned cases we forget the subscript mentioning graph $G$ whenever the
context is clear. Given a subset of vertices $S\subseteq V$ we denote by
$G[S]$ the subgraph induced by $S$, that is $G[S]=(S,E\cap(S\times S))$. In a
slight abuse of notation, we use $G\setminus S$ to denote the induced subgraph
$G[V\setminus S]$. A _connected component_ is a maximal subset of vertices
$S\subseteq V$ such that $G[S]$ is connected. A _module_ of $G$ is a set
$M\subseteq V$ such that for all $u,v\in M$ it holds that $N(u)\setminus
M=N(v)\setminus M$. Two vertices $u$ and $v$ are _true twins_ whenever
$N[u]=N[v]$, and a _critical clique_ is a maximal set of true twins. A graph
is _trivially perfect_ if and only if it does not contain any $C_{4}$ (a cycle
on $4$ vertices) nor $P_{4}$ (a path on $4$ vertices) as an induced subgraph.
In the remaining of this section we describe characterizations and structural
properties of trivially perfect graphs. The first one relies on the well-known
fact that any connected trivially perfect graph contains a universal vertex
(see e.g. [35]).

######  Definition 1 (Universal clique decomposition, [13]).

A _universal clique decomposition_ (UCD) of a connected graph $G=(V,E)$ is a
pair $\mathcal{T}=\big{(}T=(V_{T},E_{T}),\mathcal{B}=\\{B_{t}\\}_{t\in
V_{T}}\big{)}$ where $T$ is a rooted tree and $\mathcal{B}$ is a partition of
the vertex set $V$ into disjoint nonempty subsets such that:

  * •

if $\\{v,w\\}\in E$ and $v\in B_{t}$, $w\in B_{s}$ then $s$ and $t$ are on a
path from a leaf to the root, with possibly $s=t$,

  * •

for every node $t\in V_{T}$, the set $B_{t}$ of vertices is the universal
clique of the induced subgraph $G[\bigcup_{s\in V(T_{t})}B_{s}]$, where
$T_{t}$ denotes the subtree of $T$ rooted at $t$.

A simple way of understanding Definition 1 is to observe that such a
decomposition can be obtained by removing the set $U$ of universal vertices of
$G$ and then recursively repeating this process on every trivially perfect
connected component of $G\setminus U$. Drange et al. [13] showed that any
connected graph admitting an UCD is trivially perfect, thus proving
equivalence between both definitions. Using the notion of UCD, Dumas et al.
[16] proved the following characterization for trivially perfect graphs that
will be heavily used in our reduction rules. A collection of subsets
$\mathcal{F}\subseteq 2^{U}$ over some universe $U$ is a _nested family_ if
$A\subseteq B$ or $B\subseteq A$ holds for any $A,B\in\mathcal{F}$.

######  Lemma 1 ([16]).

Let $G=(V,E)$ be a graph, $S\subseteq V$ a maximal clique of $G$ and
$\\{K_{1},...,K_{r}\\}$ the set of connected components of $G\backslash S$.
The graph $G$ is trivially perfect if and only if the following conditions are
verified:

  1. (i)

$G[S\cup K_{i}]$ is trivially perfect, $1\leqslant i\leqslant r$

  2. (ii)

$\bigcup_{1\leqslant i\leqslant r}\\{N_{G}(K_{i})\\}$ is a nested family

  3. (iii)

$(K_{i}\times N_{G}(K_{i}))\subseteq E$, $1\leqslant i\leqslant r$. In other
words, $K_{i}$ is a module of $G$.

In the remaining of this paper, a _$k$ -editing of $G$ into a trivially
perfect graph_ is a set $F\subseteq(V\times V)$ such that $|F|\leqslant k$ and
the graph $H=(V,E\triangle F)$ is trivially perfect. Here $E\triangle F=(E\cup
F)\setminus(E\cap F)$ denotes the symmetric difference between sets $E$ and
$F$. For the sake of readability, we simply speak of $k$-editing of $G$. We
say that $F$ is a $k$-completion (resp. $k$-deletion) when $H=(V,E\cup F)$
(resp. $H=(V,E\setminus F)$) is trivially perfect. A vertex is _affected_ by a
$k$-editing $F$ if it is contained in some pair of $F$ and _unaffected_
otherwise.

#### Packing, anti-matching and blow-up

We now define some structures and operators that will be useful for our
kernelization algorithm. We assume in the remaining of this section that we
are given a graph $G=(V,E)$. The notion of _$r$ -packing_ will be used in
reduction rules to ensure the existence of unaffected vertices in ordered sets
of critical cliques or of trivially perfect modules.

######  Definition 2 ($r$-packing).

Let $\mathcal{S}=\\{C_{1},\ldots,C_{q}\\}$ be an ordered collection of
pairwise disjoint subsets of $V$. We say that
$\mathcal{C}\subseteq\mathcal{S}$ is a _$r$ -packing_ of $\mathcal{S}$ if
$\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ for $1\leqslant p\leqslant q$,
$\sum_{i=1}^{p}|C_{i}|\geqslant r$ and the number of vertices contained in
$\mathcal{C}$ is minimum for this property.

In a slight abuse of notation we use $\mathcal{C}$ to denote both
$\\{C_{1},\ldots,C_{p}\\}$ and the set $\cup_{i=1}^{p}C_{i}$.

######  Observation 1.

Let $\mathcal{S}=\\{C_{1},\ldots,C_{q}\\}$ be an ordered collection of
pairwise disjoint subsets of $V$ such that $|C_{j}|\leqslant c$, for
$1\leqslant j\leqslant q$ and some integer $c>0$. Let
$\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ be a $r$-packing of $\mathcal{S}$. Then
$\sum_{i=1}^{p}|C_{i}|\leqslant r+(c-1)$.

###### Proof.

Since $\sum_{i=1}^{p}|C_{i}|\geqslant r$ and the number of vertices in
$\mathcal{C}$ is minimum for this property we have that
$\sum_{i=1}^{p-1}|C_{i}|\leqslant r-1$. The result follows from the fact that
$|C_{p}|\leqslant c$. ∎

######  Definition 3 (Anti-matching).

An _anti-matching_ of $G$ is a set of pairwise disjoint pairs $\\{u,v\\}$ of
vertices of $G$ such that $\\{u,v\\}\not\in E$.

In a slight abuse of notation we denote by $V(D)$ the set of vertices
contained in pairs of an anti-matching $D$.

######  Observation 2.

Let $(G,k)$ be a Yes-instance of Trivially Perfect Editing and $M$ be a module
containing a $(k+1)$-sized anti-matching. Let $F$ be a $k$-editing of $G$ and
$H=G\triangle F$. Then $N_{G}(M)$ is a clique in $H$.

###### Proof.

Let $D=\\{\\{u_{i},v_{i}\\}\mid 1\leqslant i\leqslant k+1\\}$ be a
$(k+1)$-sized anti-matching of $M$. Assume for a contradiction that $N_{G}(M)$
is not a clique in $H$ and let $\\{u,v\\}$ be a non-edge of $H$ with $u,v\in
N_{G}(M)$. By the pigeonhole principle, since $|F|\leqslant k$ there exists
$1\leqslant j\leqslant k+1$ such that $\\{u_{j},v_{j}\\}\notin F$ and for
every $x\in V(G)\setminus M$, $\\{u_{j},x\\},\\{v_{j},x\\}\notin F$. Hence
$\\{u_{j},u,v_{j},v\\}$ induces a $C_{4}$ in $H$, a contradiction. ∎

We conclude this section by introducing a gluing operation on trivially
perfect graphs, namely _blow-up_ , that will ease the design of some reduction
rules.

######  Definition 4 (Blow-up).

Let $u$ be a vertex of $G=(V,E)$ and $H=(V_{H},E_{H})$ be any graph. The
_blow-up of $G$ by $H$ at $u$_, denoted $G(u\rightarrow H)$ is the graph
obtained by replacing $u$ by $H$ in $G$. More formally:

$G(u\rightarrow H)=\big{(}(V\setminus\\{u\\})\cup
V_{H},E(G\setminus\\{u\\})\cup E_{H}\cup(V_{H}\times N_{G}(u)\big{)}$

######  Proposition 1.

Assume that $G$ is trivially perfect and let $u$ be a vertex of $G$ such that
$N_{G}[u]$ is a clique. For any trivially perfect graph $H$, the graph
$G(u\rightarrow H)$ is trivially perfect.

###### Proof.

Let $S\subseteq V\setminus\\{u\\}$ be any maximal clique of $G$ containing
$N_{G}(u)$. We apply the forward direction of Lemma 1 on $S$ to obtain
components $\\{K_{1},\ldots,K_{r}\\}$ that are modules such that $G[S\cup
K_{i}]$ is trivially perfect for every $1\leqslant i\leqslant r$ and
$\bigcup_{1\leqslant i\leqslant r}\\{N_{G}(K_{i})\\}$ is a nested family. Note
that by construction and w.l.o.g., we may assume $K_{1}=\\{u\\}$. The result
then directly follows from the reverse direction of Lemma 1 by replacing
$K_{1}$ by $H$. ∎

##  3 Reduction rules

In the remaining of this section we assume that we are given an instance
$(G=(V,E),k)$ of Trivially Perfect Editing.

###  3.1 Standard reduction rules

We first describe some well-known reduction rules [2, 3, 14, 16] that are
essential to obtain a vertex-kernel using Theorem 1 [16]. We will assume in
the remaining of this work that the instance at hand is reduced under Rules 1
and 2, meaning that none of them applies to the instance.

######  Rule 1.

Let $C\subseteq V$ be a connected component of $G$ such that $G[C]$ is
trivially perfect. Remove $C$ from $G$.

######  Rule 2.

Let $K\subseteq V$ be a critical clique of $G$ such that $|K|>k+1$. Remove
$|K|-(k+1)$ arbitrary vertices in $K$ from $G$.

######  Lemma 2 (Folklore, [2, 14]).

Rules 1 and 2 are safe and can be applied in polynomial time.

###  3.2 An $O(k)$ bound on the size of trivially perfect modules

Using an additional reduction rule bounding the size of independent sets in
any trivially perfect module by $O(k)$, Drange and Pilipczuk [14] proved that
such modules can be reduced to $O(k^{2})$ vertices. We strengthen this result
by proving that trivially perfect modules can further be reduced to $O(k)$
vertices. We first deal with modules that contain a large anti-matching.

######  Rule 3.

Let $M\subseteq V$ be a trivially perfect module of $G$. If $G[M]$ contains a
$(k+1)$-sized anti-matching $D$, then remove the vertices contained in
$M\setminus V(D)$.

######  Lemma 3.

Rule 3 is safe.

###### Proof.

Let $G^{\prime}=(V^{\prime},E^{\prime})$ be the graph obtained after
application of Rule 3. We need to prove that $(G=(V,E),k)$ is a Yes-instance
if and only if $(G^{\prime}=(V^{\prime},E^{\prime}),k)$ is a Yes-instance. The
forward direction is straightforward since $G^{\prime}$ is an induced subgraph
of $G$ and trivially perfect graphs are hereditary. We now consider the
reverse direction. Let $M^{\prime}=V(D)$ denote the set of vertices kept by
Rule 3. Moreover, let $F^{\prime}$ be a $k$-editing of $G^{\prime}$ and
$H^{\prime}=G^{\prime}\triangle F^{\prime}$. We will construct a $k$-editing
$F^{*}$ of $G$. Note that since the pairs contained in an anti-matching are
disjoint (Definition 3), $|M^{\prime}|\geqslant 2(k+1)$. Moreover, since
$|F^{\prime}|\leqslant k$ there are at most $2k$ affected vertices. Hence let
$u$ be an unaffected vertex of $M^{\prime}$. By Observation 2 and since
$M^{\prime}$ contains a $(k+1)$-sized anti-matching we have that
$N_{G^{\prime}}(M^{\prime})$ is a clique in $H^{\prime}$. The graph
$H_{u}=H^{\prime}\setminus(M^{\prime}\setminus\\{u\\})$ is trivially perfect
by heredity and $N_{H_{u}}(u)=N_{G^{\prime}}(M^{\prime})$. It follows that
$N_{H_{u}}(u)$ is a clique and Proposition 1 implies that the graph
$H=H_{u}(u\rightarrow M)$ is trivially perfect. Let $F^{*}$ be the editing
such that $H=G\triangle F^{*}$. Since $u$ is unaffected by $F^{\prime}$ and
$u\in M$ we have $N_{H_{u}}(u)=N_{G}(M)$. Hence, since $M$ is a module in $G$
we have that $N_{H}(v)=N_{G}(v)$ for every vertex $v\in M$, implying that
$F^{*}\subseteq F^{\prime}$. This concludes the proof. ∎

In order to bound the size of any trivially perfect module by $O(k)$, we
actually prove a more general reduction rule that will be useful for the rest
of our kernelization algorithm. This rule operates on a more intricate
structure, so-called _comb_ [16], that induces a trivially perfect graph but
not necessarily a module.

Figure 1: A comb of a graph $G=(V,E)$ with shaft $C$ and teeth $R$. Each set
$C_{i}$ is a critical clique while each set $R_{i}$ induces a (possibly
disconnected) trivially perfect module, $1\leqslant i\leqslant l$. Notice that
the sets $V_{p}$ and $V_{f}$ might be adjacent to some other vertices of the
graph.

######  Definition 5 (Comb [16]).

A pair $(C,R)$ of disjoint subsets of $V$ is a comb of $G$ if:

  * •

$G[C]$ is a clique that can be partitioned into $l$ critical cliques
$\\{C_{1},...,C_{l}\\}$

  * •

$R$ can be partitioned into $l$ non-empty non-adjacent trivially perfect
modules $\\{R_{1},...,R_{l}\\}$

  * •

$N_{G}(C_{i})\cap R=\bigcup_{j=i}^{l}R_{j}$ and $N_{G}(R_{i})\cap
C=\bigcup_{j=1}^{i}C_{j}$ for $1\leqslant i\leqslant l$

  * •

there exist two (possibly empty) subsets of vertices $V_{f},V_{p}\subseteq
V(G)\backslash\\{C\cup R\\}$ such that:

    * –

$\forall x\in C,\ N_{G}(x)\backslash(C\cup R)=V_{p}\cup V_{f}$ and

    * –

$\forall y\in R,\ N_{G}(y)\backslash(C\cup R)=V_{p}$.

Given a comb $(C,R)$, $C$ is called the _shaft_ of the comb and $R$ the
_teeth_ of the comb. See Fig. 1 for an illustration of Definition 5. Recall
that we assume that the graph is reduced under Rule 2, which means that
$|C_{i}|\leqslant k+1$ for $1\leqslant i\leqslant l$. Dumas et al. [16] showed
the following proposition on the structure of combs.

######  Proposition 2 ([16]).

Given a comb $(C,R)$ of $G$, the subgraph $G[C\cup R]$ is trivially perfect.
Moreover the sets $V_{p}$ and $V_{f}$, and the ordered partitions
$(C_{1},\dots,C_{l})$ of $C$ and $(R_{1},\dots,R_{l})$ of $R$ are uniquely
determined.

In the following we assume that any comb $(C,R)$ is given with the ordered
partitions $(C_{1},\dots,C_{l})$ of $C$ and $(R_{1},\dots,R_{l})$ of $R$. We
note here that Definition 5 slightly differs from the one given in [16] where
the set $V_{f}$ was required to be non-empty for technical reasons. Dropping
this constraint will ease the presentation of our reduction rules.

We now give several observations that will help understand Definition 5, in
particular its relation to trivially perfect modules. Given a trivially
perfect graph $G=(V,E)$ and its UCD $\mathcal{T}_{G}=(T,\mathcal{B})$, one can
construct a comb $(C,R)$ of $G$ by simply taking a path $P$ from a node
$v_{1}$ of $T$ to one of its descendent $v_{l}$. The shaft $C$ are the
vertices in bags of this path, the teeth $R$ are the bags of subtrees rooted
in the children (not on $P$) of any node on the path $P$. We can observe that
in this case, $V_{p}$ corresponds to vertices in the bags on the path from the
parent of $v_{1}$ to the root of $T$ and that $V_{f}$ is empty.

In particular, the vertex set of any connected trivially perfect graph can be
partitioned into a comb $(C,R)$ by taking a path from the root of its UCD to
one of its leaves. This means that when $V_{p}=V_{f}=\emptyset$, Definition 5
corresponds to a connected trivially perfect graph. Similarly, if only the set
$V_{f}$ is empty then Definition 5 corresponds to a _connected trivially
perfect module_ since $N_{G}(R)\setminus C=N_{G}(C)\setminus R=V_{p}$.

The following directly comes from the definition of a comb and is verified
whether sets $V_{p}$ and $V_{f}$ are empty or not.

######  Observation 3.

The set of vertices $C$ (resp. $R$) is a module of $G\setminus R$ (resp.
$G\setminus C$).

We will show that combs can be safely reduced to $O(k)$ vertices. We first
focus on combs having a large shaft, which will allow us to reduce trivially
perfect modules with small anti-matching to $O(k)$ vertices (Lemma 6). Then we
turn our attention to combs with many vertices in the teeth to bound the size
of every comb to $O(k)$ vertices (Lemma 8).

#### Combs with large shafts

Dumas et al. [16] showed that the length of a comb (i.e. the number $l$ of
different critical cliques in the shaft) can be reduced linearly in $k$.
However, as critical cliques contain $O(k)$ vertices by Rule 2, it only
allowed the authors to bound the number of vertices in shafts of combs to
$O(k^{2})$. Rule 4 presented in this section keeps two sets $\mathcal{C}_{a}$
and $\mathcal{C}_{b}$ containing a linear number (in $k$) of vertices at the
beginning and at the end of the shaft, allowing to bound its size linearly in
$k$. The two sets $\mathcal{C}_{a}$ and $\mathcal{C}_{b}$ will be large enough
to ensure the existence of two vertices that will be unaffected by a given
$k$-editing of the graph. We will use such vertices to prove that there exists
a $k$-editing of the graph that does not affect any vertex in the shaft lying
between $\mathcal{C}_{a}$ and $\mathcal{C}_{b}$, implying the safeness of the
rule.

######  Rule 4.

Let $(C,R)$ be a comb of $G$ such that there exist _disjoint_
$(2k+1)$-packings $\mathcal{C}_{a}$ of $\\{C_{1},\ldots,C_{l}\\}$ and
$\mathcal{C}_{b}$ of $\\{C_{l},C_{l-1},\ldots,C_{1}\\}$. Remove
$C^{\prime}=C\setminus(\mathcal{C}_{a}\cup\mathcal{C}_{b})$ from $G$.

######  Lemma 4.

Rule 4 is safe.

###### Proof.

Let $G^{\prime}=G\setminus C^{\prime}$ be the graph obtained after application
of Rule 4. Since $G^{\prime}$ is an induced subgraph of $G$ and since
trivially perfect graphs are hereditary, any $k$-editing of $G$ is a
$k$-editing of $G^{\prime}$.

For the reverse direction, let $F^{\prime}$ be a $k$-editing of $G^{\prime}$
and $H^{\prime}=G^{\prime}\triangle F^{\prime}$. We will construct a
$k$-editing $F^{*}$ of $G$. Let $c_{a}$ and $c_{b}$ be unaffected vertices in
$\mathcal{C}_{a}$ and $\mathcal{C}_{b}$, respectively. Note that both sets
contain at least $2k+1$ vertices and that $F^{\prime}$ affects at most $2k$
vertices, hence $c_{a}$ and $c_{b}$ are well-defined. Let $C_{a}$ and $C_{b}$
be the critical cliques of $C$ containing $c_{a}$ and $c_{b}$, $1\leqslant
a<b\leqslant l$. Moreover, let $C_{\circ}=C_{a+1}\cup\ldots\cup C_{b-1}$ and
$R_{\circ}=R_{a}\cup\ldots\cup R_{b-1}$. Similarly, let
$C_{<}=C_{1}\cup\ldots\cup C_{a}$, $C_{>}=C_{b}\cup\ldots\cup C_{l}$ and
$R_{>}=R_{b}\cup\ldots\cup R_{l}$ These sets are depicted Figure 2. Finally,
let $G_{\circ}=G\setminus C_{\circ}$ and $H_{\circ}=H^{\prime}\setminus
C_{\circ}$. Notice in particular that $H_{\circ}$ is trivially perfect and
that $C^{\prime}\subseteq C_{\circ}$.

Figure 2:  Illustration of the comb and the sets used in the proof of Lemma 4.
The circles are critical cliques of the shaft and the triangles are teeth. The
red vertices correspond to $c_{a}$ and $c_{b}$, the light blue rectangles
correspond to sets $\mathcal{C}_{a}$ and $\mathcal{C}_{b}$ and the light red
rectangle corresponds to $C^{\prime}$, which is removed by Rule 4.

Let $F_{\circ}\subseteq F^{\prime}$ be the $k$-editing such that
$H_{\circ}=G_{\circ}\triangle F_{\circ}$ and $S_{\circ}$ be a maximal clique
of $H_{\circ}$ containing $\\{c_{a},c_{b}\\}$. Notice that since $c_{a}$ and
$c_{b}$ are unaffected, $S_{\circ}$ is included in
$N_{G_{\circ}}(\\{c_{a},c_{b}\\})=C\cup V_{p}\cup V_{f}\cup R_{>}$. We use
Lemma 1 on $S_{\circ}$ to obtain a set of connected components
$\\{K_{1},\ldots,K_{r}\\}$ of $H_{\circ}\setminus S_{\circ}$ such that
$\\{K_{1},\ldots,K_{r}\\}$ are modules in $H_{\circ}$ whose (possibly empty)
neighborhoods in $S_{\circ}$ form a nested family. We first modify $F_{\circ}$
to obtain a $k$-editing of $G_{\circ}$ where vertices of $R_{\circ}$ are
affected uniformly.

######  Claim 1.

There exists a $k$-editing $F^{*}$ of $G_{\circ}$ such that, in
$H^{*}=G_{\circ}\triangle F^{*}$, $R_{\circ}$ is a module and
$H^{*}[R_{\circ}]=G[R_{\circ}]$.

_Proof._ We begin with several useful observations. First, $R_{\circ}$ is a
module in $G_{\circ}$ since $R\supset R_{\circ}$ is a module in $G\setminus C$
(Observation 3) and vertices of $R_{\circ}$ are adjacent to $C_{<}$ and non
adjacent to $C_{>}$. Next, since any component $K_{i}$ is a module in
$H_{\circ}$, $1\leqslant i\leqslant r$, and since $c_{a}$ and $c_{b}$ are
unaffected by $F_{\circ}$, we have
$N_{H_{\circ}}(K_{i})\cap\\{c_{a},c_{b}\\}=N_{G_{\circ}}(K_{i})\cap\\{c_{a},c_{b}\\}$.
In other words, vertices in a same component $K_{i}$ must have the same
adjacency with $\\{c_{a},c_{b}\\}$ in $G_{\circ}$ and in $H_{\circ}$.
Similarly, no vertex $v\in R_{\circ}$ belongs to $S_{\circ}$ since
$N_{G_{\circ}}(v)\cap\\{c_{b}\\}=\emptyset$. Moreover, the only vertices of
$G_{\circ}$ that are adjacent to $c_{a}$ but not $c_{b}$ are exactly those of
$R_{\circ}$. Hence for any vertex $v_{\circ}\in R_{\circ}$ it holds that
$N_{H_{\circ}}(v_{\circ})\subseteq S_{\circ}\cup R_{\circ}$.

Assume now that $R_{\circ}$ is not a module in $H_{\circ}$ and let
$v_{\circ}\in R_{\circ}$ be a vertex contained in the least number of pairs of
$F_{\circ}$ with the other element in $S_{\circ}$. Consider the graph
$\tilde{H}=H_{\circ}\setminus(R_{\circ}\setminus\\{v_{\circ}\\})$, which is
trivially perfect by heredity. Since $N_{H_{\circ}}(v_{\circ})\subseteq
S_{\circ}\cup R_{\circ}$, it follows that $N_{\tilde{H}}(v_{\circ})\subseteq
S_{\circ}$ is a clique. Hence Proposition 1 implies that the graph
$H^{*}=\tilde{H}(v_{\circ}\rightarrow G[R_{\circ}])$ is trivially perfect. Let
$F^{*}$ be the editing such that $H^{*}=G_{\circ}\triangle F^{*}$. By the
choice of $v_{\circ}$ we have $|F^{*}|\leqslant|F_{\circ}|$. It follows that
$F^{*}$ is a desired $k$-editing, concluding the proof of Claim 1. $\diamond$

We henceforth consider $H^{*}=G_{\circ}\triangle F^{*}$ where $F^{*}$ is the
$k$-editing from Claim 1. Note that the components around $S_{\circ}$ may be
different in $H_{\circ}\setminus S_{\circ}$ and $H^{*}\setminus S_{\circ}$. In
a slight abuse of notation, we still define these components by
$\\{K_{1},\ldots,K_{r}\\}$. Recall that $\\{K_{1},\ldots,K_{r}\\}$ are modules
in $H^{*}$ whose (possibly empty) neighborhoods in $S_{\circ}$ form a nested
family.

######  Claim 2.

The graph $H=G\triangle F^{*}$ is trivially perfect.

_Proof._ The graph $H$ corresponds to $H^{*}$ where vertices of $C_{\circ}$
have been added with the same neighborhood as in $G$. Let us first observe
that $S=S_{\circ}\cup C_{\circ}$ is a maximal clique in $H$. Indeed,
$C_{\circ}$ is a clique by definition and $S_{\circ}\subseteq\big{(}C\cup
V_{p}\cup V_{f}\cup R_{>}\big{)}\subseteq N_{H}(C_{\circ})=N_{G}(C_{\circ})$
(recall that $C$ is adjacent to $V_{p}\cup V_{f}$ by Definition 5 and that
vertices of $C_{\circ}$ are adjacent to every vertex of $R_{>}$). Hence
components $\\{K_{1},\ldots,K_{r}\\}$ defined in $H^{*}\setminus S_{\circ}$
are the same in $H\setminus S$ and their neighborhoods are nested in
$S_{\circ}$. We split $\\{K_{1},\ldots,K_{r}\\}$ into three types components
w.r.t their adjacencies with $\\{c_{a},c_{b}\\}$, namely:

  1. 1.

$\alpha$-components that are non-adjacent to both $c_{a}$ and $c_{b}$

  2. 2.

$\beta$-components that are adjacent to $c_{a}$ but not $c_{b}$

  3. 3.

$\delta$-components that are adjacent to both $c_{a}$ and $c_{b}$

In what follows we let $K_{\alpha}$, $K_{\beta}$ and $K_{\delta}$ denote any
$\alpha$-, $\beta$\- and $\delta$-component, respectively. Note that
$N_{H^{*}}(K_{\alpha})\subseteq N_{H^{*}}(K_{\beta})\subseteq
N_{H^{*}}(K_{\delta})\subseteq S_{\circ}$ holds by construction. Recall that
since $c_{a}$ and $c_{b}$ are unaffected by $F^{*}$,
$N_{G}(K_{i})\cap\\{c_{a},c_{b}\\}=N_{H}(K_{i})\cap\\{c_{a},c_{b}\\}$ for any
$K_{i}$. We claim that $\\{N_{H}(K_{i})\mid 1\leqslant i\leqslant r\\}$ is a
nested family. Note that Lemma 1 will imply the result since $S$ is a maximal
clique in $H$. To sustain this claim, recall that the neighborhoods of
vertices of $C_{\circ}$ are identical in $G$ and $H$. Moreover,
$N_{H}[c_{a}]\subseteq N_{H}[C_{\circ}]\subseteq N_{H}[c_{b}]$ holds as these
vertices are unaffected by $F^{*}$. It follows that $\alpha$-components (resp.
$\delta$-components) are non-adjacent (resp. adjacent) to every vertices of
$C_{\circ}$ in $H$. This means in particular that the neighborhoods of both
$\alpha$\- and $\delta$-components are nested in $S$. Moreover we can observe
that vertices of $\beta$-components are exactly the ones of $R_{\circ}$ since
they are the only ones that are adjacent to $c_{a}$ but not $c_{b}$ in $G$.
Hence, in $H$, we still have:

$N_{H}(K_{\alpha})\subseteq N_{H}(K_{\beta})\subseteq N_{H}(K_{\delta})$

It remains to prove that the neighborhoods of $\beta$-components are nested in
$S$. Let w.l.o.g. $\\{K_{1},\ldots,K_{p}\\}$, $1\leqslant p\leqslant r$ be the
$\beta$-components. By definition of a comb, the $\beta$-components (which are
also $R_{\circ}$) can be ordered w.r.t. the inclusion of their neighborhood in
$G[C_{\circ}]$. We can assume w.l.o.g. that the ordering is
$N_{G[C_{\circ}]}(K_{1})\subseteq\ldots\subseteq N_{G[C_{\circ}]}(K_{p})$.
Moreover we can observe that for any $\beta$-component $K_{i}$ we have
$N_{G[C_{\circ}]}(K_{i})=N_{H[C_{\circ}]}(K_{i})$, $1\leqslant i\leqslant p$.
Since $R_{\circ}$ is a module in $H^{*}$ by Claim 1 and since vertices of
$\beta$-components are exactly those of $R_{\circ}$, it follows that the
neighborhoods of $\beta$-components are nested. Hence $\\{N_{H}(K_{i})\mid
1\leqslant i\leqslant r\\}$ is a nested family and $H$ is a trivially perfect
graph by Lemma 1. $\diamond$

By Claim 2 the graph $H=G\triangle F^{*}$ is trivially perfect and as
$|F^{*}|\leqslant k$, it follows that $F^{*}$ is a $k$-editing of $G$,
concluding the proof of Lemma 4. ∎

######  Observation 4.

Assume that the instance $(G,k)$ is reduced under Rules 2 and 4. For any comb
$(C,R)$ of $G$ it holds that $|C|\leqslant 6k+2$.

###### Proof.

Since $G$ is reduced under Rule 2 every critical clique $C_{i}$ of the shaft
contains at most $k+1$ vertices, $1\leqslant i\leqslant l$. By Observation 1,
any $(2k+1)$-packing of $\\{C_{1},\ldots,C_{l}\\}$ (resp.
$\\{C_{l},\ldots,C_{1}\\}$) contains at most $3k+1$ vertices. It follows that
$|C|\leqslant 6k+2$ since otherwise one could find two _disjoint_
$(2k+1)$-packings of $\\{C_{1},\ldots,C_{l}\\}$ and of
$\\{C_{l},\ldots,C_{1}\\}$ and Rule 4 would apply. ∎

We are now ready to show how to reduce the size of any trivially perfect
module. We need a combinatorial result that will be useful to obtain the
claimed bound.

######  Lemma 5.

Let $G=(V,E)$ be a connected trivially perfect graph and $\alpha$ be the size
of a maximum anti-matching of $G$. There exists a comb $(C,R)$ of $G$ such
that $V=C\cup R$ and $|R|\leqslant 4\alpha$. Moreover, such a comb can be
computed in polynomial time.

###### Proof.

We provide a constructive proof that will directly imply the last part of the
result. Recall that any trivially perfect graph contains a universal vertex
and let $U_{1}\subseteq G$ be the universal clique of $G$. Let
$R^{1}_{1},\ldots,R^{1}_{p_{1}}$ denote the connected components of
$G\setminus U_{1}$. Since $G$ does not contain any $(\alpha+1)$-sized anti-
matching, there is at most one set $R^{1}_{i}$, $1\leqslant i\leqslant p_{1}$
such that $|R^{1}_{i}|>\alpha$ (as there is no edge between $R^{1}_{i}$ and
$R^{1}_{j}$, $1\leqslant i<j\leqslant p_{1}$).

Assume without loss of generality that $|R^{1}_{1}|>\alpha$. We add all
vertices of $\cup_{i=2}^{p_{1}}R^{1}_{i}$ to some set $R_{<}$ and we will
repeat this process on $G[R^{1}_{1}]$ until every connected component is
smaller than $\alpha$. More formally, at step $j>1$, for the trivially perfect
graph $G_{j}=G[R^{j-1}_{1}]$, let $U_{j}$ be its universal clique and
$R^{j}_{1},\dots,R^{j}_{p_{j}}$ be the connected components of $G_{j}\setminus
U_{j}$. Let $R^{j}_{1}$ be the one of size greater than $\alpha$ if it exists,
if it does not, stop the process and let $l$ be the last step. In particular,
$|R^{l}_{i}|\leqslant\alpha$, $1\leqslant i\leqslant p_{l}$. Let
$R_{<}=\bigcup_{j=1}^{l-1}\bigcup_{i=2}^{p_{j}}R_{i}^{j}$ and
$R_{>}=R^{l}_{1}\cup\dots\cup R^{l}_{p_{l}}$.

Recall that $|R^{l-1}_{1}|>\alpha$ by construction. This implies that
$|R_{<}|\leqslant\alpha$ since otherwise $G[R_{<}\cup R^{l-1}_{1}]$ would
contain a $(\alpha+1)$-sized anti-matching. We claim that $|R_{>}|\leqslant
3\alpha$. To support this claim, let us consider the $(\alpha+1)$-packing
$\\{R^{l}_{1},\ldots,R^{l}_{q}\\}$ of $\\{R^{l}_{1},\ldots,R^{l}_{p_{l}}\\}$
and let $R^{\prime}=\bigcup_{i=1}^{q}R_{i}^{l}$ be its vertices. Let
$R^{\prime\prime}=R_{>}\setminus R^{\prime}$. Recall that $l$ is the last step
of the process and $|R_{i}^{l}|\leqslant\alpha$ for $1\leqslant i\leqslant
p_{l}$. Hence by Observation 1 it holds that $|R^{\prime}|\leqslant 2\alpha$.
Thus, we have that $|R^{\prime\prime}|\leqslant\alpha$ since otherwise
$G[R^{\prime}\cup R^{\prime\prime}]$ would contain a $(\alpha+1)$-sized anti-
matching, a contradiction. Hence
$|R_{>}|=|R^{\prime}|+|R^{\prime\prime}|\leqslant 3\alpha$.

To obtain a comb for $G$ we consider the set $C=\\{U_{1},\ldots,U_{l}\\}$ as
the shaft (recall that $U_{1}$ is the universal clique of $G$ and that $U_{j}$
denotes the universal clique of $G[R^{j-1}_{1}]$ at every step $1<j\leqslant
l$). Moreover, for every $1\leqslant j<l$, the tooth $R_{j}$ is defined as
$\\{R_{2}^{j},\ldots,R_{p_{j}}^{j}\\}$, the last tooth $R_{l}$ being $R_{>}$.
By construction $(C,R=\bigcup_{j=1}^{l}R_{j})$ is a comb of $G$ such that
$|R|=|R_{<}|+|R_{>}|\leqslant 4\alpha$. This concludes the proof. ∎

######  Lemma 6.

Assume that the instance $(G,k)$ is reduced under Rules 1, 2, 3 and 4 and let
$M$ be a trivially perfect module of $G$. Then $M$ contains at most $11k+2$
vertices.

###### Proof.

Observe that if $M$ contains an anti-matching of size more than $k$, then it
is reduced under Rule 3 and contains $2k+2$ vertices. Hence, suppose that $M$
does not contain a $(k+1)$-sized anti-matching. Assume first that $G[M]$ is
connected. Let $(C,R)$ be a comb obtained through Lemma 5, such that $C\cup
R=M$ and $|R|\leqslant 4k$. By Observation 4 we have that $|C|\leqslant 6k+2$.
It follows that $|M|\leqslant|C|+|R|\leqslant 10k+2$.

To conclude it remains to deal with the case where $G[M]$ is disconnected. Let
$\\{M_{1},\ldots,M_{p}\\}$ denote the connected components of $G[M]$. As $M$
does not contain a $(k+1)$-sized anti-matching, at most one of its connected
component has size greater than $k$, we may assume w.l.o.g. that it is
$M_{1}$, if existent. Let $\mathcal{C}$ be the $(k+1)$-packing of
$\\{M_{1},\ldots,M_{p}\\}$. As $|M_{1}|\leqslant 10k+2$ and $|M_{i}|\leqslant
k$ for $2\leqslant i\leqslant p$, we have that $|\mathcal{C}|\leqslant 10k+2$.
Moreover, since $M$ does not contain any $(k+1)$-sized anti-matching,
$|M\setminus\mathcal{C}|\leqslant k$ and thus $|M|\leqslant 11k+2$. This
concludes the proof. ∎

###  3.3 Combs with large teeth

We now turn our attention to the case were a given comb contains many vertices
in its teeth. The arguments are somewhat symmetric to the ones used in the
proof of Lemma 4. The main difference lies in the fact that the information
provided by unaffected vertices differ when they are contained in the teeth
rather than in the shaft.

######  Rule 5.

Let $(C,R)$ be a comb of $G$ such that there exist three disjoint sets
$\mathcal{R}_{a},\mathcal{R}_{b}$ and $\mathcal{R}_{c}$ where:

  * •

$\mathcal{R}_{a}$ is a $(2k+1)$-packing of $\\{R_{1},\ldots,R_{l}\\}$,

  * •

$\mathcal{R}_{c}=\\{R_{l},\dots,R_{q}\\}$ is a $(2k+1)$-packing of
$\\{R_{l},\ldots,R_{1}\\}$,

  * •

$\mathcal{R}_{b}$ is a $(2k+1)$-packing of $\\{R_{q-1},\ldots,R_{1}\\}$,

Remove
$R^{\prime}=R\setminus(\mathcal{R}_{a}\cup\mathcal{R}_{b}\cup\mathcal{R}_{c})$
from $G$.

######  Lemma 7.

Rule 5 is safe.

###### Proof.

Let $G^{\prime}=G\setminus R^{\prime}$ be the graph obtained after application
of Rule 5. Since $G^{\prime}$ is an induced subgraph of $G$ and since
trivially perfect graphs are hereditary, any $k$-editing of $G$ is a
$k$-editing of $G^{\prime}$.

For the reverse direction, let $F^{\prime}$ be a $k$-editing of $G^{\prime}$
and $H^{\prime}=G^{\prime}\triangle F^{\prime}$. We will construct a
$k$-editing $F^{*}$ of $G$. Let $r_{a}$, $r_{b}$ and $r_{c}$ be unaffected
vertices in $\mathcal{R}_{a}$, $\mathcal{R}_{b}$ and $\mathcal{R}_{c}$,
respectively. Note that these vertices exist as these sets contain at least
$2k+1$ vertices and $F^{\prime}$ affects at most $2k$ vertices. Let $R_{a}$,
$R_{b}$ and $R_{c}$, $1\leqslant a<b<c\leqslant l$, be the teeth of $R$
containing $r_{a}$, $r_{b}$ and $r_{b}$, respectively (these sets are well-
defined since the packings $\mathcal{R}_{a}$, $\mathcal{R}_{b}$ and
$\mathcal{R}_{c}$ are disjoint). Moreover, since $r_{a}$, $r_{b}$ and $r_{c}$
are unaffected by $F^{\prime}$ their neighborhoods are equal in $G^{\prime}$
and $H^{\prime}$ and hence $\big{(}N_{H^{\prime}}(r_{a})\setminus
R_{a}\big{)}\subseteq\big{(}N_{H^{\prime}}(r_{b})\setminus
R_{b}\big{)}\subseteq\big{(}N_{H^{\prime}}(r_{c})\setminus R_{c}\big{)}$.

######  Claim 3.

The set $N_{H^{\prime}}(r_{b})\setminus R_{b}$ is a clique in $H^{\prime}$.

_Proof._ Assume for a contradiction that $N_{H^{\prime}}(r_{b})\setminus
R_{b}$ contains a non-edge $\\{u,v\\}$. Recall that there is no edge between
$R_{b}$ and $R_{c}$. Hence, since $\big{(}N_{H^{\prime}}(r_{b})\setminus
R_{b}\big{)}\subseteq\big{(}N_{H^{\prime}}(r_{c})\setminus R_{c}\big{)}$ we
have that the set $\\{r_{b},u,v,r_{c}\\}$ induces a $C_{4}$ in $H^{\prime}$, a
contradiction. $\diamond$

Let $R_{\circ}=R_{a+1}\cup\ldots\cup R_{b-1}$ and
$C_{\circ}=C_{a+1}\cup\ldots\cup C_{b}$. Similarly, let
$C_{<}=C_{1}\cup\ldots\cup C_{a}$, $R_{<}=R_{1}\cup\ldots\cup R_{a}$ and
$R_{>}=R_{b}\cup\ldots\cup R_{l}$. Finally, let $G_{\circ}=G\setminus
R_{\circ}$ and $H_{\circ}=H^{\prime}\setminus R_{\circ}$. These sets are
depicted Figure 3. Notice in particular that $H_{\circ}$ is trivially perfect
and that $R^{\prime}\subseteq R_{\circ}$. Let $F_{\circ}\subseteq F^{\prime}$
be the $k$-editing such that $H_{\circ}=G_{\circ}\triangle F_{\circ}$. We
first modify $F_{\circ}$ to obtain a $k$-editing of $G_{\circ}$ where every
vertex of $C_{\circ}$ is affected uniformly.

Figure 3: Illustration of the comb and the sets used in the proof of Lemma 7.
The circles are critical cliques of the shaft and the triangles are teeth. The
red vertices correspond to $r_{a}$, $r_{b}$ and $r_{c}$, the light blue
rectangles correspond to sets $\mathcal{R}_{a}$, $\mathcal{R}_{b}$ and
$\mathcal{R}_{c}$ and the light red rectangle corresponds to $R^{\prime}$,
which is removed by Rule 5.

######  Claim 4.

There exists a $k$-editing $F^{*}$ of $G_{\circ}$ such that, in
$H^{*}=G_{\circ}\triangle F^{*}$, $C_{\circ}$ is a clique module.

_Proof._ Note that $C_{\circ}$ is a critical clique in $G_{\circ}$ since
$C\supset C_{\circ}$ is a module in $G\setminus R$ (Observation 3) and
vertices of $C_{\circ}$ are non-adjacent to vertices of $R_{<}$ and adjacent
to vertices of $R_{>}$. Assume now that $C_{\circ}$ is not a clique module in
$H_{\circ}$ and let $v_{\circ}\in C_{\circ}$ be a vertex contained in the
least number of pairs of $F_{\circ}$. Consider the graph
$H_{\circ}^{\prime}=H_{\circ}\setminus(C_{\circ}\setminus\\{v_{\circ}\\})$,
which is trivially perfect by heredity, and let $H^{*}$ be the graph obtained
from $H_{\circ}^{\prime}$ by adding vertices of
$C_{\circ}\setminus\\{v_{\circ}\\}$ as true twins of $v_{\circ}$. Let $F^{*}$
be the editing such that $H^{*}=G_{\circ}\triangle F^{*}$. The graph $H^{*}$
is trivially perfect as the class of trivially perfect graphs is closed under
true twin addition. It follows from construction that $C_{\circ}$ is a clique
module in $H^{*}$ and by the choice of $v_{\circ}$,
$|F^{*}|\leqslant|F_{\circ}|$. $\diamond$

We henceforth consider $H^{*}=G_{\circ}\triangle F^{*}$ where $F^{*}$ is the
editing from Claim 4. We now show that vertices of $R_{\circ}$ can be added
into $H^{*}$ while ensuring it remains trivially perfect.

######  Claim 5.

The graph $H=G\triangle F^{*}$ is trivially perfect.

_Proof._ We start by removing the vertices of $R_{b}\setminus\\{r_{b}\\}$ from
$H^{*}$, which will give us more control on the neighborhood of $r_{b}$ and
ease some arguments. Let
$\tilde{H}=H^{*}\setminus(R_{b}\setminus\\{r_{b}\\})$, this graph is trivially
perfect by heredity. Let $S$ be a maximal clique of $\tilde{H}$ containing
$r_{b}$. By Claim 3, $N_{\tilde{H}}(r_{b})$ is a clique and since $r_{b}$ is
unaffected by $F^{*}$ we have that $S=N_{\tilde{H}}[r_{b}]=C_{<}\cup
C_{\circ}\cup V_{p}\cup\\{r_{b}\\}$. We use Lemma 1 on $S$ to obtain a set of
connected components $\\{K_{1},\ldots,K_{r}\\}$ of $\tilde{H}\setminus S$ such
that $\\{K_{1},\ldots,K_{r}\\}$ are modules in $\tilde{H}$ whose (possibly
empty) neighborhoods in $S$ form a nested family. We further split components
$\\{K_{1},\ldots,K_{r}\\}$ into two types: $K_{i}$ is an $\alpha$-component if
$N_{\tilde{H}}(K_{i})\subseteq\big{(}N_{\tilde{H}}(r_{a})\cap S\big{)}$ and a
$\beta$-component otherwise, $1\leqslant i\leqslant r$. Since
$N_{\tilde{H}}(r_{a})\cap S=V_{p}\cup C_{<}$ we have that, for any
$\alpha$-component $K_{\alpha}$, $N_{\tilde{H}}(K_{\alpha})\subseteq V_{p}\cup
C_{<}$. Moreover, since $S=N_{\tilde{H}}[r_{b}]$ and since $C_{\circ}$ is a
clique module in $\tilde{H}$ by Claim 4, every $\beta$-component $K_{\beta}$
satisfies $N_{\tilde{H}}(K_{\beta})=V_{p}\cup C_{<}\cup
C_{\circ}=S\setminus\\{r_{b}\\}$.

Observe now that $(V_{p}\cup C_{<})\subseteq N_{G}(R_{\circ})\subseteq
S\setminus\\{r_{b}\\}$. In other words, the neighborhood of any tooth of
$R_{\circ}$ contains the neighborhood of any $\alpha$-component and is
contained in the neighborhood of any $\beta$-component. Moreover the
neighborhoods of the teeth of $R_{\circ}$ are nested in $G$ by definition of a
comb. It follows that the vertices of $R_{\circ}$ can be safely added to
$\tilde{H}$ with the same neighborhood as they have in $G$, ensuring that the
resulting graph $H_{b}$ is trivially perfect. It remains to add the vertices
of $R_{b}$ back into the graph. By Claims 3 and 1, the graph
$H=H_{b}(r_{b}\rightarrow G[R_{b}])$ is trivially perfect. $\diamond$

By Claim 5 the graph $H=G\triangle F^{*}$ is trivially perfect and as
$|F^{*}|\leqslant k$, it follows that $F^{*}$ is a $k$-editing of $G$,
concluding the proof of Lemma 7. ∎

######  Lemma 8.

Assume that the instance $(G,k)$ is reduced under Rules 1, 2, 3, 4 and 5. Let
$(C,R)$ be a comb of $G$. Then $|C\cup R|=O(k)$.

###### Proof.

First, note that $|C|\leqslant 6k+2$ thanks to Observation 4. We proceed in
the same fashion to bound the size of $R$. As the teeth of a comb are
trivially perfect modules, Lemma 6 implies that $|R_{i}|\leqslant 11k+2$,
$1\leqslant i\leqslant l$. Hence by Observation 1 any $(2k+1)$-packing of
$\\{R_{1},\ldots,R_{l}\\}$ requires at most $13k+2$ vertices. It follows that
$|R|\leqslant 39k+6$ since otherwise one could find three disjoint
$(2k+1)$-packings of $R$ that meet the requirements of Rule 5. Altogether we
obtain that $|C\cup R|\leqslant 45k+8$ which concludes the proof. ∎

###  3.4 Reducing the graph exhaustively

We conclude this section by showing that the graph can be reduced in
polynomial time.

######  Lemma 9.

There is a polynomial time algorithm that outputs an instance
$G^{\prime}=(V^{\prime},E^{\prime})$ such that none of Rules 1 to 5 applies.

###### Proof.

First, Rules 1 and 2 can be applied in polynomial time thanks to Lemma 2. We
now need to apply the other rules on trivially perfect modules and combs. For
the modules, it is sufficient to reduce _strong modules_ , which are modules
that do not overlap with other modules. We can enumerate strong modules in
linear time [34]. For each strong module $M$ we can check in polynomial time
if it is trivially perfect. We can moreover check if $M$ contains a
$(k+1)$-sized anti-matching by finding a maximum matching in the complement
graph $\overline{G[M]}$, for instance using Edmonds’ algorithm [17]. If $M$
has a large anti-matching, then we can apply Rule 3. Otherwise, if
$|M|\geqslant 11k+2$ then it can be reduced using Rule 4. Indeed, $G[M]$
contains in this case at most one connected component $M^{\prime}$ with more
than $k$ vertices, such that $|M\setminus M^{\prime}|\leqslant k$ (since
otherwise $M$ would contain a $(k+1)$-sized anti-matching). We compute a comb
$(C,R)$ through Lemma 5 in $G[M^{\prime}]$, with $|R|\leqslant 4k$. It follows
that $|C|>6k+2$ and Observation 4 implies that Rule 3 applies.

It remains to show that the combs not included in a trivially perfect module
can be reduced in polynomial time. In order to do this Dumas et al. [16]
showed that so-called _critical combs_ can be enumerated in polynomial time, a
critical comb being an inclusion-wise maximal comb where $V_{f}\neq\emptyset$
and $R\cup C\cup V_{f}$ does not induce a trivially perfect module. In
particular, critical combs contain every comb not included in a trivially
perfect module. Hence it is sufficient to only reduce these combs. Given a
critical comb, Rules 4 and 5 can be applied in polynomial time. This concludes
the proof. ∎

Combining Theorem 1 and Lemmas 6, 8 and 9 we obtain the main result of this
work.

######  Theorem 2.

Trivially Perfect Editing admits a kernel with $O(k^{2})$ vertices.

##  4 The deletion variant

As mentioned in the introduction, a quadratic vertex-kernel is known to exist
for Trivially Perfect Completion [1]. The results presented Section 3 can be
adapted to prove that Trivially Perfect Deletion also admits a quadratic
vertex-kernel by simply replacing any mention of “editing” by “deletion” (this
also work with completion).

More precisely, one can see that in order to prove the safeness of Rules 3, 4
and 5, the $k$-editing $F^{*}$ for the original graph that is derived from a
$k$-editing $F^{\prime}$ for the reduced instance only uses operations that
were done by $F^{\prime}$. In particular, if $F^{\prime}$ only contains non-
edges then so does $F^{*}$, meaning that it is a valid solution. Together with
the fact that Rules 1 and 2 are safe for the deletion variant, we obtain the
following.

######  Theorem 3.

Trivially Perfect Deletion admit a kernel with $O(k^{2})$ vertices.

##  5 Conclusion

In this work we improved known kernelization algorithms for the Trivially
Perfect Editing and Trivially Perfect Deletion problems, providing a quadratic
vertex-kernel for both of them. This matches the best known bound for the
completion variant [1]. Improving upon these bounds is an appealing challenge
that may require a novel approach. On the other hand, it would be interesting
to develop lower bounds for kernelization on such problems. Finally, even if
the use of unaffected vertices in the design of reduction rules is common, its
combination with the structural properties of trivially perfect graphs in
terms of their maximal cliques allowed us to design stronger reduction rules.
We hope that the approach presented in this work may lead to finding or
improving kernelization algorithms for some related problems. Let us for
instance mention the cubic vertex-kernel for Proper Interval Completion [3]
and the quartic one for Ptolemaic Completion [10] that might be appropriate
candidates.

## References

  * [1] Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, and Théo Pierron.  (Sub) linear kernels for edge modification problems toward structured graph classes.  Algorithmica, 84(11):3338–3364, 2022.
  * [2] Stéphane Bessy, Christophe Paul, and Anthony Perez.  Polynomial kernels for 3-leaf power graph modification problems.  Discrete Applied Mathematics, 158(16):1732–1744, 2010.
  * [3] Stéphane Bessy and Anthony Perez.  Polynomial kernels for proper interval completion and related problems.  Information and Computation, 231:89–108, 2013.
  * [4] Ulrik Brandes, Michael Hamann, Luise Häuser, and Dorothea Wagner.  Skeleton-based clustering by quasi-threshold editing.  In Algorithms for Big Data: DFG Priority Program 1736, pages 134–151. Springer, 2023.
  * [5] Ulrik Brandes, Michael Hamann, Ben Strasser, and Dorothea Wagner.  Fast quasi-threshold editing.  In ESA 2015: 23rd European Symposium on Algorithms, pages 251–262. Springer, 2015.
  * [6] Pablo Burzyn, Flavia Bonomo, and Guillermo Durán.  NP-completeness results for edge modification problems.  Discrete Applied Mathematics, 154(13):1824–1844, 2006.
  * [7] Leizhen Cai.  Fixed-parameter tractability of graph modification problems for hereditary properties.  Information Processing Letters, 58(4):171–176, 1996.
  * [8] Leizhen Cai and Yufei Cai.  Incompressibility of $H$-free edge modification problems.  Algorithmica, 71(3):731–757, 2015.
  * [9] Christophe Crespelle, Pål Grønås Drange, Fedor V Fomin, and Petr Golovach.  A survey of parameterized algorithms and the complexity of edge modification.  Computer Science Review, 48:100556, 2023.
  * [10] Christophe Crespelle, Benjamin Gras, and Anthony Perez.  Completion to chordal distance-hereditary graphs: a quartic vertex-kernel.  In WG 2021: Graph-Theoretic Concepts in Computer Science, pages 156–168. Springer, 2021.
  * [11] Christophe Crespelle, Rémi Pellerin, and Stéphan Thomassé.  A quasi-quadratic vertex kernel for cograph edge editing, 2022.
  * [12] Pål Grønås Drange, Markus Fanebust Dregi, Daniel Lokshtanov, and Blair D. Sullivan.  On the threshold of intractability.  Journal of Computer and System Sciences, 124:1–25, 2022.
  * [13] Pål Grønås Drange, Fedor V Fomin, Michał Pilipczuk, and Yngve Villanger.  Exploring the subexponential complexity of completion problems.  ACM Transactions on Computation Theory, 7(4):1–38, 2015.
  * [14] Pål Grønås Drange and Michał Pilipczuk.  A polynomial kernel for trivially perfect editing.  Algorithmica, 80(12):3481–3524, 2018.
  * [15] Maël Dumas, Anthony Perez, and Ioan Todinca.  Polynomial kernels for strictly chordal edge modification problems.  In IPEC 2021: 16th International Symposium on Parameterized and Exact Computation, volume 214 of LIPIcs, pages 17:1–17:16, 2021.
  * [16] Maël Dumas, Anthony Perez, and Ioan Todinca.  A cubic vertex-kernel for trivially perfect editing.  Algorithmica, 85(4):1091–1110, 2023.
  * [17] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of mathematics, 17:449–467, 1965.
  * [18] Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: theory of parameterized preprocessing.  Cambridge University Press, 2019.
  * [19] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [20] Martin Charles Golumbic.  Trivially perfect graphs.  Discrete Mathematics, 24(1):105–107, 1978.
  * [21] Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf.  Engineering exact quasi-threshold editing.  In SEA 2020: 18th International Symposium on Experimental Algorithms, volume 160 of LIPIcs, pages 10:1–10:14, 2020.
  * [22] Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez.  On the (non-)existence of polynomial kernels for Pl-free edge modification problems.  Algorithmica, 65(4):900–926, 2013.
  * [23] Jiong Guo.  Problem kernels for np-complete edge deletion problems: Split and related graphs.  In Takeshi Tokuyama, editor, ISAAC 2007: 18th International Symposium on Algorithms and Computation, volume 4835 of Lecture Notes in Computer Science, pages 915–926. Springer, 2007.
  * [24] Haim Kaplan, Ron Shamir, and Robert E Tarjan.  Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs.  SIAM Journal on Computing, 28(5):1906–1922, 1999.
  * [25] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103. Springer, 1972.
  * [26] Christian Komusiewicz and Johannes Uhlmann.  A cubic-vertex kernel for flip consensus tree.  Algorithmica, 68(1):81–108, 2014.
  * [27] Stefan Kratsch and Magnus Wahlström.  Two edge modification problems without polynomial kernels.  Discrete Optimization, 10(3):193–199, 2013.
  * [28] Yunlong Liu, Jianxin Wang, Jie You, Jianer Chen, and Yixin Cao.  Edge deletion problems: Branching facilitated by modular decomposition.  Theoretical Computer Science, 573:63–70, 2015.
  * [29] Dániel Marx and RB Sandeep.  Incompressibility of H-free edge modification problems: Towards a dichotomy.  Journal of Computer and System Sciences, 125:25–58, 2022.
  * [30] James Nastos and Yong Gao.  Familial groups in social networks.  Social Networks, 35(3):439–450, 2013.
  * [31] Assaf Natanzon, Ron Shamir, and Roded Sharan.  A polynomial approximation algorithm for the minimum fill-in problem.  SIAM Journal on Computing, 30(4):1067–1079, 2000.
  * [32] Jaroslav Nešetřil and Patrice Ossona De Mendez.  On low tree-depth decompositions.  Graphs and combinatorics, 31(6):1941–1963, 2015.
  * [33] Roded Sharan.  Graph modification problems and their applications to genomic research.  PhD thesis, Tel-Aviv University, 2002.
  * [34] Marc Tedder, Derek Corneil, Michel Habib, and Christophe Paul.  Simpler linear-time modular decomposition via recursive factorizing permutations.  In ICALP 2008: 35th International Colloquium on Automata, Languages, and Programming, pages 634–645. Springer, 2008.
  * [35] Jing-Ho Yan, Jer-Jeong Chen, and Gerard J Chang.  Quasi-threshold graphs.  Discrete applied mathematics, 69(3):247–255, 1996.


# Separating micrometer-sized particles utilizing a dusty plasma ratchet

Zhi-min Cai  College of Physics Science and Technology, Hebei University,
Baoding 071002, China  Zong-bo Ma  College of Physics Science and Technology,
Hebei University, Baoding 071002, China  You-kai Zhao  College of Physics
Science and Technology, Hebei University, Baoding 071002, China  Fu-cheng Liu
College of Physics Science and Technology, Hebei University, Baoding 071002,
China  Ya-feng He  College of Physics Science and Technology, Hebei
University, Baoding 071002, China  Hebei Research Center of the Basic
Discipline for Computational Physics, Hebei University, Baoding 071002, China
<EMAIL_ADDRESS>
###### Abstract

Directional transport-dominated particle separation presents major challenges
in many technological applications. The Feynman ratchet can convert the random
perturbation into directional transport of particles, offering innovative
separation schemes. Here, we propose the design of a dusty plasma ratchet
system to accomplish the separation of micron-sized particles. The dust
particles are charged and suspended at specific heights within the saw
channel, depending on their sizes. Bi-dispersed dust particles can flow along
the saw channel in opposite directions, resulting in a perfect purity of
particle separation. We discuss the underlying mechanism of particle
separation, wherein dust particles of different sizes are suspended at
distinctive heights and experience electric ratchet potentials with opposite
orientations, leading to their contrary flows. Our results demonstrate a
feasible and highly efficient method for separating micron-sized particles.

††preprint: AIP/123-QED

Particle separation has significant applications across various fields
including physics, chemistry, biology and more. Numerous efforts have been
devoted to developing effective separation methods based on different
mechanisms, such as the sieve filter,Stogin  electrophoresis,Cui
acousticophoresis,Garg ; Dai  and chromatography.Wei  Of particular interest
is the Feynman ratchet, which has the remarkable ability to convert random
motion into directional transport of particles.Hanggi ; Reimann ; Drexler ;
Mukhopadhyay  Ratchet-based particle separations have been achieved
experimentally, such as in microfluidic ratchets,Matthias ; Tang ; Skaug ;
Roth ; Kowalik  and numerically based on LangevinSlanina ; Reguera ; Germs  or
Monte CarloLi  simulations. Compared with extensively studied neutral agents
like the biological cells, if the particle is charged, especially those of
micron-size, ratchet-based approaches would become versatile and practical in
manipulating particle transport and separation by applying a ratchet electric
potential, that is a challenging task.

Dusty plasma is a system in which micron-sized dust particles are charged in a
weakly ionized gas.Morfill ; Shukla ; Jorge  These dust particles can undergo
transport, relying on the local plasma parameters which mainly determine the
electric and ion drag forces, or through externally applied driving.
Spontaneous long-rang transport between two dust sources has been
observed.Edward  Tunable transport of dust particles has also been achieved by
externally manipulating the potential profiles through the application of two
consecutive harmonics excitation,Shinya  phase-controllable electrical
electrodes,Jiang  or by utilizing a strong magnetic field.Land  Furthermore,
particle separation of binary particle systems has been achieved under
microgravity conditions, that was attributed to the process of uphill
diffusionKiller  or a force disparity.Stefan  In a recent dusty plasma ratchet
experiment,He  monodisperse dust particles were rectified into directional
transport with a desirable direction by regulating the discharge conditions.
We believe that the response of dust particles to the discharge conditions
definitely depends on their sizes. Here, we report the experimental separation
of bi-dispersed dust particles through the utilization of a straight ratchet
in dusty plasma. The two sizes of dust particles, suspended at distinctive
heights within the saw channel of the straight ratchet, can flow in opposite
directions, resulting in a perfect separation purity of 100%.

Figure 1: Sketch of the bi-dispersed particle separation process in a dusty
plasma ratchet experiment. Bi-dispersed dust particles are injected at the
inlet of the system. The small dust particles (red balls) and the large dust
particles (green balls) flow in opposite directions towards the two outlets
along the saw channel, and eventually into the two collection pools, resulting
in the particle separation.

The experimental setup is depicted schematically in Fig. 1. A straight resin
ratchet is positioned over the lower electrode connected to an $rf$ (13.56
MHz) power supply via a matching box. This ratchet structure comprises 26
sawteeth, with each sawtooth being 6 mm long, collectively extending over a
length of 156 mm. The ratchet has a thickness of 9 mm, and the asymmetrical
sawtooth possesses a depth of 3.5 mm. This configuration naturally forms a saw
channel between the two side sawteeth of the straight ratchet, with the
narrowest width of 6 mm. This saw channel is connected to two square
collection pools embedded with slide glass at the bottom for gathering the
separated dust particles.

Dust particles used are monodisperse polystyrene microspheres (from BaseLine
ChromTech Research Center) with the relative standard deviation of the
determination less than 4%. To assess the separation effect of the dusty
plasma ratchet, we select nine types of monodisperse dust particles with radii
of 1, 2.5, 5, 7.5, 10, 11.5, 12, 13, and 14 $\mu$m, respectively. These two
sizes are combined pairwise to demonstrate bi-dispersed particle separation.

A capacitively coupled Argon plasma is generated between the upper and lower
electrodes, which are separated by a distance of 60 mm. This plasma operates
at typical gas pressures of $p$=10-30 Pa and discharge powers of $P$=5-30 W.
To introduce binary dust particles into the system, we use a shaker initially
containing a mixture of these particles, gradually dropping them into the saw
channel through the middle inlet. These dust particles are confined to the
center of the saw channel by the electric field of sheaths from the two sides
sawteeth, and suspended at their respective balance heights, where the gravity
and the upward electric field force balance, typically around $\sim$3-8 mm
above the lower electrode, depending on their mass. The dust particles then
perform specific flow along the saw channel until they ultimately reach and
enter the collection pools.

To facilitate the observation of the separation process of the bi-dispersed
dust particles, we use a red laser beam and a green laser beam, each with a
power of 5 mW. The red laser beam is employed to illuminate and identify the
small dust particles, while the green laser beam is used for the large dust
particles. We utilize a camera (EOS 90D, 1920$\times$1080 pixels, 120 fps)
from the upper transparent electrode to monitor and distinguish the movement
of each size of dust particles during the particle separation process.

Figure 2: Particle separation experiments. (a) A small amount of a mixture of
bi-dispersed dust particles with radii of $r_{d}$=7.5, 13 $\mu$m is injected
into the inlet of the saw channel at the initial stage of the experiment.
Small (large) dust particles are illuminated with a red (green) laser beam.
(b)-(d) With the continual injection of the mixture, the bi-dispersed dust
particles begin to flow along the saw channel, but in opposite directions,
resulting in their separation. The visible particles at the bottom of each
panel are the shadows of the laser illuminated particles suspended on the
mirrored electrode plate. Gas pressure $p$=26 Pa, discharge power $P$=8 W.
Multimedia view.

We first demonstrate the separation of a mixture of bi-dispersed dust
particles with radii of $r_{d}$=7.5, 13 $\mu$m. Here, we gradually and
carefully introduce this mixture into the saw channel through the middle inlet
while simultaneously collecting the separated dust particles at the two
collection pools, as depicted in Figs. 1 and 2 (Multimedia view). During the
initial stage of the experiment, only a few dust particles are injected into
the inlet of the saw channel, as indicated in Fig. 2(a). This limited number
of particles prevents the formation of a significant collective effect, which
is necessary to overcome the confining electric ratchet potential from the
sawteeth and induce directional flow along the saw channel. As the number of
dropped dust particles increases, the collective effect among charged dust
particles becomes more pronounced. At this point, the confines of a single
sawtooth region are no longer capable of accommodating all these charged dust
particles. As a result, certain dust particles begin to move outside this
sawtooth and enter the neighboring sawteeth, as shown in Fig. 2(b). This
behavior is a consequence of the growing particle density and their
interactions, leading to a more significant particle flow and redistribution
throughout the saw channel. At this moment, the mixture of bi-dispersed dust
particles starts to flow in the opposite direction, the small dust particles
flow towards outlet 2, while the large dust particles transport towards outlet
1, suggesting a beginning of the particle separation.

Figure 3: Micrograph showing the separation effect. (a) and (b) demonstrate
the gathered large ($r_{d}$=13 $\mu$m) and small ($r_{d}$=7.5 $\mu$m) dust
particles that fall on the two slide glasses located within the collection
pools 1 and 2, respectively, indicating a separation purity of 100%.

As we continuously drop the mixture of bi-dispersed dust particles into the
inlet of the saw channel, the described process occurs repeatedly and
successively. Consequently, the small dust particles consistently flow towards
outlet 2, while the large dust particles persistently move towards outlet 1,
as denoted in Figs. 2(c) and 2(d). It is conceivable that as long as we
continuously drop the mixture of bi-dispersed dust particles into the inlet of
the saw channel, we can achieve the final separation of the large dust
particles at collection pool 1 and the small dust particles at collection pool
2, as demonstrated in Figs. 3(a) and 3(b). Our experiments clearly demonstrate
the feasibility of using the dusty plasma ratchet as a method to separate
micro particles effectively.

Figure 4: Distribution of particle number within the saw channel as a function
of time during the continuous injection of the bi-dispersed dust particles. As
the experiment progresses, the small dust particles with a radius of
$r_{d}$=7.5 $\mu$m flow towards outlet 2, (a), while the large dust particles
with a radius of $r_{d}$=13 $\mu$m move towards outlet 1, (b).

Figure 4 illustrates the distribution of particle number within the saw
channel as a function of time, providing crucial insights into the particle
dynamics and the efficiency of the separation process. At $t$=18.6 s, when a
small quantity of bi-dispersed dust particles enter the inlet, they are
uniformly distributed near the inlet region. As additional bi-dispersed dust
particles are continuously added into the inlet, the corresponding
distributions for both the small and large dust particles extend towards both
sides of the saw channel, as denoted in Figs. 4(a) and 4(b). This extension
signifies the collective effect and increased particle density as more
particles flow into the system. As the particle number continues to increase,
the distribution of the small dust particles shows a lift at the right end,
while the distribution of the large dust particles rises at the left end.
These upward shifts in the curves represent the directional transport of the
bi-dispersed dust particles in completely opposite directions.The shifting and
evolution of the distribution curves over time clearly demonstrate the
efficacy of the dusty plasma ratchet in achieving effective and directional
particle separation. It’s important to note that the peaks of the
distributions of the bi-dispersed dust particles, which appear near the inlet,
are a result of the continual injection of dust particles from this point. The
continuous addition of particles at the inlet contributes to the steady flow
and maintains the distributions throughout the process, leading to the
particle separation observed in the experimental setup.

Figure 5: Separation purity and yield. At the outlet 1 (2), only large (small)
dust particles are gathered with a purity of $EP$=100%. The color-coded bars
represent yields $EY$ which increase with the number $N_{a}{\rm(inlet)}$ of
injected particles.

To evaluate the ability of our device to separate dust particles from a
mixture, we calculate the purity $EP$, the proportion of particle type $a$
(either small or large) in outlet $i$ relative to the total number of
particles in this outlet, and the yield $EY$, the number of particle type $a$
gathered in outlet $i$ over the total number of injected particles of the same
type, defined as:

$\displaystyle EP$ $\displaystyle=$
$\displaystyle\frac{N_{a}{\rm(outlet}_{i})}{N_{total}{\rm(outlet}_{i})},$ (1)
$\displaystyle EY$ $\displaystyle=$
$\displaystyle\frac{N_{a}{\rm(outlet}_{i})}{N_{a}{\rm(inlet)}},$ (2)

here, $N_{a}$ represents the number of particle $a$, $N_{total}$ the total
particle number of the dropped mixture, $i$=1, 2 the outlet positions. The bar
graphs $EP$ in Fig. 5 present the separation purity at the two outlets. At
outlet 1, the collection is solely composed of large dust particles,
indicating a purity of 100%, as depicted in the micrograph presented in Fig.
3(a). Similarly, at outlet 2, a purity of 100% is attained as well, with only
small dust particles being gathered, as illustrated in the micrograph in Fig.
3(b). These outcomes highlight a perfect efficiency achieved in separating
these dust particles.

The associated yields for the purified dust particles at the two outlets
increase with the injected particle number, as depicted by the colored bars
$EY$ in Fig. 5. This trend is attributed to the fact that a residual quantity
of approximately $\sim$30 dust particles remains within each sawtooth,
amounting to a total of approximately $N_{res}$$\sim$400 dust particles, after
experimental operations. In Eq. (2), $N_{a}{\rm(outlet_{i})}$ $=$
$N_{a}{\rm(inlet)}$ $-$ $N_{res}$, thus, increasing the injection number
$N_{a}{\rm(inlet)}$ can significantly raise the yield. For instance, with an
input of $N_{a}{\rm(inlet)}$$=$10,000 dust particles, a yield of 96% can be
achieved. In practical scenarios, where $N_{a}{\rm(inlet)}$ attains
considerable magnitudes, a yield approaching 100% becomes feasible.

Table 1: Tested binary mixtures with particle radii $r_{d1}$ and $r_{d2}$.
Y-separable. N-inseparable in opposite directions $r_{d1}$ ($\mu$m) $r_{d2}$ ($\mu$m) | 1 | 2.5 | 5 | 7.5 | 10 | 11.5 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---
1 | - | N | Y | Y | Y | Y | Y | Y | Y
2.5 | N | - | Y | Y | Y | Y | Y | Y | Y
5 | Y | Y | - | Y | Y | Y | Y | Y | Y
7.5 | Y | Y | Y | - | Y | Y | Y | Y | Y
10 | Y | Y | Y | Y | - | N | N | Y | Y
11.5 | Y | Y | Y | Y | N | - | N | N | Y
12 | Y | Y | Y | Y | N | N | - | N | N
13 | Y | Y | Y | Y | Y | N | N | - | N
14 | Y | Y | Y | Y | Y | Y | N | N | -

We further examined the bi-dispersed particle separation using various binary
mixtures with different particle radii, as detailed in Table 1. Generally, as
long as the radius difference between the two dust particle sizes is larger
than approximately 2 $\mu$m, the bi-dispersed dust particles can be directed
to flow in opposite directions and effectively separated, ultimately gathering
in their respective collection pools. However, when the radius difference
between the two sizes of dust particles is very small, their suspended heights
become so close that the positive ion wakes generated by the upper small
particles start to influence the transport of the lower large particles. As a
result, the bi-dispersed dust particles may not necessarily flow in opposite
directions; instead, they could exhibit movement in the same direction but at
different speeds. This implies a constraint on the effectiveness of the dusty
plasma ratchet in achieving oppositely-flowing particle separation under these
specific conditions.

The proposed method has a stable separation efficiency for a wider range of
particle radii. If one type of particles in the bi-dispersed mixture is
sufficiently large, for instance, with $r_{d}$$\gtrsim$15 $\mu$m under the
present experiment conditions, such that the electric field force can no
longer support their weights, they would fall directly onto the lower
electrode at the inlet. This situation is also applicable to other large and
massive particles, such as metal and quartz. In this case, as long as the
other type of particles in the bi-dispersed particle mixture can remain stably
suspended and flow into the collection pool, the particle separation can still
be effectively achieved.

The observed directed flow of dust particles is unrelated to the used laser
illumination, as the irradiation force exerted on the dust particles by the
laser beam is completely negligible, owing to the laser power of 5 mW. To
validate this, we conducted tests by interchanging the positions of the two
lasers. It was observed that this manipulation had no impact on the
directional transport and separation of dust particles. In addition, during
the separation operation, it is necessary to gradually introduce the dust
particles to establish directed flow, in order to avoid the rapid injection of
a large number of dust particles surging towards the two ends of the saw
channel.

The particle separation demonstrated here results from the directional
transport of the bi-dispersed mixture in opposite directions. The
configuration of the straight ratchet creates a ratchet plasma sheath along
the saw channel in the capacitively coupled discharge. Charged dust particles
experience an electric ratchet potential within this non-electroneutral
ratchet plasma sheath. The asymmetrical orientation of the ratchet potential
determines the transport direction of dust particles. Due to the highly
nonlinear feature of the sheath and the height-dependent transport property of
dust particles, the small and large dust particles are suspended at different
heights within the sheath and experience their respective ratchet potentials
with opposite orientations, resulting in their opposite flow and the particle
separation. Therefore, by controlling the discharge conditions to regulate the
bi-dispersed mixture to be suspended at appropriate heights within the sheath,
we can enable them to flow in opposite directions.

In summary, we have realized the micron-sized particle separation using a
designed dusty plasma ratchet. The height-dependent transport property of dust
particles enables the bi-dispersed dust particles to flow in opposite
directions along the straight ratchet. The designed dusty plasma ratchet
demonstrated its capability and feasibility for separating micron-sized
particles with a remarkable purity of 100% and a higher yield. This research
opens up promising possibilities for practical particle separation
applications, with potential benefits in various fields such as microfluidics,
nanotechnology, and particle manipulation.

Project supported by the National Natural Science Foundation of China (Grant
Nos. 11975089 and 12275064), the Interdisciplinary Research Program of Natural
Science of Hebei University (Grant No. DXK202010), and the Hebei Natural
Science Fund (Grant No. A2021201003), and the Scientific Research and
Innovation Team project of Hebei University (Grant No. IT2023B03).

AUTHOR DECLARATIONS
Conflict of Interest
The authors have no conflicts to disclose.

Author Contributions
Zhi-min Cai: Data curation (lead); Formal analysis (lead); Investigation
(lead); Methodology (lead); Validation (equal); Visualization (equal); Writing
– original draft (equal). Zong-bo Ma: Data curation (equal); Formal analysis
(equal); Validation (equal); Writing – original draft (equal). You-kai Zhao:
Data curation (equal); Formal analysis (equal); Validation (equal). Fu-cheng
Liu: Data curation (equal); Formal analysis (equal); Supervision (equal);
Validation (equal); Writing – review & editing (equal). Ya-feng He: Data
curation (equal); Funding acquisition (lead); Supervision (equal); Validation
(equal); Writing – review & editing (equal).

DATA AVAILABILITY
The data that support the findings of this study are available from the
corresponding authors upon reasonable request.

REFERENCES

## References

  * (1) B. B. Stogin, L. Gockowski, H. Feldstein, H. Claure, J. Wang, and T. S. Wong, Sci. Adv. $\mathbf{4}$, eaat3276 (2018).
  * (2) H. H. Cui, J. Voldman, X. F. He, and K. M. Lim, Lab Chip, $\mathbf{9}$, 2306 (2009).
  * (3) H. Q. Dai, B. Z. Xia, and D. J. Yu, Appl. Phys. Lett. $\mathbf{119}$, 111601 (2021).
  * (4) N. Garg, T. M. Westerhof, V. Liu, R. Liu, E. L. Nelson, and A. P. Lee, Microsyst. Nanoeng. $\mathbf{4}$, 17085 (2018).
  * (5) G. T. Wei, F. K. Liu, and C. R. Wang, Anal. Chem. $\mathbf{71}$, 2085 (1999).
  * (6) P. Hänggi and F. Marchesoni, Rev. Mod. Phys. $\mathbf{81}$, 387 (2009).
  * (7) P. Reimann, Phys. Rep. $\mathbf{361}$, 57 (2002).
  * (8) C. Drexler, S. A. Tarasenko, P. Olbrich, J. Karch, M. Hirmer, F. Müller, M. Gmitra, J. Fabian, R. Yakimova, S. Lara-Avila, S. Kubatkin, M. Wang, R. Vajtai, P. M. Ajayan, J. Kono, and S. D. Ganichev, Nat. Nanotechnol. $\mathbf{8}$, 104 (2013).
  * (9) A. K. Mukhopadhyay, B. Liebchen, and P. Schmelcher, Phys. Rev. Lett. $\mathbf{120}$, 218002 (2018).
  * (10) S. Matthias and F. Müller, Nature $\mathbf{424}$, 53 (2003).
  * (11) H. Tang, J. Q. Niu, H. Jin, S. J. Lin, and D. X. Cui, Microsyst. Nanoeng. $\mathbf{8}$, 62 (2022).
  * (12) M. J. Skaug, C. Schwemmer, S. Fringes, C. D. Rawlings, and A. W. Knoll, Science $\mathbf{359}$, 1505 (2018).
  * (13) J. S. Roth, Y. Zhang, P. Bao, M. R. Cheetham, X. Han, and S. D. Evans, Appl. Phys. Lett. $\mathbf{106}$, 183703 (2015).
  * (14) M. Kowalik and K. J. M. Bishop, Appl. Phys. Lett. $\mathbf{108}$, 203103 (2016).
  * (15) F. Slanina, Phys. Rev. E $\mathbf{99}$, 012604 (2019).
  * (16) D. Reguera, A. Luque, P. S. Burada, G. Schmid, J. M. Rubí, and P. Hänggi, Phys. Rev. Lett. $\mathbf{108}$, 020604 (2012).
  * (17) W. C. Germs, E. M. Roeling, L. J. van IJzendoorn, R. A. J. Janssen, and M. Kemerink, Appl. Phys. Lett. $\mathbf{102}$, 073104 (2013).
  * (18) Z. G. Li and G. Drazer, Phys. Rev. Lett. $\mathbf{98}$, 050602 (2007).
  * (19) G. E. Morfill and A. V. Ivlev, Rev. Mod. Phys. $\mathbf{81}$, 1353 (2009).
  * (20) P. K. Shukla and B. Eliasson, Rev. Mod. Phys. $\mathbf{81}$, 25 (2009).
  * (21) J. Berumen and J. Goree, Phys. Rev. E $\mathbf{104}$, 035208 (2021).
  * (22) E. Thomas, W. E. Amatucci, C. Compton, B. Christy, and J. D. Jackson, Phys. Plasmas $\mathbf{10}$, 1159 (2003).
  * (23) S. Iwashita, E. Schüngel, J. Schulze, P. Hartmann, Z. Donkó, G. Uchida, K. Koga, M. Shiratani, and U. Czarnetzki, J. Phys. D: Appl. Phys. $\mathbf{46}$, 245202 (2013).
  * (24) K. Jiang, Y. F. Li, T. Shimizu, U. Konopka, H. M. Thomas, and G. E. Morfill, Phys. Plasmas $\mathbf{16}$, 123702 (2009).
  * (25) V. Land, W. J. Goedheer, and M. R. Akdim, Phys. Rev. E $\mathbf{72}$, 046403 (2005).
  * (26) C. Killer, T. Bockwoldt, S. Schütt, M. Himpel, A. Melzer, and A. Piel, Phys. Rev. Lett. $\mathbf{116}$, 115002 (2016).
  * (27) S. Schütt and A. Melzer, Phys. Rev. E $\mathbf{103}$, 053203 (2021).
  * (28) Y. F. He, B. Q. Ai, C. X. Dai, C. Song, R. Q. Wang, W. T. Sun, F. C. Liu, and Y. Feng, Phys. Rev. Lett. $\mathbf{124}$, 075001 (2020).