Expansion Lemma—Variations and Applications to Polynomial-Time Preprocessing

Abstract

In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel—an instance equivalent to the input instance, whose size is just a function of the parameter. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. The developments in machinery (showing lower bounds for the sizes of the kernels) have led researchers to question what are the asymptotically optimum sizes for the kernels of fixed-parameter tractable problems. In this article, we surveyed a tool called expansion lemma that helps in reducing the size of the kernel. Its early origin was in the form of crown decomposition, i.e., to obtain the linear kernel for the Vertex Cover problem; the specific lemma was identified as the tool behind the optimal $O\left(k^2\right)$ kernel for the undirected feedback vertex set problem. Since then, several variations and extensions of the tool have been discovered. We surveyed them along with their applications in this article.

1. Introduction

Preprocessing is an age-old technique used for implementing algorithms, especially for difficult problems. In the field of parameterized complexity, preprocessing has gained formal recognition. A parameterized problem involves a parameter in addition to the input instance. The objective of parameterized complexity is to determine whether it is possible to design an algorithm that limits combinatorial explosion to the parameter while keeping the rest of the running time polynomial in the input size. Such an algorithm is known as a fixed-parameter algorithm, and a problem that can be solved by such an algorithm is called fixed-parameter tractable.

It is well-known (see, for example, [1]) that a decidable parameterized problem is fixed-parameter tractable if and only if the input instance can be reduced in the polynomial time to an equivalent instance, whose size is a function of the parameter. Such an equivalent instance is said to be a kernel. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. Machinery to show the non-existence of polynomial-sized kernels [2,3] and lower bounds for kernel sizes [4] under complex theoretic assumptions make the theory more interesting.

In this article, we surveyed a tool called expansion lemma that helps reduce the size of the kernel. Its early origin was in the form of crown decomposition, used for obtaining the linear kernel for the Vertex Cover problem [5]; the specific lemma was identified as the tool behind the optimal $O\left(k^2\right)$ kernel for the Undirected Feedback Vertex Set problem [6]. Since then, several variations and extensions of the tool have been discovered. In this paper, we surveyed them along with their applications. We provided sketches of as many results as possible wherever the main (and likely only) tool for the application was the expansion lemma variation. For several problems, there were several other ideas involved in obtaining the improved kernel beyond the tool. Moreover, wherever the main tool was the expansion lemma, we explained the algorithm in a self-contained way. For others, we indicated how the tool was applied; we often did not go into the other complicated technical details as they distract from the main purpose of the survey.

Organization of the paper. In Section 2, we introduce basic terminologies and notations. We begin with the technical part of the paper in the following three sections. In Section 3, we introduce the crown decomposition technique, basic lemmas, and their application to obtain some improved kernels. In Section 4, we introduce the expansion lemma and its use for several problems in kernelization. Finally, in Section 5, we discuss the recent developments, including generalizations of the (basic) expansion lemma, along with their applications. We conclude with some possible future research directions in Section 6.

2. Preliminaries

2.1. Parameterized Complexity and Kernelization

A parameterized problem L is a subset of ${\sum }^{*}\times \mathbb{N}$ where $\sum$ is a finite alphabet. Assuming that $k\in \mathbb{N}$ is given in unary, an instance to a parameterized problem is $(x,k)$ where $x\in {\sum }^{*}$ and $k\in \mathbb{N}$.

Definition 1

(fixed-parameter tractability). A parameterized problem $L\subseteq {\sum }^{*}\times \mathbb{N}$ is said to be fixed-parameter tractable (or FPT) if there exists an algorithm for solving this problem L that input $(x,k)$ runs in ${f\left(k\right)\left|x\right|}^{\mathcal{O}\left(1\right)}$-time, where $f\mathbb{N}\to \mathbb{N}$ is a computable function.

Definition 2

(kernelization). Let $L\subseteq {\sum }^{*}\times \mathbb{N}$ be a parameterized problem. A kernelization for L is a polynomial time (${\left(\right|x|+k)}^{\mathcal{O}\left(1\right)}$-time) procedure that replaces an input instance $(x,k)$ by an input instance $(x^{\prime },k^{\prime })$, such that

• $(x,k)\in L$ if and only if $(x^{\prime },k^{\prime })\in L$.
• $|x^{\prime }|+k^{\prime }\le g\left(k\right)$ for some computable function $g:\mathbb{N}\to \mathbb{N}$.

It is well-known that a decidable parameterized problem is FPT if and only if it admits kernelization [1]. Kernelization can be viewed as a theoretical foundation of preprocessing heuristics. We are interested in investigating when a parameterized problem admits kernelization of a small size, particularly a kernel of a polynomial size with as small an upper bound as possible. For other definitions, notations, and details on parameterized complexity and kernelization, please refer to [1,7,8,9,10,11].

2.2. Sets, Numbers, and Graph Theory

We use $\mathbb{N}$ to denote the set of natural numbers. For $r\in \mathbb{N}$, we denote the set $\{1,\dots ,r\}$ by $\left[r\right]$. A Boolean formula is an expression of binary variables with a logical operator conjunction (∧), disjunction (∨), and negation $(\neg$). A Boolean formula is in conjunctive normal form (or CNF) if it is a conjunction of clauses. A literal is a Boolean variable in its own form or in its complemented form. Each clause is a disjunction of literal. We usually use $G=(V,E)$ to denote an undirected graph, and $D=(V,A)$ to denote a directed graph. Let $V\left(G\right)$ denote the set of vertices of G, and $E\left(G\right)$ the set of edges of G. When G is clear from context, let $n=\left|V\right(G\left)\right|$ and $m=\left|E\right(G\left)\right|$. Informally, we use n to denote the number of vertices and m to denote the number of edges in the input graph. Given a graph $G=(V,E)$ and $X\subseteq V\left(G\right)$, we use $G\left[X\right]$ to denote an induced subgraph of G; its vertex set is X, and its edge set consists of all edges of $E\left(G\right)$ that have both endpoints in X. Let $G-X$ denote the subgraph of G induced on the vertex set $V\left(G\right)\backslash X$. A clique in an undirected graph is a set of vertices where every pair of vertices are adjacent to each other. An independent set is a pairwise non-adjacent set of vertices. A tournament is a directed graph T, such that for every pair of vertices $u,v\in V\left(T\right)$, one of $uv$ or $vu$ is a directed edge of T. In an undirected graph $G=(V,E)$, a path is a set P of distinct vertices (except possibly for the start vertex and the end vertex), such that the vertices of P can be arranged in an order $v_1,\dots ,v_d$, such that for every $1\le i\le d-1$, $v_i{v}_{i+1}\in E\left(G\right)$. Informally, for all $1\le i\le d-1$, $v_i\ne v_{i-1}$ for a path. Similarly, in a directed graph $D=(V,A)$, a directed path can be defined in a similar way when for every $i\le d-1$, $(v_i,v_{i+1})\in A$. A (directed) cycle is a (directed) path that starts and ends at the same vertex. A connected component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. For subsets $X,A,B\subseteq V\left(G\right)$, we say X separates A and B when no component of $G-X$ contains vertices from both $A\backslash X$ and $B\backslash X$. Given a vertex subset $X\subseteq V\left(G\right)$, we use $N_G\left(X\right)$ to denote the open neighborhood of X and $N_G\left[X\right]$ to denote the closed neighborhood of X. When graph G is clear from the context, we omit the subscript.

A vertex v of G is a cut vertex if $G-\left\{v\right\}$ has more connected components than G. Graph G is bi-connected if $\left|V\right(G)\ge 3$, and it has no cut vertex. Graph G is a block graph if each of its maximal bi-connected components is a clique. A tree is a connected undirected graph with no cycle (or equivalently, a connected undirected acyclic graph). A forest is a graph, every connected component of which is a tree. A directed acyclic graph is a directed graph with no directed cycles. A topological ordering for a directed acyclic graph is a linear ordering of vertices, such that for every directed edge $uv$, vertex u comes before v in the ordering. An undirected graph $G=(V,E)$ is said to be bipartite if $V\left(G\right)=A\uplus B$, such that for every $uv\in E\left(G\right)$, $u\in A$ if and only if $v\in B$. We call A and B the bipartitions of G. Another alternate characterization is that a bipartite graph has no odd cycle. We use $G=(A\uplus B,E)$ to denote a bipartite graph such that A and B are its bipartitions and E is the set of its edges. A set $M\subseteq E\left(G\right)$ is said to be a matching of a graph if for every two edges $uv,xy\in M$, $\{u,v\}\cap \{x,y\}=\varnothing$. A vertex $u\in V\left(G\right)$ is said to be matched by a matching M, if there is an edge of M incident on u. A matching M of G is said to saturateA if $A\subseteq V\left(M\right)$. A matching is said to be perfect matching if all vertices are matched by M. A cycle C in a graph is said to be an induced cycle if $G\left[C\right]$ has no edge other than the edges of the cycle. A graph is said to be a chordal graph if it has no induced cycle of a length of at least four. An out-tree is a directed graph where each vertex has an in-degree of (at most) 1, and the underlying (undirected) graph is a tree. An out-forest is a disjoint union of out-trees. A graph is said to be k-colorable if there is a function $\lambda :V\left(G\right)\to \left[k\right]$ for some $k\in \mathbb{N}$ such that for every $uv\in E\left(G\right)$, $\lambda \left(u\right)\ne \lambda \left(v\right)$. Such a function $\lambda$ is called a proper coloring of G. It is well-known that a bipartite graph is 2-colorable. Graph G is said to be factor-critical if for every $u\in V\left(G\right)$, the graph $G-u$ has a perfect matching. For other terminologies of the graph theory, we use standard graph-theoretic notations by Diestel [12].

We use the following well-known proposition several times in the paper.

Proposition 1

(Hall’s Theorem [13]). Let $G=(V=A\uplus B,E)$ be a bipartite graph. Then, G has a matching saturating A if and only if for every $X\subseteq A$, $\left|N\right(X\left)\right|\ge \left|X\right|$.

Given a bipartite graph $G=(A\uplus B,E)$, a set $X\subseteq A$ is said to be a hall set if $\left|N\right(X\left)\right|<\left|X\right|$. A hall set is said to be minimal if none of its proper subsets is a hall set. Given a bipartite graph $G=(A\uplus B,E)$, a minimal hall set can be computed in polynomial time using Proposition 1.

Before we state the following proposition, we need a few notations. For a graph $G=(V,E)$, suppose that $S\subseteq V\left(G\right)$ and a set $\mathcal{C}$ of vertex-disjoint subgraphs of $G-S$, let ${\mathcal{N}}_G(S,\mathcal{C})=\{H\in \mathcal{C}\mid E(S,V\left(H\right))\ne \varnothing \}$.

Proposition 2

(Gallai–Edmonds structure theorem [14,15]). For every graph $G=(V,E)$, there are disjoint subsets $X,Y,Z\subseteq V\left(G\right)$, such that

(i) 

$X\cup Y\cup Z=V\left(G\right)$;

(ii) 

$Y=N_G\left(X\right)$;

(iii) 

Every connected component of $G\left[X\right]$ is factor-critical;

(iv) 

$G\left[Z\right]$ has perfect matching; and

(v) 

For every nonempty subset $Y^{\prime }\subseteq Y$, it holds that $|{\mathcal{N}}_G(Y^{\prime },\mathcal{C})|\ge |Y^{\prime }|$.

Furthermore, such $X,Y,Z$ can be computed in polynomial time.

2.3. Graph Parameters

We introduce different graph parameters that we will use in this paper. A subset $S\subseteq V\left(G\right)$ is a vertex cover of G if for every edge $uv\in E\left(G\right)$, $\{u,v\}\cap S\ne \varnothing$. It follows that for an undirected graph G, if S is a vertex cover, then $V\left(G\right)\backslash S$ is an independent set (and vice versa). A subset $S\subseteq V\left(G\right)$ is called a cluster vertex deletion set of G if every connected component of $G-S$ is a clique. A subset $S\subseteq V\left(G\right)$ is a feedback vertex set of G if $G-S$ has no cycle.

The following graph parameter requires a more non-trivial definition.

Definition 3

(Pathwidth [16,17,18]). A path decomposition of graph G is a pair $(T,\chi )$ in which $T=(V_T,E_T)$ is a path and $\chi =\{{\chi }_i\mid i\in V_T\}$ is a family of subsets of $V\left(G\right)$ called bags, such that

(i) 

${\cup }_{i\in V_T}{\chi }_i=V\left(G\right)$.

(ii) 

for each edge $uv\in E\left(G\right)$, there is $i\in V_T$ such that $u,v\in {\chi }_i$.

(iii) 

for each vertex $u\in V\left(G\right)$, the set of nodes $\{i\in V_T\mid u\in {\chi }_i\}$ induces a connected subgraph of T.

The value ${max}_{i\in V_T}\left\{\right|{\chi }_i|-1\}$ is called the width of the path decomposition $(T,\chi )$. The pathwidth of a graph is the minimum width taken over all possible tree decompositions of G. It is not very hard to understand that the pathwidth of a path (or a linear forest) is 1. Similarly, the pathwidth of a cycle is 2, and the pathwidth of a caterpillar is also 1. Moreover, the pathwidth of a clique with n vertices is $n-1$. On an informal note, the pathwidth of a graph is a measure of how close a graph is to a path.

We begin the technical part of the survey with a structure and a lemma that could be considered a precursor to the expansion lemma.

3. Crown Decomposition and Applications

In this section, we define a related technique called “crown decomposition” and its application to some problems. In Section 3.1, Section 3.2, Section 3.3, Section 3.4 and Section 3.5, we discuss how crown decomposition techniques are used to obtain kernels for Vertex Cover, $(n-k)$-coloring, maximum satisfiability, $(n-k)$-list coloring, and longest cycle problems, respectively. After that, in Section 3.6, we discuss a generalization of the crown decomposition technique recently introduced by Chen et al. [19].

In the context of the vertex cover problem, a well-known reduction rule to discard the pendant (degree one) vertices is to pick their neighbors (and delete them and their neighbors) in the solution [1].

A crown introduced by Fellows [20] generalizes the structure’s underlying pendant vertices.

Definition 4

(Crown decomposition). Given a graph $G=(V,E)$, a crown decomposition of G is a partition of $V\left(G\right)=C\uplus H\uplus R$ such that

• $C\ne \varnothing$;
• C is an independent set;
• There is no edge between a vertex of C and a vertex of R, i.e., H separates C from R; and
• There exists a matching of size $\left|H\right|$ among the edges $E\cap (H\times C)$.

Set C can be seen as a crown placed on the head H of the remaining part (body) R. If G has a pendant vertex x with its (unique) neighbor y, then $C=\left\{x\right\}$, $H=\left\{y\right\}$ and $R=V\backslash \{x,y\}$ constitute the crown decomposition.

Lemma 1

(Crown Lemma-1, [5,20]). Let G be a graph without isolated vertices with at least $3k+1$ vertices. Then there is a polynomial-time algorithm that either

• Finds a matching of size $k+1$ in G; or
• Finds a crown decomposition of G.

Fellows [20] applied Lemma 1 for kernelization in the following way. First, they observe that if there is a matching of size $k+1$, then the instance is a trivial yes or no instance for some problems. Moreover, in the other case, the head of the crown can be argued to be in some optimum solution (as it hits a large number of obstructions) and, hence, can be deleted, resulting in a reduction rule.

The following variation of Lemma 1 can be useful sometimes. This lemma also serves as a precursor to the more general expansion lemma described in the next section.

Lemma 2

(Crown Lemma-2, [5,11,21]). Let $G=(V=A\uplus B,E)$ be a bipartite graph with no isolated vertices in B, and $\left|B\right|\ge \left|A\right|$. Then there is a polynomial time algorithm that either

• Finds a matching saturating A; or
• Finds a crown decomposition $(C,H,R)$ of G, with $C\subseteq A$ and $H\subseteq B$.

If there is no matching saturating A, then by Hall’s theorem (Proposition 1), there exists a minimal hall set $C\subseteq A$, such that $\left|N\right(C\left)\right|<\left|C\right|$. A minimal hall set gives rise to a crown decomposition; see [11] for proof.

We exemplify these lemmas using some examples.

3.1. Vertex Cover

We now describe a summary of a kernel of $3k$ vertices for Vertex Cover (defined in Box 1) provided by Chor et al. [5] where the earliest application of Lemma 1 can be seen. The isolated vertices of the input of graph G can be safely removed. Then, they invoke the algorithm in Lemma 1, which either gives a matching of size $k+1$ in G or a crown decomposition of G if G has more than $3k$ vertices. In the former case, it can be concluded that the input instance is a non-instance as any vertex cover of G needs at least $k+1$ vertices to cover the edges of the matching.

Box 1. Vertex Cover Problem.

Vertex Cover (VC)

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices for every $uv\in E\left(G\right)$, $u\in S$, or $v\in S$?

Hence, they assume that the algorithm returns a crown decomposition of G with crown C and head H. Let M be the matching of H into C that saturates H. Any vertex cover that covers the edges in $G[H\cup C]$ has to contain at least $\left|M\right|=\left|H\right|$ many vertices. Since M saturates H and C is an independent set, the set H covers all of the edges in $G[H\cup C]$. Hence, we can safely reduce the problem instance to $(G\backslash (H\cup C),k-|H\left|\right)$. Hence, we conclude that we can reduce the vertex cover instance as long as $\left|V\right(G\left)\right|>3k$. Hence, vertex cover has a kernel of $3k$ vertices. This bound has been improved to a kernel with $2k-logk$ vertices by Lampis et al. [22] using linear programming techniques. See Li and Zhu [23] for another $2k$-vertex kernel for Vertex Cover.

3.2. $(n-k)$-Coloring

Given an undirected graph, determining whether its vertices can be properly colored with k colors is NP-hard even for $k=3$. So a kernel or an FPT algorithm is not possible unless P = NP. However, a related problem is whether graph G on n vertices can be colored properly with $n-k$ colors, which is the same as whether k colors can be saved. The formal definition is as follows.

This problem defined in Box 2 admits an FPT algorithm and a $3k$ vertex kernel using Lemma 1 by Chor et al. [5] (also see [11] for more details). The idea is to apply Lemma 2 to the complement graph. If it contains a matching of size k, then those k pairs of non-edges in G can help us save k colors. If not, crown C is a clique in G needs $\left|C\right|$ colors, and all vertices in C are adjacent to every vertex of $V\backslash (H\cup C)$. Furthermore, the matching saturating H helps to color vertices in H using colors used in C. Thus, we can remove $H\cup C$ and recurse on the remaining vertices. This process stops if we discover that we have already used more than $(n-k)$ colors, so the input is a non-instance or that there are only $3k$ vertices. Recently, Li et al. [24] have improved this result by giving a $(2+\epsilon )k$ vertex kernel for this problem. They provided a new structure called ‘fractal critical crown’ of a graph, we use Proposition 2 and the notion of a factor-critical crown (see Section 3.6 for definition) to obtain their results.

Box 2. $(n-k)$-Coloring Problem.

$(n-k)$-Coloring

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a coloring $\Xi :V\to \{1,2,\dots |V|-k\}$ such that $\Xi \left(x\right)\ne \Xi \left(y\right)$ whenever $xy\in E$?

3.3. Maximum Satisfiability

We formally define the Maximum Satisfiability problem below.

It is folklore that such a CNF formula has a truth assignment satisfying at least $m/2$ clauses, which implies that we can assume that $m\le 2k$, as otherwise, the instance is a YES instance. It is also easy to see (by a greedy algorithm that appropriately sets an unassigned variable in each clause in the sequence) that the formula $\varphi$ is satisfiable, i.e., a yes-instance for Maximum Satisfiability (defined in Box 3) for if $n\ge m$.

Box 3. Maximum Satisfiability Problem.

Maximum Satisfiability

Input: A Conjunctive Normal Form (CNF) formula ϕ with n variables and m clauses, and a nonnegative integer k.

Parameter: k.

Question: Does ϕ have a truth assignment satisfying at least k clauses?

Thus, it can be assumed that $n<m<2k$. Lokshtanov [25] showed (as below) using Lemma 2, where n can be made to be less than k. The idea is to construct a bipartite graph with bipartition A and B where A corresponds to the variables in the formula, and B corresponds to the clauses in the formula. There is an edge between $x\in A$ and a $c\in B$ if x appears in clause c.

If $n\ge k$, then from Lemma 2, if we have a matching saturating A, then clauses in the matching can be satisfied by setting the variables in the matching appropriately. Thus, we will be able to satisfy at least k clauses. Otherwise, it can be argued that the crown $(C,H,R)$ can be used to satisfy the clauses represented by H by appropriately setting the variables represented by C, and removing those clauses and variables. See [11] for more details.

3.4. $(n-k)$-List Coloring

Banik et al. [26] use Lemma 2 to obtain an FPT algorithm for $(n-k)$-List Coloring; a generalization of the problem is presented at Box 2 in Section 3.2, where there is a reduction rule that binds the number of colors over all the lists to n. The problem is formally defined below.

Here, they create an auxiliary bipartite graph with vertices $V\left(G\right)$ on one side, $\mathcal{C}$, and the colors in every vertex list on the other side, adding edges between a vertex and a color if its list contains it. After that, they invoke Lemma 2. If there is a matching saturating $\mathcal{C}$, the number of colors is bounded by $\left|V\right(G\left)\right|=n$. Otherwise, we have a crown decomposition $(C,H,R)$ with $C\subseteq \mathcal{C}$ and $H\subseteq V\left(G\right)$. Since there is a matching M from H to C saturating H and $N\left(C\right)=H$, we can safely color the vertices of H using the colors C according to the matching M and reduce the instance. Thus, the number of colors is reduced to n. Further ideas are used to obtain an FPT algorithm for this problem defined in Box 4.

Box 4. $(n-k)$-List Coloring Problem.

$(n-k)$-List Coloring

Input: A graph $G=(V,E)$, an integer k and for every $u\in V\left(G\right)$, a set $L\left(u\right)$ of exactly $(n-k)$ colors.

Parameter: k.

Question: Is there a proper coloring of G such that for all $u\in V\left(G\right)$, the color assigned to u is in $L\left(u\right)$?

3.5. Longest Cycle Parameterized by Vertex Cover Size

Bodlaender et al. [27] showed that the longest cycle (vc) as defined in Box 5 admits a kernel with $\mathcal{O}\left(k^2\right)$ vertices. Here, they construct an auxiliary bipartite graph with pairs of vertices on one side and $I=V\left(G\right)\backslash S$ on the other side with edges added if both vertices in a pair are adjacent to a vertex in I. We now apply Lemma 2. If there is a matching saturating I, the overall number of vertices is $\mathcal{O}\left(k^2\right)$. Otherwise, we have a crown decomposition $(C,H,R)$ with $C\subseteq I$ and $H\subseteq S$. Let M match from H to C, saturating H. We claim that for any vertex $v\in C$ not saturated by M, we can reduce the instance to $(G-v,k,\ell ,S)$. Suppose a solution cycle $C^{\prime }$ in G contains v. Since I is an independent set, the two neighbors of v in C are $s_1,s_2\in S$. There is another vertex $v^{\prime }\in I$ adjacent to both $s_1$ and $s_2$ as there is an edge in the matching M corresponding to $v^{\prime }$ and the pair $(s_1,s_2)\in H$. This gives us a cycle $C^{″}$ by replacing v with $v^{\prime }$ in $G-v$.

Box 5. Longest Cycle Parameterized by Vertex Cover.

Longest Cycle (vc)

Input: graph G, integers k and ℓ and a vertex cover S of G such that $\left|S\right|=k$.

Parameter: k.

Question: Does G contain a cycle on ℓ vertices?

3.6. Generic Crown Decomposition and Its Application to Packing and Covering Problems

Chen et al. [19] introduced a general notion of crowns and used it to obtain an $\mathcal{O}\left(k\right)$ vertex kernel for $T_r$-Packing problem (for each fixed integer r) where $T_r$ is a tree with r edges.

It is folklore that many covering problems in graphs can be formulated as instances of d-Hitting Set defined as follows.

Similarly, many packing problems in graphs can be formulated as instances of d-set packing, defined as follows.

It is folklore that the d-hitting set (defined in Box 6) and d-set packing (defined in Box 7) problems can be formulated as a dominating set problem and their duals in bipartite graphs that are defined as follows.

Box 6. d-Hitting Set Problem.

d-Hitting Set

Input: A family $\mathcal{F}$ of sets over a universe U, where each set in $\mathcal{F}$ has a size of, at most, d, and an integer k.

Parameter: k.

Question: Does there exist a subset $X\subseteq U,\left|X\right|\le k$, such that X contains at least one element from each set in $\mathcal{F}$?

Box 7. d-Set Packing Problem.

d-Set Packing

Input: A family $\mathcal{F}$ of sets over a universe U, where each set in $\mathcal{F}$ has a size of, at most, d, and an integer k.

Parameter: k.

Question: Does there exist a subset ${\mathcal{F}}^{\prime }\subseteq \mathcal{F},\left|{\mathcal{F}}^{\prime }\right|=k$ such that every element in U is contained in at most one set in ${\mathcal{F}}^{\prime }$?

We formally state the definition of a generic crown decomposition below.

Definition 5

([19]). Let $G=(V=A\uplus B,E)$ be a bipartite graph such that for all $x\in B$, $de{g}_G\left(x\right)=d$. Then, a generic crown decomposition $(C,H,X)$ of G is given by a head $H\subseteq A$ and a crown $C\subseteq (A\uplus B)\backslash (H\cup C)$ satisfying the following properties

• H is a separator in G, one collection of connected components being C.
• $N\left(H\right)\supseteq C\uplus B$.
• There is an injective mapping $M:H\to C\cap B$, such that

  -

  For all $x\in H$, $xM\left(x\right)\in E\left(G\right)$, and

  -

  Each $v\in A$ is a neighbor of, at most, one $x\in M\left(H\right)$.

• $X=(A\uplus B)\backslash (H\cup C)$ are the remaining vertices.

The authors proved that $(G,k)$ is a YES instance for d-red/blue dominating set (or d-red/blue distance-3 packing, resp.) if and only if $(G-(H\cup C),k)$ is YES instance where $(C,H,X)$ is a generic crown decomposition of G.

The authors devised a framework for obtaining crown rules for covering and packing problems in graphs. They defined a notion of crown decomposition specific to the problem. They then reduced the problem to d-red/blue dominating set (defined in Box 8) or d-red/blue distance-3 packing (defined in Box 9) where the problem-specific crown decomposition corresponded to a generic crown decomposition. From the safety of the reduction corresponding to the generic crown decomposition, the safety of the problem-specific crown decomposition follows.

Box 8. Red-Blue Dominating Set Problem.

d-Red/Blue Dominating Set

Input: A bipartite graph $G=(R\uplus B,E)$, where $\forall x\in B:deg\left(x\right)=d$, and an integer k.

Parameter: k.

Question: Does there exist a subset $X\subseteq R,\left|X\right|\le k$ such that X such that $N\left(X\right)=B$?

Box 9. Distance-3 Red-Blue Set Packing Problem.

d-Red/Blue Distance-3 Packing

Input: A bipartite graph $G=(R\uplus B,E)$, where $\forall x\in B:deg\left(x\right)=d$, and an integer k.

Parameter: k.

Question: Does there exist a subset $X\subseteq B,\left|X\right|\ge k$ such that each $x\in R$ is a neighbor of, at most, one $x\in X$?

The authors demonstrate this framework in the context of the following covering and packing problems.

The dual version of the above problem is defined as follows.

They [19] define the r-tree crown decomposition as follows.

Definition 6

([19]). An r-tree crown decomposition of a graph $G=(V,E)$ is a partitioning of $V\left(G\right)=C\uplus H\uplus X$ satisfying the following properties.

• H (the head) separates C from X in G.
• $G\left[C\right]$ (C is the crown) induces no subgraph that is a tree with r edges.
• There are r injective mappings ${\pi }_1,\dots ,{\pi }_r$ from H to C called witness functions such that for all $i\ne j$, ${\pi }_i\left(H\right)\cap {\pi }_j\left(H\right)=\varnothing$ and for each $v\in H$, the vertex set $\left\{p\right\}\cup \{{\pi }_i\left(v\right)\mid 1\le i\le r\}$ forms a tree with r edges in G.

Given an instance $(G,k)$ of r-Edge-Tree-Packing (see Box 10), the authors construct a bipartite graph $G^{\prime }=(R\uplus B,E^{\prime })$ as follows. Let $R=V$ and B be the set of all trees with r edges present in G. Add an edge $uv\in E^{\prime },u\in R,v\in B$ if and only if the vertex u is part of the tree corresponding to v.

Box 10. r-Edge-Tree Packing Problem.

r-Edge-Tree-Packing

Input: An undirected graph G and an integer k.

Parameter: k

Question: Is there a set of at least k pairwise disjointed collections of trees with r edges in G?

Let us focus on an r-tree crown decomposition $(C,H,X)$ in G. The witness functions ${\pi }_1,\dots ,{\pi }_r$ from H to C correspond to a mapping M from H to some of the trees in B; in particular $v\in H$ is mapped to the tree $\{v,{\pi }_1\left(v\right),\dots ,{\pi }_r\left(v\right)\}$. From the definition of ${\pi }_i,i\in \left[r\right]$, one can conclude that M is a matching and $M\left(H\right)$ is a packing. Thus, $(C^{\prime },H,X^{\prime })$ is a generic crown decomposition in $G^{\prime }$ where $C^{\prime }=C\uplus M\left(H\right)$ and $X^{\prime }=V\left(G^{\prime }\right)\backslash (H\cup C^{\prime })$. Since $(G^{\prime },k)$ is a YES instance of r-red/blue distance-3 packing (see Box 9) if and only if $(G^{\prime }-(H\cup C^{\prime }),k-|H\left|\right)$ is a YES instance of r-red/blue distance-3 packing, one can conclude that $(G,k)$ is a YES instance of r-edge-tree-packing if and only if $(G-(H\cup C),k-|H\left|\right)$ is a YES instance of r-edge-tree-packing.

Using the above reduction, the authors provided a kernel with at most $(r^2+1)(r+1)k$ vertices for r-edge-tree-packing. The authors also devised a methodology to transfer a kernelization result from a packing problem to the corresponding covering problem with a similar size (see [19] for more details). Thus, a kernel with at most $(r^2+1)(r+1)k$ vertices for r-edge-tree-covering (see Box 11) also follows.

Box 11. r-Edge-Tree-Covering Problem.

r-Edge-Tree-Covering

Input: An undirected graph G and an integer k.

Parameter: k

Question: Is there a set S of, at most, k vertices, such that $G-S$ has no tree with r edges as a subgraph?

3.7. Other Examples

More examples of the application of crown decompositions and some variants include

• A kernel with $\mathcal{O}\left(k^3\right)$ vertices for triangle packing (packing vertex disjoint triangles as subgraphs) [28];
• A kernel with $\mathcal{O}\left(k^2\right)$ vertices for k-internal spanning tree (finding a spanning tree with at least k internal vertices) [29];
• A linear-sized kernel for several variants of Vertex Cover [30];
• A $(2d-1)k^{d-1}+k$ sized kernel for d-Hitting Set [31];
• A $\mathcal{O}\left(k^{d-1}\right)$ sized kernel for d-set packing [32]; and
• A kernel with $7k$ vertices for $P_3$-packing (packing vertex disjoint $P_3$s as subgraphs) [33]. Later, Xiao and Khu [34] improved this result into a kernel with $5k$ vertices using the crown decomposition with some critical observations.

4. (Basic) Expansion Lemma and Applications

In this section, we provide the definitions of ‘q-expansion’ and the expansion lemma that generalize Hall’s theorem (Proposition 1). In the following subsections, we give a summary of how expansion lemma has been used for several problems, e.g., p-component order connectivity, Feedback Vertex Set, Cluster Vertex Deletion, and several other theoretical graph problems.

Definition 7

(q-Expansion). Let $G=(V=A\uplus B,E)$ be a bipartite graph with vertex bipartition $(A,B)$. For a positive integer q, a set of edges $M\subseteq E\left(G\right)$ is called a q-expansion of A into B if

• Every vertex of A is incident to exactly q edges of M, and
• M Saturates exactly $q\left|A\right|$ vertices in B.

For $q=1$, a q-expansion is matching. We now have expansion lemma, which was introduced by Thomassé [6].

Lemma 3

(q-Expansion Lemma [6]). Let $q\ge 1$ be a positive integer and $G=(V=A\uplus B,E)$ be a bipartite graph such that

• $\left|B\right|\ge q\left|A\right|$, and
• There are no isolated vertices in B.

Then, there exist nonempty vertex sets $X\subseteq A$ and $Y\subseteq B$, such that

1. 

There is a q-expansion of X into Y, and

2. 

$N_G\left(Y\right)\subseteq X$.

Furthermore, sets X and Y can be found in polynomial time in the size of G (see Figure 1 for an illustration of $q=2$).

When $q=1$, note that the sets $Y,X$, and $V\left(G\right)\backslash (X\cup Y)$ form a crown decomposition with crown, head, and body, respectively. Hence, the expansion lemma can be seen as a generalization of Lemma 2. In particular, it allows us to work with objects that need to be hit that can be of size more than 2. It gives a way to “encode” disjoint objects of size $q+1$ such that any solution must hit these objects. We use this to argue that there is a solution containing X, noting that every object Y is part of can be transformed into a solution containing X.

We illustrate this with a few examples below. To encode objects in this way, we usually construct an auxiliary bipartite graph where we apply the expansion lemma.

4.1. p-Component Order Connectivity

In p-component order connectivity, the goal is to find a subset of k vertices in a given graph, such that every component of the remaining graph has a size of, at most, p for a fixed integer of p. More formally, note that when $p=1$, $G-S$ is an independent set. Thus, p-component order connectivity is a generalization of vertex cover (see Box 1). We explain how a kernel with $\mathcal{O}\left(p^{3}k\right)$ vertices can be obtained for this problem. Note that improved kernels are available for this problem using stronger versions of the expansion lemma (see Section 5), we give an $\mathcal{O}\left(k^{3}p\right)$ kernel to illustrate a simple application of Lemma 3. The results in the literature are improvements of this result using some new tools (available in Section 5).

We can obtain an approximate solution X of, at most, $(p+1)k$ by repeatedly finding connected subsets of size $p+1$, adding it to X and deleting it from G (if $\left|X\right|>(p+1)k$, then it is a no-instance). We can safely remove all components in $G-X$ with a size of, at most, p, as its vertices cannot be part of any optimal solution. We now use an auxiliary bipartite graph Q with X on one side and components of $G-X$ on the other side. We add an edge between a vertex $u\in X$ and a component D in $G-X$ if u has a neighbor in D. If the number of components in $G-X$ is more than $p(p+1)k$, then the conditions for Lemma 3 are satisfied with $q=p$. Thus, we obtain a head $H\subseteq X$ and a crown C, which is a subset of connected components in $G-X$, such that there is a p-expansion of H into C and $N_Q\left(C\right)\subseteq H$. Our reduction rule, similar to that of the vertex cover, includes all of H into the solution, removes H and components of C and drops k by $\left|H\right|$. We again aim to claim that for an optimal solution S, the set $S^{\prime }=(S\backslash (H\cup C))\cup H$ is also an optimal solution. The p-expansion gives a collection of $\left|H\right|$ disjointed connected sets of sizes $(p+1)$ that any solution needs to hit. Hence, $|S^{\prime }|\le |S|$. We use that $N_Q\left(C\right)\subseteq H$ and the graph on C contains only components with a size of, at most, p to claim that $S^{\prime }$ is indeed a solution. This is because all of the connected sets of sizes more than p where vertices in components of C are part of must contain a vertex in H. These are hit by $S^{\prime }$. Thus, the number of connected components in $G-X$ is bounded by $p(p+1)k$. Each of these components has a size of, at most, p. Hence, we obtain a kernel with $\mathcal{O}\left(p^{3}k\right)$ vertices for this problem (defined in Box 12).

Box 12. p-Component Order Connectivity Problem.

p-Component Order Connectivity

Input: Graph G and an integer k.

Parameter: k.

Question: Does G contain a subset S of vertices, $\left|S\right|\le k$, such that every connected component of $G-S$ has a size of, at most, p?

4.2. Undirected Feedback Vertex Set

Thomassé [6] gave a kernel with $\mathcal{O}\left(k^2\right)$ vertices for the Feedback Vertex Set. The main idea is to use the expansion lemma to bind the maximum degree of the graph to $\mathcal{O}\left(k\right)$.

Suppose a vertex v in the graph has a degree more than $11k$. In polynomial time, one can determine [11,35], where v is part of at least $k+1$ cycles with v as the only intersection (in which case v is forced into the solution) or find a set $S_v$ with a size of, at most, $3k$, which hits all of the cycles passing through v. The next step is to bind the number of components in the graph $G-(\left\{v\right\}\cup S_v)$ that has a vertex adjacent to v. Firstly, note that v is adjacent to exactly one vertex in such components; otherwise, there is a cycle containing v not intersecting $S_v$. Such components can be disregarded in this graph, which can contain cycles. Note that the number of such components is at most k as they form disjointed cycles.

Consider the auxiliary bipartite graph where one partition is $S_v$ and the other partition is the remaining components of $G-(\left\{v\right\}\cup S_v)$ and add edges if a vertex in $S_v$ is incident to a vertex in the component. If the number of components is more than $6k$, then Lemma 3 can be used with $q=2$ to find subsets with each vertex in $S_v$ forming a 2-expansion. Note that since v is adjacent to these components, this provides us with a set of cycles containing v corresponding to each 2-expansion. Using the presence of these cycles, it can be proven that any cycles hit by vertices in these components can be hit by either v or all the vertices in the expansion subset of $S_v$. The authors encode this by creating disjoint 2-cycles containing v and each vertex in the expansion subset of $S_v$ if not already present.

This bounds the number of such connected components to $2|S_v|\le 6k$. Thus, the number of vertices adjacent to v is bounded by $6k+|S_v|+k\le 10k$. At most, k of these vertices can have 2 edges to v as we can delete v if it is a part of the $k+1$ cycle intersecting only at v. Thus, the degree of v is bounded by $11k$.

From other reduction rules, it is possible to prove that the graph has a minimum degree of three. Finally, in this case, it can be proved that Feedback Vertex Set (defined in Box 13) admits a kernel with $\mathcal{O}(k\Delta )$ vertices where $\Delta$ is the maximum degree of G. Thus, we have a kernel with $\mathcal{O}\left(k^2\right)$ vertices as $\Delta \le 11k$.

Recently, Iwata [36] obtained a kernel with $\mathcal{O}\left(k^2\right)$ vertices in $\mathcal{O}(m+n)$ time.

Box 13. Undirected Feedback Vertex Set Problem.

Feedback Vertex Set (FVS)

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ is acyclic?

4.3. Cluster Vertex Deletion

The cluster vertex deletion problem can be formulated as a 3-hitting set (see Box 6 with $d=3$) problem with $U=V\left(G\right)$ and $\mathcal{F}$ being the vertex sets of all induced paths on three vertices ($P_3$s) of G. Abu-Khzam [31] obtained a kernel with $\mathcal{O}\left(k^2\right)$ elements for the 3-hitting set. This kernel can be adapted to obtain kernels with $\mathcal{O}\left(k^2\right)$ vertices for cluster vertex deletion.

Fomin et al. [37] obtained a kernel with $\mathcal{O}\left(k^{5/3}\right)$ vertices using Lemma 3 and more sophisticated techniques. We will see a brief overview of this kernel here.

Bounding the number of cliques. We give a simple argument to show how Lemma 3 can be used to bound the number of cliques to $6k$.

First, find a maximal collection $\mathcal{P}$ of the vertex disjoint $P_3$ in G. If $\left|\mathcal{P}\right|>k$, we return a no-instance as there is no optimal cluster vertex deletion set with a size of, at most, k. Otherwise, set S as the subset of vertices in $\mathcal{P}$. Note that $\left|S\right|\le 3k$. We use an auxiliary bipartite graph Q with S on one side and components (cliques) of $G-S$ on the other side. Add an edge between a vertex $u\in S$ and a component D in $G-S$ if u has a neighbor in D. Remove isolated cliques, if any. If the number of remaining cliques is more than $6k$, then the conditions are satisfied for Lemma 3 with $q=2$. This provides a head $H\subseteq S$ and a crown C, which is a subset of components in $G-S$, such that there is a 2-expansion from H to C and $N_Q\left(C\right)\subseteq H$. The reduction rule, similar to that of vertex cover, includes all of H into the solution, removes H and the components of C, and drops k by $\left|H\right|$. This is because it is easy to show that for any optimal solution X, the set $X^{\prime }=X\backslash (H\cup C)\cup H$ is also an optimal solution. The 2-expansion gives a collection of $\left|H\right|$ disjointed $P_3$s that any solution needs to hit. Hence, $|X^{\prime }|\le |X|$. Then they use that $N_Q\left(C\right)\subseteq H$ and that the graph on C is a cluster graph to claim that $X^{\prime }$ is indeed a solution. This is because all $P_3$s containing vertices in components of C have to contain a vertex in H, and these are covered by $X^{\prime }$. Thus, the total number of cliques in $G-S$ is bounded by $6k$.

A marking procedure and a weak form of crown decomposition. After bounding the number of cliques in $G-S$ by $6k$, the authors [37] performed a marking procedure; this procedure involved associating an edge in $G-S$ with each vertex in S, such that exactly one endpoint of the edge is adjacent to that vertex. If $k+1$ edges are associated with a vertex in S, it can be concluded that this vertex must be in the solution as it is the intersection of the $k+1$ $P_3$ and reduces the instance accordingly. Otherwise, if $k^{2/3}$ vertices of S roughly have $k^{2/3}$ edges associated with them, call the run ‘successful’ and mark and delete these vertices. This marking procedure is repeated until a successful run is obtained.

Let U be the set of all marked vertices and M be the set of endpoints of the edges marked in the unsuccessful final run. Let $L=S\backslash U$. The sets $U,V\left(G\right)\backslash S$, and L can be viewed as a weak form of the crown decomposition with U being the head, $V-S$ being the crown, and L being the body. When the crown decomposition is applied to obtain kernels, usually it can be concluded that there is a cluster vertex deletion set that contains all of the head, none of the crown, and all of the edges of the crown within the head. Similarly, in the weak crown decomposition, it can be concluded that most of the vertices of the head U go into a solution, almost none of the vertices of the crown $V\left(G\right)\backslash S$ is in the solution, and almost all of the edges from $V\left(G\right)\backslash S$ are within U.

Identifying good/bad cliques and bounding remaining vertices. Nonetheless, there is no straightforward reduction rule for this weak crown decomposition that the authors obtain. Toward this, they classify the cliques in $G-S$ into good cliques and bad cliques (based on the weak form of crown decomposition). Based on its properties, the number of vertices of bad cliques can be bounded to $\mathcal{O}\left(k^{5/3}\right)$. For a vertex $s\in S$ and a good clique C, the authors [37] identify a small subset of the vertices of C based on the number of neighbors of C in s. Then they show that good cliques exhibit vertex-cover-like behaviors; any solution either contains s or the small side of a good clique. This property can be exploited by using Lemma 3 to bound the number of vertices of the good cliques to $\mathcal{O}\left(k^{5/3}\right)$ as well. This completes a sketch of subquadratic kernel for Cluster Vertex Deletion as defined in Box 14.

Box 14. Cluster Vertex Deletion Problem.

Cluster Vertex Deletion (cvd)

Input: Graph G and an integer k.

Parameter: k.

Question: Does G contain a subset S of, at most, k vertices, such that every connected component of $G\backslash S$ is a clique?

4.4. Other Deletion Problems

In this section, we list some other deletion problems where the expansion lemma was used to obtain kernels.

Here, d is a fixed integer. There have been several previous works on d-PVC with $d=4,d=5$, etc. Cerveny and Suchy [38] provided parameterized algorithms for 4-PVC and 5-PVC (assign $d=4$ and $d=5$ respectively in Box 15). Later, Cerveny et al. [39] obtained a polynomial kernel for d-Path Vertex Cover with $\mathcal{O}\left(k^2\right)$ vertices for $d=4$ and $d=5$ using Lemma 3. They also obtained a polynomial kernel for d-Path Vertex Cover with $k^4{d}^{\mathcal{O}\left(d\right)}$ vertices and edges for every fixed d.

Box 15. d-Path Vertex Cover Problem.

d-Path Vertex Cover (d-PVC)

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ has no path of length d?

Let $\left|S\right|=\ell$. Majumdar et al. [40] used Lemma 3 to obtain a kernel with $\mathcal{O}\left({\ell }^5\right)$ vertices for VC-2-Mod. Note that the connected components of graphs $G-S$ include isolated vertices, paths, and cycles. Lemma 3 is used to bind the number of odd-cycle components to $\mathcal{O}\left({\ell }^3\right)$. An auxiliary bipartite graph is created with sets of size three in S that form an independent set on one side, and the odd cycle components on the other side, adding edges based on a notion called blocking set. After applying Lemma 3 with $q=4$, each 3-sized independent set in the expansion has 4 private odd cycles. It can be proved that it is safe to delete one of the four odd cycle components resulting in an instance with $O\left({\ell }^3\right)$ many odd cycles (without increasing the size of S). Finally, a kernel with $\mathcal{O}\left({\ell }^5\right)$ vertices can be obtained with additional arguments for VC-2-Mod as defined in Box 16.

Box 16. Vertex Cover parameterized by degree-2-modulator.

VC-2-Mod

Input: A graph $G=(V,E)$, a set $S\subseteq V\left(G\right)$ such that every vertex of $G-S$ has a degree of, at most, 2, and an integer k.

Parameter: $\left|S\right|$

Question: Does G have a vertex cover with a size of, at most, k?

Philip et al. [41] provided a kernel with $\mathcal{O}\left(k^2\right)$ vertices for Pathwidth-One Vertex Deletion. Cygan et al. [42] used Lemma 3 to give a simpler kernel with $\mathcal{O}\left(k^2\right)$ vertices for this above problem as defined in Box 17.

Box 17. Pathwidth-One Vertex Deletion Problem.

Pathwidth-One Vertex Deletion

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ has a pathwidth of, at most, one?

Kim and Kwon [43] initiated the study of Block Graph Vertex Deletion problem from parameterized complexity perspective and provided a kernel with $\mathcal{O}\left(k^9\right)$ vertices. Later, Agrawal et al. [44] improved it by giving a kernel with $\mathcal{O}\left(k^4\right)$ vertices using Lemma 3.

Jansen et al. [45] provided a kernel with $\mathcal{O}\left(k^{161}{log}^{58}k\right)$ edges for Chordal Vertex Deletion. Later, Agrawal et al. [46] improved their results using Lemma 3 into a kernel with $\mathcal{O}\left(k^{12}{log}^{2}k\right)$ edges. In addition, Agrawal et al. [46] used the notion of the independence degree of a vertex to obtain this result.

Misra et al. [47] initiated the study of the Even Cycle Transversal problem from a parameterized complexity perspective. They proved the problem to be FPT and gave a kernel with $\mathcal{O}\left(k^2\right)$ vertices. Their kernelization algorithm also uses Lemma 3 as a crucial tool to obtain such a kernel upper bound.

Minch and van Leeuwen [48] provided a kernel with $\mathcal{O}\left(k^3\right)$ vertices for Out-Forest Vertex Deletion Set. Later, Agrawal et al. [49] used Lemma 3 to obtain an improved kernel with $\mathcal{O}\left(k^2\right)$ vertices.

Misra et al. [50] studied the Independent Feedback Vertex Set problem from a parameterized complexity perspective. This problem is a variation of Feedback Vertex Set (defined in Box 13) with additional constraints imposed for the feedback vertex set. They use Lemma 3 to obtain a kernel with $\mathcal{O}\left(k^3\right)$ vertices and edges.

A common theme for the problems Pathwidth-One Vertex Deletion (Box 17), Block Graph Vertex Deletion (Box 18), Chordal Vertex Deletion (Box 19), Even Cycle Transversal (Box 20), Out-Forest Vertex Deletion Set (Box 21), and Independent Feedback Vertex Set (Box 22) is that they all have some infinite cycles as forbidden subgraphs. The application of Lemma 3 (expansion lemma) for all of these problems is inspired by the application by Thomassé [6] for Feedback Vertex Set. The q-expansion from the lemma is used to identify sets of cycles that pairwise intersect in one or two vertices, which has to be hit by the solution. This is used to bind a degree measure for vertices v of G (the measure depends on the problem) by bounding the number of components associated with v.

Box 18. Block Graph Vertex Deletion Problem.

Block Graph Vertex Deletion

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ is a block graph?

Box 19. Chordal Vertex Deletion Problem.

Chordal Vertex Deletion

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ has no induced cycle of a length of (at least) four?

Box 20. Even Cycle Transversal Problem.

Even Cycle Transversal

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that $G-S$ has no even cycle?

Box 21. Out-Forest Vertex Deletion Problem.

Out-Forest Vertex Deletion Set

Input: A directed graph $D=(V,A)$ and a positive integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(D\right)$ of, at most, k vertices, such that $D-S$ is an out-forest?

Box 22. Independent Feedback Vertex Set Problem.

Independent Feedback Vertex Set

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that S is an independent set and $G-S$ is acyclic?

4.5. Graph Packing Problems

The expansion lemma is also used on packing problems. We list a few below.

Cycle Packing is a well-studied problem in parameterized complexity and kernelization. The disjoint cycle packing problem asks if there are at least k cycles in a graph that are pairwise disjoint. It is well-known that the disjoint cycle packing is FPT and admits no polynomial kernelization unless $\mathsf{NP}\subseteq \mathsf{coNP}/\mathsf{poly}$ [51]. After that, Agrawal et al. [52] introduced relaxation criteria in disjointedness constraints and defined the following two problems Pairwise t-Disjoint Cycle Packing and Almost t-Disjoint Cycle Packing for a fixed integer t.

Note that if $t=1$, then Almost t-Disjoint Cycle Packing (Box 23) is same as Vertex Disjoint Cycle Packing. On the other hand, if $t=0$, then Pairwise t-Disjoint Cycle Packing is the same as Vertex Disjoint Cycle Packing problem. Agrawal et al. [52] proved that when $t=1$, Pairwise t-Disjoint Cycle Packing (defined in Box 24) admits a kernel with $\mathcal{O}(k^{4}logk)$ vertices. This makes crucial use of Lemma 3. If $t=\left|V\right(G\left)\right|$, then Pairwise t-Disjoint Cycle Packing is polynomial-time solvable.

Box 23. Almost t-Disjoint Cycle Packing Problem.

Almost t-Disjoint Cycle Packing

Input: An undirected graph G and an integer k.

Parameter: k.

Question: Are there at least k distinct cycles $C_1,\dots ,C_k$ in G, such that every vertex of G appears in, at most, t of these cycles?

Box 24. Pairwise t-Disjoint Cycle Packing Problem.

Pairwise t-Disjoint Cycle Packing (t-PDCP)

Input: An undirected graph G and an integer k.

Parameter: k.

Question: Are there at least k distinct cycles $C_1,\dots ,C_k$ in G such that for every $i\ne j$, $|V\left(C_i\right)\cap V\left(C_j\right)|\le t$?

A simple application of Lemma 3 can obtain a kernelization with $\mathcal{O}\left(k^2\right)$ vertices. Fomin et al. [37] provided an improved kernel with $\mathcal{O}\left(k^{5/3}\right)$ vertices for 3-Path Packing. They used Lemma 3 to obtain this result. Later, Bessy et al. [53] introduced a new technique called rainbow matching and improved this result into a kernel for 3-Path Packing (Box 25) with $\mathcal{O}\left(k\right)$ vertices.

Box 25. 3-Path Packing Problem.

3-Path Packing

Input: An undirected graph $G=(V,E)$ and an integer k.

Parameter: k

Question: Are there k pairwise vertex disjoints inducing $P_3$ in G?

4.6. Other Problems

In this section, we discuss some applications of the expansion lemma other than hitting or packing problems in graphs.

Lokshtanov et al. [54] gave a kernel for set splitting (defined in Box 26) parameterized by k with at most $2k$ sets and k elements. They use a notion of strong cut-sets in a hypergraph, which is closely related to crowns in graphs.

Box 26. Set Splitting Problem.

Set splitting

Input: A universe $\mathcal{U}$, a family $\mathcal{F}$ of subsets of $\mathcal{U}$, and a positive integer k.

Parameter: k.

Question: Is there a bipartition of $\mathcal{U}$ such that at least k sets have non-empty intersection with both parts?

Fomin et al. [55] use Lemma 3 with $q=2$ to give a $3k$-vertex kernel for Maximum Internal Spanning Tree as defined in Box 27.

Box 27. Maximum Internal Spanning Tree Problem.

Maximum internal spanning tree

Input: Graph G and a positive integer k.

Parameter: k.

Question: Is there a spanning tree of G with at least k internal vertices?

5. Recent Developments

In this section, we discuss recent developments, including several variations of the expansion lemma along with their applications. Such new variations have appeared recently. Some of those variants are generalizations, and some of them have stronger and special implications. This section is primarily devoted to the notions of stronger expansion lemma, double expansion lemma, balanced expansion lemma, balanced crown decomposition, and additive expansion lemma (see the relevant subsections for details).

5.1. Weighted q-Expansion Lemma

We introduced p-component order connectivity in Section 4.1 and explained how a kernel with $\mathcal{O}\left(p^{3}k\right)$ vertices can be obtained. In this section, we explain how to obtain a kernel with $\mathcal{O}\left(p^{2}k\right)$ vertices for the same problem using a weighted version of the expansion lemma. The weighted version of the expansion lemma was introduced by Kumar and Lokshtanov [56], who gave a kernel with $2pk$ vertices of this problem. A variant of this lemma was also proposed by Xiao [57], who also gave an $\mathcal{O}\left(pk\right)$ kernel for this problem.

We use a simpler version of the weighted expansion lemma from [11]. We start with some definitions.

Definition 8

(Weighted q-Expansion). Consider a bipartite graph $G=(V=A\uplus B,E)$ with a weight function $w:V\left(G\right)\to \{1,\dots ,W\}$ for an integer W. Given a subset $X\subseteq V\left(G\right)$, let $w\left(X\right)={\displaystyle \sum _{x\in X}}w\left(x\right)$. For an integer $q\ge 1$, a function $f:B\to A$ is called a weighted q-expansion of A into B if

• for every $b\in B$, $f\left(b\right)\in N\left(b\right)$, and
• for every $a\in A$, $w\left(f^{-1}\left(a\right)\right)\ge q-W+1$.

When $W=1$, a weighted q-expansion corresponding to a q-expansion for $a\in A$, $w\left(f^{-1}\left(a\right)\right)\ge q$, and $w\left(f^{-1}\left(a\right)\right)$ is the number of neighbors of a in B.

Lemma 4

(Weighted expansion lemma [11]). Let q and W be positive integers. Consider a bipartite graph $G=(V=A\uplus B,E)$ with weight function $w:V\left(G\right)\to \{1,\dots ,W\}$ such that

1. 

$w\left(B\right)\ge q\left|A\right|$; and

2. 

There are no isolated vertices in B.

Then there exist non-empty vertex sets $X\subseteq A$, $Y\subseteq B$ and a function $f:Y\to X$ such that

• f is a weighted q-expansion of X into Y, and
• No vertex in Y has a neighbor outside X, i.e., $N\left(Y\right)\subseteq X$.

Furthermore, the sets X and Y and the function f can be found in time $\mathcal{O}\left(m{n}^{1.5}{W}^{2.5}\right)$.

We first provide a kernel with $\mathcal{O}\left(p^{2}k\right)$ vertices for p-component order connectivity for the problem (discussed in [11]) as a precursor to the kernel with $2pk$ vertices by Kumar and Lokshtanov [56]. Recall the auxiliary bipartite graph in Section 4.1 with modulator X on one side and $\mathcal{C}$, the connected components of $G-X$, in the other one. For each connected component in $\mathcal{C}$, we assign its weight as the number of vertices in the component. Note that these weights are at most p. For all the vertices in X, we assign weight 1.

We now apply Lemma 4 with $q=2p-1$ to obtain a subset $H\subseteq X$ and a subset $C\subseteq \mathcal{C}$ such that there is a weighted q-expansion of H into C. For any optimal solution S, we look at the set $S^{\prime }=S\backslash (H\cup C)\cup H$. The weighted q-expansion gives us disjoint connected sets in the auxiliary bipartite graph, each of whose weight is at least $q-p+1\ge p$. Thus, we can conclude that the weighted q-expansion represents a connected set of size at least $p+1$ in G, which any solution needs to hit. Similar to the argument in Section 4.1, we can prove that $S^{\prime }$ is an optimal solution. Thus, we have a reduction rule as long as Lemma 4 is applicable. If this is not the case, we have $w\left(\mathcal{C}\right)\le q\left|X\right|\le (2p-1)(p+1)k$ in the auxiliary bipartite graph. From the conclusion that the number of vertices in $G-X$ is $w\left(\mathcal{C}\right)$, we have a $\mathcal{O}\left(p^{2}k\right)$ kernel.

Note that in the kernel with $\mathcal{O}\left(p^{3}k\right)$ vertices for p-component order connectivity described in Section 4.1, we were not able to capture the sizes of the components in the auxiliary bipartite graph. We manage to do so using weighted expansions.

Kumar and Lokshtanov [56] use some further ideas and linear programming to improve the kernel size to $2pk$.

5.2. Stronger Expansion Lemma and Double Expansion Lemma

Fomin et al. [37] defined the following stronger notion of a q-expansion. Let $G=(V=A\uplus B,E)$ be a bipartite graph. Let $q>0$ be an integer, $\widehat{A}\subseteq A$, and $\widehat{B}\subseteq B$. We say that there is a stronger q-expansion of $\widehat{A}$ into $\widehat{B}$ if for all subsets $X\subseteq \widehat{A}$, we have $|N_G\left(X\right)\cap \widehat{B}|\ge q|X|$. Using this notion, they prove the following version of the expansion lemma, which does not need the conditions that $\left|B\right|\ge q\left|A\right|$ or that there are no isolated vertices in B.

Lemma 5

(Stronger Expansion Lemma [37]). Let q be a positive integer, and $G=(V=A\uplus B,E)$ be a bipartite graph. Then there exist (possibly empty) sets $\widehat{A}\subseteq A$ and $\widehat{B}\subseteq B$ such that

1. 

$\widehat{A}$ has a stronger q-expansion into $\widehat{B}$,

2. 

$N_G\left(\widehat{B}\right)\subseteq \widehat{A}$, and

3. 

$|B\backslash \widehat{B}|\le q|A\backslash \widehat{A}|$.

Moreover, the sets $\widehat{A}$ and $\widehat{B}$ can be computed in polynomial time. See Figure 2 for an illustration with $q=2$.

This lemma is different from Lemma 3 as it does not require that $\left|B\right|\ge q\left|A\right|$ and there are no isolated vertices in B. Moreover, note that this lemma does not demand that $\widehat{A}$ and $\widehat{B}$ must be non-empty. If $\widehat{B}=\varnothing$ for some graph G, then $\widehat{A}=\varnothing$ as there is a stronger q-expansion from $\widehat{A}$ to $\widehat{B}$. Moreover, since $|B\backslash \widehat{B}|\le q|A\backslash \widehat{A}|$, we have $\left|B\right|\le q\left|A\right|$. Therefore, if $\left|B\right|>q\left|A\right|$, then $\widehat{B}\ne \varnothing$.

Note that in Lemma 3 (expansion lemma), $\left|Y\right|=q\left|X\right|$. However, in a stronger expansion lemma, it could be that $|\widehat{B}|>q|\widehat{A}|$. The intuition in applying a stronger expansion lemma for a problem instance is that some vertices of $\widehat{B}$ could be safely eliminated from the input graph. Note that since $|B\backslash \widehat{B}|\le q|A\backslash \widehat{A}|$, to bound the size of B as a function of $\left|A\right|$, we might need to remove some of the vertices of $\widehat{B}$. Observe that for every $u\in \widehat{A}$, there is at least q edges incident. Thus, by keeping exactly $q|\widehat{A}|$ vertices in $\widehat{B}$, the property of a q-expansion from $\widehat{A}$ is maintained. Thus, the other vertices from $\widehat{B}$, which only has neighbors to $\widehat{A}$, could be deleted.

The following problem Arc Disjoint 4-Cycle Packing provides an intuition to use the above lemma.

Babu et al. [58] first proved that for every fixed $r\ge 3$, Arc Disjoint r-Cycle Packing is NP-complete in directed graphs of girth r, and this NP-completeness result holds for every $r\ge 4$ when the input graph is bipartite. After that, they provide a kernel with $\mathcal{O}\left(k^2\right)$ vertices and $\mathcal{O}\left(k^3\right)$ arcs for $r=4$, i.e., for the Arc Disjoint 4-Cycle Packing (see Box 28) problem using a stronger expansion lemma (Lemma 5). A brief summary of the kernelization algorithm by Babu et al. [58] works as follows.

• Initially, the authors apply some preprocessing rules to the input graph D and ensure that every arc $(u,v)$ of D is contained in at most $(4k-4)$ distinct 4-cycles, the pairwise intersection of which is $\{u,v\}$.
• Let $\mathcal{X}$ be a collection of the maximal set of 4-cycles, such that for every pair of 4-cycles in $\mathcal{X}$, there is at most one common vertex. The authors prove that if $\left|\mathcal{X}\right|>16k^2$, then the input is a YES instance.
• So, it can be assumed that $\left|\mathcal{X}\right|\le 16k^2$. Let $\mathcal{P}$ be the set of all 3 paths that are contained in the 4-cycle in $\mathcal{X}$. As $\left|\mathcal{X}\right|\le 16k^2$, $\left|\mathcal{P}\right|$ is $\mathcal{O}\left(k^2\right)$. What is left is to bind the number of vertices in $V\left(D\right)\backslash V\left(\mathcal{P}\right)$.
• The authors construct an auxiliary bipartite graph H with bipartitions A and B where $A=\mathcal{P}$ and $B=V\left(D\right)\backslash V\left(\mathcal{P}\right)$. For $u\in B$ and $\{x,y,z\}\in \mathcal{P}$, there is an edge in H if and only if $\{x,y,z,u\}$ is a 4-cycle in D.
• One can now apply Lemma 5 with $q=1$ and obtain a stronger 1-expansion with sets $\widehat{A}\subseteq A$ and $\widehat{B}\subseteq B$. It ensures that $|B\backslash \widehat{B}|\le |A\backslash \widehat{A}|$. Let $\widehat{M}\subseteq E(\widehat{A},\widehat{B})$ be the set of edges of H such that every vertex of $\widehat{A}$ is incident to exactly one vertex of $\widehat{B}$ and every vertex of $\widehat{B}$ is incident to exactly one vertex of $\widehat{A}$.
• Finally, the authors apply a reduction rule that deletes the set of vertices from $\widehat{B}$, which is not saturated by $\widehat{M}$. The 4-cycles that these vertices are part of can be covered by picking one of the vertices from the corresponding 3-paths in $\widehat{A}$. The matching M ensures that there exists a 4-cycle for each 3-path in $\widehat{A}$. Thus, the reduction rule is safe.
• The reduction rule is no longer applicable when the set of vertices from $\widehat{B}$ that is not saturated by $\widehat{M}$ is empty. In this case, we have $\left|B\right|=|B\backslash \widehat{B}|+|\widehat{B}|\le |A\backslash \widehat{A}|+|\widehat{A}|=|A|$, which is $\mathcal{O}\left(k^2\right)$. Thus, we obtain a kernel with $\mathcal{O}\left(k^2\right)$ vertices.

Box 28. Arc Disjoint r-Cycle Packing Problem.

Arc Disjoint r-Cycle Packing

Input: A directed graph $D=(V,A)$ and an integer k.

Parameter: k

Question: Are there at least k pairwise arc disjoint directed cycles of length r in D?

Fomin et al. [37] provided a kernel for the above problem (as defined in Box 29) with $\mathcal{O}\left(k^{3/2}\right)$ vertices that use both Lemma 3 (expansion lemma) and Lemma 5 (stronger expansion lemma).

The authors also went on to prove Lemma 6 stated below that simultaneously provides expansion in multiple graphs.

Box 29. Vertex-Disjoint Triangle Packing in Tournament.

Triangle Packing in Tournaments

Input: A tournament $D=(V,A)$ and an integer k.

Parameter: k.

Question: Are there at least k pairwise vertex disjoint directed triangles in D?

Lemma 6

(Double Expansion Lemma [37]). Let q be a positive integer and $G,H_1,H_2,\dots ,H_d$ be bipartite graphs with bipartitions $A\uplus B,A_1\uplus R_1,\dots ,A_d\uplus R_d$, respectively, such that for every $i\ne j$, $A_i\cap A_j=\varnothing ,R_i\cap R_j=\varnothing$, ${\cup }_{i=1}^d{A}_i=A$, and ${\cup }_{i=1}^d{R}_i\subseteq B$. We can in polynomial time compute $\widehat{A}\subseteq A,\widehat{B}\subseteq B,{\widehat{A}}_i\subseteq A_i,{\widehat{R}}_i\subseteq R_i$ for every $i\in \left[d\right]$ such that

1. 

$\widehat{B}={\cup }_{i=1}^d{\widehat{R}}_i$,

2. 

$|B\backslash \widehat{B}|\le q(\left|A\right|+|{\cup }_{i=1}^d{\widehat{A}}_i\left|\right)$,

3. 

$\widehat{A}$ has a stronger q-expansion into $\widehat{B}$ and for every $i\in \left[d\right]$, ${\widehat{A}}_i$ has a stronger q-expansion into ${\widehat{R}}_i$ in $H_i$,

4. 

$N_G\left(\widehat{B}\right)\subseteq \widehat{A}$, and

5. 

for all $i\in \left[d\right]$, $N_{H_i}\left(R_i\right)\subseteq A_i$.

A double expansion lemma was used in Feedback Vertex Set in Tournaments to give an improved kernel. We formally define the problem below.

Feedback Vertex Set in Tournaments can be cast as a 3-hitting set problem (see Box 6), and hence its kernel can be adapted to obtain a kernel with $\mathcal{O}\left(k^2\right)$ vertices. Fomin et al. [37] used Lemma 6 (double expansion lemma) to obtain a kernel with $\mathcal{O}\left(k^{3/2}\right)$ vertices. We give a sketch of the algorithm below.

As hitting directed cycles in a tournament is equivalent to hitting directed triangles in a tournament, a 3-approximation algorithm follows for Feedback Vertex Set in Tournaments. However, a set S has a size of, at most, $7k/3$ can also be obtained due to Minch et al. [59] such that $D-S$ is acyclic. We call an arc $(x,y)\in A$ as strong arc if $(x,y)$ is part of at least $k+2$ triangles with the other endpoints of the triangles from S. In this case, one of x and y has to be in every solution.

Since $D-S$ is acyclic, its vertices have a topological ordering. We can extend this to an ordering of vertices of D by adding vertices in S such that it minimizes certain “conflicts". In this ordering, we can then argue that the vertices of every triangle in D that do not contain a strong arc are within $7k$ distance from each other in the ordering. Hence, these triangles are, in a sense local.

The problem boils down to simultaneously hitting strong arcs and the local triangles. This is achieved by using Lemma 6 by constructing a global graph corresponding to the strong arcs and local graphs for the local triangles.

First, the vertices of $D-S$ are broken into groups of size $100k$ according to the topological ordering. Then, the authors [37] look at the first $p=4\sqrt{k}$ of such groups $Y_1,Y_2,\dots ,Y_p$, and discard the first and last $7k+1$ vertices of each to form intervals $Y_1^{\prime },Y_2^{\prime },\dots ,Y_p^{\prime }$. For $i\in \left[p\right]$, let $S_i$ be the set of vertices in S that are placed within $Y_i^{\prime }$ in the ordering of $V\left(D\right)$. Note that the vertices of any local triangle containing a vertex in $Y_i^{\prime }$ are contained in the set $S_i\cup Y_i$. Then each interval $Y_i^{\prime },i\in \left[p\right]$ can be divided into q subintervals $Y_{i,1},Y_{i,2},\dots ,Y_{i,q}$, each of size $3\sqrt{k}$.

Next, they define a global bipartite graph G with bipartition $S\uplus \{Y_{i,j}:i\in \left[p\right],j\in \left[q\right]\}$ and strong arcs. Additionally, the authors define local bipartite graphs $H_i$ with bipartition $S_i\uplus \{Y_{i,j}:i\in \left[p\right],j\in \left[q\right]\}$ that contains the local triangles. Finally, they appropriately apply a double expansion lemma (Lemma 6) to obtain expansion and neighborhood containment properties in all of the graphs simultaneously. This allows them to find a vertex in $V\left(D\right)\backslash S$, which can be safely deleted. When the lemma is no longer applicable, the number of vertices is $\left|S\right|+|{\cup }_{i\in \left[p\right]}{Y}_i|\le 2k+100k·4\sqrt{k}$. This gives us a summary of the kernel for Feedback Vertex Set in Tournaments (defined in Box 30) with $\mathcal{O}\left(k^{3/2}\right)$ vertices (See [37] for more details).

Box 30. Feedback Vertex Set Problem in Tournament.

Feedback Vertex Set in Tournaments

Input: A tournament $D=(V,A)$ and an integer k.

Parameter: k.

Question: Is there a set $S\subseteq V\left(D\right)$ of, at most, k vertices, such that $D-S$ is acyclic?

5.3. Balanced Expansion and Balanced Crown Decomposition

Now, we introduce the notion of balanced crown decomposition, balanced expansion, and some related polynomial-time algorithms developed by Casel et al. [60].

Definition 9

(Balanced Expansion). Let $G=(V=A\uplus B,E,w)$ be a vertex-weighted bipartite graph, where $w_{max}^B={max}_{b\in B}w\left(b\right)$. For $q\in {\mathbb{N}}_0$, a partition $A_1\cup A_2$ of A, and $f:B\to A$, the tuple $(A_1,A_2,f,q)$ is called a balanced expansion if:

1. 

$w\left(a\right)+w\left(f^{-1}\left(a\right)\right)\ge q-w_{max}^B+1$ if $a\in A_1$,

2. 

$w\left(a\right)+w\left(f^{-1}\left(a\right)\right)\le q+w_{max}^B-1$ if $a\in A_2$,

3. 

for all $b\in B$, $f\left(b\right)\in N\left(b\right)$, and

4. 

$N\left(f^{-1}\left(A_1\right)\right)\subseteq A_1$.

(See Figure 3 for an illustration).

Based on the above definition, the weight of a vertex of A combined with the weight of its pre-image is in the range of $q-w_{max}^B+1$ and $q+w_{max}^B-1$. The function f is similar to the condition of expansion in Section 4. Using the above definition, Casel et al. [60] proved the following result.

Lemma 7

(Balanced Expansion Lemma). Consider a vertex-weighted bipartite graph $G=(V=A\uplus B,E,w)$ with no isolated vertices in B and $q\ge {max}_{b\in B}w\left(b\right)=w_{max}^B$. A balanced expansion $(A_1,A_2,f,q)$ for G can be computed in the $\mathcal{O}\left(mn\right)$-time. Furthermore, if $w\left(A\right)+w\left(B\right)\ge q\left|A\right|$, then $A_1\ne \varnothing$.

The following is a more fine-grained version of the balanced expansion defined in [60].

Definition 10

(Fractional Balanced Expansion). Let $G=(V=A\uplus B,E,w)$ be a vertex-weighted bipartite graph, where $w_{max}^B={max}_{b\in B}w\left(b\right)$. For $q\in {\mathbb{N}}_0$, a partition $A_1\cup A_2$ of A, and $g:E\left(G\right)\to {\mathbb{N}}_0$, the tuple $(A_1,A_2,g,q)$ is called a fractional balanced expansion if:

1. 

$w\left(a\right)+{\sum }_{b\in B}g\left(ab\right)\ge q$ if $a\in A_1$,

2. 

$w\left(a\right)+{\sum }_{b\in B}g\left(ab\right)\le q$ if $a\in A_2$,

3. 

for all $b\in B$, ${\sum }_{a\in A}g\left(ab\right)\le w\left(b\right)$, and

4. 

$N(B_U\cup B_{A_1})\subseteq A_1$, where $B_a=\{b\in B\mid g\left(ab\right)>0\}$ for $a\in A$, $B_{A^{\prime }}={\cup }_{a\in A^{\prime }}{B}_a$ for $A^{\prime }\subseteq A$ and $B_U=\{b\in B\mid {\sum }_{a\in A}g\left(ab\right)<w\left(b\right)\}$.

Such a tuple $(A_1,A_2,g,q)$ can be interpreted as a fractional balanced expansion as follows. The weights of the vertices of the $f^{-1}$ function are distributed to edges through the g function, i.e., g can be interpreted as a fractional assignment from $v\in B$ to $u\in N\left(b\right)$. For the non-fractional version (in Definition 9, we aim that for all $v\in B$, $g\left(uv\right)=w\left(u\right)$ for a unique $u\in A$ while $g\left(u^{\prime }v\right)=0$ when $u^{\prime }\in A\backslash \left\{u\right\}$.

The authors [60] prove the following fractional version of Lemma 7.

Lemma 8

(Fractional Balanced Expansion Lemma). Let $G=(V=A\uplus B,E,w)$ be a vertex-weighted bipartite graph, where $w_{max}^B={max}_{b\in B}w\left(b\right)$. For $q\in {\mathbb{N}}_0$, a partition $A_1\cup A_2$ of A and $g:E\left(G\right)\to {\mathbb{N}}_0$, a fractional balanced expansion $(A_1,A_2,g,q)$ can be computed $\mathcal{O}\left(mn\right)$-time. Furthermore, if $w\left(A\right)+w\left(B\right)\ge q\left|A\right|$, then $A_1\ne \varnothing$.

The authors [60] use Lemma 7 to prove the construction of a structure called λ-balanced crown decomposition for a fixed integer $\lambda$ described below.

Definition 11

($\lambda$-balanced crown decomposition [60]). A $\lambda$-balanced crown decomposition for a vertex-weighted graph $G=(V,E,w)$ is a tuple $(C,H,\mathfrak{R},f)$ where $(H,C,R)$ is a partition of $V\left(G\right)$ and $\mathfrak{R}$ is a partition of R and $f:\mathbb{C}\mathbb{C}\to H$ where $\mathbb{C}\mathbb{C}\left(C\right)$ is the set of connected components of $G\left[C\right]$ such that:

1. 

there are no edges from C to R,

2. 

$w\left(Q\right)<\lambda$ for each $Q\in \mathbb{C}\mathbb{C}\left(C\right)$,

3. 

$f\left(Q\right)\in N\left(Q\right)$ for every $Q\in \mathbb{C}\left(C\right)$,

4. 

$w\left(h\right)+w\left(f^{-1}\left(h\right)\right)\ge \lambda$ for each $h\in H$, and

5. 

$G\left[R^{\prime }\right]$ is connected and $\lambda \le w\left(R^{\prime }\right)\le 3\lambda -3$ for each $R^{\prime }\in \mathfrak{R}$.

The first four properties are those of crown property with some added weight specifications (see [57]), and the last property ensures that all parts of the partition are fairly balanced. Moreover, the fourth condition implies that every $u\in H$ should be connected to component(s) of $G\left[C\right]$ with weight at least $\lambda -1$. The notion of the $\lambda$-balanced crown decomposition is something that Casel et al. [60] contributed toward when obtaining new results. However, a crucial contribution of Definition 11 by [60] is the fifth condition. The fifth condition states that every part of the partition of R is of weight within the range $[\lambda ,3\lambda -3]$.

Lemma 7 (balanced expansion lemma) was not directly used to prove any kernel upper bound result, but was used by Casel et al. [60] to prove the “balanced crown lemma” that we state below.

Lemma 9

(Balanced Crown Lemma [60]). Let $G=(V,E,w)$ be a vertex-weighted graph and $\lambda \in \mathbb{N}$, such that each connected component in G has a weight of at least λ. A λ-balanced crown decomposition $(C,R,\mathfrak{R},f)$ of G can be computed in $\mathcal{O}\left(k^2\right|V\left|\right|E\left|\right)$-time where $k=\left|H\right|+\left|\mathfrak{R}\right|\le min\left\{w\right(G)/\lambda ,|V\left|\right\}$.

Casel et al. [60] used Lemma 9 to obtain a kernel for the weighted version of a separation and packing problem that we define below. Note that W-Weight Separator can be viewed as a weighted variant of the p-component order connectivity problem, and W-Weight Packing is simply its packing analog (see Box 31 and Box 32 below).

Box 31. W-Weight Separator Problem.

W-Weight Separator

Input: A vertex-weighted undirected graph $G=(V,E,w)$ and integer k.

Question: Is there a set $S\subseteq V\left(G\right)$ of, at most, k vertices, such that every connected component of $G-S$ has a total weight of less than W?

Box 32. W-Weighted Packing Problem.

W-Weight Packing

Input: A vertex-weighted undirected graph $G=(V,E,w)$ and integers k.

Question: Are there k pairwise disjoint sets $V_1,\dots ,V_k$, such that for every $1\le i\le k$, $V_i\subseteq V\left(G\right),w\left(V_i\right)\ge k$ and $G\left[V_i\right]$ is connected?

For both these above mentioned problems, Casel et al. [60] provided kernels with $3k(W-1)$ vertices, which can be computed in $\mathcal{O}\left(k^2\right|V\left|\right|E\left|\right)$-time.

Finally, they studied the balanced connected partition problem stated below.

In the same paper, they use Definition 11 and Lemma 9 to give a polynomial time for Max-Min (Min–Max) Balanced Connected Partition, which outputs a partition $V_1^{*},\dots ,V_k^{*}$ of $V\left(G\right)$ such that for each $i\in \left[k\right]$, $G\left[V_i\right]$ is connected and $w\left(V_i^{*}\right)\ge W/3$ to give an approximation algorithm for Max-Min (Min–Max) Balanced Connected Partition as defined in Box 33.

Box 33. Balanced Connected Partition Problem.

Max-Min (Min–Max) Balanced Connected Partition

Input: A vertex-weighted undirected graph $G=(V,E,w)$ and integer k.

Question: Is there a partition $V_1,\dots ,V_k$ of $V\left(G\right)$ such that for each $i\in \left[k\right]$, $w\left(V_i\right)\ge W$ and $G\left[V_i\right]$ is connected?

5.4. Additive Expansion Lemma

Koana et al. [61] introduced the following variant of the expansion and the expansion lemma.

Definition 12

(q-Additive Expansion, [61]). Let $G=(V=A\uplus B,E)$ be a bipartite graph and q be a positive integer. Then, G is said to have a q-additive expansion from A into B if for every $B^{\prime }\subseteq B$ of size q, there is a matching saturating A in $G[A,B\backslash B^{\prime }]$.

For completeness, we give proof of the following proposition that is stated in [61].

Proposition 3.

Let $G=(V=A\uplus B,E)$ be a bipartite graph. There is a q-additive expansion from A into B if and only if for every nonempty $X\subseteq A$, $\left|N\right(X\left)\right|\ge \left|X\right|+q$.

Proof. 

We will prove this using Hall’s theorem.

Consider the forward direction (⇒) first. Suppose that G has a q-additive expansion from A to B. Then, for every $B^{\prime }\subseteq B$ of size q, there is a matching saturating A in $G^{\prime }=G[A,B\backslash B^{\prime }]$. It means that for every non-empty $X\subseteq A$, $|N\left(X\right)\backslash B^{\prime }|\ge |X|$. Consider the value of $|N_G\left(X\right)|$. If $|N_G\left(X\right)|<|X|+q$, then consider a set of an arbitrary set $\widehat{B}$ of q vertices from $N_G\left(X\right)$. Clearly, $\widehat{B}\subseteq B$ has q vertices. However, then in the graph $\widehat{G}=G[A,B\backslash \widehat{B}]$, for the same set $X\subseteq A$, it holds that $|N_{\widehat{G}}\left(X\right)|<|X|$. Then it leads to a contradiction that there is a matching saturating A in $\widehat{G}$.

Let us now prove the backward direction (⇐). Suppose that for every nonempty $X\subseteq A$, $\left|N\right(X\left)\right|\ge \left|X\right|+q$. We have to justify that for every $B^{\prime }\subseteq B$ of size q, there is a matching saturating A in $G[A,B\backslash B^{\prime }]$. Suppose that for some $B^{*}\subseteq B$ of size q, there is no matching saturating A in $G^{*}=G[A,B\backslash B^{*}]$. Then, by Proposition 1 (Hall’s theorem), there is $X\subseteq A$, such that $|N_{G^{*}}\left(X\right)|<|X|$. As $B^{*}$ is of size q, then in G also, it holds that $|N_G\left(X\right)|<|X|+q$. This contradicts the premise, which completes the proof of the observation. □

Now, we state the additive expansion lemma and give a short explanation of how it has been used to provide an improved kernel for partial vertex cover.

Lemma 10

(Additive Expansion Lemma [61]). Let $q\ge 1$ and $G=(V=A\uplus B,E)$ be a bipartite graph. If $\left|B\right|>q\left|A\right|$ and there is no isolated vertex in B, then there exists nonempty $\widehat{A}\subseteq A$ and $\widehat{B}\subseteq B$ such that

• There is a q-additive expansion of $\widehat{A}$ into $\widehat{B}$; and
• No vertex of $\widehat{B}$ has the neighbor outside $\widehat{A}$, i.e., $N\left(\widehat{B}\right)\subseteq \widehat{A}$.

First, the authors [61] provide a kernel with $(\ell +2)(k+\ell )$ vertices that use the expansion lemma (Lemma 3). It works as follows.

• First, they consider the LP formulation of Vertex Cover. By Nemhauser and Trotter [62], there is a fractional optimal solution for the LP formulation of Vertex Cover such that all vertices are assigned values of either 0, 1, or 1/2.
• Let $V_0,V_1,V_{1/2}$ denote the vertices that are assigned values 0, 1, 1/2, respectively. If $|V_1|+|V_{1/2}|\ge k+\ell +1$, then the instance is a no-instance.
• Otherwise, they construct an auxiliary bipartite graph, and apply the expansion lemma to obtain a kernel with $(\ell +2)(k+\ell )$ vertices.

After that, they give a proof using the additive expansion lemma (Lemma 10), a kernel with $({\ell }^{\prime }+1)(k+\ell )$ vertices can be obtained, such that ${\ell }^{\prime }=max\{\ell ,1\}$. The rest of the proof for the problem defined in Box 34 has similar structures, but a crucial difference is that they use Lemma 10 instead of Lemma 3.

Box 34. Partial Vertex Cover Problem.

Partial vertex cover

Input: An undirected graph $G=(V,E)$ and two integers $k,\ell$.

Parameter: $k+\ell$

Question: Is there a set S of, at most, k vertices, such that $G-S$ has (at most) $\left|E\right(G\left)\right|-\ell$ edges?

6. Conclusions and Future Research

Our aim in this survey is to bring variations and parameterized complexity applications of an important tool called expansion lemma into one place. Different authors have obtained variations to suit the specific problems they deal with, and so some of the applications tend to apply to specific kinds of problems. The survey is non-exhaustive simply because new variations and applications are exploding at a fast pace. We hope that our survey will trigger further applications of these variations in parameterized complexity. It will be interesting to see more applications of recent variants, such as Lemma 4, Lemma 6, and Lemma 10, and to find tighter bounds for the kernel results to which they are applied. In particular, the following research directions would be interesting to investigate.

• There are some other well-studied vertex deletion problems in the kernelization perspective, e.g., an $\mathcal{O}\left(k^2\right)$ vertex kernel for Split Vertex Deletion (see [63]) but it has a kernel lower bound of $\mathcal{O}\left(k^{2-\epsilon }\right)$ edges [4]. It would be interesting to see if one of these variants of the expansion lemma can be useful to obtain a sub-quadratic vertex kernel for these problems.
• Recently, Jacob et al. [64,65] introduced the study of vertex deletion problems to scattered graph classes. While they proved parameterized complexity of this problem, kernelization complexity is open and unexplored. It would be nice to explore if the expansion lemma or some of its variants can be useful for this.