Let $U$ be a minimal subset of $V(G)$ such that $G-U$ is a proper interval
graph. Then, by Proposition 6.25, there exists $w\in V(G)$ such that
$U=\\{u\in V(G):\mathsf{end}_{f}(w)\in f(u)\\}$. Now, let $v\in U$ be a vertex
such that $N[v]=N[w]$ and when we go in clockwise order starting at
$\mathsf{end}_{f}(v)$ (and neglecting vertices whose intervals coincide with
that of $v$ apart from $v$ itself), the last end $\mathsf{end}_{f}(\cdot)$
that we encounter among those of all vertices in $U$ that have the same
neighborhood as $w$ is that of $v$. In particular, as the maximum independent
set size is at least $4$, this means that there does not exist a vertex $u$
with the same closed neighborhood as $v$ (and in particular, which is a
neighbor of $w$) and yet “ends after $v$”, that is, $\mathsf{end}_{f}(v)\in
f(u)$. So, $T=\\{u\in V(G):\mathsf{end}_{f}(v)\in f(u),N[v]\neq
N[u]\\}=\\{u\in V(G):\mathsf{end}_{f}(v)\in f(u)\\}\subseteq U$ (see Fig. 6).
If $w=v$, we are done. Else, we have that $T\subset U$ because $v\in U$ but
$v\notin T$. By Proposition 6.25, $G-T$ is a proper interval graph. However,
this contradicts the minimality of $U$. ∎

Recall that the crux of the proof should be in the following lemma.

######  Lemma 6.27.

Consider Proper Interval Vertex Deletion on proper circular-arc graphs that
admit no claw, net, tent, $C_{4}$, $C_{5}$, $C_{6}$ and $C_{7}$ as induced
subgraphs. Then, it admits an $\widetilde{{\mathcal{O}}}(n)$-space
$2^{{\mathcal{O}}(k)}\cdot n^{{\mathcal{O}}(1)}$-time (static) algorithm.

Towards the proof of this lemma, we have the following lemma. In particular,
this lemma gives a characterization of minimal solutions that does not depend
on $f$.

######  Lemma 6.28.

Let $G$ be a proper circular-arc graph with representation $f$ and that has an
independent set of size at least $4$. Let $v\in V(G)$, and denote $U=\\{u\in
V(G):\mathsf{end}_{f}(v)\in f(u),N[v]\neq N[u]\\}$. Then, there exists $x\in
V(G)$ such that $U=W_{v,x}$ where $W_{v,x}=\\{u\in N[v]\cap N[x]:N[u]\neq
N[v],N[u]\subseteq N[v]\cup N[x]\\}$.

###### Proof.

Let $x$ be a vertex such that $x\in U$ (and so $\mathsf{end}_{f}(v)\in f(x)$)
and among all vertices in $U$ the end of its interval $\mathsf{end}_{f}(x)$ is
furthest from $\mathsf{end}_{f}(v)$ (when distance is measure in clockwise
order); see Fig. 7. In what follows, we show that $U=W_{v,x}$.

Figure 7: A figure for the proof of Lemma 6.28. In particular, $1,2,3,5\notin
U$ since $\mathsf{end}_{f}(v)$ does not belong to their intervals, and
$4\notin U$ since $N[v]=N[4]$. Additionally, $1,2\notin W_{v,x}$ since they do
not belong to $N[x]$, $3\notin W_{v,x}$ since $N[3]$ is not contained in
$N[v]\cup N[x]$, $4\notin W_{v,x}$ since $N[v]=N[4]$, and $5\notin W_{v,x}$
since $4\notin N[v]$.

In one direction, consider some $u\in U$. Then, because
$\mathsf{end}_{f}(v)\in f(u)$, $\mathsf{end}_{f}(v)\in f(x)$ and $G$ has an
independent set of size at least $4$, and by the choice of $w$, this means
that when we go from $\mathsf{start}_{f}(v)$ in clockwise order, we observe
the ordering
$\mathsf{start}_{f}(v)<\mathsf{start}_{f}(u)\leq\mathsf{start}_{f}(x)<\mathsf{end}_{f}(v)<\mathsf{end}_{f}(u)\leq\mathsf{end}_{f}(x)$;
see Fig. 7. So, $f(u)$ has non-empty intersection with both $f(v)$ and $f(x)$,
and it is contained in their union, which means that $u\in N[v]\cap N[x]$ and
$N[u]\subseteq N[v]\cup N[x]$. Because $u\in U$, it also holds that $N[u]\neq
N[v]$, and hence $u\in W_{v,x}$.

In the other direction, consider some $u\in W_{v,x}$. Because $u\in N[v]\cap
N[x]$ and in particular $u\in N(v)$, we have that $\mathsf{end}_{f}(v)\in
f(u),\mathsf{start}_{f}(v)\in f(u)$ or $f(v)=f(u)$. Because $N[u]\neq N[v]$
while $N[u]\subseteq N[v]\cup N[x]$, there exists a vertex that is a neighbor
of $u$ and $x$ but not of $v$. However, by the choice of $x$ and because $G$
has an independent set of size at least $4$, in case $\mathsf{start}_{f}(v)\in
f(u)$ or $f(v)=f(u)$, this is not possible. For intuition, see Fig. 7 (where
it can be seen that any vertex in $N[u]\setminus N[x]$, which in this case is
$5$, must be “more to the left” than $x$, which imply that $u$ is “more to the
left” than $v$) and Fig. 8. So, necessarily, $\mathsf{end}_{f}(v)\in f(u)$. ∎

Figure 8: A figure for the proof of Lemma 6.28. Here, there cannot be an
independent set of size at least $4$ (even if additional intervals were added,
preserving the property that not interval properly contains another), and we
have $u\in W_{v,x}\setminus U$. Intuitively, we do have that $u$ must be “more
to the left” than $v$, but it can do so, still being a neighbor of both $v$
and $x$, while going “far enough” to the left so that it can intersect the
start, rather than the end, of $v$; yet, this prevents the graph from having a
large independent set.

We complement Lemma 6.28 with the following simple observation.

######  Observation 6.29.

Let $G$ be a proper circular-arc graph with representation $f$ such that the
maximum independent set size of $G$ is at most $3$, and which admits no claw,
net, tent, $C_{4}$, $C_{5}$, $C_{6}$ and $C_{7}$ as induced subgraphs. Then,
$G$ is a proper interval graph.

###### Proof.

Targeting a contradiction, suppose that $G$ is not a proper interval graph.
Then, as $G$ admits no claw, net, tent, $C_{4}$, $C_{5}$, $C_{6}$ and $C_{7}$
as induced subgraphs, by Proposition 6.22, it must admit some hole $C_{i}$ for
$i\geq 8$ as an induced subgraph. As $C_{i}$ for any $i\geq 8$ has an
independent set of size at least $4$, so does $G$, and therefore we have
reached a contradiction. ∎

Now, it becomes easy to prove Lemma 6.27:

###### Proof of Lemma 6.27.

The algorithm works as follows. It first checks in
$\widetilde{{\mathcal{O}}}(n)$ space and polynomial time whether $G$ is
already proper interval graph by making use of the algorithm in Lemma 6.5, and
if the answer is positive, then it returns that we have a yes-instance (with
solution $\emptyset$). Notice that although the algorithm in Lemma 6.5 works
for streams, we can simulate it by iterating over the edges in $G$.

Afterwards, for every pair of vertices $v,x\in V(G)$, it computes
$W_{v,x}=\\{u\in N(v)\cap N(x):N[u]\neq N[v],N(u)\subseteq N(v)\cup N(x)\\}$
and if $|W_{v,x}|\leq k$, then:

  * •

It checks in $\widetilde{{\mathcal{O}}}(n)$ space and polynomial time whether
$G-W_{v,x}$ is a proper interval graph by making use of the algorithm in Lemma
6.5.

  * •

If the answer is positive, then it returns that we have a yes-instance (with
solution $W_{v,x}$).

At the end, having not returned a positive answer so far, the algorithm
returns “no-instance”. This completes the description of the algorithm.

Clearly, our algorithm uses $\widetilde{{\mathcal{O}}}(n)$ space and
polynomial time. We now argue that it is correct. In one direction, suppose
that $(G,k)$ is a yes-instance, and let $U$ be a solution for it. If $G$ is
already a proper interval graph, then by the correctness of the algorithm in
Lemma 6.5, our algorithm returns “yes-instance”. Else, by Observation 6.29,
$G$ has an independent set of size at least $4$. Then, Lemmas 6.26 and 6.28
imply that there exists a pair of vertices $v,x\in V(G)$ such that
$U=W_{v,x}$. By the correctness of the algorithm in Lemma 6.5, in the
iteration corresponding to this pair our algorithm should return “yes-
instance”.

In the other direction, suppose that our algorithm returns “yes-instance”. By
the correctness of the algorithm in Lemma 6.5, either $G$ is already a proper
interval graph, or our algorithm has found a subset of vertices $W$ of size at
most $k$ such that $G-W$ is a proper interval graph. So, $(G,k)$ is a yes-
instance. ∎

Finally, we are ready to prove Lemma 6.21.

###### Proof of Lemma 6.21.

The algorithm works as follows. We first consider every subset $X\subseteq
V(G)$ of size at most $6$, and for each such subset $X$, we check whether it
induces a claw, net, tent, $C_{4}$, $C_{5}$, $C_{6}$ or $C_{7}$; in case the
answer is positive, we branch on which vertex to delete from $X$ (that is, the
algorithm calls itself recursively on $(G-v,k-1)$ for each $v\in X$). After
this, we call the algorithm in Lemma 6.27 and return the same answer.

By Proposition 6.22 and because we select which vertices to delete to hit all
claws, nets, tents, $C_{4}$’s, $C_{5}$’s, $C_{6}$’s and $C_{7}$’s in an
exhaustive manner, there exists a solution to $(G,k)$ if and only if there
exists a solution to one of the instances with whom we call the algorithm in
Lemma 6.27. Moreover, by Proposition 6.24, each call is made with a proper
circular-arc graph. So, by the correctness of the algorithm in Lemma 6.27, our
algorithm is correct.

For the first part of our algorithm, notice that going over every subset
$X\subseteq V(G)$ of size at most $7$ and doing brute-force to check
isomorphism are done in $\widetilde{{\mathcal{O}}}(n)$ space. Moreover, the
total time required by this part if $7^{k}\cdot n^{{\mathcal{O}}(1)}$ (since
we branch in at most $7$ ways, and in each the parameter $k$ is decreased).
So, by the space and time complexities of the algorithm in Lemma 6.27, we
conclude that the space and time complexities of our algorithm are as stated.
∎

Based on Theorem 2.2, 6.5 and 6.21, we conclude the correctness of Theorem
6.4.

###  6.2 Block Vertex Deletion in One Pass

Recall (see Section 4.3) that a graph $G$ is a block graph if every
biconnected component of it is a clique and equivalently, if it is
$\\{D_{4},C_{\ell+4,\,\ell\geq 0}\\}$-free.

The purpose of this section is to prove the following theorem.

######  Theorem 6.30.

Block Vertex Deletion admits a $1$-pass semi-streaming algorithm with
$2^{{\mathcal{O}}(k)}\cdot n^{{\mathcal{O}}(1)}$ post-processing time.

####  6.2.1 Reconstruction Algorithm

In this section we present a somewhat more general result on the
reconstruction of block graphs. We begin by defining $t$-flow graphs and
$t$-block graphs that generalize block graphs. Next, we present a 1-pass
randomized streaming algorithm for reconstruction of $t$-flow graphs. Then,
combined with a simple recognition algorithm, based on _Perfect Elimination
Ordering_ , we obtain a 1-pass randomized streaming algorithm for
reconstruction of $t$-block graphs. As a corollary we obtain a one-pass
randomized reconstruction algorithm for block graphs.

######  Definition 6.31.

For an integer $t\geq 1$, a graph $G$ is called _$t$ -flow graph_ if and only
if for each pair of vertices $u,v\in V(G)$ either $\\{u,v\\}\in E(G)$, or
there is a subset $S$ of at most $t$ vertices such that $u$ and $v$ are
disconnected in $G-S$.

######  Definition 6.32.

For an integer $t\geq 1$, a graph $G$ is called a _$t$ -block graph_ if it is
a chordal graph where any two maximal cliques intersect in at most $t$
vertices.

Note that $1$-block graphs are the same as _block graphs_. Recall that a
_clique-tree decomposition_ of a graph $G$ is a tree-decomposition $(T,\beta)$
such that every bag $\beta(v)$ for $v\in V(T)$ induces a clique in $G$
[BLS99]. Then recall that a graph $G$ is chordal if and only if it admits a
clique-tree decomposition [BLS99]. Then following observation is immediate.

######  Observation 6.33.

A graph $G$ is a $t$-block graph if and only if it is a chordal $t$-flow
graph.

Let us begin with a reconstruction algorithm for $t$-flow graph.

######  Lemma 6.34.

Let $t\geq 1$ be an integer. The class of $t$-flow graphs has a 1-pass
randomized reconstruction algorithm, with $n^{t+{\mathcal{O}}(1)}$ post-
processing time and $\widetilde{\mathcal{O}}(n)$ space.

###### Proof.

Let ${\cal F}=\\{V_{1},V_{2},\ldots,V_{r}\\}$ be a $(n,t,2)$-separating family
over $V(G)$. Note that such a family contains $r=(t+2)^{10}\log(t+2)\log n$
vertex subsets, and it can be constructed in
${\mathcal{O}}(t^{{\mathcal{O}}(1)}n\log n)$ time and space (Corollary 4.5).
Recall that, for any pair of vertices $\\{u,v\\}$ and any $Q\subseteq V(G)$
such that $|Q|\leq t$, there is an $V_{i}\in{\cal F}$ such that $u,v\in V_{i}$
and $V_{i}\cap S=\emptyset$. For $V_{i}\in\cal F$, let $G_{i}=G[V_{i}]$. We
now describe our algorithm.

  * •

Streaming Phase. With the family $\cal F$ in hand, our algorithm computes the
following data structures in 1-pass: $(i)$ the degree $d_{G}(v)$ of every
vertex $v\in V(G)$, and $(ii)$ for each $G_{i}$, a (randomized) connectivity
sketch $D_{i}$ (Proposition 4.8). Note that $D_{i}$ is a spanning-forest of
$G_{i}$ and we can enumerate $E(D_{i})$. Further, we require
$\widetilde{\mathcal{O}}(r\cdot n)$ space to store all these data-structures.
Let $G^{\prime}$ be the graph with vertex set $V(G)$ and edge-set $\cup_{1\leq
i\leq r}E(D_{i})$, and note that we can explicitly construct $G^{\prime}$,
which requires $\widetilde{\mathcal{O}}(r\cdot n)$ space.

  * •

Reconstruction Algorithm. Next, let us describe the post-processing algorithm
to reconstruct $G$. Recall that our goal is to devise an
$n^{t+{\mathcal{O}}(1)}$-time and $\widetilde{\mathcal{O}}(n)$-space algorithm
that, given a pair of vertices $u,v\in V(G)$ as input, outputs that either
$\\{u,v\\}\in E(G)$, or $\\{u,v\\}\notin E(G)$, or else $G$ is not a $t$-flow
graph. This algorithm is as follows. We first define a graph $\widetilde{G}$
on the vertex $V(G)$, and compute the degree $d_{\widetilde{G}}(v)$ of every
vertex $v\in V(G)$. Note that this graph $\widetilde{G}$ is not explicitly
constructed. Initially, let $\widetilde{G}=G^{\prime}$. Then we consider every
distinct pair of non-adjacent vertices $x,y$ in $\widetilde{G}$. For each
vertex pair $x,y$, we determine if $\\{x,y\\}\in E(G)$ or not as follows. We
consider every subset $S$ of at most $t$ vertices such that $x,y\notin S$. For
each choice of $S$, we first determine $V_{i}\in\cal F$ such that $x,y\in
V_{i}$ and $S\cap V_{i}=\emptyset$. Then we check if $x$ and $y$ are connected
in $G_{i}=G[V_{i}]$ by using its connectivity sketch $D_{i}$. If $x$ and $y$
are connected in $G_{i}$ for every choice of $S$, then we conclude that edge
$\\{x,y\\}$ is in $\widetilde{G}$ and increment $d_{\widetilde{G}}(x)$ and
$d_{\widetilde{G}}(y)$ by 1 each. Furthermore, if the pair $x,y$ is the input
pair $u,v$, then we also remember if this particular pair forms an edge or a
non-edge. Finally, when all vertex pairs have been processed, we check if
$d_{G}(v)$ is equal to $d_{\widetilde{G}}(v)$ for all $v\in V(G)$. If not,
then we output that $G$ is not a $t$-flow graph. Otherwise, we output that $G$
is not a $t$-flow graph, and the succinct representation queries, given $u,v$,
whether or not $\\{u,v\\}\in E(\widetilde{G})$. Observe that, it is clear that
the above algorithm requires $n^{t+{\mathcal{O}}(1)}$ time and
$\widetilde{\mathcal{O}}(n)$ space.

We now argue that above reconstruction algorithm is correct. Towards this, we
first show that $E(G)\subseteq E(\widetilde{G})$, irrespective of whether or
not $G$ is a $t$-flow graph. Consider any edge $\\{x,y\\}\in E(G)$, and
consider any subset of vertices $S\subseteq V(G)$ such that $|S|\leq t$ and
$x,y\notin S$. Then, the separating-family $\cal F$ contains $V_{i}$ such that
$x,y\in V_{i}$ and $S\cap V_{i}=\emptyset$. Since $\\{x,y\\}\in E(G_{i})$ and
$D_{i}$ is a spanning forest of $G_{i}=G[V_{i}]$ (from the connectivity sketch
by Proposition 4.8), we have that $x,y$ must in the same connected component
of $D_{i}$. Hence, $x,y$ are connected in $G_{i}$. Since this holds for every
choice of $S$, it follows that $\\{x,y\\}\in E(\widetilde{G})$. By applying
this argument to every edge in $E(G)$, we obtain that $E(G)\subseteq
E(\widetilde{G})$.

Next, let us argue that $E(\widetilde{G})\subseteq E(G)$, assuming that $G$ is
a $t$-flow graph. Towards this, consider an edge $\\{x,y\\}\in
E(\widetilde{G})$. As $G^{\prime}$ is a subgraph of both $G$ and
$\widetilde{G}$, if $\\{x,y\\}\in E(G^{\prime})$ then $\\{x,y\\}\in E(G)$.
Otherwise, $\\{x,y\\}\notin E(G^{\prime})$. Then, for every $S\subseteq V(G)$
such that $|S|\leq t$ and $x,y\notin S$, consider $V_{i}\in\cal F$ such that
$x,y\in V_{i}$ and $S\cap V_{i}=\emptyset$. Observe that, as $\\{x,y\\}\in
E(\widetilde{G})$, there is a path in $G_{i}=G[V_{i}]$ from $x$ to $y$. This
path is also present in the graph $G^{\prime}-S$. Since this holds for every
choice of $S$, the minimum-separator of $x$ and $y$ in $G^{\prime}$ has $t+1$
or more vertices. Therefore, assuming that $G$ is a $t$-flow graph,
$\\{x,y\\}\in E(G)$. Finally, this argument holds for every edge in
$\widetilde{G}$, and hence $E(\widetilde{G})\subseteq E(G)$. Combined with the
above we obtain that $E(G)=E(\widetilde{G})$, when ever $G$ is a $t$-flow
graph.

Finally, let us argue that our reconstruction algorithm is correct. In one
direction let $G$ be a $t$-flow graph. Then, as $E(G)=E(\widetilde{G})$, we
have $d_{G}(v)=d_{\widetilde{G}}(v)$ for every vertex $v\in V(G)$. Hence the
reconstruction algorithm correctly concludes that $G$ is a $t$-flow graph (and
the succinct representation is correct). In the reverse direction, suppose
that the algorithm concludes that $G$ is a $t$-flow graph. This means that
$d_{G}(v)=d_{\widetilde{G}}(v)$ for every vertex $v\in V(G)$. We give a proof
by contradiction, and let us assume that $G$ is not a $t$-flow graph. This
means there exists $u,v\in V(G)$ such that $\\{u,v\\}\notin E(G)$ and for
every $S\subseteq V(G)$, $|S|\leq t$, $u$ and $v$ are connected in $G-S$. Then
$\\{u,v\\}\in E(\widetilde{G})$, and as $E(G)\subseteq E(\widetilde{G})$, it
must be the case that $d_{\widetilde{G}}(v)\geq d_{G}(v)+1$. But this is a
contradiction since $d_{G}(v)=d_{\widetilde{G}}(v)$. Therefore, $G$ must be a
$t$-flow graph. This concludes the proof of this lemma. ∎

We are now ready to present a reconstruction algorithm for $t$-block graphs.
Towards this we require a few results about chordal graphs.

######  Definition 6.35.

A _perfect elimination ordering_ of a graph $G$ is an ordering
$v_{1},v_{2},\ldots v_{n}$ of the vertex set $V(G)$ such that for any
$i\in\\{1,2,\ldots n\\}$, $N_{G_{i}}(v_{i})$ is a clique in the graph
$G_{i}=G-\\{v_{1},v_{2},\ldots v_{i-1}\\}$.

The following is a well-known characterization of chordal graph. Recall that a
vertex $v$ in a graph $G$ is called _simplician_ if $N(v)$ induces a clique in
$G$.

######  Proposition 6.36 ([BLS99]).

A graph $G$ is a chordal graph if and only if it has a perfect elimination
ordering. Furthermore, given a chordal graph $G$ such an ordering can be
obtained (greedily) by repeatedly picking a simplicial vertex in the current
graph and deleting it.

######  Lemma 6.37.

Let $t\geq 1$ be an integer. The class of $t$-block graphs has a 1-pass
randomized reconstruction algorithm, with $n^{t+{\mathcal{O}}(1)}$ post-
processing time and $\widetilde{\mathcal{O}}(n)$ space.

###### Proof.

Let $G$ denote the input graph. We begin by applying the reconstruction
algorithm for $t$-flow graph from Lemma 6.34 to $G$. If it concludes that $G$
is not a $t$-flow graph, then we output that $G$ is not a $t$-block graph.
Otherwise, $G$ is a $t$-flow graph we obtain a succinct representation of $G$.
Now ,our goal is to test if $G$ is also a chordal graph. Here we apply the
algorithm of Proposition 6.36, which requires that we repeatedly pick a
simplicial vertex in the current graph and removing it. Observe that it is
enough to describe a $\widetilde{\mathcal{O}}(n)$ algorithm to find a
simplicial vertex in the current remaining graph. This algorithm is as
follows. We examine the vertices one by one, and for each vertex $v$ we first
enumerate its neighborhood $N(v)$, and then test if every pair of vertices in
it forms an edge or not. If so, we conclude that $v$ is a simplicial vertex.
Otherwise, $v$ is not a simplicial vertex. It is clear that this runs in
$n^{{\mathcal{O}}(1)}$ time and $\widetilde{\mathcal{O}}(n)$ space.

Our algorithm tests if the $t$-flow graph is chordal by attempting to compute
a perfect elimination ordering of it. If it succeeds, then we output that $G$
is a $t$-block graph, and also output its succinct representation from Lemma
6.34. Otherwise, we output that $G$ is not a $t$-block graph. To argue the
correctness of this algorithm, observe that if the algorithm does succeed in
computing a perfect elimination ordering of $G$, then it is a chordal by
Proposition 6.36. Hence, $G$ is a $t$-block graph by Observation 6.33. In the
reverse direction, if $G$ is a $t$-block graph, then it is a chordal $t$-flow
graph. Hence, by Proposition 6.36, our algorithm produces a perfect
elimination ordering of $G$. Hence it outputs that $G$ is a $t$-block graph.
This concludes the proof of this lemma. ∎

Let us remark that the above lemma, which describes a linear-space algorithm
to recognize whether a given $t$-flow graph is also chordal, crucially depends
on the fact that the $t$-flow graphs have a linear-space reconstruction
algorithm. In contrast, for general graphs we obtain a lower-bound
$\Omega(n^{2})$ for recognizing chordal graphs (see Theorem 9.2).

####  6.2.2 Post-processing Algorithm

In this section we present the post-processing algorithm for Block Vertex
Deletion (BVD). This algorithm takes as input a graph $G$ and an integer $k$,
and outputs a vertex subset $S\subseteq V(G)$ such that $G-S$ is a block
graph, if one exists. This algorithm uses $\widetilde{\mathcal{O}}(n)$ space,
and in particular we assume that the input graph $G$ is presented in read-only
memory. Our algorithm follows the approach of [AKLS16] (to obtain the fastest
possible algorithm) with suitable modifications to use only
$\widetilde{\mathcal{O}}(n)$ space.

Let us first consider the case when the input graph $G$ is
$\\{C_{4},D_{4}\\}$-free. Then, we have the following proposition from
[AKLS16].

######  Proposition 6.38 (Lemma 6 [AKLS16]).

Let $G$ be a graph that is $\\{C_{4},D_{4}\\}$-free. Then $G$ has at most
$n^{2}$ maximal cliques, and any two maximal cliques intersect in at most one
vertex.

Given a graph $G$ that is $C_{4}$ and $D_{4}$ free, consider the _auxiliary
graph_ $H$ constructed from $G$ as follows. $H$ is a bipartite graph with
vertex set $V(H)=V(G)\cup V_{\cal C}$ where $\cal C$ is the collection of all
maximal cliques in $G$ and $V_{\cal C}$ is a collection of vertices, with one
vertex $v_{C}$ for each element $C$ of $\cal C$. The edge set $E(H)$ consists
of all pairs $(v,v_{C})$, where $v\in V(G)$, $v_{C}\in V_{\cal C}$ and
$C\in\cal C$, such that the vertex $v$ belongs to the clique $C$.

######  Proposition 6.39 (Lemma 7 [AKLS16]).

Let $G$ be a $\\{C_{4},D_{4}\\}$-free graph, and let $H$ be the auxiliary
graph of $G$. Then, $S\subseteq V(G)$ is a block vertex deletion set of $G$ if
and only if $S$ is a feedback vertex set of $H$.

Agrawal, Kolay, Lokshtanov and Saurabh [AKLS16] explicitly constructed $H$ and
used an algorithm for Feedback Vertex Set on $H$ (while using weights to
ensure that only vertices from $V(G)$ are picked). We cannot do this, since
just storing the vertex set of $H$ takes ${\mathcal{O}}(n^{2})$ space. So, we
have a more difficult task of resolving the Feedback Vertex Set problem on $H$
without even constructing its vertex set explicitly.

For our algorithm, we require the following subroutine that counts the number
of maximal cliques in $G$ that contain a specified vertex $v$.

######  Lemma 6.40.

Let $G$ be a graph and let $v$ be any vertex. Then there is an algorithm that
counts the number of maximal cliques in $G$ that contain $v$ using
$\widetilde{\mathcal{O}}(n\cdot\log\alpha)$ space in time $\alpha\cdot
n^{{\mathcal{O}}(1)}$, where $\alpha$ denotes the number of maximal cliques in
$G$ that contain $v$.

###### Proof.

We present the algorithm in the following pseudo-code. The input is a graph
$G$ and a vertex $v$. We assume that the vertices of $G$ are numbered from $1$
to $n$ in some arbitrary order.

Input: Graph $G$ on $n$ vertices, vertex $v$

Output: Number of maximal cliques in $G$ containing vertex $v$

1 // GLOBAL VARIABLES

2 $\sigma\leftarrow$ an arbitrary ordering of the vertices in $V(G)$ where
$\sigma(v)=1$

3 // bitvector of the current partial maximal clique

4 $X\leftarrow$ bit-vector of length $n$ initialized to all $0$

5 $X[1]\leftarrow 1$ // Add $v$ to $X$

6 Function  _Count-X-Cliques(__)_ :

7 $Stop\leftarrow\sf{False}$

8 $uPrev\leftarrow 0$

9 $numCliques\leftarrow 0$

10 while  _not Stop_ do

11 $u\leftarrow$ the common neighbor of $X$ in $V(G)\setminus X$ minimizing
$\sigma(u)$ such that $\sigma(u)>\sigma(uPrev)$ and
$\sigma(u)>\sigma(w)~{}\forall w\in X$

12 if  _$u=\sf{NULL}$_ then

13 if  _$numCliques=0$_ then

14 // then the input $X$ cannot be extended to a larger clique

15 $numCliques\leftarrow 1$

16

17 end if

18 $Stop\leftarrow\sf{True}$

19

20 else

21 $uPrev\leftarrow u$

22 $X[\sigma(u)]\leftarrow 1$ // Extend $X$ by the vertex $u$

23 // Recursively count maximal cliques containing $X$ extended by $u$

24 $uCliques\leftarrow$ Count-X-Cliques(__)

25 $numCliques\leftarrow numCliques+uCliques$

26

27 $X[\sigma(u)]\leftarrow 0$ // Restore $X$

28

29 end if

30

31 end while

32 return _$numCliques$_

33

Algorithm 1 Counting the number of Maximal Cliques in $G$ containing vertex
$v$

The algorithm is implemented a simple branching algorithm. We start by
defining an arbitrary ordering $\sigma$ of the vertices in $V(G)$ such that
$v$ is the first vertex; note that this requires ${\mathcal{O}}(n)$ space and
$n^{{\mathcal{O}}(1)}$ time. We then define a global length-$n$ bit-vector $X$
that contains the vertices of the current (partial) maximal clique. The
algorithm is implemented via the function Count-X-Cliques() that makes
recursive calls at each branching. When this function is called, it iterates
over all the common neighbors $u$ of $X$ in $V(G)\setminus X$ such that
$\sigma(u)>\sigma(w)~{}\forall w\in X$, one by one from smallest to largest.
For each $u$, it counts the number of maximal cliques containing
$X\cup\\{u\\}$. It adds up all these numbers and returns the sum as the number
of maximal cliques in $G$ containing $X$. Observe that, to determine the next
common neighbor of $X$, it only needs to remember the previous common neighbor
and check all larger vertices in $V(G)\setminus X$ one by one. Note that this
can be done in $n^{{\mathcal{O}}(1)}$ time and ${\mathcal{O}}(\log n)$ space.
If no common neighbor of $X$ exists, then $X$ itself is a maximal clique and
we return $1$. It is clear that every maximal clique in $G$ that contains $v$
is generated and counted once, in the lexicographic order induced by $\sigma$
on subsets of $V(G)$. Indeed, for any two common neighbors $u,u^{\prime}$ of
$X$ such that $\sigma(u)<\sigma(u^{\prime})$, the maximal cliques that
contains both vertices are only generated in the branch for $X\cup u$ (and not
in the branch for $X\cup u^{\prime}$). Next, we show the claimed bounds on
space and time.

Observe that each call to the function Count-X-Cliques() requires only a
constant number of local-variables, that each require at most $\log\alpha$
bits to store. Further, the depth of recursion is upper-bounded by $n$ since
each recursive call sets a $0$-bit of $X$ to $1$. Hence the total space used
by the algorithm is $\widetilde{\mathcal{O}}(n\cdot\log\alpha)$. Finally,
observe that after any $n$ successive calls made to Count-X-Cliques(), we must
encounter a maximal clique of $G$ that contains $v$, and each call internally
requires $n^{{\mathcal{O}}(1)}$ time. Hence the total time required by this
algorithm is $\alpha\cdot n^{{\mathcal{O}}(1)}$. ∎

As a corollary of Proposition 6.38 and Lemma 6.40, we obtain the following.

######  Lemma 6.41.

Let $G$ be a graph that is $\\{C_{4},D_{4}\\}$-free. Then in
$n^{{\mathcal{O}}(1)}$ time and $\widetilde{\mathcal{O}}(n)$ space, we can
count and store the number of maximal cliques in $G$ that contain $v$ for
every vertex $v\in V(G)$.

Next, we present a few lemmas and reduction rules that will be useful for our
algorithm.

######  Lemma 6.42.

Let $G$ be a graph that is $\\{C_{4},D_{4}\\}$-free. Then the following
statements hold.

  * •

Let $v\in V(G)$ be a vertex that lies in only one maximal clique of $G$. Then,
$S\subseteq V(G)$ is a block vertex deletion set of $G$ if and only if it is a
block vertex deletion set for $G-v$.

  * •

Let $G^{\prime}$ be the graph obtained from $G$ by iteratively removing all
vertices that lie in only one maximal clique. Then, $G^{\prime}$ can be
computed in $n^{{\mathcal{O}}(1)}$ time and using $\widetilde{\mathcal{O}}(n)$
space. Moreover, if $G$ is a block-graph then $G^{\prime}$ is the empty graph.

  * •

Let $H^{\prime}$ be the auxiliary graph of $G^{\prime}$. Then, every vertex of
$H^{\prime}$ has at least two distinct neighbors.

###### Proof.

Consider the first statement. One direction is clear—if $S$ is a solution to
$G$, then it is also a solution to $G-v$. In the reverse direction, consider
the block graph $(G-v)-S$. Then observe that, adding back $v$ to $(G-v)-S$
results in a block graph as well, since the neighborhood of $v$ in $G$ is a
clique. For the second statement, to compute the graph $G^{\prime}$, we find a
vertex $v$ in $G$ that lies in only one maximal clique. Here we apply Lemma
6.40, and it is clear that the required space and time bounds are obtained.
Next, if $G$ were a block graph then it has a perfect elimination ordering
(see Definition 6.35 and Proposition 6.36) that is obtained by greedily
removing simplicial vertices from $G$ one by one. Hence, iteratively removing
all vertices of $G$ that lie in only one maximal clique results in an empty
graph. Finally, for the third statement observe that, as each vertex in $G$ is
part of two distinct maximal cliques, in $H$ it has at least two neighbors.
Similarly, any maximal clique in $G$ contains at least two vertices, and hence
it has at least two neighbors in $H$. ∎

######  Lemma 6.43.

Let $G$ be a $\\{C_{4},D_{4}\\}$-free graph such that every vertex of $G$ lies
in at least two maximal cliques. Further, suppose that there is no connected
component of $G$ that is just a cycle. Let $H$ be the auxiliary graph of $G$.

  * (i)

In $n^{{\mathcal{O}}(1)}$ time and ${\mathcal{O}}(n)$ space, we can identify
and mark each vertex $v\in V(G)$ such that $d_{G}(v)=2$ and
$d_{G}(u)=d_{G}(u^{\prime})=2$ where $u,u^{\prime}$ are the two neighbors of
$v$ in $G$.

  * (ii)

Let $P$ be a maximal path in $H$ such that all of its vertices are of degree 2
in $H$, $P$ is not a cycle and the end-vertices are from $V(G)$. Then all
internal vertices of $P$ that lie in $V(G)$ are marked, and the two end-
vertices are unmarked.

  * (iii)

If $v$ is a marked vertex, then there is a maximal path $P$ in $H$ such that
all vertices of $P$ are of degree $2$, $P$ is not a cycle, the endpoints of
$P$ lie in $V(G)$ and they are unmarked.

  * (iv)

Let $S\subseteq V(G)$ be a feedback vertex set of $H$. Then, there exists
another feedback vertex set $S^{\prime}\subseteq V(G)$ whose vertices are all
unmarked and such that $|S^{\prime}|\leq|S|$.

###### Proof.

For $(i)$, we simply enumerate each vertex $v$ of degree $2$ in $G$, and then
test if the two neighbors of $v$ are also of degree $2$. Here we note that
every vertex of $G$ lies in at least 2 maximal cliques, and therefore there
are no vertices of degree 1 in $G$. After this marking procedure, observe that
if $Q$ is a maximal path in $G$ such that every vertex of $Q$ has degree $2$
in $G$, then all internal vertices of $Q$ are marked, while the two endpoints
are unmarked. Since $V(G)\subseteq V(H)$, we can carry over the marking in $G$
to the auxiliary graph $H$.

For $(ii)$, let is let $u,v$ be the two endpoints of $P$ and note that $u,v\in
V(G)$. Let $u^{\prime}$ and $u^{\prime\prime}$ be the neighbors of $u$ in
$V(H)\setminus V(P)$ and $V(P)$, respectively. Note that
$u^{\prime},u^{\prime\prime}\in V_{\cal C}$ correspond to maximal cliques of
$G$. Consider $u^{\prime}$ and let $K\in{\cal C}$ be the maximal clique of $G$
corresponding to it. Note that we have two cases: either the $K$ contains at
least 3 vertices, or only 2 vertices. In the first case $u\in V(K)$ has at
least $3$ neighbors in $G$, 2 in $V(K)$ and another in the maximal clique
corresponding to $u^{\prime\prime}$. Hence $u$ is unmarked (indeed, we can
further argue that $P$ must exclude $u$). In the second case $u^{\prime}$ is
of degree 2 in $H$, and it has a neighbor $x\in V(G)$ in $H$. Then $u$ and $x$
are adjacent in $G$ (forming the clique $C$ corresponding to $u^{\prime}$).
However, as $P$ is maximal and $x\notin V(P)$ it must be the case that
$d_{H}(x)\geq 3$. Then it is clear that $d_{G}(x)\geq 3$. Hence, in the graph
$G$, while $d_{G}(v)=2$, one of it’s neighbors $x$ has degree at least $3$.
Therefore, once again, $u$ is not marked. Similar arguments apply to the
vertex $v$, and hence $u,v$ are not marked. Now consider any internal vertex
$w$ of $P$ that lies in $V(G)$, and observe that $d_{G}(w)=2$ and for the two
neighbors $w^{\prime},w^{\prime\prime}$ of $w$ in $G$,
$d_{G}(w^{\prime})=d_{G}(w^{\prime\prime})=2$. Hence, every internal vertex of
$P$ that lie in $V(G)$ are marked.

For $(iii)$, recall that $v$ is marked in $G$, only if $d_{G}(v)=2$ and the
two neighbors of $v$ in $G$, $u,w$ are also of degree $2$ in $G$. Then observe
that, corresponding to the path $u-v-w$ in $G$, we have a path $P^{\prime}$ in
$H$ that consists of $u-x-v-y-w$ where $x,y\in V_{\cal C}$ correspond to the
maximal cliques $\\{u,v\\}$ and $(v,w)$ of $G$, respectively. Next consider a
maximal path $P^{\prime\prime}$ of $H$ that contains $P^{\prime}$ such that
all vertices of $P^{\prime\prime}$ are of degree $2$ in $H$. If
$P^{\prime\prime}$ is a cycle of $H$ then by construction it corresponds to a
cycle $C$ in $G$ whose vertices have degree $2$ in $G$. This means that $C$ is
a connected component of $G$ that is just a cycle, which is forbidden by the
premise of the lemma. Hence $P^{\prime\prime}$ is not a cycle in $H$, and it
contains a maximal sub-path $P$ whose both-endpoints are in $V(G)$. By $(ii)$,
the two endpoints of $P$ are unmarked.

For $(iv)$, first observe that any vertex $v\in V(G)\subseteq V(H)$ such that
$d_{H}(v)\geq 3$ must satisfy $d_{G}(v)\geq 3$, and hence it is unmarked.
Next, observe that as $G$ has no connected component that is an isolated
cycle, $H$ has no cycle whose all vertices are of degree $2$ in $H$.
Therefore, any cycle $C$ of $H$ can be partitioned into maximal paths whose
vertices are of degree 2 in $H$ and the remaining vertices that have degree 3
or more. Each such maximal path $P^{\prime}$ contains another maximal path
$P^{\prime\prime}$ such that the endpoints of $P^{\prime\prime}$ lie in
$V(G)$. By $(ii)$, the endpoints of $P^{\prime\prime}$ are unmarked. Now
consider the feedback vertex set $S\subseteq V(G)$ of $H$ and consider any
marked vertex $w\in S$. By $(iii)$, $w$ lies in a maximal path $P$ of $H$ such
that all vertices of $P$ are of degree 2, $P$ is not a cycle, the end-vertices
of $P$ lie in $V(G)$ and they are unmarked. Since any cycle containing $w$
must contain both $u$ and $v$, it is clear $(S\setminus\\{w\\})\cup\\{u\\}$ is
another feedback vertex set of $H$ of same or smaller size. Therefore, by
replacing every marked vertex in $S$, we can obtain a feedback vertex set
$S^{\prime}$ that contains only unmarked vertices and $|S^{\prime}|\leq|S|$.
This concludes the proof. ∎

Let us now describe our algorithm for Block Vertex Deletion on the class of
$\\{C_{4},D_{4}\\}$-free graphs.

######  Lemma 6.44.

Let $G$ be a $\\{C_{4},D_{4}\\}$-free graph and let $k$ be an integer. Then
there is a randomized algorithm that can decide if there is a block vertex
deletion set of cardinality at most $k$ in $G$, and compute one if it exists.
This algorithm runs in $17^{k}n^{{\mathcal{O}}(1)}$ time, uses
$\widetilde{\mathcal{O}}(nk)$ space and succeeds with constant probability
$>2/3$.

###### Proof.

Our algorithm is based on Proposition 6.39 and a simple randomized branching
algorithm for Feedback Vertex Set ([BBYG00]; see also Chapter 5 in [CFK+15]).
Let $H$ be the auxiliary graph of $G$, and recall that we seek a feedback
vertex set of cardinality at most $k$ in $H$ that is a subset of $V(G)$. Note
that, as the number of maximal cliques in $G$ could be ${\mathcal{O}}(n^{2})$,
it is not possible for us to explicitly construct the graph $H$. Therefore, we
must extract the required information about $H$ from $G$ in
$\widetilde{\mathcal{O}}(n)$ space and $n^{{\mathcal{O}}(1)}$ time.

To simplify the algorithm, let us immediately deal with a special case.
Suppose that $G$ contains a connected component that is an isolated cycle $C$
of length $4$ or more. Then, observe that corresponding to $C$ we obtain a
connected component $C^{\prime}$ of $H$ that is also a cycle whose vertices
correspond to $V(C)$ and $E(C)$. For such cycles, we simply pick an arbitrary
vertex of $C$ into our solution, decrease $k$ by 1, and remove the rest of $C$
from $G$. The optimality and correctness of this step is clear. When this
reduction is not applicable, we can assume that there is no connected
component of $G$ that is just a cycle. Hence, there is a vertex of degree at
least 3 in every connected component of $G$.

The randomized branching algorithm for feedback vertex set [CFK+15], first
applies some simple reduction rules to ensure that every vertex has at least
$3$ distinct neighbors. Then, it can be shown that if $S$ is any feedback
vertex set, then at least half the edges have an endpoint in $S$. In our
setting, where space is bounded, applying these reduction rules becomes a
little more challenging. Towards this, we first apply Lemma 6.42 and Lemma
6.43, which can be done in $\widetilde{\mathcal{O}}(n)$ space and
$n^{{\mathcal{O}}(1)}$ time. Further, Lemma 6.43 ends up marking a subset of
vertices of $V(G)\subseteq V(H)$. Then, we prove the following claim.

######  Claim 6.45.

Let $S\subseteq V(G)$ is a feedback vertex set of $H$ that contains only
unmarked vertices, and let $\widetilde{E}\subseteq E(H)$ be the collection of
all those edges that have an unmarked endpoint. Then if we pick an edge $e\in
F$ uniformly at random, then with probability at least $1/17$, one endpoint of
$e$ lies in $S$.

To prove this claim, observe that by Lemma 6.42, every vertex in $H$ has two
distinct neighbors. Moreover, by Lemma 6.43, if $P$ is a maximal path made of
degree-2 vertices in $H$, then all vertices of $P\cap V(G)$ except perhaps the
two end-vertices of $P$ and their immediate neighbors in $P$ are marked. Let
us consider every vertex in $V_{\cal C}\subseteq V(H)$ of degree-2 in $H$
whose both neighbors from $V(G)$ have been marked, as another marked vertex.
Then for every maximal path $P$ of degree-2 vertices in $H$, all vertices are
marked except for at most 6 vertices, the two endpoints and the 4 vertices in
$P$ that closest to them. Note that, we don’t need to explicitly mark these
vertices, but only require them for analysis. Also note that if $v\in V(H)$ is
marked then $d_{H}(v)=2$. The proof of this claim, now easily follows from
Lemma 5.1 of [CFK+15] that states that when graph $X$ has minimum degree 3,
and $Y$ is any feedback vertex set of $X$, then a randomly sampled edge of $X$
has an endpoint in $Y$ with probability at least $1/2$.

Indeed, consider the graph $H^{\prime}$ obtained by contracting each edge
whose both endpoints are marked vertices in $H$ one by one, until every edge
has at least one unmarked endpoint. Observe that there is a bijection between
the edges of $H^{\prime}$ and the edges of $H$ with at least one unmarked
endpoint. Further observe that any maximal path of degree-2 vertices of
$H^{\prime}$ have length at most $7$. Moreover, any feedback vertex set of
$H^{\prime}$ is a feedback vertex set of $H$, and any feedback vertex set of
$H$ that contains only unmarked vertices is a feedback vertex set of $G$. Now
consider a feedback vertex set $X$ of $H$, and consider the forest
$H^{\prime}-X$. Let $Y=V(H^{\prime})\setminus X$, and we claim that $|Y|\leq
16|E(X,Y)|$ where $E(X,Y)$ denotes the edges of $H^{\prime}$ with one endpoint
in $X$ and the other in $Y$. Let $V_{1},V_{2},V_{3}$ denote the subsets of
vertices of $H^{\prime}-X$ of degree $1$, $2$ and $\geq 3$ respectively. Note
that $|V_{3}|\leq|V_{1}|$, by a standard result on forests. And, as the
minimum degree of $H^{\prime}$ is two, each vertex in $V_{1}$ has a distinct
edge in $H^{\prime}$ whose other endpoint lies in $X$, i.e.
$|V_{1}|\leq|E(X,Y)|$. Hence, $|V_{3}|+|V_{1}|\leq 2|E(X,Y)|$. Next, to bound
$|V_{2}|$ consider the forest $H^{\prime\prime}$ obtained from $H^{\prime}-X$,
by contracting every vertex of degree $2$. Then
$|E(H^{\prime\prime})|\leq|V_{3}|+|V_{1}|-1$. Observe that each edge of
$H^{\prime\prime}$ corresponds to a maximal path of degree 2 vertices in
$H^{\prime}-Y$ whose length is upper-bounded by $7$, and these paths partition
$V_{2}$. Hence $|V_{2}|\leq 7|E(H^{\prime\prime})|\leq
7(|V_{3}|+|V_{1}|-1)\leq 14|E(X,Y)|$, and therefore we conclude that $|Y|\leq
16|E(X,Y)|$. Then, we conclude that $|E(H^{\prime}-X)|\leq|Y|\leq 16|E(X,Y)|$.
Finally, let $E(X)$ be the set of edges with at least one endpoint in $X$ and
note that $|E(X)|\geq|E(X,Y)|\geq|V_{1}|$. And let $E(Y)$ be the set of edges
with both endpoints in $Y$; $|E(Y)|=|E(H^{\prime}-X)|\leq 16|E(X,Y)|$.
Therefore the probability that an edge that is sampled uniformly at random
from $E(H^{\prime})$ has an endpoint in $X$ is at least $1/17$.

Following this claim, and Proposition 6.39, a simple randomized algorithm
could be as follows: sample an edge $e\in\widetilde{E}$, then select the
endpoint $v$ of $e$ from $V(G)$ into the solution, and then solve $(H-v,k-1)$.
This algorithm would produce a solution in polynomial time with probability
$1/17^{k}$. Unfortunately, as $H$ is not explicitly constructed, we cannot
easily sample edge of $\widetilde{E}$. However, observe the following. Let
$V^{\prime}\subseteq V(G)$ be all the unmarked vertices. The probability that
a vertex $v\in V^{\prime}$ is selected by the above random process is equal to
$d_{H}(v)/|\widetilde{E}|$. Here we rely on the fact that if $v$ is an
unmarked vertex in $H$, then all edges incident on $v$ are present in
$\widetilde{E}$. Hence, if we sample a vertex $v\in V(G)$ with probability
$d_{H}(v)/|\widetilde{E}|$, then with probability $1/17$, $v\in S$. To
implement this sampling process, we only need to know the degrees of the
vertices in $V(G)$ and as $H$ is bipartite we have $|\widetilde{E}|=\sum_{v\in
V(G)~{}:~{}v\text{ is unmarked}}d_{H}(v)$. These values can obtained from
Lemma 6.41 in $n^{{\mathcal{O}}(1))}$ time and $\widetilde{\mathcal{O}}(n)$
space. After sampling, $v$ we can recursively solve the instance $(H-v,k-1)$.
Here the base case of this algorithm where $k=0$ is handled by Lemma 6.42. It
allows us to test if $G$ is a block graph in polynomial time and
$\widetilde{\mathcal{O}}(n)$ space. If this test fails, we output that there
is no solution, or else there is a solution of size $0$ for $G$. Observe that
this leads to a polynomial time algorithm that requires
$\widetilde{\mathcal{O}}(nk)$ space and outputs a feedback vertex set
$S\subseteq V(G)$ of size $k$ with probability at least $1/17^{k}$. By
repeating this algorithm ${\mathcal{O}}(17^{k})$ times we obtain a simple
randomized algorithm for Block Vertex Deletion in $\\{C_{4},D_{4}\\}$-free
graphs that $17^{k}\cdot n^{{\mathcal{O}}(1)}$ time and uses
$\widetilde{\mathcal{O}}(nk)$ space. By standard arguments, it follows that
this algorithm succeeds with probability $>2/3$ (which can be boosted to any
constant by further repetitions). ∎

Finally, we extend the above lemma to an algorithm for Block Vertex Deletion.

######  Lemma 6.46.

Block Vertex Deletion admits a randomized FPT-algorithm that runs in time
$17^{k}n^{{\mathcal{O}}(1)}$ time $\widetilde{\mathcal{O}}(nk)$ space, where
$k$ is the parameter denoting the solution size. It outputs a solution with
constant probability.

###### Proof.

Let $G$ be the input graph. Our algorithm is implemented in two stages. In the
first stage, we have a simple branching algorithm that finds $C_{4}$ or a
$D_{4}$ in $G$ and branches on which of it’s vertices lies in a solution of
size $k$. This process can be represented via a branching tree of depth $k$,
where each node has four child-nodes. At the leaf of each node, either we
obtain a subgraph $G^{\prime}$ that is $\\{C_{4},D_{4}\\}$-free, or conclude
that the choices made to arrive at that node does nnt lead to a solution of
size $k$. Note that this stage of the algorithm can be implemented in time
${\mathcal{O}}(4^{k}n^{4})$ and space ${\mathcal{O}}(k\log n)$. In the next
stage, we apply Lemma 6.44 to the graph $G^{\prime}$ along with the parameter
$k^{\prime}$. Here $k^{\prime}=k~{}-($the number of vertices selected in Stage
1$)$. It follows that Stage $2$ runs in time $17^{k}n^{{\mathcal{O}}(1)}$ and
$\widetilde{\mathcal{O}}(nk)$ space, and succeeds with constant probability.
Hence, we obtain the required algorithm for Block Vertex Deletion. ∎

From Theorem 2.2, Lemma 6.37 and Lemma 6.46 we obtain Theorem 6.30. Here we
also rely on the fact that the class of block graphs are hereditary.

##  7 Cut Problems

Our starting point is the sampling primitive of Guha, McGregor and Tench
[GMT15] (with appropriately set parameters). The main idea here is to sample
roughly $\widetilde{\cal O}(k^{{\cal O}(1)})$ vertex subsets of the input
graph so that with good probability, for every set $S\subseteq V(G)$ that is
disjoint from some forbidden substructure (of potentially unbounded size) in
$G$, there is a set of sampled subgraphs that are disjoint from $S$ and whose
union also contains a forbidden substructure for the problem concerned. This
allows us to produce $\widetilde{\cal O}(k^{{\cal O}(1)}n)$ subgraphs that can
still certify when a vertex set is not a solution for the problem at hand.
However, this is only the first part of our approach and problem-specific
steps need to be taken following this.

Sampling Primitive ($V(G),n,k,q$)888We assume that $n,k,q\geq 1$.: Sample
$\ell=64qk^{3}\ln n$ vertex subsets $V_{1},\dots,V_{\ell}$ of $G$. Each
$V_{i}$ is sampled by independently picking each vertex of $G$ with
probability $1/2k$. Let $G_{i}=G[V_{i}]$ for every $i\in[\ell]$, let ${\cal
L}=\\{G_{1},\dots,G_{\ell}\\}$ and for every $S\subseteq V(G)$, let ${\cal
L}_{S}=\\{G_{i}\in{\cal L}\mid V(G_{i})\cap S=\emptyset\\}$.

We now summarize a useful property of the sampling primitive, which is
required for the correctness of some of our algorithms.

######  Lemma 7.1 (Properties of Sampling Primitive $(V(G),n,k,q)$).

Fix a set $\\{{\mathcal{C}}_{1},\dots,{\mathcal{C}}_{r}\\}$ where $r\leq
n^{q}$ and each ${\mathcal{C}}_{i}$ is a set of subgraphs of $G$. With
probability at least $1-2/n$, the following event occurs: For every $k$-vertex
set $S\in V(G)$ and for every ${\mathcal{C}}_{i}$, if $S$ is disjoint from
some $C\in{\mathcal{C}}_{i}$, then $\bigcup_{G\in{\cal L}_{S}}G$ contains some
$C^{\prime}\in{\mathcal{C}}_{i}$.

###### Proof.

Let ${\mathcal{S}}_{k}$ denote the set of all $k$-vertex sets in $G$. For
every fixed $S\in{\mathcal{S}}_{k}$, the expected number of sampled vertex
subsets disjoint from $S$,

$\mathrm{\bf
E}[~{}|{\mathcal{L}}_{S}|~{}]=(1-1/2k)^{k}\cdot\ell\geq\ell/4=16qk^{3}\ln n.$

Using standard Chernoff bounds we get:

$\mathrm{Prob}[~{}|{\cal L}_{S}|<8qk^{3}\ln n~{}]\leq e^{2qk^{3}\ln n}\leq
1/n^{2k}.$

Let ${\bf Y}$ denote the event that for every $S\in{\mathcal{S}}_{k}$, $|{\cal
L}_{S}|\geq 8qk^{3}\ln n$. Taking the union bound over all
$S\in{\mathcal{S}}_{k}$, we conclude that:

$\mathrm{Prob}[~{}~{}\exists S\in{\mathcal{S}}_{k}:|{\cal L}_{S}|<8qk^{3}\ln
n~{}]=\mathrm{Prob}[~{}\vbox{\hrule height=0.5pt\kern
1.07639pt\hbox{\kern-1.49994pt$\bf Y$\kern-1.00006pt}}~{}]\leq 1/n^{k}.$

We say that $S\in{\mathcal{S}}_{k}$ is good if for every $i\in[r]$ at least
one element of ${\mathcal{C}}_{i}$ disjoint from $S$ is contained in the union
of the graphs in ${\cal L}_{S}$. We say that $S\in{\mathcal{S}}_{k}$ is bad
otherwise. Let $\bf X$ denote the event that every $S\in{\mathcal{S}}_{k}$ is
good. Recall that:

$\mathrm{Prob}[~{}\vbox{\hrule height=0.5pt\kern
1.07639pt\hbox{\kern-1.49994pt$\bf
X$\kern-1.00006pt}}~{}]\leq\mathrm{Prob}[~{}\vbox{\hrule height=0.5pt\kern
1.07639pt\hbox{\kern-1.49994pt$\bf
Y$\kern-1.00006pt}}~{}]+\mathrm{Prob}[~{}\vbox{\hrule height=0.5pt\kern
1.07639pt\hbox{\kern-1.49994pt${\bf X}$\kern-1.00006pt}}\mid{\bf Y}~{}].$

Now, we observe the following for a fixed $S\in{\mathcal{S}}_{k}$:

$\mathrm{Prob}[~{}S\textrm{ is bad}\mid{\bf Y}~{}]\leq n^{q}\cdot
n^{2}\cdot(1-1/(2k)^{2})^{8qk^{3}\ln n}\leq 1/n^{2k}.$

Here, for each $i\in[r]$, we fixed a graph $C$ in ${\mathcal{C}}_{i}$, used
union bound along with the fact that the number of edges in $C$ is at most
$n^{2}$ and then took union bound over the ${\mathcal{C}}_{i}$’s. Finally,
taking the union bound over all $S\in{\mathcal{S}}_{k}$, we conclude that:

$\mathrm{Prob}[~{}~{}\exists S\in{\mathcal{S}}_{k}:S\textrm{ is bad}\mid{\bf
Y}~{}]=\mathrm{Prob}[~{}\vbox{\hrule height=0.5pt\kern
1.07639pt\hbox{\kern-1.49994pt${\bf X}$\kern-1.00006pt}}\mid{\bf Y}~{}]\leq
1/n^{k}.$

Therefore, with probability at least $1-2/n^{k}\geq 1-2/n$, we conclude that
every $k$-vertex set in ${\mathcal{S}}_{k}$ is good. This completes the proof
of the lemma.∎

In the rest of this section, we use the above sampling primitive as the first
step in our fixed-parameter semi-streaming algorithms for well-studied cut
problems. As discussed above, this primitive identifies $\widetilde{\cal
O}(k^{{\cal O}(1)}n)$ subgraphs that can still certify when a vertex set is
not a solution for the problem at hand. However, these subgraphs may still be
large and dense. Therefore, for the problems we consider in this section, we
provide a problem-specific sparsification step that allows us to shrink the
number of edges in each subgraph while ensuring that non-solutions can be
witnessed by a substructure in the union of the sparsified subgraphs.

###  7.1 Odd Cycle Transversal

Recall that in the Odd Cycle Transversal (OCT) problem, the input is a graph
$G$ and integer $k$ and the goal is to decide whether there is a set of at
most $k$ vertices that intersect every odd cycle in $G$.

Before we proceed, we recall the notion of the bipartite double cover of a
graph.

######  Definition 7.2 ([AGM12]).

For a graph $G$, the bipartite double cover of $G$ is the graph $D$
constructed from $G$ as follows. For each $v\in V(G)$, construct
$v_{a},v_{b}\in V(D)$ and for each edge $(u,v)\in E(G)$, create two edges
$(u_{a},v_{b})$ and $(u_{b},v_{a})$.

The above definition was used by Ahn, Guha and McGregor [AGM12] to give the
first dynamic semi-streaming algorithm to test bipartiteness. In this work, we
use the properties of bipartite double covers to generalize their result and
give a fixed-parameter semi-streaming algorithm for checking if a graph is at
most $k$ vertices away from being bipartite, i.e., OCT.

See 2.5

###### Proof.

If $k=0$, then we simply need to check whether the input graph is bipartite.
For this, we use the aforementioned algorithm of Ahn, Guha and McGregor
[AGM12]. Hence, we may assume that $k\geq 1$. Let $G$ be the input graph. We
run Sampling Primitive ($V(G),n,k,2$) to generate the vertex sets
$V_{1},\dots,V_{\ell}\subseteq V(G)$ and then process the input stream as
follows. For each sampled vertex set $V_{i}$, we use Proposition 4.8 to
maintain a connectivity sketch for the bipartite double cover of $G_{i}$,
which is denoted by $G_{i}^{\sf aux}$ (see Definition 7.2). Recall that
$G_{i}^{\sf aux}$ has exactly $2|V_{i}|$ vertices. Therefore, the space
requirement for each $V_{i}$ is bounded by $\widetilde{{\cal O}}(n)$. This
completes the processing step. Since $\ell=\widetilde{{\cal O}}(k^{{\cal
O}(1)})$, the space used by our processing step is $\widetilde{{\cal
O}}(k^{{\cal O}(1)}\cdot n)$ as required.

It remains for us to describe our fixed-parameter post-processing routine.
Recall that for any $c>0$ and $i\in[\ell]$, with probability at least
$1-1/n^{c}$, we can recover a spanning forest of $G_{i}^{\sf aux}$. By
choosing $c$ to be large enough and taking the union bound over polynomially
many subgraphs, we obtain a spanning forest $T_{i}$ of $G_{i}^{\sf aux}$ for
each $i\in[\ell]$ and conclude that with probability at least $1-1/n$, each
$T_{i}$ is indeed a spanning forest of $G_{i}^{\sf aux}$. Now, we define
$H_{i}$ to be the subgraph of $G_{i}$ induced by edges that contribute a copy
to $T_{i}$. That is, an edge $e=(u,v)\in E(G_{i})$ is added to $H_{i}$ if and
only if $(u_{a},v_{b})$ or $(u_{b},v_{a})$ is contained in $E(T_{i})$. Notice
that the number of edges in each $H_{i}$ is bounded by ${\cal O}(n)$, implying
that the number of edges in the graph $\bigcup_{i\in[\ell]}H_{i}$ is
$\widetilde{\cal O}(k^{{\cal O}(1)}n)$.

######  Claim 7.3.

With probability at least $1-3/n$, the following holds: For every $S\subseteq
V(G)$ of size $k$, if there is an odd cycle in $G-S$, then there is an odd
cycle present in the subgraph $\bigcup_{G_{i}\in{\cal L}_{S}}H_{i}$.

###### Proof.

Observe that an undirected graph has an odd cycle if and only if it has an
odd-length closed walk and let ${\mathcal{C}}_{1}$ denote the set of odd-
length closed walks in $G$. Invoking Lemma 7.1 with $r=q=1$, we conclude that
with probability at least $1-2/n$, if $S$ is a set of size at most $k$ such
that there are no odd-length closed walks in the graph $\bigcup_{G_{i}\in{\cal
L}_{S}}G_{i}$, then $S$ hits all odd-length closed walks in $G$.

Towards the proof of the claim we next argue that for each $i\in[\ell]$ and
$(u,v)\in E(G_{i})$, there is an odd $u$-$v$ walk in $H_{i}$. That is, even if
we have ignored the edge $(u,v)$ in the sparsification, we would have at least
preserved an odd $u$-$v$ walk, which we later argue would suffice for our
purposes. Indeed, notice that since $(u,v)\in E(G_{i})$, it follows that
$(u_{a},v_{b})\in E(G_{i}^{\sf aux})$. Therefore, it must be the case that
$u_{a}$ and $v_{b}$ lie in the same tree in the spanning forest $T_{i}$. Call
this tree $\Gamma_{i}^{u,v}$ and let $e_{1},\dots,e_{r}$ be the edges that
comprise the unique $u_{a}$-$v_{b}$ path in $\Gamma_{i}^{u,v}$ and notice that
the edges of $G_{i}$ corresponding to the edges in $\\{e_{1},\dots,e_{r}\\}$
are present in $H_{i}$ by definition. Moreover, notice that $r$ must be odd
since $u_{a}$ and $v_{b}$ lie on opposite sides of the bipartite graph
$G_{i}^{\sf aux}$. Hence, we obtain a $u$-$v$ walk in $H_{i}$ containing an
odd number of edges as required. Given this, we are ready to complete the
proof of the claim.

We have already observed that with probability at least $1-2/n$, for any
vertex set $S$ of size at most $k$, if there is an odd cycle in $G-S$ (and
hence an odd-length closed walk), then there is an odd-length closed walk
$C^{S}=x^{S}_{1},\dots,x^{S}_{r_{S}},x^{S}_{1}$ in $\bigcup_{G_{i}\in{\cal
L}_{S}}G_{i}$. Fix an $S$ such that $G-S$ contains an odd cycle and let
$e_{1},\dots,e_{r_{S}}$ be the edges in the odd-length closed walk $C_{S}$. We
have argued above that for every $j\in[r_{S}]$ and $e_{j}=(x_{j},x_{j+1({\sf
mod}~{}r_{S})})$, there is an odd $x_{j}$-$x_{j+1({\sf mod}~{}r_{S})}$ walk in
$\bigcup_{G_{i}\in{\cal L}_{S}}H_{i}$, implying an odd-length closed walk in
$\bigcup_{G_{i}\in{\cal L}_{S}}H_{i}$ as required. This completes the proof of
the claim. ∎

Given the above claim, we conclude that with probability at least $1-3/n$, any
set $S\subseteq V(G)$ is a solution for the OCT instance $(G,k)$ if and only
if $S$ is a solution for the OCT instance $(G^{\prime},k)$ where
$G^{\prime}=\bigcup_{G_{i}\in{\cal L}}H_{i}$. Therefore, our post-processing
algorithm computes the sparsified instance $(G^{\prime},k)$ with
$\widetilde{\cal O}(k^{{\cal O}(1)}n)$ edges and invokes the ${\cal
O}(3^{k}k^{3}(m+n))$-time $k^{{\cal O}(1)}(m+n)$-space algorithm from [KMRS20]
for OCT. This completes the proof of the theorem. ∎

###  7.2 Subset Feedback Vertex Set

Recall that in the Subset Feedback Vertex Set problem, the input is a graph
$G$, a set $T\subseteq V(G)$ of vertices called terminals and an integer $k$.
The goal is to determine whether there is a set $S\subseteq V(G)$ of size at
most $k$ that intersects all cycles in $G$ that contain a vertex of $T$. We
assume the following input model for instances of this problem. For each
terminal, when the first edge incident on it is inserted, it is inserted along
with a pair of bits that indicate whether (and if so, which of) the endpoints
of this edge are terminals.

See 2.6

###### Proof.

Let $G$ be the input graph. We run Sampling Primitive ($V(G),n,k+1,2$) to
generate the vertex sets $V_{1},\dots,V_{\ell}\subseteq V(G)$ and then process
the input stream as follows. We use Proposition 4.7 to construct a
$(k+1)n$-sparse recovery data structure $\mathcal{X}$ of size
$\widetilde{{\cal O}}(kn)$ and for each terminal, we insert all edges adjacent
to it, into this data structure. We also have a ${\cal O}(\log n)$-bit counter
that counts the number of such edges. Moreover, for each vertex set $V_{i}$
produced by the sampling primitive, we maintain a dynamic connectivity sketch
of $G_{i}=G[V_{i}]$ (call this data structure $D_{i}$) using Proposition 4.8.
This completes the processing. Since $\ell=\widetilde{{\cal O}}(k^{{\cal
O}(1)})$ and $\mathcal{X}$ has size $\widetilde{{\cal O}}(kn)$ the space used
by our processing step is $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$ as
required.

In the post-processing step, we first check the counter to determine whether
the number of edges incident on terminals exceeds $(k+1)n$. If the answer is
yes, then we return No. Otherwise, we do the following. We recover all edges
incident on $T$ by extracting all elements from $\mathcal{X}$ (see Proposition
4.7). Call this set $E_{\mathcal{X}}$. For every $i\in[\ell]$, we construct a
spanning forest of $G_{i}$ from $D_{i}$ (Proposition 4.8). Choosing $c$ to be
large enough and applying the union bound over all $\\{G_{i}\mid
i\in[\ell]\\}$, we conclude that with probability at least $1-1/n$, for every
$i\in[\ell]$, $H_{i}$ is a spanning forest of $G_{i}$. We now run the
$25.6^{k}(m+n)$-time $k^{{\cal O}(1)}(m+n)$-space randomized algorithm from
[LRS18]999This algorithm is in fact a $k^{{\cal O}(1)}(m+n)$-time (and so,
also a $k^{{\cal O}(1)}(m+n)$-space) algorithm with success probability
$1/25.6^{k}$. for ${\cal O}(\log n)$ repetitions to solve the instance
$(E_{\mathcal{X}}\cup\bigcup_{i\in[\ell]}H_{i},T,k)$.

We now prove the correctness of our algorithm.

######  Claim 7.4.

The following statements hold.

  1. 1.

If $(G,T,k)$ is a yes-instance, then the number of edges incident to $T$ is at
most $(k+1)n$.

  2. 2.

With probability at least $1-3/n$, every $S\subseteq V(G)$ is a solution for
$(G,T,k)$ if and only if $S$ is a solution for
$(E_{\mathcal{X}}\cup\bigcup_{G_{i}\in{\cal L}}H_{i},T,k)$.

###### Proof.

For the first statement, fix a solution $S$ for $(G,T,k)$ and consider the
edges incident on $T$ that do not have a vertex in $S$ as an endpoint. It is
sufficient to prove that the number of such edges is at most $n$. And indeed,
this is the case since each edge incident on a terminal must form a
biconnected component of $G-S$ on its own and the number of biconnected
components of a graph is bounded by $n$.

Consider the second statement. Let $G^{\prime}$ be the subgraph of $G$
obtained by taking the subgraph $\bigcup_{G_{i}\in{\cal L}}H_{i}$ and then
adding the edges in $E_{\mathcal{X}}$. Since $G^{\prime}$ is a subgraph of
$G$, it follows that if $S$ is a solution for $(G,T,k)$, it is also a solution
for $(G^{\prime},T,k)$.

We now consider the converse direction. For every $u,v\in V(G)$, let
${\mathcal{C}}_{uv}$ denote the set of all $u$-$v$ paths in $G$. Consider the
set $\\{{\mathcal{C}}_{uv}\mid u,v\in V(G)\\}$ which has size at most $n^{2}$.
Invoking Lemma 7.1 guarantees that with probability at least $1-2/{n}$, for
every set $P\subseteq V(G)$ of size at most $k+1$, and every $u,v\in V(G)$, if
there is a $u$-$v$ path in $G-P$ then there is a $u$-$v$ path in
$G^{\prime}-P$. Henceforth, we assume that this event indeed occurs. Now,
suppose that $S$ is a solution for $(G^{\prime},T,k)$, but is not a solution
for $(G,T,k)$. Let $t\in T$ be such that $C$ is a $t$-cycle in $G-S$ which is
not present in $G^{\prime}-S$. Recall that every block of $G^{\prime}-S$ that
$t$ is contained in, consists of a single edge incident on $t$. Moreover,
since $G^{\prime}$ contains every edge in $G$ that is incident on $t$, it
follows that every edge in $G$ that is incident on $t$ but not incident on $S$
is already present in $G^{\prime}-S$. We now observe that for $t$ to have a
flow of 2 to some vertex in $G-S$, there must be a pair of adjacent vertices
$u,v\notin T$ that lie on a $t$-cycle in $G-S$, but which have no path between
them in $G^{\prime}-S-\\{t\\}$ (i.e., they lie in distinct blocks of
$G^{\prime}-S$ that are separated by $t$). Consider the set
$S^{\prime}=S\cup\\{t\\}$ and notice that we have inferred the existence of a
$u$-$v$ path in $G-S^{\prime}$. As already argued using Lemma 7.1, there must
be a $u$-$v$ path in $G^{\prime}-S^{\prime}$, a contradiction. This completes
the proof of the claim. ∎

Since the instance $(E_{\mathcal{X}}\cup\bigcup_{i\in[\ell]}H_{i},T,k)$ has
$n$ vertices and $\widetilde{\cal O}(k^{{\cal O}(1)}n)$ edges, the theorem
follows. ∎

###  7.3 Multiway Cut

Recall that in the Multiway Cut problem, the input is a graph $G$, a set
$T\subseteq V(G)$ of vertices called terminals and an integer $k$. The goal is
to determine whether there is a set $S\subseteq V(G)$ of size at most $k$ such
that there is no connected component of $G-S$ containing two terminals. As was
the case for Subset Feedback Vertex Set, we assume the following input model
for instances of this problem. For each terminal, when the first edge incident
on it is inserted, it is inserted along with a pair of bits that indicate
whether (and if so, which of) the endpoints of this edge are terminals.

See 2.7

###### Proof.

We run Sampling Primitive ($V(G),n,k,2$) to generate the vertex sets
$V_{1},\dots,V_{\ell}\subseteq V(G)$ and then process the input stream as
follows. For each vertex set $V_{i}$ produced by the sampling primitive, we
maintain a dynamic connectivity sketch of $G_{i}=G[V_{i}]$ (call this data
structure $D_{i}$) using Proposition 4.8. This completes the processing. Since
$\ell=\widetilde{{\cal O}}(k^{{\cal O}(1)})$, the space used by our processing
step is $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$ as required.

In the post-processing step, for every $i\in[\ell]$, we construct a spanning
forest of $G_{i}$ from $D_{i}$ (Proposition 4.8). Choosing $c$ to be large
enough and applying the union bound over all $\\{G_{i}\mid i\in[\ell]\\}$, we
conclude that with probability at least $1-1/n$, for every $i\in[\ell]$,
$H_{i}$ is a spanning forest of $G_{i}$. We now run the known ${\cal
O}(4^{k}k^{{\cal O}(1)}(m+n))$-time $k^{{\cal O}(1)}(m+n)$-space fixed-
parameter algorithm for Multiway Cut (see, for example, [CFK+15]) on the
instance $(\bigcup_{i\in[\ell]}H_{i},T,k)$ which has $n$ vertices and
$\widetilde{\cal O}(k^{{\cal O}(1)}n)$ edges.

We now prove the correctness of our algorithm.

######  Claim 7.5.

With probability at least $1-3/n$, every $S\subseteq V(G)$ is a solution for
$(G,T,k)$ if and only if $S$ is a solution for $(\bigcup_{G_{i}\in{\cal
L}}H_{i},T,k)$.

###### Proof.

Let $G^{\prime}=\bigcup_{G_{i}\in{\cal L}}H_{i}$. Since $G^{\prime}$ is a
subgraph of $G$, it follows that if $S$ is a solution for $(G,T,k)$, it is
also a solution for $(G^{\prime},T,k)$.

We now consider the converse direction. For every $u,v\in V(G)$, let
${\mathcal{C}}_{uv}$ denote the set of all $u$-$v$ paths in $G$. Consider the
set $\\{{\mathcal{C}}_{uv}\mid u,v\in V(G)\\}$ which has size at most $n^{2}$.
Invoking Lemma 7.1 guarantees that with probability at least $1-2/{n}$, for
every set $P\subseteq V(G)$ of size at most $k$, and every $u,v\in V(G)$, if
there is a $u$-$v$ path in $G-P$ then there is a $u$-$v$ path in
$G^{\prime}-P$. Henceforth, we assume that this event occurs. Now, suppose
that $S$ is a solution for $(G^{\prime},T,k)$, but is not a solution for
$(G,T,k)$. Let $t_{1},t_{2}\in T$ be such that $Q$ is a $t_{1}$-$t_{2}$ path
in $G-S$. But then, there must be a $t_{1}$-$t_{2}$ path in
$G^{\prime}-S^{\prime}$ also, yielding a contradiction. This completes the
proof of the claim. ∎

Since the instance $(\bigcup_{i\in[\ell]}H_{i},T,k)$ has $n$ vertices and
$\widetilde{\cal O}(k^{{\cal O}(1)}n)$ edges, the theorem follows. ∎

Notice that in contrast to the static setting, the edge deletion variants of
the above problems cannot be trivially reduced to the vertex deletion variants
by, say, subdividing edges. This is because the number of vertices now blows
up, plus the two edges that correspond to a single original edge may now
appear far apart in time. Hence, one has to treat the edge deletion variants
separately. Our focus in this paper is on the vertex deletion variants and we
leave the edge deletion variants for future work.

##  8 Our Refinement of The SemiPS Class

We recall the class SemiPS introduced by Chitnis and Cormode [CC19] and then
formally define our new notions related to parameterized semi-streaming
algorithms.

######  Definition 8.1 (SemiPS).

[CC19] The class SemiPS comprises precisely those parameterized problems that
are solvable using $\widetilde{{\cal O}}(f(k)\cdot n)$ bits for some
computable function $f$, allowing unbounded computation at each edge update,
and also at the end of the stream, i.e., in post-processing.

######  Definition 8.2 (FPT-Semi-PS and FPSS algorithms).

The class FPT-Semi-PS comprises precisely those parameterized graph problems
that are solvable using a $\widetilde{{\cal O}}(f(k)\cdot n)$-space streaming
algorithm for some computable function $f$, allowing $f(k)n^{{\cal
O}(1)}$-time at each edge update, and also at the end of the stream, i.e., in
post-processing. We call algorithms of this form, fixed-parameter semi-
streaming algorithms, or FPSS-algorithms.

Clearly, FPT-Semi-PS is contained in SemiPS, but the converse (restricted to
graph problems) is not true as SemiPS contains W-hard problems, whereas FPT-
Semi-PS is clearly contained in FPT. We recall that, in this paper all FPSS-
algorithms we designed only require $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot
n)$-space and polynomially bounded time at each edge update. Therefore, we in
fact have worked within a further refinement of FPT-Semi-PS that is already
very rich in the amount and type of graph problems it contains as we have
shown.

We next refine the class FPT-Semi-PS by introducing the notion of (polynomial)
semi-streaming kernelization and also introduce the weaker notion of
(polynomial) semi-streaming compression. Recall that Fafianie and Kratsch
[FK14] first introduced the notion of streaming kernelization, which, for a
parameterized problem $P$ is a polynomial-time $k^{{\cal O}(1)}\log n$-space
streaming algorithm $\mathcal{A}$ that, on input $(I,k)$, outputs an instance
$(I^{\prime},k^{\prime})$ of $P$, where $(I,k)$ is a yes-instance if and only
if $(I^{\prime},k^{\prime})$ is a yes-instance and
$|I^{\prime}|,k^{\prime}\leq f(k)$ for some polynomially bounded function $f$.
However, for vast numbers of well-studied parameterized graph problems, this
definition places insurmountable constraints and so, we introduce an
appropriate notion of semi-streaming kernelization. We show through Theorem
8.5 that this definition is robust and consistent with our definition of
parameterized semi-streaming algorithms and mimics the relation between
(static) kernelization and (static) parameterized algorithms.

######  Definition 8.3 (Semi-streaming Kernelization).

Let $P$ be a graph problem parameterized by $k\in{\mathbb{N}}$. A semi-
streaming kernelization for $P$ is an $\widetilde{{\mathcal{O}}}(k^{{\cal
O}(1)}n)$-space streaming algorithm $\mathcal{A}$ with polynomially bounded
time at each edge update and polynomial post-processing time that, on input
$(I,k)$, outputs an instance $(I^{\prime},k^{\prime})$ of $P$, where $(I,k)$
is a yes-instance if and only if $(I^{\prime},k^{\prime})$ is a yes-instance
and $|I^{\prime}|,k^{\prime}\leq f(k)$ for some computable function $f$. If
$f$ is a polynomial function, then we say that $\mathcal{A}$ is a polynomial
semi-streaming kernelization.

######  Definition 8.4 (Semi-streaming Compression).

Let $P$ be a graph problem parameterized by $k\in{\mathbb{N}}$ and let $Q$ be
any language. A semi-streaming compression of $P$ into $Q$ is an
$\widetilde{{\mathcal{O}}}(k^{{\cal O}(1)}n)$-space streaming algorithm
$\mathcal{A}$ polynomially bounded time at each edge update and polynomial
post-processing time that, on input $(I,k)$, outputs an instance $I^{\prime}$
of $Q$ such that $(I,k)$ is a yes-instance of $P$ if and only if $I^{\prime}$
is a yes-instance of $Q$ and $|I^{\prime}|\leq f(k)$ for some computable
function $f$. If $f$ is a polynomial function, then we say that $\mathcal{A}$
is a polynomial semi-streaming compression of $P$ into $Q$. We also simply say
that $\mathcal{A}$ is a (polynomial) semi-streaming compression for $P$.

######  Theorem 8.5.

Let $P$ be a parameterized graph problem. Then, $P$ is in FPT-Semi-PS if and
only if it is decidable and has a semi-streaming kernelization.

###### Proof.

Let $P$ be parameterized by $k\in{\mathbb{N}}$. Suppose that $P\in$ FPT-Semi-
PS and let $\mathcal{A}$ be a $\widetilde{{\cal O}}(f(k)\cdot n)$-space
streaming algorithm for $P$ that uses $f(k)n^{{\cal O}(1)}$-time for post-
processing and between edge updates. Decidability trivially follows from the
existence of $\mathcal{A}$. If $f(k)>\log n$, then, we can simply store the
input graph using space bounded by $2^{2f(k)}$ and output it as the required
equivalent instance of $P$. On the other hand, if $f(k)<\log n$, then
$\mathcal{A}$ itself is a $\widetilde{{\cal O}}(n)$-space streaming algorithm
with polynomially bounded post-processing time and polynomially bounded time
between edge updates. Hence, we can use $\mathcal{A}$ to solve the input
instance and output an equivalent trivial instance of $P$. This gives a semi-
streaming kernelization for $P$.

Conversely, suppose that $P$ has a semi-streaming kernelization $\mathcal{A}$.
Then, we run $\mathcal{A}$ on the input instance, say $(I,k)$, and use
decidability to solve the computed equivalent instance
$(I^{\prime},k^{\prime})$ (whose size is bounded by some $f(k)$) using
additional space bounded by $g(k)$ for some computable $g$. This is a fixed-
parameter semi-streaming algorithm for $P$ as required. ∎

As in the case of static kernelization, the primary classification goal in
semi-streaming kernelization is to identify problems that have polynomial
semi-streaming kernelization and for those that do, to obtain outputs whose
size can be bounded by the slowest-growing polynomial function possible. We
extend the definitions of semi-streaming kernelization and compression from
single passes to multiple passes in the natural way.

##  9 Lower Bounds

In this section, we show lower bounds implying that (i) there are problems in
FPT that are not in FPT-Semi-PS, and (ii) our corollary for Theorem 2.1 when
$\mathcal{H}$ is the class of split graphs is tight (for $\mathcal{H}$ being
cluster graphs, a lower bound is already known from [CCE+16]).

We use the two party communication model, introduced by Yao [Yao79] to prove
lower bounds on streaming algorithms. In this model of communication, there
are two players, Alice and Bob, holding inputs $x\in X$ and $y\in Y$
respectively, where $X$ and $Y$ are two arbitrary sets. Their objective is to
compute a given function $f~{}:~{}X\times Y\rightarrow\\{0,1\\}$, by
communicating as few bits as possible. It is assumed that both players have
infinite computational power. The minimum number of bits communicated, for any
pair of inputs $(x,y)$, to compute the function $f$, is called the
(deterministic) communication complexity of $f$, denoted by $D(f)$. For a
randomized protocol $P$, we say $P$ has error probability at most
$\varepsilon$ if $\Pr(P(x,y)=f(x,y))\geq 1-\varepsilon$ for all inputs $x\in
X$ and $y\in Y$. Here, the randomness is over the private coin tosses of Alice
and Bob. The randomized communication complexity of $f$, denote by $R(f)$, is
the minimum communication cost over all the randomized protocols for $f$ with
error probability at most $1/3$. In the one-way communication model, only
Alice is allowed to send one message to Bob and no other message is allowed to
be sent. We use $D^{1-\text{way}}(f)$ and $R^{1-\text{way}}(f)$ to denote the
one way deterministic and randomized communication complexity of $f$,
respectively. Notice that $D(f)\geq R(f)$ and$D^{1-\text{way}}(f)\geq
R^{1-\text{way}}(f)$.

Lower bounds on $D^{1-\text{way}}(f)$ and $R^{1-\text{way}}(f)$ can be used
for proving lower bounds on deterministic and randomized $1$-pass streaming
algorithms via standard reductions. That is, given a function $f$, Alice
creates a stream $\sigma_{x}$ from her input $x$ and Bob creates a stream
$\sigma_{y}$ from his input $y$. First Alice runs the streaming algorithm on
$\sigma_{x}$ and passes the state of the algorithm to Bob. Then, Bob continues
the execution of the streaming algorithm on $\sigma_{y}$. Finally, the output
of the streaming algorithm is used to solve the problem $f$. This provides
space complexity lower bound of the streaming algorithm to be at least
$D^{1-\text{way}}(f)$ and $R^{1-\text{way}}(f)$.

Next, we describe some well known communication problems and state their
communication lower bounds.

##### INDEX.

The INDEX problem is one of the most commonly used communication problems to
prove lower bounds on streaming algorithms. In the INDEX problem, Alice is
given an $n$-length bit string $x_{1}\ldots x_{n}\in\\{0,1\\}^{n}$ and Bob is
given an index $i\in[n]$. Bob wants to find the bit $x_{i}$.

######  Proposition 9.1 ([KNR99]).

$R^{1-\text{way}}({\sf INDEX})=\Omega(n)$.

##### GRAPH INDEX.

In this problem, Alice is given a bipartite graph $G$ with bipartition
$V(G)=A\uplus B$ such $|A|=|B|=n$. Bob is given a pair $(a,b)\in A\times B$
and he wants to test whether $\\{a,b\\}\in E(G)$ or not. A reduction from
INDEX implies that $R^{1-\text{way}}({\sf GRAPH\;INDEX})=\Omega(n^{2})$ (see
Proof of Theorem 2.1 [CGMV20]).

##### Chordal Recognition.

We prove that any $1$-pass streaming algorithm to recognize a chordal graph
requires $\Omega(n^{2})$ space.

######  Theorem 9.2.

Any $1$-pass streaming algorithm to test whether a graph is chordal requires
$\Omega(n^{2})$ space.

###### Proof.

We give a reduction from GRAPH INDEX. In this problem, Alice is given a
bipartite graph $G$ with bipartition $A\cup B$, where $|A|=|B|=n$,
$A=\\{a_{1},\ldots,a_{n}\\}$ and $B=\\{b_{1},\ldots,b_{n}\\}$. Bob is given a
pair $(a_{i},b_{j})\in A\times B$ and he want to test whether
$(a_{i},b_{j})\in E(G)$. Alice and Bob will construct a graph $H$ such that
$H$ is chordal if and only if $(a_{i},b_{j})\in E(G)$ as follows. The vertex
set of $H$ is $A\cup B\cup\\{x_{i},y_{i}~{}\colon~{}i\in[n]\\}$. Alice will
add all the edges of $G$ to $H$ and make $A\cup\\{x_{1},\ldots,x_{n}\\}$ a
clique. Then, Alice will add the set of edges
$\\{(x_{r},y_{r^{\prime}})~{}\colon~{}r\neq r^{\prime}\\}$. Recall that
$(a_{i},b_{j})$ is the pair Bob has. Bob will add the edges $(a_{i},y_{i})$,
$(y_{i},b_{j})$, and $\\{(b_{j},x_{r})~{}\colon~{}r\in[n]\\}$. This completes
the construction of $H$.

Next we prove that $H$ is a chordal graph if and only if $(a_{i},b_{j})\in
E(G)$. From the construction of $H$, we have that
$C=a_{i},y_{i},b_{j},x_{i},a_{i}$ is a cycle of length $4$ and
$(x_{i},y_{i})\notin E(H)$. Now, if $(a_{i},b_{j})\notin E(G)$, then
$(a_{i},b_{j})\notin E(H)$ and hence $C$ is an induced $C_{4}$ in $H$. That
is, if $(a_{i},b_{j})\notin E(G)$, then $H$ is not a chordal graph. Next, we
prove the other direction of the correctness proof. That is, if
$(a_{i},b_{j})\in E(G)$, then $H$ is a chordal graph. Let $e=(y_{i},b_{j})$.
First, it is easy to see that $H-e$ is a split graph with
$A^{\prime}=A\cup\\{x_{1},\ldots,x_{n}\\}$ being a clique and
$B^{\prime}=B\cup\\{y_{1},\ldots,y_{n}\\}$ being an independent set in $H-e$.
That is, $e$ is the only edge present in $H[B^{\prime}]$. For the sake of
contradiction, suppose $H$ is not a chordal graph. Then, by the structure of
$H$, there is an induced $C_{4}$ in $H$ containing $e$. Let
$y_{i},b_{j},q,q^{\prime}$ be an induced $C_{4}$ in $H$. As $H^{\prime}$ is a
split graph, we have that $q,q^{\prime}\in A^{\prime}$. As
$\\{(b_{j},x_{r})~{}\colon~{}r\in[n]\\}\subseteq E(H)$, $q^{\prime}\in
A^{\prime}$, and $y_{i},b_{j},q,q^{\prime}$ is an induced $C_{4}$ in $H$, we
have that $q^{\prime}\in A$. Moreover, by the construction of $H$, the only
one vertex in $A$ which is adjacent to $y_{i}$ is $a_{i}$. Therefore,
$q^{\prime}=a_{i}$. Then, since $(a_{i},b_{j})=(q^{\prime},b_{j})\in E(H)$, we
got a contradiction that $y_{i},b_{j},q,q^{\prime}$ is an induced $C_{4}$ in
$H$. ∎

##### Split Graph Recognition.

Here, we prove a streaming lower bound for recognizing split graphs that
implies that our corollary for Theorem 2.1 when $\mathcal{H}$ is the class of
split graphs, is essentially tight.

######  Theorem 9.3.

Any $1$-pass streaming algorithm to test whether the graph is a split graph
requires $\Omega(n)$ space.

###### Proof sketch.

We give a reduction from the INDEX problem. In this problem Alice has a bit
string $x_{1}\ldots x_{n}$ and Bob has an index $i\in[n]$. Bob wants to know
that whether $x_{i}=1$ or not. Alice and Bob will construct a graph $G$ as
follows. The vertex set of $G$ is
$\\{y_{1},\ldots,y_{n}\\}\cup\\{z_{1},\ldots,z_{n}\\}$. For each $1\leq
j<j^{\prime}\leq n$ such that $x_{i}=x_{j}=1$ Alice will add an edge
$(y_{j},y_{j^{\prime}})$. Recall that Bob has an index $i$. He will add edges
between $x_{i}$ and $\\{z_{1},\ldots,z_{n}\\}$. Notice that if $x_{i}=1$, then
$G$ graph is a split graph. Otherwise $G$ is not a split graph. Thus, by
Proposition 9.1, the theorem follows. ∎

A similar lower bound for Custer Vertex Deletion is already known from
[CCE+16].

##  10 Concluding Remarks and Discussion

In this paper, we have given a framework to design semi-streaming algorithms
for NP-hard cut problems and proved two meta theorems that reduce the task of
solving, for any graph class $\mathcal{H}$, the corresponding Vertex Deletion
to $\mathcal{H}$ problem, to just the recognition problem (i.e. solving it for
just for $k=0$) when: (i) $\mathcal{H}$ is characterized by a finite set of
forbidden induced subgraphs, or (ii) $\mathcal{H}$ is hereditary, where
additionally “reconstruction” rather than just recognition is required. The
second case encompasses graph classes that are characterized by a possibly
infinite set of obstructions. We have exemplified the usage of our theorems
with several applications to well-studied graph problems, and we believe that
these will serve as building blocks for many more applications in the future.
We remark that the running times in many of our results are also optimal under
ETH.

A point to note here is that considering Vertex Deletion to $\mathcal{H}$
where $\mathcal{H}$ is defined by excluding a set of forbidden graphs as
minors or topological minors is not very interesting in our setting. In
particular, if $\mathcal{H}$ is defined by excluding a finite set of forbidden
graphs as minors or topological minors (e.g., $\mathcal{H}$ is the class of
planar graphs), then the number of edges in any $G\in\mathcal{H}$ is upper
bounded by ${\cal O}(n)$. Thus, given an instance $(G,k)$ of Vertex Deletion
to $\mathcal{H}$ one can check whether the number of edges in $G$ is ${\cal
O}(kn)$. If the answer is no, then we have a no-instance. Otherwise, we can
simply store the entire graph. This means that Vertex Deletion to
$\mathcal{H}$ for such $\mathcal{H}$ trivially belongs to the class SemiPS
[CC19]. Further, we know that for all such $\mathcal{H}$, Vertex Deletion to
$\mathcal{H}$ is in FPT (see, for example, [CFK+15]), which implies that in
fact, whether or not Vertex Deletion to $\mathcal{H}$ belongs to the class
FPT-Semi-PS (which is contained in SemiPS) simply depends on whether there is
a static linear-space FPT algorithm for the problem that can be used in post-
processing. While this is an interesting research direction in itself, it
presents different challenges to those we encounter when the goal is to sketch
the input graph stream. On the other hand, suppose that $\mathcal{H}$ is
defined by excluding an infinite number of forbidden graphs as minors. It is
well-known from the Graph Minors project that if a graph class is
characterized by an infinite set of forbidden minors, then it is also
characterized by a finite set of forbidden minors, as a result of which we
fall back into the previous case. Finally, to the best of our knowledge, there
are no natural graph classes characterized by an infinite set of forbidden
topological minors.

Let us conclude the paper with a few open questions and further research
directions.

  * •

A central tool in Parameterized Complexity is the usage of graph
decompositions. Which among them is relevant to parameterized problems in the
semi-streaming model? Also, which of the width-parameters corresponding to
them is relevant? With respect to tree decompositions, once a graph has
bounded treewidth $w$, its number of edges is already ${\mathcal{O}}(nw)$,
which means that it can just be stored explicitly. More interestingly, we
believe that the “unbreakability decompositions” (which generalize tree
decompositions) given in [CLP+19, CKL+21] can be computed in
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$ space. If this is achieved,
then the classic Minimum Bisection problem (see Appendix for the formal
definition) can be dealt in the same manner as we deal with other cut problems
in this paper, yielding a parameterized algorithm for it in the semi-streaming
model. We leave this as an interesting question.

  * •

One of the main inspirations behind Parameterized Complexity is the graph
minors project of Robertson and Seymour [Dow12, LSZ20]. Here, the central
algorithms are for Minor Containment and Disjoint Paths, also on specific
graph classes. Could one develop a theory for algorithmic graph minors in the
semi-streaming model?

  * •

Our work naturally motivates revisiting and improving classic algorithmic
methods in Parameterized Complexity where space exceeds
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$. For example, consider the
celebrated matroid-based technique to design polynomial kernels by Kratsch and
Wahlström [KW20, KW14]—can it be implemented in
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$ space? If the answer is
positive, then, for example, composed with our sketch for Odd Cycle
Transversal, we may derive a semi-streaming kernelization for this problem.
Here, and in many other foundational techniques, completely new ideas may be
required. As we mentioned above, in light of semi-streaming in particular, and
big data in general, increasing importance must be given to space complexity.

  * •

In recent years, parameterized approximation algorithms and lossy
kernelization have become a very active subject of research (see, e.g.,
[Mar08, FKLM20, CCK+20b, LPRS17, KS20, KLM19, LMR+21, LSS20]). Indeed, we do
not have to choose between parameterized analysis and approximation, but
combine them and “enjoy the best of both worlds”—for example, we can develop a
$(1+\epsilon)$-approximation algorithm that runs in $2^{{\mathcal{O}}(k)}\cdot
n^{{\mathcal{O}}(1)}$ time for some problems that are both APX-hard and
W[1]-hard. Naturally, we can use approximation also in the context of
parameterized algorithms in the semi-streaming model. Then, we may use the
same definition, but seek an approximate rather than exact solution.

  * •

Lastly, we would like to remark that the study of parameterized (graph)
problems in the semi-streaming model can also be of significant interest when
the input graph is restricted to belong to a certain graph class. Here, of
course, it only makes sense to consider dense classes of graphs. For example,
most geometric intersection graphs classes are dense (containing cliques of
any size), and, recently, they are being extensively studied from the
viewpoint of Parameterized Complexity (see, e.g., [GKW08, FLP+20, dBBK+18,
PSZ19, FLP+19]). So, they may be natural candidates in this regard. In
particular, recognizing the family of interval graphs in the semi-streaming
model is an interesting open question.

## References

  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459–467. SIAM, 2012.
  * [AH22] Josh Alman and Dean Hirsch.  Parameterized sensitivity oracles and dynamic algorithms using exterior algebras.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 9:1–9:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [AKLS16] Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh.  A faster FPT algorithm and a smaller kernel for block graph vertex deletion.  In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 1–13. Springer, 2016.
  * [AMW20] Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams.  Dynamic parameterized problems and algorithms.  ACM Trans. Algorithms, 16(4):45:1–45:46, 2020.
  * [BBG00] Ann Becker, Reuven Bar-Yehuda, and Dan Geiger.  Randomized algorithms for the loop cutset problem.  J. Artif. Intell. Res., 12:219–234, 2000.
  * [BBYG00] Ann Becker, Reuven Bar-Yehuda, and Dan Geiger.  Randomized algorithms for the loop cutset problem.  Journal of Artificial Intelligence Research, 12:219–234, 2000.
  * [BCC+22] Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J. A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger.  Fixed-parameter sensitivity oracles.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 23:1–23:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [BLS99] Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad.  Graph classes: a survey.  SIAM, 1999.
  * [BPS15] Neta Barkay, Ely Porat, and Bar Shalem.  Efficient sampling of non-strict turnstile data streams.  Theor. Comput. Sci., 590:106–117, 2015.
  * [CC19] Rajesh Chitnis and Graham Cormode.  Towards a theory of parameterized streaming algorithms.  In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [CCD+21] Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, and Anna Zych-Pawlewicz.  Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 796–809. SIAM, 2021.
  * [CCE+16] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova.  Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1326–1344. SIAM, 2016.
  * [CCHM15] Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh.  Parameterized streaming: Maximal matching and vertex cover.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1234–1251. SIAM, 2015.
  * [CCK+20a] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan.  From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.  SIAM J. Comput., 49(4):772–810, 2020.
  * [CCK+20b] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan.  From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.  SIAM J. Comput., 49(4):772–810, 2020.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [CGMV20] Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova.  Vertex ordering problems in directed graph streams.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1786–1802. SIAM, 2020.
  * [CKL+21] Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, and Magnus Wahlström.  Randomized contractions meet lean decompositions.  ACM Trans. Algorithms, 17(1):6:1–6:30, 2021.
  * [CLP+19] Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Minimum bisection is fixed-parameter tractable.  SIAM J. Comput., 48(2):417–450, 2019.
  * [dBBK+18] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  A framework for eth-tight algorithms and lower bounds in geometric intersection graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 574–586, 2018.
  * [DH05] Erik D. Demaine and Mohammad Taghi Hajiaghayi.  Bidimensionality: new connections between FPT algorithms and ptass.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 590–601. SIAM, 2005.
  * [DHH96] Xiaotie Deng, Pavol Hell, and Jing Huang.  Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs.  SIAM J. Comput., 25(2):390–403, February 1996.
  * [DHK05] Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi.  Algorithmic graph minor theory: Decomposition, approximation, and coloring.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 637–646. IEEE Computer Society, 2005.
  * [Die00] Reinhard Diestel.  Graduate texts in mathematics.  Graph theory, 173, 2000.
  * [DKT14] Zdenek Dvorák, Martin Kupec, and Vojtech Tuma.  A dynamic data structure for MSO properties in graphs with bounded tree-depth.  In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014\. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 334–345. Springer, 2014.
  * [Dow12] Rod Downey.  The birth and early years of parameterized complexity.  In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pages 17–38, 2012.
  * [FK14] Stefan Fafianie and Stefan Kratsch.  Streaming kernelization.  In International Symposium on Mathematical Foundations of Computer Science, pages 275–286. Springer, 2014.
  * [FKLM20] Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi.  A survey on approximation in parameterized complexity: Hardness and algorithms.  Algorithms, 13(6):146, 2020.
  * [FKM+05] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theor. Comput. Sci., 348(2-3):207–216, 2005.
  * [FKSV02] Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan.  An approximate l1-difference algorithm for massive data streams.  SIAM J. Comput., 32(1):131–151, 2002.
  * [FLMS12] Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.  Planar F-deletion: Approximation, kernelization and optimal FPT algorithms.  In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 470–479. IEEE, 2012.
  * [FLP+19] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Finding, hitting and packing cycles in subexponential time on unit disk graphs.  Discret. Comput. Geom., 62(4):879–911, 2019.
  * [FLP+20] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Eth-tight algorithms for long path and cycle on unit disk graphs.  In 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, pages 44:1–44:18, 2020.
  * [Fuj98] Toshihiro Fujito.  A unified approximation algorithm for node-deletion problems.  Discret. Appl. Math., 86(2-3):213–231, 1998.
  * [GKW08] Panos Giannopoulos, Christian Knauer, and Sue Whitesides.  Parameterized complexity of geometric problems.  The Computer Journal, 51(3):372–384, 2008.
  * [GKW19] Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese.  Parameterized approximation schemes for independent set of rectangles and geometric knapsack.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 53:1–53:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [GLL18] Anupam Gupta, Euiwoong Lee, and Jason Li.  Faster exact and approximate algorithms for k-cut.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 113–123. IEEE Computer Society, 2018.
  * [GMT15] Sudipto Guha, Andrew McGregor, and David Tench.  Vertex and hyperedge connectivity in dynamic graph streams.  In Tova Milo and Diego Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 241–247. ACM, 2015.
  * [Gol04] Martin Charles Golumbic.  Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57).  North-Holland Publishing Co., NLD, 2004.
  * [HK07] Pinar Heggernes and Dieter Kratsch.  Linear-time certifying recognition algorithms and forbidden induced subgraphs.  Nord. J. Comput., 14(1-2):87–108, 2007.
  * [KLM19] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi.  On the parameterized complexity of approximating dominating set.  J. ACM, 66(5):33:1–33:38, 2019.
  * [KMN+23] Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, and Marek Sokolowski.  Dynamic treewidth, 2023.
  * [KMRS20] Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh.  Faster graph bipartization.  J. Comput. Syst. Sci., 109:45–55, 2020.
  * [KNR99] Ilan Kremer, Noam Nisan, and Dana Ron.  On randomized one-round communication complexity.  Comput. Complex., 8(1):21–49, 1999.
  * [KS20] Ariel Kulik and Hadas Shachnai.  Analysis of two-variable recurrence relations with application to parameterized approximations.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 762–773. IEEE, 2020.
  * [KW14] Stefan Kratsch and Magnus Wahlström.  Compression via matroids: A randomized polynomial kernel for odd cycle transversal.  ACM Trans. Algorithms, 10(4):20:1–20:15, 2014.
  * [KW20] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.
  * [LMR+21] Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan, Saket Saurabh, and Meirav Zehavi.  FPT approximation for FPT problems.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 (to appear). SIAM, 2021.
  * [LPRS17] Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh.  Lossy kernelization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224–237, 2017.
  * [LRS18] Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh.  Linear time parameterized algorithms for subset feedback vertex set.  ACM Trans. Algorithms, 14(1):7:1–7:37, 2018.
  * [LSS20] Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan.  A parameterized approximation scheme for min $k$-cut.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 798–809. IEEE, 2020.
  * [LSZ20] Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Efficient graph minors theory and parameterized algorithms for (planar) disjoint paths.  In Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pages 112–128, 2020.
  * [LY80] John M. Lewis and Mihalis Yannakakis.  The node-deletion problem for hereditary properties is NP-complete.  J. Comput. Syst. Sci., 20(2):219–230, 1980.
  * [LY94] Carsten Lund and Mihalis Yannakakis.  On the hardness of approximating minimization problems.  J. ACM, 41(5):960–981, 1994.
  * [Mar08] Dániel Marx.  Parameterized complexity and approximation algorithms.  The Computer Journal, 51(1):60–78, 2008.
  * [McG14] Andrew McGregor.  Graph stream algorithms: a survey.  ACM SIGMOD Record, 43(1):9–20, 2014.
  * [MPS23] Konrad Majewski, Michal Pilipczuk, and Marek Sokolowski.  Maintaining cmso properties on dynamic structures with bounded feedback vertex number.  In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254 of LIPIcs, pages 46:1–46:13. Schloss Dagstuhl - Leibniz-Zentrum f”ur Informatik, 2023.
  * [Mut05] Shanmugavelayutham Muthukrishnan.  Data streams: Algorithms and applications.  Now Publishers Inc, 2005.
  * [NSS95] M. Naor, L. J. Schulman, and A. Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS ’95, pages 182–191, Washington, DC, USA, 1995. IEEE Computer Society.
  * [PSS+22] Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, and Alexandre Vigny.  Algorithms and data structures for first-order logic with connectivity under vertex failures.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 102:1–102:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [PSZ19] Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1035–1054, 2019.
  * [SW15] Xiaoming Sun and David P. Woodruff.  Tight bounds for graph problems in insertion streams.  In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pages 435–448. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [vtHV13] Pim van ’t Hof and Yngve Villanger.  Proper interval vertex deletion.  Algorithmica, 65(4):845–867, 2013.
  * [Weg67] Gerd Wegner.  Eigenschaften der Nerven homologisch-einfacher Familien im Rn.  1967\.
  * [Yan78] Mihalis Yannakakis.  Node- and edge-deletion np-complete problems.  In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 253–264. ACM, 1978.
  * [Yao79] Andrew Chi-Chih Yao.  Some complexity questions related to distributive computing(preliminary report).  In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79, pages 209–213, New York, NY, USA, 1979. Association for Computing Machinery.

##  Appendix A Problem Definitions

Feedback Vertex Set on Tournaments Parameter: $k$ Input: A tournament $T$ and
integer $k$. Question: Is there a set $S\subseteq V(G)$ of size at most $k$
such that $T-S$ is acyclic.

Split Vertex Deletion Parameter: $k$ Input: A graph $G$ and integer $k$.
Question: Is there a set $S\subseteq V(G)$ of size at most $k$ such that $G-S$
is a split graph, i.e., the vertex set can be partitioned into two – one
inducing a complete graph and the other, an independent set.

Threshold Vertex Deletion Parameter: $k$ Input: A graph $G$ and integer $k$.
Question: Is there a set $S\subseteq V(G)$ of size at most $k$ such that $G-S$
is a threshold graph, i.e., a split graph that also excludes the induced path
on 4 vertices.

Cluster Vertex Deletion Parameter: $k$ Input: A graph $G$ and integer $k$.
Question: Is there a set $S\subseteq V(G)$ of size at most $k$ such that $G-S$
is a cluster graph, i.e., every connected component is a complete graph.

Minimum Bisection Parameter: k Input: A graph $G$ and an integer $k$.
Question: Does there exists a partition $(A,B)$ of $V(G)$ such that
$||A|-|B||\leq 1$ and $E(A,B)\leq k$?