# Meta-theorems for Parameterized Streaming Algorithms

Daniel Lokshtanov Pranabendu Misra Fahad Panolan M. S. Ramanujan University of
California, Santa Barbara, USA<EMAIL_ADDRESS>Mathematical
Institute<EMAIL_ADDRESS>Institute of Technology, Hyderabad.
<EMAIL_ADDRESS>of Warwick, UK. r.maadapuzhi-
<EMAIL_ADDRESS>Saket Saurabh Meirav Zehavi Department of Informatics,
University of Bergen, Norway and Institute of Mathematical Sciences, HBNI,
India<EMAIL_ADDRESS>University of the Negev, Israel.
<EMAIL_ADDRESS>
The streaming model was introduced to parameterized complexity independently
by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and
Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode,
Esfandiari, Hajiaghayi and Monemizadeh [SPAA15] and by Chitnis, Cormode,
Esfandiari, Hajiaghayi, McGregor, Monemizadeh and Vorotnikova [SODA16].
Despite its strong motivation, the applicability of the streaming model to
central problems in parameterized complexity has remained, for almost a
decade, quite limited. Indeed, due to simple $\Omega(n)$-space lower bounds
for many of these problems, the
$k^{{\mathcal{O}}(1)}\cdot\mathsf{polylog}(n)$-space requirement in the model
is too strict.

Thus, we explore semi-streaming algorithms for parameterized graph problems,
and present the first systematic study of this topic. Crucially, we aim to
construct succinct representations of the input on which optimal post-
processing time complexity can be achieved.

  * •

We devise meta-theorems specifically designed for parameterized streaming and
demonstrate their applicability by obtaining the first $k^{{\cal O}(1)}\cdot
n\cdot\mathsf{polylog}(n)$-space streaming algorithms for well-studied
problems such as Feedback Vertex Set on Tournaments, Cluster Vertex Deletion,
Proper Interval Vertex Deletion and Block Vertex Deletion. In the process, we
demonstrate a fundamental connection between semi-streaming algorithms for
recognizing graphs in a graph class $\mathcal{H}$ and semi-streaming
algorithms for the problem of vertex deletion into $\mathcal{H}$.

  * •

We present an algorithmic machinery for obtaining streaming algorithms for cut
problems and exemplify this by giving the first $k^{{\cal O}(1)}\cdot
n\cdot\mathsf{polylog}(n)$-space streaming algorithms for Graph
Bipartitization, Multiway Cut and Subset Feedback Vertex Set.

###### Contents

  1. 1 Introduction
  2. 2 Our Contributions and Methodology
    1. 2.1 Our First Meta-theorem: $\mathcal{H}$ is Characterized by the Absence of Finitely Many Induced Subgraphs
    2. 2.2 Our Second Meta-theorem: $\mathcal{H}$ is Characterized by the Absence of Infinitely Many Induced Subgraphs
    3. 2.3 Our Third Algorithmic Result: A Framework for Cut Problems
    4. 2.4 Refinement of the Class SemiPS
  3. 3 Related Work
  4. 4 Preliminaries
    1. 4.1 Splitters and Separating Families
    2. 4.2 Semi-streaming Algorithms
    3. 4.3 Graphs and Graph Classes
  5. 5 From Recognition to Vertex Deletion to $\mathcal{H}$ with Finitely Many Obstructions
    1. 5.1 The Fixed-parameter Semi-streaming Algorithm for Vertex Deletion to $\mathcal{H}$
    2. 5.2 Corollaries
  6. 6 From Reconstruction to Vertex Deletion to $\mathcal{H}$ with Infinitely Many Obstructions
    1. 6.1 Proper Interval Vertex Deletion in ${\mathcal{O}}(\log^{2}n)$ Passes
      1. 6.1.1 Reconstruction Algorithm
      2. 6.1.2 Post-processing Algorithm
    2. 6.2 Block Vertex Deletion in One Pass
      1. 6.2.1 Reconstruction Algorithm
      2. 6.2.2 Post-processing Algorithm
  7. 7 Cut Problems
    1. 7.1 Odd Cycle Transversal
    2. 7.2 Subset Feedback Vertex Set
    3. 7.3 Multiway Cut
  8. 8 Our Refinement of The SemiPS Class
  9. 9 Lower Bounds
  10. 10 Concluding Remarks and Discussion
  11. A Problem Definitions

##  1 Introduction

The Parameterized Streaming model was proposed independently by Fafianie and
Kratsch [FK14] and Chitnis, Cormode, Hajiaghayi and Monemizadeh [CCHM15] with
the goal of studying space-bounded parameterized algorithms for NP-complete
problems. In this setting, the space is restricted to
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)})$ (that is,
${\mathcal{O}}(k^{{\mathcal{O}}(1)}\cdot\mathsf{polylog}(n))$), where the
parameter $k$ is a non-negative integer that aims to express some structure in
the input. A feature of this model is that it allows one to design (exact)
streaming algorithms for certain NP-complete graph problems such as Vertex
Cover (where the parameter $k$ is the size of the solution, i.e., the vertex
cover).

Unfortunately, even allowing
${\mathcal{O}}(k^{{\mathcal{O}}(1)}\cdot\mathsf{polylog}(n))$ space can only
lead to limited success as numerous NP-complete graph problems (when
parameterized by the solution size) require space $\widetilde{\Omega}(n)$ even
when $k$ is a fixed constant (e.g., $k=0$) [FK14, CCHM15]. 111For instance,
consider the classic NP-complete problem Graph Bipartization, where the goal
is to determine, given a graph $G$ and number $k$, whether removing $k$
vertices from $G$ results in a bipartite graph. For $k=0$, this problem is
nothing but testing whether $G$ is bipartite, for which there is a
$\Omega(n\log n)$-space lower bound for one-pass algorithms [SW15].
Subsequently, Chitnis and Cormode [CC19] made an important advance by defining
a hierarchy of complexity classes for parameterized streaming; among these
classes, they defined the SemiPS (parameterized semi-streaming) class. This
class, in the spirit of standard semi-streaming [Mut05, FKM+05], includes all
graph problems that can be solved by an algorithm that uses
$\widetilde{{\mathcal{O}}}(f(k)n)$ space for some computable function $f$ of
$k$.

The class SemiPS allows unbounded computational power, both while processing
the stream and in post-processing. Notice that this implies that several
problems that are not expected to have fixed-parameter algorithms (e.g.,
problems that are W[1]-hard on planar graphs) are contained in SemiPS, since
the entire input can be stored and then solved in post-processing. Thus, the
model seems too powerful to combine well with the usual meaning of efficiency
in parameterized algorithms (i.e., solvability in time $f(k)\cdot n^{{\cal
O}(1)}$). This leaves a gap in the area which must be addressed. That is, what
would be an appropriate refinement of SemiPS that captures problems in FPT? We
bridge this gap in the state of the art by initiating the study of
parameterized streaming algorithms where the space complexity is bounded by
$\widetilde{{\mathcal{O}}}(f(k)n)$ and the time complexity is bounded by
$g(k)n^{{\cal O}(1)}$ at every edge update and in post-processing, for
computable functions $f$ and $g$. We call such algorithms fixed-parameter
semi-streaming algorithms (or FPSS algorithms).

The study of parameterized streaming algorithms has remained in a relatively
early stage, with the state of the art predominantly focused on studying
individual problems. In contrast, there has been remarkable progress in
incorporating various other domains into the framework of parameterized
complexity, such as: Dynamic Graph Algorithms [DKT14, AMW20, CCD+21, MPS23,
KMN+23], Approximation Algorithms [DHK05, LPRS17, GLL18, GKW19, LSS20,
CCK+20a] and Sensitivity Oracles [BCC+22, AH22, PSS+22]. The wide interest in
these domains is also a consequence of various unique challenges that arise in
their settings. The setting of parameterized streaming algorithms offers its
own unique challenges as well. For instance, since we cannot store all the
edges incident to a vertex, it becomes challenging to utilize many of the
standard tools and techniques of Parameterized Complexity.

In this paper, we significantly advance the study of parameterized streaming
algorithms by giving _meta-theorems_ , which lead to the first FPSS algorithms
for large classes of problems studied in Parameterized Complexity. This
includes algorithms for Vertex Deletion to $\cal H$, where $\cal H$ can be a
graph class characterized by a finite forbidden family, or it can be a
hereditary graph class. We also give a framework for various graph-cut
problems and apply it to obtain the first FPSS algorithms for Graph
Bipartization (also called Odd Cycle Transversal), Multiway Cut and Subset
Feedback Vertex Set. Another key contribution is to show how, in several
cases, one can essentially “reconstruct” the input graph, providing “query-
access” to its edge-set using only $\widetilde{{\mathcal{O}}}(f(k)n)$ space,
thereby allowing the use of various algorithmic tools in Parameterized
Complexity. Of course these tools must then be employed within limited space
themselves, which in itself is a non-trivial problem that we address in this
paper.

##  2 Our Contributions and Methodology

Our algorithmic contribution consists of (i) two meta-theorems that yield FPSS
algorithms for several basic graph optimization problems, and (ii) a
methodology to obtain FPSS algorithms for well-studied graph cut problems. Our
results in (i) are arguably the first general purpose theorems applicable to
dense graphs in this line of research, and using the machinery we develop in
(ii), we resolve an open problem of Chitnis and Cormode [CC19] on whether Odd
Cycle Transversal has an $\widetilde{{\mathcal{O}}}(f(k)n)$-space streaming
algorithm. To obtain our results, we introduce novel sparsification
methodologies and combinatorial results that could be of independent interest
or of use in the design of other parameterized semi-streaming algorithms.

We next describe the graph optimization problems we focus on, which are all
vertex-deletion problems. Let $\cal H$ be a family of graphs. The canonical
vertex-deletion problem corresponding to the family $\cal H$ is defined as
follows.

Vertex Deletion to $\mathcal{H}$ Parameter: $k$ Input: A graph $G$, and an
integer $k$. Task: Decide whether there is a vertex set $S$ of size at most
$k$ such that $G-S\in\mathcal{H}$.

This family of problems includes fundamental problems in graph theory and
combinatorial optimization, e.g., Planar Vertex Deletion, Odd Cycle
Transversal, Chordal Vertex Deletion, Interval Vertex Deletion, Feedback
Vertex Set, and Vertex Cover (corresponding to $\mathcal{H}$ being the class
of planar, bipartite, chordal, interval, acyclic or edgeless graphs,
respectively). Many vertex-deletion problems are well known to be NP-complete
[LY80, Yan78]. Therefore, they have been studied extensively within various
algorithmic paradigms such as approximation algorithms, parameterized
complexity, and algorithms on restricted input classes [FLMS12, Fuj98, LY94].
However, when the input graph is too large to fit into the available memory,
these paradigms on their own are insufficient. This naturally motivates the
study of these problems in the streaming model.

Importantly, in the streaming setting, for Vertex Deletion to $\mathcal{H}$,
even the special case of $k=0$ (i.e., recognition of graphs in
${\mathcal{H}}$) is already non-trivial for many natural choices of
$\mathcal{H}$. That is, just the question of determining whether a given graph
$G$ belongs to $\mathcal{H}$ becomes significantly much harder in the
streaming setting compared to the static (i.e., non-streaming) setting and in
some cases, it is provably impossible to achieve any non-trivial upper bounds
(e.g., as we show in this paper, for chordal graphs). So, there is a
significant challenge in developing space-bounded (i.e., $\widetilde{\cal
O}(n)$-space) algorithms for recognition of various graph classes. Our first
meta theorem provides some evidence as to why the recognition problem is
challenging for many natural graph classes, by drawing a fundamental
correspondence between recognition of graphs in $\mathcal{H}$ and solving
Vertex Deletion to $\mathcal{H}$.

###  2.1 Our First Meta-theorem: $\mathcal{H}$ is Characterized by the Absence
of Finitely Many Induced Subgraphs

Our first result can be encapsulated in the following surprising message,
where $\mathcal{H}$ is defined by excluding a finite number of forbidden
graphs as induced subgraphs.

Vertex deletion to $\mathcal{H}$ is not harder than recognition for
$\mathcal{H}$.

That is, we show that Vertex Deletion to $\mathcal{H}$ has an FPSS algorithm
if and only if graphs in $\mathcal{H}$ can be recognized with a semi-streaming
algorithm. Equivalently, one could say that in the streaming model, just
checking whether a given graph is a member of $\mathcal{H}$ appears to be as
difficult as solving the seemingly much more general Vertex Deletion to
$\mathcal{H}$ problem.

To be precise, we prove the following theorem.

######  Theorem 2.1.

Let $\mathcal{H}$ be a family of graphs defined by a finite number of
forbidden induced subgraphs such that $\mathcal{H}$ admits a
deterministic/randomized $p$-pass recognition algorithm in the turnstile
(resp. insertion-only) model for some $p\in\mathbb{N}$. Then, Vertex Deletion
to $\mathcal{H}$ admits a deterministic/randomized $p$-pass $\widetilde{{\cal
O}}(k^{{\cal O}(1)}\cdot n)$-space streaming algorithm in the turnstile (resp.
insertion-only) model with post-processing time $2^{{\cal O}(k)}\cdot n^{{\cal
O}(1)}$.

In the above statement, a $p$-pass recognition algorithm for $\mathcal{H}$ is
a $p$-pass $\widetilde{{\mathcal{O}}}(n)$-space streaming algorithm with
polynomially bounded time between edge updates and in post-processing that,
given a graph $G$, correctly concludes whether or not $G\in\mathcal{H}$. The
turnstile model permits edge additions and removals whereas the insertion-only
model only permits the former. So, our result guarantees that if one can
recognize whether a given graph belongs to $\mathcal{H}$, then one can also
solve Vertex Deletion to $\mathcal{H}$ within the same number of passes and
using only $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$-space. Notably, the
dependency of the running time we attain on $k$ is the best possible under the
Exponential Time Hypothesis (ETH)— for each of the specific Vertex Deletion to
$\mathcal{H}$ problems for which we draw corollaries from Theorem 2.1 (and in
fact, even for the much simpler Vertex Cover problem), it is known that there
does not exist a $2^{o(k)}n^{{\mathcal{O}}(1)}$-time algorithm under ETH even
in the static setting [CFK+15].

As a corollary of Theorem 2.1, we get the first FPSS algorithms for well-
studied problems such as Feedback Vertex Set on Tournaments (FVST), Split
Vertex Deletion (SVD), Threshold Vertex Deletion (TVD) and Cluster Vertex
Deletion (CVD). We refer the reader to the Appendix for the formal
descriptions of these problems.

Proof overview for Theorem 2.1. Suppose that the premise holds for the graph
class $\mathcal{H}$ and let $(G,k)$ be the given instance of Vertex Deletion
to $\mathcal{H}$. Moreover, let $\mathcal{R}$ be the finite set of graphs
excluded by graphs in $\mathcal{H}$ as induced subgraphs. Suppose that the
instance is a yes-instance and let $S$ be a hypothetical inclusionwise-minimal
solution. Then, there is a set $\mathcal{T}$ of size $|S|$, which is a set of
$\mathcal{R}$-subgraphs (subgraphs isomorphic to graphs in $\mathcal{R}$) of
$G$ such that for every graph in $\mathcal{T}$, there is a unique vertex of
$S$ that it intersects. Let $V(\mathcal{T})$ denote the union of the vertex
sets of the subgraphs in $\mathcal{T}$ and notice that $|V(\mathcal{T})|\leq
dk$, where $d$ is the maximum number of vertices among the graphs in
$\mathcal{R}$. Note that $d$ is a constant in our setting. We now construct an
$(n,dk,(dk)^{2})$-splitter family ${\mathcal{F}}_{1}$ with $\widetilde{\cal
O}(k^{{\cal O}(1)})$ functions and guess a function
$f_{1}\in{\mathcal{F}}_{1}$ which is injective on $V(\mathcal{T})$. We refer
the reader to Definition 4.1 in Section 4 for a formal definition of splitter
families. At this point, it is sufficient for the reader to know that (i) for
positive integers $n,x,y$, an $(n,x,y)$-splitter family is a set of functions
mapping $[n]$ to $[y]$ such that every subset of $[n]$ of size $x$ is
injectively mapped to $[y]$ by at least one of these functions and (ii) there
are efficient ways to construct a small enough $(n,x,x^{2})$-splitter family.

Returning to our description, we treat $f_{1}$ as a function that colors
$V(G)$ with at most $(dk)^{2}$ colors. Now, in a single pass, for every set
$J$ of at most $d$ colors, we run the recognition algorithm on the subgraph of
$G$ induced by the colors in $J$. For each of those subgraphs which have been
determined to not be in $\mathcal{H}$, we use a second family of splitters (of
size ${\cal O}(\log n)$) to compute a set of at most $d$ “candidate” vertices
that could potentially be part of a minimal solution for the original
instance. This gives us a set $Z$ of size $k^{{\cal O}(1)}$ which contains
$S$. At this point, we can obtain a $2^{{\cal O}(k\log k)}n$-time post-
processing as follows – guess a subset $S^{\prime}$ of $Z$ of size at most $k$
and use the family ${\mathcal{F}}_{1}$ to check whether there is an
$\mathcal{R}$-subgraph of $G$ disjoint from $S^{\prime}$. Notice that if such
an $\mathcal{R}$-subgraph exists, then there would be a function in
${\mathcal{F}}_{1}$ that is injective on $S^{\prime}$ plus the vertices of
this subgraph and since the subgraph only spans at most $d$ color classes of
this function, we would have already stored a bit identifying whether or not
this subgraph is in $\mathcal{H}$.

In order to improve the post-processing time to a single-exponential in $k$
(matching asymptotic lower bounds even in the static setting), we give a non-
trivial reduction to the $d$-Hitting Set problem. Notice that such a reduction
in the static setting is trivial – the $\mathcal{R}$-subgraphs of the input
graph correspond to the sets that need to be “hit”. However, we require
additional work in our case since the space constraints in our setting
prohibit us from explicitly identifying the forbidden subgraphs in $G$. We
overcome this obstacle by showing that for every subset of $Z$ of size at most
$d$, our data structure can determine whether a solution needs to intersect it
and show that it is also sufficient for a solution to intersect precisely
these sets. To compute this $d$-Hitting Set instance, we employ a further
family of splitters with appropriately chosen parameters.

###  2.2 Our Second Meta-theorem: $\mathcal{H}$ is Characterized by the
Absence of Infinitely Many Induced Subgraphs

By strengthening the requirements in Theorem 2.1, we obtain a similar result
even when the set of forbidden induced subgraphs for $\mathcal{H}$ may be of
infinite size. For example, the obstruction set that defines the class of
proper interval graphs is infinite since it contains all chordless cycles.
More generally, our result holds for any hereditary graph class (i.e., graph
class closed under taking induced subraphs). Here, we require reconstruction
for $\mathcal{H}$ rather than recognition for $\mathcal{H}$, which means that
for a given graph $G$, we need to determine whether $G\in\mathcal{H}$ (as in
recognition), but in case the answer is positive, we also need to output a
succinct representation of $G$. By succinct representation, we mean a data
structure that takes $\widetilde{{\mathcal{O}}}(n)$ space and supports “edge
queries”—given a pair of vertices $u,v$, it answer whether $\\{u,v\\}$ is an
edge in $G$. In addition to this requirement, we also suppose to be given an
algorithm that solves the problem (in $\widetilde{{\mathcal{O}}}(n)$ space) in
the static setting, which is clearly an easier task than attaining the same
result in the streaming setting. Specifically, we prove the following theorem.

######  Theorem 2.2.

Let $\mathcal{H}$ be a hereditary graph class such that:

  1. 1.

$\mathcal{H}$ admits a $p$-pass deterministic/randomized reconstruction
algorithm for some $p\in\mathbb{N}$ in the turnstile (resp. insertion-only)
model, and

  2. 2.

Vertex Deletion to $\mathcal{H}$ admits a deterministic/randomized
$\widetilde{{\mathcal{O}}}(n\cdot g(k))$-space $f(k)\cdot
n^{{\mathcal{O}}(1)}$-time (static) algorithm where $g$ and $f$ are some
computable functions of $k$.

Then, Vertex Deletion to $\mathcal{H}$ admits a $p$-pass
deterministic/randomized $\widetilde{{\mathcal{O}}}(n\cdot g(k)\cdot
k^{{\mathcal{O}}(1)})$-space streaming algorithm with post-processing time
$2^{k}\cdot f(k)\cdot n^{{\mathcal{O}}(1)}$ in the turnstile (resp. insertion-
only) model.

We demonstrate the applicability of our theorems for the classes of proper
interval graphs and block graphs, where the size of the obstruction set is
infinite. For each one of these two problems, we design a reconstruction
algorithm that works in $\widetilde{{\mathcal{O}}}(n)$ space in the static
setting. Overall, this yields the following corollaries.

######  Corollary 2.3.

Proper Interval Vertex Deletion admits a randomized
${\mathcal{O}}(\log^{2}n)$-pass
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$-space streaming algorithm
with $2^{{\mathcal{O}}(k)}\cdot n^{{\mathcal{O}}(1)}$ post-processing time in
the turnstile model.

######  Corollary 2.4.

Block Vertex Deletion admits a randomized 1-pass
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$-space streaming algorithm
with $2^{{\mathcal{O}}(k)}\cdot n^{{\mathcal{O}}(1)}$ post-processing time in
the turnstile model.

Proof overview for Theorem 2.2. Using a construction of an
$(n,k,2)$-separating family, we begin by obtaining a family of
$k^{{\mathcal{O}}(1)}\log n$ vertex subsets of $G$,
$F_{1},F_{2},\ldots,F_{t}$, with the property that for every pair of vertices
$u,v$, and every vertex subset $S$ of size at most $k$ that excludes $u,v$,
there exists an $F_{i}$ that contains $u,v$ and is disjoint from $S$. For each
induced subgraph $G_{i}=G[F_{i}]$, we call the given reconstruction algorithm
and attempt to reconstruct $G_{i}$ (where all calls are done simultaneously).
For all pairs of vertices $u,v$ that never occur together in any $G_{i}$ that
we managed to reconstruct, we prove that every solution to $(G,k)$ must
contain at least one vertex from each of these pairs. So, by considering the
union $\widetilde{G}$ of the graphs $G_{i}$ that we managed to reconstruct, we
are able to reconstruct (implicitly) $G$ up to not knowing whether there exist
edges between the aforementioned pairs of vertices. However, these pairs of
vertices impose “vertex-cover constraints”, and we can directly consider every
possibility of getting rid of them by branching (into at most $2^{k}$ cases).
After that, we simulate the given parameterized algorithm on $\widetilde{G}$
minus the vertices already deleted.

Application to Proper Interval Vertex Deletion. In light of Theorem 2.2, we
need to design a reconstruction algorithm as well as a (static) parameterized
algorithm that uses $\widetilde{{\mathcal{O}}}(n)$ space.

Reconstruction. Without loss of generality, we can focus only on connected
graphs, and we observe that whenever we remove the closed neighborhood of a
vertex in a connected proper interval graph, we get at most two connected
components. The latter observation motivates the definition of a “middle
vertex”, which is a vertex such that each of the (at most two) connected
components that result from the removal of its closed neighborhood has at most
$\frac{9}{10}n$ vertices. We note that a randomly picked vertex has
probability at least $\frac{4}{5}$ to be a middle vertex. This gives rise to a
divide-and-conquer strategy where, at each step, we will aim to “organize” the
unit intervals corresponding to vertices in the closed neighborhood of a
middle vertex, and then recurse to organize those corresponding to vertices in
each of the connected components resulting from their removal. However, these
three tasks are not independent, and therefore we need to define an annotated
version of the reconstruction problem. Here, we are given, in addition to $G$,
a partial order on its vertex set, and we need to determine if $G$ admits a
unit interval model (and is therefore a unit interval graph) where for pairs
of vertices $u<v$, the interval of $u$ starts before that of $v$.

Now, suppose we handle this annotated version, being at some intermediate
recursive call, and call the graph corresponding to it by $G$ (which is an
induced subgraph of the original input graph). Let $v$ be the middle vertex,
$M$ be its closed neighborhood, and $L$ and $R$ be the two connected
components of $G-M$ (which may be empty), so that $<$ indicates that $L$
should be ordered before $R$ (or else their naming is chosen arbitrarily). We
note that in various arguments, conflicts may arise—for example, here we may
have a vertex in one component that is smaller than a vertex in the other (by
$<$), and vice versa, in which case we can directly conclude that the original
input graph is not a proper interval graph. It turns out that for $L$ (and
symmetrically for $R$), it sufficient just to solve the problem while refining
$<$ so that vertices with higher number of neighbors in $M$ will be bigger
than those having lower number of neighbors in $M$ (with the opposite for
$R$); clearly, for all vertices, the number of neighbors in $L,M$ and $R$ can
be computed in one pass. We prove that whichever solution (being a unit
interval model) will be returned for $L$ and $R$, it should be possible to
“patch” it with any unit interval ordering of $M$ given that it complies with
the following (and that the original graph is a proper interval graphs): we
refine the ordering $<$ for $M$ so that vertices with higher degree in $L$
will be smaller, while vertices with higher degree in $R$ will be bigger. As
the resolution of $L$ and $R$ is given by the recursive calls, let us now
explain how to resolve $M$.

To handle $M$, we first prove that in any unit interval model of it (if one
exists), when we go over the vertices from left to right, their degree in $M$
is non-decreasing, then reaches some pick (that is the degree of $v$), and
after that becomes non-increasing. If $L$ and $R$ are empty, then we show that
can choose as the leftmost vertex any vertex in $M$ that is smallest by $<$
and has minimum degree in $M$ among such vertices, and if $L$ is not empty
(and it is immaterial if $R$ is empty or not), we can choose as the leftmost
vertex any vertex in $M$ that has highest degree in $L$ and is simultaneously
smallest by $<$, and has smallest degree in $M$ within these vertices (but
possibly not within all vertices in $M$). Let this vertex be $a$. Then, all
neighbors of $a$ are ordered from left to right non-decreasingly by their
degree in $M$ (taking into account some information from the ordering of $L$,
which we will neglect in this brief overview, in order to break ties), and
after them all non-neighbors of $a$ are ordered from left to right non-
increasingly by their degree in $M$. Clearly, to attain the neighbors of $a$,
we just need one more pass.

Overall, the above yields a potential unit interval model for original input
graph $G$ – in particular, we argue that if $G$ is a proper interval graph,
then this must be a model of it. Lastly, the model is verified by another pass
on the stream, checking that $G$ and the graph that the model represents are
indeed the same graphs.

Static Algorithms. Here, we essentially show that the known
$2^{{\mathcal{O}}(k)}n^{{\mathcal{O}}(1)}$ algorithm by van ’t Hof and
Villanger [vtHV13] can be implemented in
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$ space.

Application to Block Vertex Deletion. As before, we start with reconstruction
and then turn to the static algorithms (which are here, unlike the case of
proper interval graphs, non-trivial).

Reconstruction. We provide reconstruction algorithms for a graph class that is
broader than the class of block graphs. Here, a $t$-flow graph is one where
between every pair of non-adjacent vertices, the number of vertex-disjoint
paths is at most $t$, and a $t$-block graph is a $t$-flow graph that is
chordal. A block graph is just a $1$-block graph. For the reconstruction of
$t$-flow graphs, the algorithm starts similarly to the proof of Theorem 2.2.
We first attain a family of $t^{{\mathcal{O}}(1)}\log n$ vertex subsets of
$G$, $F_{1},F_{2},\ldots,F_{r}$, with the property that for every pair of
vertices $u,v$ and vertex subset of size at most $t$, there exists an $F_{i}$
that contains $u,v$ and is disjoint from $S$. Using one pass on the stream,
for each induced subgraph $G_{i}=G[F_{i}]$, we compute a spanning forest, and
for each vertex in $G$, we compute its degree (in $G$). Then, we let
$G^{\prime}$ be the union of these spanning forests. In post-processing, we
construct (implicitly) a graph $\widetilde{G}$ from $G^{\prime}$ as follows
(only $G^{\prime}$ is kept explicitly). For every pair of non-adjacent
vertices $u,v$ in $G^{\prime}$ and every vertex subset of $G$ if size at most
$t$, we choose some $G_{i}$ that contains both $u,v$ and no vertex from $S$
(which can be shown to exist), and if it holds that $u$ and $v$ are in the
same connected component of $G_{i}$, then we add the edge $\\{u,v\\}$. If
every vertex has the same degree in $G$ and $\widetilde{G}$, then we conclude
the $G$ is a $t$-flow graph with reconstruction (stored in an implicit manner)
$\widetilde{G}$, and else we conclude that $G$ is not a $t$-flow graph. For
correctness, we note that it can be shown that, necessarily, $E(G)\subseteq
E(\widetilde{G})$, and that in case $G$ is a $t$-flow graph, then also
$E(\widetilde{G})\subseteq E(G)$ (else it may not be true). The degree test is
used to prove that reverse direction, where the algorithm returns true, in
which case the degree equalities and the fact that $E(G)\subseteq
E(\widetilde{G})$ imply that $G=\widetilde{G}$ (and we construct
$\widetilde{G}$ in a way that ensures it is a $t$-flow graph.

To adapt the result to reconstruct $t$-block graphs, we first reconstruct them
as $t$-flow graphs (because every $t$-block graph is in particular a $t$-flow
graph), and then, having already this reconstruction at hand, we check whether
they have a perfect elimination ordering in polynomial time and
$\widetilde{{\mathcal{O}}}(n)$ space.

Static Algorithms. We build on the work of Agrawal, Kolay, Lokshtanov and
Saurabh [AKLS16] for Block Vertex Deletion. However, implementing their
algorithm in space $\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$ is a
non-trivial task because their $2^{{\mathcal{O}}(k)}n^{{\mathcal{O}}(1)}$-time
algorithm for this problem uses space (even worse than) $\Omega(n^{2})$. In
their algorithm, they first hit small obstructions by branching (which can
clearly be done in $\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$ space),
and then they know that the resulting graph contains only
${\mathcal{O}}(n^{2})$ maximal cliques (however, there exist graphs where this
bound is tight). They then construct an auxiliary bipartite graph $H$ whose
vertex set consists of $V(G)$ and a vertex for each maximal clique in $G$, and
where a vertex in $V(G)$ is adjacent to all cliques that contain it. It is
argued that any subset $S\subseteq V(G)$ is a block graph deletion set in $G$
if and only if it is a feedback vertex set in $H$. So, the problem reduces to
seeking a minimum feedback vertex in $H$ that avoids the vertices representing
cliques. This can be simply done by an algorithm for Feedback Vertex Set (with
undeletable vertices). However, in our case, we cannot even explicitly write
the vertex set of $H$, which can be of size $\Omega(n^{2})$. So, instead, we
employ a very particular known sampling algorithm for Feedback Vertex Set.
This is an algorithm by Becker, Bar-Yehuda and Geiger [BBG00], which, after
reducing the graph to another graph that has minimum degree $3$, uniformly at
random selects an edge and randomly chooses an endpoint for it, and that
endpoint is deleted and added to the solution. It is argued that, for any
feedback vertex set, with probability at least $1/2$, the selected edge has at
least one endpoint from the feedback vertex set.

To simulate this algorithm without constructing $H$, we show (i) how to
compute the degree of every vertex in $V(G)$ in $H$, and (ii) how to apply the
reduction rules to ensure that its minimum degree is $3$. We select a vertex
in $V(G)$ (to delete and insert to our solution) with probability proportional
to its degree. This already gives us a $2^{{\mathcal{O}}(k)}n$-time
$\widetilde{{\mathcal{O}}}(k^{{\mathcal{O}}(1)}n)$-space algorithm for Block
Vertex Deletion.

###  2.3 Our Third Algorithmic Result: A Framework for Cut Problems

We devise sparsification algorithms that, in combination with random sampling
is used to deal with additional graph problems that are not encompassed by the
previous theorems. Of special interest to us in this set of problems is Odd
Cycle Transversal (OCT). In this problem, one aims to decide whether there is
a set of at most $k$ vertices in the given graph whose deletion leaves a
bipartite graph. In other words, the “obstruction” set for OCT is the set of
all odd cycles. Chitnis and Cormode [CC19] ask whether there exists a
$\widetilde{{\cal O}}(g(k)\cdot n)$-space streaming algorithm for OCT even if
one were to allow $f(k)$-passes. Furthermore, they point out that already for
$k=1$, the existence of such an algorithm is open (for $k=0$, this is nothing
but testing bipartiteness, for which a single-pass semi-streaming algorithm is
known [AGM12]). Using our framework, we obtain the following result.

######  Theorem 2.5.

There is a 1-pass $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$-space
randomized streaming algorithm for OCT with $\widetilde{{\cal
O}}(3^{k}k^{{\cal O}(1)}n)$-time post-processing.

Thus, Theorem 2.5 affirmatively answers the open problem of Chitnis and
Cormode [CC19] in its most general form by giving a 1-pass (instead of the
$f(k)$-passes they asked for) semi-streaming algorithm for Odd Cycle
Transversal.

##### Overview of our framework.

Our framework has two high-level steps. The first is generic and the second is
problem-specific.

Step 1: The first step of our framework is a sampling primitive of Guha,
McGregor and Tench [GMT15]. The main idea here is to sample roughly
$\widetilde{\cal O}(k^{{\cal O}(1)})$ vertex subsets $V_{1},\dots,V_{\ell}$ of
the input graph and argue that with good probability, the subgraph defined by
the union of the edges in the sampled graphs preserves important properties of
the input graph. In our case, we prove that at least one “no-witness” of every
non-solution is preserved in the sampled subgraph.

More precisely, we show that for every set $S\subseteq V(G)$ that is disjoint
from some forbidden substructure in $G$ (e.g., odd cycles) and hence not a
solution, the subgraph of $G$ defined by the union of the sampled subgraphs
also contains a forbidden substructure disjoint from $S$. This allows us to
identify a set of $\widetilde{\cal O}(k^{{\cal O}(1)})$ subgraphs that can
always provide a witness when a vertex set is not a solution for the problem
at hand. For problems closed under taking subgraphs, this implies that solving
the problem on the sampled subgraph is sufficient.

Step 2: At the end of Step 1, however, we are still left with a major
obstacle. That is, the sampled subgraphs may still be dense and it is far from
obvious how one could “sparsify” them while preserving the aforementioned
properties. Therefore, as the second step in our template, one needs to also
provide a problem-specific $\widetilde{\cal O}(k^{{\cal O}(1)}n)$-space
sparsification step that allows us to reduce the number of edges we keep from
each of the sampled subgraphs to ${\cal O}(n)$, while ensuring that non-
solutions can still be witnessed by a substructure in the union of the
sparsified subgraphs. If this is achieved, one may invoke existing linear-time
(static) FPT algorithms for the problem on the sparsified instance and show
that a solution for this reduced instance is also a solution for the original
instance.

We next briefly sketch our sparsification procedure for Odd Cycle Transversal
that leads to Theorem 2.5. The bipartite double cover of a graph $G$ is the
bipartite graph with two copies of the original vertex set $V$ (say $V_{a}$
and $V_{b}$) and two copies of each edge (for an edge $(u,v)$ in the original
graph, there are two edges $(u_{a},v_{b})$ and $(u_{b},v_{a})$, where for each
$z\in\\{u,v\\}$ and $x\in\\{a,b\\}$, $z_{x}$ is the copy of $z$ contained in
$V_{x}$). Ahn, Guha and McGregor [AGM12] used this auxiliary graph in their
bipartiteness-testing algorithm by observing that $G$ is bipartite precisely
when its bipartite double cover has exactly twice as many connected components
as $G$. In our work, we conduct a closer examination of bipartite double
covers and exploit the fact that odd-length closed walks in $G$ (which must
exist if $G$ is non-bipartite) that contain a vertex $v$ correspond precisely
to $v_{a}$-$v_{b}$ paths in the bipartite double cover of $G$. We build upon
this fact to show that the edges preserved by computing a dynamic connectivity
sketch for all the sampled subgraphs together preserve odd-length closed walks
in the union of these subgraphs. Finally, we argue that solving OCT with a
static FPT algorithm on the sparsified instance is equivalent to solving OCT
on the original instance.

##### Applying the framework to other cut problems.

Recall that each specific application of the framework boils down to
designing, for the cut problem at hand, (i) a problem-specific sparsification
subroutine and (ii) a linear-space (or ideally, linear-time) FPT algorithm for
use in post-processing. For instance, consider the classic Subset Feedback
Vertex Set and Multiway Cut problems. We show that these two problems also
fall under the same framework. For Subset Feedback Vertex Set, the obstruction
set is the family of all cycles that contain “terminals”—the objective of
Subset Feedback Vertex Set is to determine whether one can choose at most $k$
vertices that intersect all cycles in the input graph $G$ that pass through at
least one designated vertex, called a terminal (the input contains, in
addition to $G$ and $k$, a subset of vertices called terminals). In the case
of Multiway Cut the obstruction set is the family of all paths that connect
pairs of “terminals”. In this problem, the input is $G$, $k$ and a vertex
subset called terminals and the objective is to determine whether a set of at
most $k$ vertices intersects every path in $G$ between a pair of terminals.
For both these problems, we show how to combine the sampling primitive behind
our algorithm for Odd Cycle Transversal along with problem-specific
sparsifications for these (to handle Point (i) above) and the invocation of
existing linear-time FPT algorithms (to handle Point (ii) above). Roughly
speaking, in the sparsification step for Subset FVS, we maintain a dynamic
connectivity sketch for the sampled subgraphs along with the edges incident on
terminals and for Multiway Cut, we show that it is sufficient to maintain a
dynamic connectivity sketch for the sampled subgraphs This leads us to the
following two results.

######  Theorem 2.6.

There is a 1-pass $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$-space
randomized streaming algorithm for Subset Feedback Vertex Set with
$\widetilde{{\cal O}}(2^{{\cal O}(k)}\cdot n)$-time post-processing.

######  Theorem 2.7.

There is a 1-pass $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$-space
randomized streaming algorithm for Multiway Cut with $\widetilde{{\cal
O}}(4^{k}k^{{\cal O}(1)}\cdot n)$-time post-processing.

###  2.4 Refinement of the Class SemiPS

Our algorithmic results demonstrate that the notion of fixed-parameter semi-
streaming algorithms is widely applicable to parameterized versions of graph
optimization problems. As a result, we obtain an associated natural complexity
class (which we call FPT-Semi-PS) that is the analogue of the class FPT
(fixed-parameter tractable problems) in the semi-streaming setting. In the
same spirit, we also introduce notions of semi-streaming kernelization (and
semi-streaming compression), where the algorithm uses
$\widetilde{{\mathcal{O}}}(k^{{\cal O}(1)}n)$ space overall and polynomial
time at each edge update and in post-processing, and eventually outputs an
equivalent instance of size $f(k)$ of the same problem (or a different
problem, respectively). This output is called a kernel (or a compression,
respectively). We show that our definitions are robust and faithfully reflect
their analogues in the static setting. That is, we show (see Theorem 8.5)
that:

A (decidable) parameterized problem has an FPSS algorithm if and only if it
has a semi-streaming kernelization.

Notice that FPT-Semi-PS is contained in FPT. We show that there are problems
in FPT that are not in FPT-Semi-PS by proving a $\Omega(n^{2})$-space lower
bound for the Chordal Vertex Deletion problem even when $k=0$, that is, for
the problem of recognizing whether a given graph is chordal.

In summary, our contributions in this paper are grounded in a novel
exploration of parameterized streaming algorithms. By developing unified
algorithms through meta-theorems, proposing a complexity class and
demonstrating its richness through containment of numerous well-studied
parameterized graph problems, our work significantly extends the boundaries of
the field. Our advances also naturally point to a large number of open
questions in parameterized streaming (see Section 10 for a discussion).

##  3 Related Work

Recently, Chakrabarti et.al [CGMV20] studied _vertex-ordering problems_ in
digraphs such as testing Acyclicity and computing Feedback Vertex (Arc) sets.
In brief, they gave space lower bounds of $\Omega(n^{1+1/p})$ in general
digraphs and $\Omega(n/p)$ in Tournaments for these problems, where $p$ is the
number of passes. Moreover, they analyze the post-processing complexity of
their algorithm and show that both the time and space complexity of their
post-processing are essentially optimal. We refer to [McG14, CGMV20] for more
details and further references.

Fafianie and Kratsch [FK14] introduced a notion of streaming kernelization,
which is an algorithm that takes polynomial time, $\Omega(p(k)\log n)$ space
and outputs an equivalent instance whose size is bounded polynomially in the
parameter $k$, where $p$ is some polynomial function of $k$, and $n$ is the
input size. In this setting they gave streaming kernelizations for certain
problems such as $d$-Hitting Set in $1$-pass and Edge Dominating Set in
2-passes. On the other hand, they obtained $\Omega(m)$-space lower-bounds for
1-pass streaming kernelization for many problems including Feedback Vertex
Set, Odd Cycle Transversal, Cluster Vertex Deletion and interestingly, Edge
Dominating Set. Here $m$ denotes the number of edges. Further, they obtained
multi-pass lower bounds for Cluster Editing and Chordal Completion – they gave
a $\Omega(n/t)$-space lower bound for $t$-pass algorithms. Chitnis et.al
[CCHM15, CCE+16] studied parameterized streaming algorithms for Vertex Cover
and the more general $d$-Hitting Set problem and gave a
$\widetilde{\mathcal{O}}(k^{d})$-space streaming kernelization even on dynamic
streams. We remark that in [CCHM15], a $\widetilde{\mathcal{O}}(nk)$-space
1-pass streaming FPT algorithm for Feedback Vertex Set was presented, along
with an $\Omega(n)$ lower-bound.

In the previously discussed work of Chitnis and Cormode [CC19], they proposed
a hierarchy of complexity classes for parameterized streaming. In particular
they defined the classes FPS, SubPs, SemiPS, SupPS and BrutePS that bound
space usage to $\widetilde{\mathcal{O}}(f(k))$, $f(k)\cdot o(n)$,
$\widetilde{\mathcal{O}}(f(k)\cdot n)$, $\widetilde{\mathcal{O}}(f(k)\cdot
n^{1+\epsilon})$ for $0\leq\epsilon<1$ and $\widetilde{\mathcal{O}}(n^{2})$,
respectively. In their setting there is no restriction on time, i.e. an
unbounded amount of time may be spent during the streaming phase and post-
processing (although this was not exploited for their positive results). Then
it is clear that every decidable graph problem lies in BrutePS, since we can
store the entire graph and solve it via brute force computation. They show
that certain problems such as Dominating Set and Girth are tight for BrutePS
in 1-pass, i.e. they require $\Omega(n^{2})$ space. Similarly, they show that
Feedback Vertex Set and $k$-Path are tight for SemiPS, i.e. require
$\widetilde{\mathcal{O}}(f(k)\cdot n)$ space. They also proved a general
result placing all minor-bidimensional problems [DH05] in the class SemiPS.
Their argument implies that these problems are also typically in the class
FPT-Semi-PS depending on whether or not they have a static linear-space fixed-
parameter algorithm. However, the problems we consider in this paper are not
minor-bidimensional and so, this theorem is inapplicable in our case.
Furthermore, as mentioned earlier, Vertex Cover and $d$-Hitting Set lie in
FPS, i.e. they require $\widetilde{\mathcal{O}}(f(k))$ space for some function
$f$ of $k$ alone.

Let us remark that, in light of this result for $d$-Hitting Set, one could be
tempted to conclude that Vertex Deletion to $\mathcal{H}$ (for $\mathcal{H}$
characterized by finite forbidden induced subgraphs) can be reduced to an
instance of $d$-Hitting Set in the natural way (i.e., forbidden subgraphs of
the input graph correspond to sets in the $d$-Hitting Set instance). However,
in the streaming setting, with only $\widetilde{\mathcal{O}}(f(k)\cdot
n)$-space available, this reduction is no longer feasible since we are unable
to store all edges and enumerate all obstructions. As an illustrative example,
consider the question of recognizing whether an input graph is $k$-vertex
deletions away from being a cluster graph in the semi-streaming setting.
Recall that cluster graphs are exactly the induced-$P_{3}$-free graphs. Since
the edges forming a $P_{3}$ may arrive far apart in time, one cannot hope to
simply reduce the problem to a 3-Hitting Set instance and solve it, unless one
stores the entire graph. Therefore, in spite of the
$\widetilde{\mathcal{O}}(k^{d})$-space streaming kernelization for $d$-Hitting
Set [CCE+16], this approach cannot be used to resolve such graph modification
problems. In this work we give a novel data structure (see Section 5 and the
discussion following the proof of Theorem 2.1) using which one can indeed
reduce the given instance of any Vertex Deletion to $\mathcal{H}$ problem (for
such $\mathcal{H}$) to an instance of $d$-Hitting Set that is bounded
polynomially in $k$, using $\widetilde{\cal O}(k^{{\cal O}(1)}n)$ space.

Finally, it is important to mention the work of Feigenbaum et.al. [FKSV02],
who also considered time complexity in the context of streaming algorithms. In
particular, they defined a class called PASST$(s,t)$ (stands for probably
approximately correct streaming space complexity $s$ and time complexity $t$)
that additionally bounds the per-item processing time during the streaming
phase. However, in this work also the post-processing time is not bounded.
Chitnis and Cormode (see Remark 43 [CC19]) also consider restricting the per-
item processing time and the post-processing time to only
$n^{{\mathcal{O}}(1)}$. However, while this is suitable for streaming
kernelization algorithms [FK14], it is too restrictive when asking for
parameterized streaming algorithms.

##  4 Preliminaries

When clear from the context, we use $m$ and $n$ to denote the number of edges
and vertices respectively.

###  4.1 Splitters and Separating Families

######  Definition 4.1.

[NSS95] Consider $n,k,\ell\in{\mathbb{N}}$ such that $k\leq n,\ell$. An
$(n,k,\ell)$-splitter ${\mathcal{F}}$ is a family of functions from $[n]$ to
$[\ell]$ such that for every set $S\subseteq[n]$ of size $k$, there exists a
function $f\in{\mathcal{F}}$ that is injective on $S$.

######  Proposition 4.2 (Splitter construction).

[NSS95] For every $n,k\geq 1$, one can construct an $(n,k,k^{2})$\- splitter
of size ${\mathcal{O}}(k^{6}\log k\log n)$ in time (and space) $k^{{\cal
O}(1)}n\log n$.

We also require the following construction of a family of subsets over a set.

######  Definition 4.3 ($(n,k,\ell)$-Separating Family).

Let $U$ be a universe of $n$ elements. An _$(n,k,\ell)$ -separating family_
over $U$ is a family $\cal F$ of subsets of $U$, such that for any pair of
disjoint subsets $A$ and $B$ of $U$ where $|A|\leq k$ and $|B|\leq\ell$, there
exists $F\in\cal F$ such that $A\cap F=\emptyset$ and $B\subseteq F$.

######  Lemma 4.4.

Let $U$ be a universe of $n$ elements, and let $\ell\leq k$ be two integers.
There exists an $(n,k,\ell)$-separating family of size
${\mathcal{O}}((k+\ell)^{2\ell+6}\log(k+\ell)\log n)$ that can be enumerated
in ${\mathcal{O}}((k+\ell)^{2\ell+{\mathcal{O}}(1)}\cdot n\log n)$ time (and
space).

###### Proof.

Let $q=\ell+k$. We begin by enumerating an $(n,q,q^{2})$-splitter $\cal H$
over $U$. Recall that $\cal H$ is a collection of functions from $U$ to
$\\{1,2,\ldots,q^{2}\\}$ such that, for any subset $X$ of $U$ of size at most
$q$, there exists a function $h\in\cal H$ such that $h(i)\neq h(j)$ for any
two distinct $i,j\in X$. From Proposition 4.2, we have a construction of $\cal
H$ containing ${\mathcal{O}}(q^{6}\log q\log n)$ functions in
${\mathcal{O}}(q^{{\mathcal{O}}(1)}\cdot n\log n)$ time (and space). For each
function $h\in\cal H$, we enumerate the following family of subsets of $U$.
For each subset $Y$ of size $\ell$ of $\\{1,2,\ldots,q^{2}\\}$ we output
$h^{-1}(Y)\subseteq U$. Note that, for each $h\in\cal H$ we enumerate at most
$q^{2\ell}$ subsets of $U$, and we denote them by ${\cal F}_{h}$. We define
the $(n,k,\ell)$-separating family $\cal F$ as the union of these subsets,
i.e. ${\cal F}=\bigcup_{h\in{\cal H}}{\cal F}_{h}$. Observe that $\cal F$
contains ${\mathcal{O}}(q^{2\ell+6}\log q\log n)$ subsets of $U$, and it can
be enumerated in ${\mathcal{O}}(q^{2\ell}\cdot q^{{\mathcal{O}}(1)}\cdot n\log
n)$ time (and space).

It only remains to argue that $\cal F$ is indeed a $(n,k,\ell)$-separating
family over $U$. Towards this, consider any two disjoint subsets $A$ and $B$
of $U$ of size at most $k$ and $\ell$, respectively. Then there is a function
$h\in H$ such that $h(i)\neq h(j)$ for all $i\neq j\in A\cup B$. Let
$Y=\\{h(i)\mid i\in B\\}$, then observe that $h^{-1}(Y)\in F$ is disjoint from
$A$ and contains $B$. This holds for any choice of the subsets $A$ and $B$,
and hence $\cal F$ is a $(n,k,\ell)$-separating family over $U$. ∎

We require the following corollary of the above lemma, where we wish to
separate pairs of vertices from vertex subsets of size at most $k$ in a graph.

######  Corollary 4.5.

Let $G$ be a graph on $n$ vertices. Then, there is a family $\cal F$ of
${\mathcal{O}}((k+2)^{10}\log(k+2)\log n)$ subsets of $V(G)$ such that for any
pair of vertices $u,v$ and any subset $X$ of at most $k$ vertices where
$u,v\notin X$, there exists $F\in\cal F$ such that $u,v\in F$ and $X\cap
F=\emptyset$. Such a family $\cal F$ can be enumerated in
${\mathcal{O}}(k^{{\mathcal{O}}(1)}\cdot n\log n)$ time (and space).

###  4.2 Semi-streaming Algorithms

We assume standard word RAM model of computation with words of bitlength
${\cal O}(\log n)$, where $n$ is the vertex count of the input graph. Vertex
labels are assumed to fit within single machine words and can be operated on
in ${\cal O}(1)$-time.

##### Insertion-only streams.

Let $P$ be a problem parameterized by $k\in{\mathbb{N}}$. Let $(I,k)$ be an
instance of $P$ that has an input $X=\\{x_{1},\dots,x_{i},\dots,x_{m}\\}$ with
input size $|I|=m$. Let ${\mathcal{S}}$ be a stream of ${\sf INSERT}(x_{i})$
(i.e., the insertion of an element $x_{i}$) operations of underlying instance
$(I,k)$. In particular, the stream ${\mathcal{S}}$ is a permutation
$X^{\prime}=\\{x^{\prime}_{1},\dots,x^{\prime}_{i},\dots,x^{\prime}_{m}\\}$
for $x^{\prime}_{i}\in X$ of an input $X$.

##### Dynamic/turnstile streams.

Let $P$ be a problem parameterized by $k\in{\mathbb{N}}$. Let $(I,k)$ be an
instance of $P$ that has an input $X=\\{x_{1},\dots,x_{i},\dots,x_{m}\\}$ with
input size $|I|=m$. We say that stream ${\mathcal{S}}$ is a turnstile
parameterized stream if ${\mathcal{S}}$ is a stream of ${\sf INSERT}(x_{i})$
(i.e., the insertion of an element $x_{i}$) and ${\sf DELETE}(x_{i})$ (i.e.,
the deletion of an element $x_{i}$) operations applying to the underlying
instance $(I,k)$ of $P$.

Throughout this paper, when we refer to a (semi-)streaming algorithm without
explicitly mentioning the number of passes required, then the number of passes
is 1. Similarly, when the type of input stream (whether it is insertion-only
or turnstile) is not explicitly mentioned, then it is to be understood that
the input stream being referred to is a turnstile stream. We also assume that
in either stream, when the input is an instance $(I,k)$ of a parameterized
graph problem $P$, the algorithm is aware of the vertex set of the input
graph. Moreover, $k$ is first given in the stream in unary and never deleted.
It is only then that the stream begins providing $I$. Note that the elements
in $I$ can potentially undergo deletion and reinstertions, depending on the
input model.

######  Definition 4.6 ($k$-sparse recovery algorithm).

A $k$-sparse recovery algorithm is a data structure which accepts insertions
and deletions of elements from $[n]$ and recovers all elements of the stream
if, at the recovery time, the number of elements stored in it is at most $k$.

We require the following result of Barkay, Porat and Shalem [BPS15] which we
have specialized to our setting.

######  Proposition 4.7 (Lemma 9, [BPS15]).

There is a deterministic structure, SRS with parameter $k$, denoted by SRSk,
that that keeps a sketch of stream $I$ (comprising insertions and deletions of
elements from $[n]$) and can recover all of $I$’s elements if $I$ contains at
most $k$ distinct elements. It uses ${\cal O}(k\log(n))$ bits of space, and is
updated in ${\cal O}(\log^{2}k)$ operations amortized.

In other words, Barkay, Porat and Shalem [BPS15] have given a deterministic
$k$-sparse recovery algorithm that uses $\widetilde{{\cal O}}(k)$ space.

We also require the following version of the dynamic connectivity result of
Ahn, Guha and McGregor [AGM12].

######  Proposition 4.8.

[AGM12] For every $c\in{\mathbb{N}}$, there exists a 1-pass $\widetilde{{\cal
O}}(n)$-space streaming algorithm in the turnstile model that, in post-
processing, constructs a spanning forest of the input graph with probability
at least $1-1/n^{c}$ in time $\widetilde{{\cal O}}(n)$.

###  4.3 Graphs and Graph Classes

Fix a set of graphs $\mathcal{R}$. Any graph that does not contain a graph in
$\mathcal{R}$ as an induced subgraph is called an $\mathcal{R}$-free graph. We
use $d_{\mathcal{R}}$ to denote the maximum number of vertices among the
graphs in $\mathcal{R}$. We say that $S$ is an $\mathcal{R}$-deletion set of a
graph $G$ if $G-S$ is $\mathcal{R}$-free. We say that a subgraph of $G$ is an
$\mathcal{R}$-subgraph if it is isomorphic to a graph in $\mathcal{R}$.

In the rest of this section, we recall the various graph classes we consider
in this paper and characterizations of these classes that we use in our
algorithms.

Acyclic tournaments are precisely those tournaments that exclude directed
triangles [Die00]. Split graphs are graphs whose vertex set can be partitioned
into two disjoint sets, one of which is a clique and the other is an
independent set. Split graphs are also characterized by the exclusion of
$\\{2K_{2},C_{4},C_{5}\\}$ [Gol04]. Cluster graphs are graphs where every
connected component is a clique. These are also characterized by the exclusion
of $\\{P_{3}\\}$ [Gol04]. Threshold graphs are precisely those graphs that are
characterized by the exclusion of $\\{2K_{2},C_{4},P_{4}\\}$ respectively
[Gol04]. Block graph are graphs in which every biconnected component is a
clique. It is known that they are characterized by the exclusion of
$\\{D_{4},C_{\ell+4,\,\ell\geq 0}\\}$ [BLS99]. Here $D_{4}=K_{4}-e$ for some
edge $e\in E(K_{4})$, and $C_{\ell+4}$ denotes an induced cycle on $\ell+4$
vertices.

##  5 From Recognition to Vertex Deletion to $\mathcal{H}$ with Finitely Many
Obstructions

Recall that for a class $\mathcal{H}$ of graphs, in the Vertex Deletion to
$\mathcal{H}$ problem, the input is a graph $G$ and integer $k$ and the
objective is to decide whether there is a set $S\subseteq V(G)$ of size at
most $k$ such that $G-S\in\mathcal{H}$. The standard parameterization is $k$,
the size of the solution. In this section, we only focus on the case where
$\mathcal{H}$ is characterized by a finite set of forbidden induced subgraphs.

We begin by formally capturing the notion of an efficient semi-streaming
algorithm that recognizes graphs in $\mathcal{H}$.

######  Definition 5.1.

A class of graphs $\mathcal{H}$ admits a $p$-pass recognition algorithm if
there exists a $p$-pass $\widetilde{{\mathcal{O}}}(n)$-space streaming
algorithm with polynomially bounded time between edge updates and in post-
processing that, given a graph $G$, correctly concludes whether or not
$G\in\mathcal{H}$.

###  5.1 The Fixed-parameter Semi-streaming Algorithm for Vertex Deletion to
$\mathcal{H}$

We are now ready to prove our first meta theorem.

See 2.1

###### Proof.

Let $\mathcal{R}$ denote the finite set of graphs excluded by graphs in
$\mathcal{H}$ as induced subgraphs. In what follows, let $d=d_{\mathcal{R}}$
denote the size of the largest graph in the fixed set of graphs $\mathcal{R}$.
Note that $d$ is a constant in this setting. Recall that we know $V(G)$ (and
hence $n$) and $d$ apriori, while $k$ is provided at the beginning of the
stream. Let $\alpha=max\\{dk,k+d\\}$ and
$\beta=d^{2}\cdot\binom{\alpha}{d}\cdot\alpha^{c}\ln n+d$ (where $c$ is the
constant in the ${\cal O}(\cdot)$ notation in the size of the splitter family
as given in Proposition 4.2).

  1. (i)

We construct an $(n,\alpha,\alpha^{2})$-splitter family ${\mathcal{F}}_{1}$ of
size at most $\alpha^{c}\ln n$, which can be constructed in time
$\alpha^{{\cal O}(1)}\cdot n\ln n$ (Proposition 4.2).

  2. (ii)

We construct an $(n,d+1,(d+1)^{2})$-splitter family ${\mathcal{F}}_{2}$ of
size $d^{{\cal O}(1)}\ln n$, which can be constructed in time $d^{{\cal
O}(1)}\cdot n\ln n$.

  3. (iii)

We construct an $(n,\beta,\beta^{2})$-splitter family ${\mathcal{F}}_{3}$ of
size at most $\beta^{c}\ln n$, which can be constructed in time $\beta^{{\cal
O}(1)}\cdot n\ln n$.

Before describing our (post-)processing steps, we define some useful notation.

  * •

For every $f_{1}\in{\mathcal{F}}_{1}$, and $J\subseteq[\alpha^{2}]$, we denote
by $G_{f_{1},J}$ the graph $G[f_{1}^{\mathsf{-1}}(J)]$, i.e., the subgraph
induced by those vertices of $G$ whose image under $f_{1}$ is contained in
$J$.

  * •

Similarly, for every $f_{3}\in{\mathcal{F}}_{3}$, and $J\subseteq[\beta^{2}]$,
we denote by $G_{f_{3},J}$ the graph $G[f_{3}^{\mathsf{-1}}(J)]$, i.e., the
subgraph induced by those vertices of $G$ whose image under $f_{3}$ is
contained in $J$.

  * •

For every $f_{2}\in{\mathcal{F}}_{2}$, $i\in[(d+1)^{2}]$ and graph
$G_{f_{1},J}$, we denote by $G_{f_{2},i,f_{1},J}$ the graph
$G_{f_{1},J}-f_{2}^{\mathsf{-1}}(i)$. That is, the graph obtained from
$G_{f_{1},J}$ by deleting those vertices whose image under $f_{2}$ is $i$.

  * •

Let $\mathcal{X}$ denote the set:

$\\{G_{f_{1},J}\mid f_{1}\in{\mathcal{F}}_{1},J\subseteq[\alpha^{2}],|J|\leq
d\\}$ $\bigcup\\{G_{f_{2},i,f_{1},J}\mid
f_{1}\in{\mathcal{F}}_{1},f_{2}\in{\mathcal{F}}_{2},i\in[(d+1)^{2}],J\subseteq[\alpha^{2}],|J|\leq
d\\}$ $\bigcup\\{G_{f_{3},J}\mid
f_{3}\in{\mathcal{F}}_{3},J\subseteq[\beta^{2}],|J|\leq d\\}.$

Notice that $|\mathcal{X}|\leq|{\mathcal{F}}_{1}|\cdot
d\cdot\binom{\alpha^{2}}{d}+|{\mathcal{F}}_{1}|\cdot|{\mathcal{F}}_{2}|\cdot
d\cdot\binom{\alpha^{2}}{d}\cdot(d+1)^{2}+|{\mathcal{F}}_{3}|\cdot
d\cdot\binom{\beta^{2}}{d}=\widetilde{{\cal O}}((kd)^{{\cal
O}(d)})=\widetilde{{\cal O}}(k^{{\cal O}(1)})$.

Processing the stream: We process the graph stream by running the $p$-pass
recognition algorithm (call this algorithm, $\mathcal{A}$) assumed in the
premise of the theorem for each of the graphs in $\mathcal{X}$. Since
$|\mathcal{X}|=\widetilde{{\cal O}}(k^{{\cal O}(1)})$, the space used by our
algorithm is $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$ as required.
Moreover, for each graph $G^{\prime}\in\mathcal{X}$, the premise guarantees
that we can decide whether $G^{\prime}\in\mathcal{H}$ by running a polynomial-
time post-processing algorithm on the data-structure constructed by Algorithm
$\mathcal{A}$, denoted by $\langle G^{\prime}\rangle$. We call this post-
processing algorithm, Algorithm $\mathcal{B}$. We say that
$\mathcal{B}(\langle G^{\prime}\rangle)=\top$ if $G^{\prime}\in\mathcal{H}$
and $\mathcal{B}(\langle G^{\prime}\rangle)=\bot$ otherwise.

We are now ready to describe our fixed-parameter post-processing algorithm.

Post-processing: For every $f_{1}\in{\mathcal{F}}_{1}$ we construct a vertex
set $Z_{f_{1}}$ as follows. For every $v\in V(G)$, we add $v$ to the set
$Z_{f_{1}}$ if and only if there exists $J\subseteq[\alpha^{2}]$ of size at
most $d$ such that (i) $v\in V(G_{f_{1},J})$, (ii) $\mathcal{B}(\langle
G_{f_{1},J}\rangle)=\bot$ and (iii) for every $f_{2}\in{\mathcal{F}}_{2}$,
$\mathcal{B}(\langle G_{f_{2},f_{2}(v),f_{1},J}\rangle)=\top$. Clearly,
computing $Z_{f_{1}}$ takes $k^{{\cal O}(1)}\cdot n^{{\cal O}(1)}$-time.
Therefore, computing the set $\mathcal{Z}=\\{Z_{f_{1}}\mid
f_{1}\in{\mathcal{F}}_{1}\\}$ can be done in $k^{{\cal O}(1)}\cdot n^{{\cal
O}(1)}$-time and additional $\widetilde{{\cal O}}(k^{{\cal O}(1)}n)$-space.

Let $Z^{\star}=\cup_{Z\in\mathcal{Z}}Z$. We now construct a $d$-set system
${\mathcal{E}}$ with universe $Z^{\star}$ as follows. For every $L\subseteq
Z^{\star}$ of size at most $d$, we add $L$ to ${\mathcal{E}}$ if and only if
there is an $f_{3}\in{\mathcal{F}}_{3}$ and a set $J\subseteq[\beta^{2}]$ of
size at most $d$ such that $J$ is disjoint from $f_{3}(Z^{\star}\setminus L)$
and $\mathcal{B}(\langle G_{f_{3},J}\rangle)=\bot$. This completes the
construction of ${\mathcal{E}}$. Notice that the number of sets in
${\mathcal{E}}$ is bounded by $d\cdot|Z^{\star}|^{d}$.

Finally, we execute the standard linear-space $O^{*}(d^{k})$-time branching
FPT algorithm for $d$-Hitting Set on the instance
$(Z^{\star},{\mathcal{E}},k)$ (see, for example, [CFK+15]) and return the
answer returned by this execution. This completes the description of the
algorithm. We now argue the correctness of this algorithm.

We begin by bounding the size of $Z^{\star}$.

######  Claim 5.2.

$|Z^{\star}|\leq d^{2}\cdot\binom{\alpha^{2}}{d}\cdot\alpha^{c}\ln n$.

###### Proof.

To prove the claim, it suffices to prove that for every
$f_{1}\in{\mathcal{F}}_{1}$ and $J\subseteq[\alpha^{2}]$ such that $|J|\leq
d$, at most $d$ vertices of $G_{f_{1},J}$ can be added to the set $Z_{f_{1}}$.
The claim then follows from the bound of $d\cdot\binom{\alpha^{2}}{d}$ on
possible values of $J$ and the bound of $\alpha^{c}\ln n$ on the size of
$|{\mathcal{F}}_{1}|$.

We say that a vertex $v$ is contributed to $Z_{f_{1}}$ by a set
$J\subseteq[\alpha^{2}]$ of size at most $d$ if $v\in V(G_{f_{1},J})$,
$\mathcal{B}(\langle G_{f_{1},J}\rangle)=\bot$, and for every
$f_{2}\in{\mathcal{F}}_{2}$, $\mathcal{B}(\langle
G_{f_{2},f_{2}(v),f_{1},J}\rangle)=\top$. We now argue that each $J$
contributes at most $d$ vertices to $Z_{f_{1}}$. To do so, we show that a
vertex of $G_{f_{1},J}$ is contributed to $Z_{f_{1}}$ by $J$ precisely if it
intersects every $\mathcal{R}$-subgraph of $G_{f_{1},J}$, that is,
$G_{f_{1},J}-v\in\mathcal{H}$. Since each graph in $\mathcal{R}$ contains at
most $d$ vertices, there can be at most $d$ such vertices.

Suppose to the contrary that a vertex $v\in V(G_{f_{1},J})$ is contributed to
$Z_{f_{1}}$ by $J$ and $G_{f_{1},J}-v$ is not in $\mathcal{H}$. Let $H$ be an
$\mathcal{R}$-subgraph of $G_{f_{1},J}-v$ and let $f_{2}\in{\mathcal{F}}_{2}$
be a function which is injective on $V(H)\cup\\{v\\}$. Since
${\mathcal{F}}_{2}$ is an $(n,(d+1),(d+1)^{2})$-splitter, such an $f_{2}$
exists. However, notice that $\mathcal{B}(\langle
G_{f_{2},f_{2}(v),f_{1},J}\rangle)=\bot$, contradicting our assumption that
$v$ is contributed to $Z_{f_{1}}$ by $J$. This completes the proof of the
claim. ∎

We next observe that if $(G,k)$ is a yes-instance of Vertex Deletion to
$\mathcal{H}$, then it is sufficient to look for our solution within
$Z^{\star}$.

######  Claim 5.3.

Every minimal solution of size at most $k$ in $G$ is contained in $Z^{\star}$.

###### Proof.

Let $S$ be an inclusionwise-minimal solution of size at most $k$ (also called
an $\mathcal{R}$-deletion set). That is, $G-S\in\mathcal{H}$. Let
$\mathcal{T}$ denote a set of obstructions witnessing the minimality of $S$.
In other words, $\mathcal{T}$ is a set of $\mathcal{R}$-subgraphs of $G$ such
that for every graph in $\mathcal{T}$, there is a unique vertex of $S$ that it
intersects. Since $S$ is a minimal $\mathcal{R}$-deletion set, such a set of
$|S|$ $\mathcal{R}$-subgraphs must exist. For each $v\in S$, we denote by
$\mathcal{T}_{v}$ the unique graph in $\mathcal{T}$ that contains $v$. Let
$V(\mathcal{T})$ denote the union of the vertex sets of the subgraphs in
$\mathcal{T}$ and notice that $|V(\mathcal{T})|\leq dk$.

Now, consider a function $f_{1}\in{\mathcal{F}}_{1}$ that is injective on
$V(\mathcal{T})$. Since ${\mathcal{F}}_{1}$ is an $(n,dk,(dk)^{2})$-splitter
family, such an $f_{1}$ exists. We argue that $S\subseteq Z_{f_{1}}$. For each
$v\in S$, let $J_{v}\subseteq[(dk)^{2}]$ denote the set $\\{f_{1}(u)\mid u\in
V(\mathcal{T}_{v})\\}$. Notice that $|J_{v}|\leq d$. Moreover, it must be the
case that for every $v\in S$ , the graph $G[f_{1}^{\mathsf{-1}}(J_{v})]$ has
at least one minimal $\mathcal{R}$-deletion set of size exactly 1 (which is
the vertex $v$) and at most $d$ distinct minimal $\mathcal{R}$-deletion sets
of size exactly 1. The former is a consequence of the fact that
$G[f_{1}^{\mathsf{-1}}(J_{v})]$ is disjoint from $S\setminus\\{v\\}$ and the
latter is a consequence of the fact that the graphs in $\mathcal{R}$ have size
bounded by $d$.

Notice that for each $v\in S$, since $v$ is an $\mathcal{R}$-deletion set of
$G[f_{1}^{\mathsf{-1}}(J_{v})]$, it follows that for every
$f_{2}\in{\mathcal{F}}_{2}$, the graph
$G_{f_{2},f_{2}(v),f_{1},J}\in\mathcal{H}$ and therefore, it must be the case
that $\mathcal{B}(\langle G_{f_{2},f_{2}(v),f_{1},J}\rangle)=\top$. In other
words, the vertex $v$ is contributed to $Z_{f_{1}}$ by $J_{v}$ (see proof of
Claim 5.2 for the definition). Hence, we conclude that $S\subseteq
Z_{f_{1}}\subseteq Z^{\star}$. This completes the proof of the claim. ∎

######  Claim 5.4.

A set $S\subseteq V(G)$ is a solution for the instance $(G,k)$ of Vertex
Deletion to $\mathcal{H}$ if and only if it is a solution for the $d$-Hitting
Set instance $(Z^{\star},{\mathcal{E}},k)$.

###### Proof.

Suppose that $(G,k)$ is a yes-instance of Vertex Deletion to $\mathcal{H}$ and
let $S\subseteq V(G)$ be a solution. By Claim 5.3, we have that $S\subseteq
Z^{\star}$. Now, suppose that $S$ is not a solution for the $d$-Hitting Set
instance $(Z^{\star},{\mathcal{E}},k)$ and let $L\in{\mathcal{E}}$ be a set
disjoint from $S$. Then, by the construction of ${\mathcal{E}}$, we have that
there is a function $f_{3}$ and a set $J\subseteq[\beta^{2}]$ disjoint from
$f_{3}(S)$ such that $\mathcal{B}(\langle G_{f_{3},J})=\bot$. This implies
that there is a subgraph of $G$, i.e., $G_{f_{3},J}$ that contains an
$\mathcal{R}$-subgraph and is disjoint from $S$, a contradiction to our
assumption that $S$ is an $\mathcal{R}$-deletion set in $G$.

Conversely, suppose that $S$ is a solution for the $d$-Hitting Set instance
$(Z^{\star},{\mathcal{E}},k)$, but not an $\mathcal{R}$-deletion set in $G$.
Then, there is an $\mathcal{R}$-subgraph $H$ in $G-S$. Let $L=V(H)\cap
Z^{\star}$. Notice that $|L|\leq d$ since $|V(H)|\leq d$. Moreover, we claim
that in the construction of ${\mathcal{E}}$, we would have added the set $L$
to ${\mathcal{E}}$. To see this, first observe that $Z^{\star}\cup V(H)$ has
size at most $\beta$ and so, there is a function $f_{3}\in{\mathcal{F}}_{3}$
which is injective on $Z^{\star}\cup V(H)$. Therefore, for $J=f_{3}(V(H))$, we
have that $J$ is disjoint from $f_{3}(Z^{\star}\setminus L)$ and
$\mathcal{B}(\langle G_{f_{3},J}\rangle)=\bot$, ensuring that $L$ is contained
in ${\mathcal{E}}$. Since $S$ is a solution for the $d$-Hitting Set instance
$(Z^{\star},{\mathcal{E}},k)$, it follows that $S$ intersects $L$ and hence
also intersects $V(H)$, a contradiction to our assumption that $S$ is not an
$\mathcal{R}$-deletion set in $G$. This completes the proof of the claim. ∎

This completes the proof of Theorem 2.1. ∎

##### Further insights that can be drawn from our proof of Theorem 2.1.

First of all, notice that that in the proof of this theorem, if there is a
randomized $p$-pass recognition algorithm for $\mathcal{H}$ where the post-
processing succeeds with high probability (i.e., with probability at least
$1-1/n^{c}$ for any $c\in{\mathbb{N}}$), then one obtains a randomized
$p$-pass $\widetilde{{\cal O}}(k^{{\cal O}(1)}n)$-space streaming algorithm
for Vertex Deletion to $\mathcal{H}$ with $2^{{\cal O}(k)}n^{{\cal
O}(1)}$-time post-processing and a randomized $p$-pass $\widetilde{{\cal
O}}(k^{{\cal O}(1)}\cdot n)$-space polynomial streaming compression for Vertex
Deletion to $\mathcal{H}$, both of which succeed with high probability.
Similarly, if we have a recognition algorithm for $\mathcal{H}$ only on
insertion-only streams, then we can still use Theorem 2.1, with the caveat
that the resulting algorithms for Vertex Deletion to $\mathcal{H}$ also only
work for insertion-only streams.

Secondly, our algorithm can be used to obtain a polynomial compression from
Vertex Deletion to $\mathcal{H}$ to $d$-Hitting Set. Indeed, if $d^{k}<n$,
then the fixed-parameter post-processing algorithm we use can be seen to
solves the problem in polynomial time, allowing us to produce a trivial
equivalent instance of $d$-Hitting Set as the output. On the other hand, if
$d^{k}>n$, then the size of the $d$-Hitting Set instance
$(Z^{\star},{\mathcal{E}},k)$ is already bounded by $d\cdot|Z^{\star}|^{d}\leq
d\cdot d^{2}\cdot\binom{\alpha^{2}}{d}\cdot\alpha^{c}\ln n=k^{{\cal O}(1)}$ as
required.

###  5.2 Corollaries

######  Lemma 5.5.

For each of the following graph classes $\mathcal{H}$, there is a finite
family $\mathcal{R}$ such that $\mathcal{H}$ is precisely the class of graph
that exclude graphs in $\mathcal{R}$ as induced subgraphs: Acyclic
tournaments, split graphs, threshold graphs and cluster graphs. Moreover, the
first three graph classes have a deterministic 1-pass recognition algorithms
and cluster graphs have a randomized 1-pass recognition algorithm that
succeeds with probability at least $1-1/n^{c}$ for any given $c>0$.

###### Proof.

As discussed in Section 4.3, it is known that acyclic tournaments are
precisely those tournaments that exclude directed triangles [Die00]. Split
graphs, cluster graphs and threshold graphs are characterised by the exclusion
of $\\{2K_{2},C_{4},C_{5}\\},\\{P_{3}\\},$ and $\\{2k_{2},C_{4},P_{4}\\}$
respectively [Gol04]. Furthermore, acyclic tournaments [Die00], split graphs
and threshold graphs [Gol04] have characterizations through their degree
sequence. That is, it is sufficient to know the degrees of each vertex in
order to be able to recognize graphs from these classes. As storing the degree
of each vertex can be trivially done in $\widetilde{{\cal O}}(1)$ space, the
algorithm follows.

For cluster graphs, it is straightforward to see that they can be recognized
from a spanning forest and the degree sequence. Indeed, a graph $G$ is a
cluster graph if and only if for every tree $T$ in a spanning forest of $G$
and every vertex $v\in V(T)$, the degree of $v$ in $G$ is precisely
$|V(T)|-1$. In order to compute a spanning forest of the input graph with high
probability, we use Proposition 4.8. This completes the proof of the lemma. ∎

As immediate corollaries of Theorem 2.1 and Lemma 5.5, we obtain in one shot
the first 1-pass $\widetilde{{\cal O}}(k^{{\cal O}(1)}\cdot n)$-space
streaming algorithms for several vertex-deletion problems such as Feedback
Vertex Set on Tournaments, Split Vertex Deletion, Threshold Vertex Deletion
and Cluster Vertex Deletion (for the last of which the algorithms are
randomized). Moreover, our data structures enable the post-processing for
these algorithms to be done by a single-exponential fixed-parameter algorithm
parameterized by the solution size. Furthermore, notice that the post-
processing time used by the 1-pass recognition algorithms for the above
specific graph classes (in Lemma 5.5) is $\widetilde{{\cal O}}(n)$. Combining
this fact with a closer inspection of the proof of Theorem 2.1 indicates that
the polynomial factor in the running times of the fixed-parameter post-
processing routines for these problems is in fact only $\widetilde{{\cal
O}}(n)$. Thus, we have the following results.

##### Further impact of our techniques in the form of new algorithms for
Vertex Deletion to $\mathcal{H}$ in the static setting.

As discussed above, a closer examination of the proof of Theorem 2.1 implies
an FPT algorithm for Vertex Deletion to $\mathcal{H}$ where the polynomial
factor in the running time is $n\cdot T(n)$ where $T(n)$ is the time required
to recognize a graph in $\mathcal{H}$. In the standard $2^{{\cal
O}(k)}n^{{\cal O}(1)}$ branching algorithm for Vertex Deletion to
$\mathcal{H}$, this factor is at least $T^{\prime}(n)$ where $T^{\prime}(n)$
is the time required to compute an obstruction, i.e., an
$\mathcal{R}$-subgraph in the input graph (assuming $\mathcal{R}$ is the set
of forbidden induced subgraphs for $\mathcal{H}$). The computation of
obstructions for various graph classes is typically achieved through a
certifying recognition algorithm, i.e., an algorithm that returns an
obstruction if it concludes that the input is not in the graph class. However,
designing certifying recognition algorithms that are nearly (or just as)
efficient as a normal recognition algorithm is a non-trivial task. Indeed,
Heggernes and Kratsch [HK07] note that usually different and sometimes deep
insights are needed to produce useful certificates. Therefore, our approach
allows one to improve the polynomial dependence in the standard $2^{{\cal
O}(k)}n^{{\cal O}(1)}$ branching algorithm for Vertex Deletion to
$\mathcal{H}$ in cases where recognition of $\mathcal{H}$ is efficient but the
time required to find an obstruction is worse by a factor of $n$ or more.

##  6 From Reconstruction to Vertex Deletion to $\mathcal{H}$ with Infinitely
Many Obstructions

In this section, we present a meta theorem to reduce the design of streaming
algorithms for deletion to hereditary graph classes to the design of
reconstruction algorithms for these classes.

Towards the presentation of our theorem, we first need to define the meaning
of reconstruction. This is done in the following two definitions.

######  Definition 6.1.

Given an $n$-vertex graph $G$, a succinct representation of $G$ is a data
structure that uses $\widetilde{{\mathcal{O}}}(n)$ space and supports an
$\widetilde{{\mathcal{O}}}(n)$-space polynomial-time procedure that, given two
vertices $u,v\in V(G)$, correctly answers whether $\\{u,v\\}\in E(G)$.

######  Definition 6.2.

For an integer $p\geq 0$, a class of graphs $\mathcal{H}$ admits a $p$-pass
reconstruction algorithm if there exists a $p$-pass
$\widetilde{{\mathcal{O}}}(n)$-space streaming algorithm with polynomial post-
processing time that, given a graph $G$, correctly concludes whether
$G\in\mathcal{H}$, and in case $G\in{\mathcal{H}}$, outputs a succinct
representation of $G$.

We are now ready to prove our meta theorem.

See 2.2

###### Proof.

Let $G$ denote the input graph, which is presented to us as a stream of edges.
Let $n=|V(G)|$. We say that a vertex subset $S\subseteq V(G)$ is a _solution_
to $(G,k)$ if $|S|\leq k$ and $G-S\in\mathcal{H}$. Let ${\cal
F}=\\{F_{1},F_{2},\ldots,F_{t}\\}$ be an $(n,k,2)$-separating family over
$V(G)$. Note that such a family contains $t=k^{{\mathcal{O}}(1)}\log n$ vertex
subsets, and it can be constructed in ${\mathcal{O}}(k^{{\mathcal{O}}(1)}n\log
n)$ time and space (Corollary 4.5). Given the family $\cal F$, for each $1\leq
i\leq t$, let $G_{i}=G[F_{i}]$. For brevity, let $\cal A$ denote the algorithm
of Item 1, which can reconstruct a graph in the class $\mathcal{H}$ in
$p$-passes. And let $\cal B$ denote the static algorithm for Vertex Deletion
to $\mathcal{H}$ of Item 2. Our streaming algorithm for Vertex Deletion to
$\mathcal{H}$ is as follows.

  * •

Streaming Phase. In the streaming phase, we construct a collection of data-
structures from the input stream of edges using the reconstruction algorithm
$\cal A$. We first construct the family $\cal F$ of subsets of $V(G)$. Then
for each graph $G_{i}=G[F_{i}]$, where $1\leq i\leq t$, we apply algorithm
$\cal A$, in parallel. At the end of the stream, for each $G_{i}$, the
algorithm either concludes that $G_{i}\in\mathcal{H}$ and outputs a succinct
representation of it, or else it concludes that $G_{i}\notin\mathcal{H}$. Let
$D_{i}$ denote the data-structure output by $\cal A$ whenever
$G_{i}\in\mathcal{H}$, and $D_{i}=\emptyset$ otherwise. Observe that each
data-structure $D_{i}$ requires $\widetilde{\mathcal{O}}(n)$ space, and there
are at most $t=k^{{\mathcal{O}}(1)}\log n$ of them. We store the family $\cal
F$ and the collection of these data-structures $\\{D_{i}\\}_{1\leq i\leq t}$.
Note that, we require $p$-passes and
$\widetilde{\mathcal{O}}(k^{{\mathcal{O}}(1)}\cdot g(k)\cdot n)$ space in the
streaming phase.

  * •

Post-processing Phase. Let us now describe the post-processing phase of our
algorithm. Let us define a graph $\widetilde{G}$ as follows:
$V(\widetilde{G})=V(G)$ and $E(\widetilde{G})=\bigcup_{1\leq i\leq
t\,:\,D_{i}\neq\emptyset}E(G_{i})$. Observe that $\widetilde{G}$ is a subgraph
of $G$, although it may not be an induced subgraph. Note that the graph
$\widetilde{G}$ is not explicitly constructed, but a succinct representation
of $\widetilde{G}$ is obtained from the data-structures $\\{D_{i}\mid 1\leq
i\leq t\\}$ as follows: given any two vertices $u,v\in V(G)$, to determine if
$\\{u,v\\}\in E(\widetilde{G})$, we query every $D_{i}$ for the edge
$\\{u,v\\}$; if any one of these queries succeed we output that $\\{u,v\\}$ is
an edge in $\widetilde{G}$, otherwise we output that $\\{u,v\\}$ is a non-edge
of $\widetilde{G}$. Next, let $E^{\prime}=\\{\\{u,v\\}\in V\times V\mid u\neq
v\text{ and }\forall~{}1\leq i\leq t\text{ such that
}D_{i}\neq\emptyset,~{}|F_{i}\cap\\{u,v\\}|\leq 1\\}$. Let
$G^{\prime}=(V(G),E^{\prime})$, and note that it is not necessarily a subgraph
of $G$ (although it can be shown to contain every edge in $E(G)\setminus
E(\widetilde{G})$). The graph $G^{\prime}$ is also not explicitly constructed,
but it is reconstructed from the vertex subsets $\\{F_{i}\mid 1\leq i\leq
t,~{}D_{i}\neq\emptyset\\}$.

To construct a solution to $(G,k)$, we do the following. We first enumerate
every minimal vertex cover of size at most $k$ in the graph $G^{\prime}$. Note
that there are at most $2^{k}$ minimal vertex covers of $G^{\prime}$ of size
at most $k$ [CFK+15]. This is accomplished by a simple branching algorithm,
that processes the edges of $G^{\prime}$ one by one. This algorithm runs in
$2^{k}\cdot n^{{\mathcal{O}}(1)}$ time and $\widetilde{\mathcal{O}}(n)$ space.
For each vertex cover $X$ of $G^{\prime}$ of size at most $k$ produced by the
above enumeration, we apply the algorithm $\cal B$ to
$(\widetilde{G}-X,k-|X|)$, and either obtain a solution $\widetilde{S}$ to
$(\widetilde{G}-X,k-|X|)$ or no such solution exists. If we do indeed find a
solution $\widetilde{S}$ to $(\widetilde{G}-X,k-|X|)$, then we output
$\widetilde{S}\cup X$ as the solution to $(G,k)$. Otherwise, for every $X$ the
algorithm $\cal B$ fails to find a solution to $(G-X,k-|X|)$, and we output
that there is no solution to $(G,k)$. This completes the description of the
algorithm.

It clear that the above algorithm requires $p$-passes, and used
${\mathcal{O}}(n\cdot g(k)\cdot k^{{\mathcal{O}}(1)})$ space and $(2^{k}\cdot
f(k))\cdot n^{{\mathcal{O}}(1)}$ time. It only remains to argue the
correctness of our algorithm. Towards this, first recall that $\cal F$ has the
following property: for any pair of vertices $u,v$ and any $S\subseteq V(G)$
such that $u,v\notin V(G)$ and $|S|\leq k$, there is a subset $F_{i}\in{\cal
F}$ such that $u,v\in F_{i}$ and $S\cap F_{i}=\emptyset$. Next, we have the
following claim: If $S$ is a solution to $(G,k)$ and $e=\\{u,v\\}\in
E^{\prime}$, then $|S\cap\\{u,v\\}|\geq 1$. That is, we claim that $S$ is a
(not necessarily minimal) vertex cover for $G^{\prime}$. We prove this claim
using the properties of the $(n,k,2)$-separation family $\cal F$ over $V(G)$.
Suppose the claim is false, and let $\\{u,v\\}\in E^{\prime}$ such that
$S\cap\\{u,v\\}=\emptyset$. Then there exists $F_{i}\in{\cal F}$ such that
$\\{u,v\\}\subseteq F_{i}$ and $S\cap F_{i}=\emptyset$. Observe that
$G_{i}=G[F_{i}]$ is an induced subgraph of $G-S$, and $G-S\in\mathcal{H}$.
Since $\mathcal{H}$ is hereditary, $G_{i}\in\mathcal{H}$ as well. Therefore,
$D_{i}\neq\emptyset$, and hence by the construction of $E^{\prime}$, we have
$\\{u,v\\}\notin E^{\prime}$. This is a contradiction.

Next, consider any vertex cover $X$ of $G^{\prime}$. We claim that
$\widetilde{G}-X=G-X$. First observe that, as $V(G)=V(\widetilde{G})$, we have
$V(G)\setminus X=V(\widetilde{G})\setminus X$. Next suppose that there are
$u,v\in V(\widetilde{G})\setminus X$ such that $\\{u,v\\}\in E(G)\setminus
E(\widetilde{G})$. Then by the definition of $\widetilde{G}$, there is no
vertex subset $F_{i}\in\cal F$ such that $G_{i}\in\mathcal{H}$ and $u,v\in
F_{i}$. In other words, for any $F_{j}\in\cal F$ such that $u,v\in F_{j}$, we
have $G_{j}\notin\mathcal{H}$ and hence $D_{j}=\emptyset$. Hence, by
definition $\\{u,v\\}\in E^{\prime}$, and therefore
$X\cap\\{u,v\\}\neq\emptyset$. But this is again a contradiction. Hence we
conclude $\widetilde{G}-X=G-X$.

Now, let us argue that $(G,k)$ has a solution if and only if our algorithm
concludes that there is a solution to $(G,k)$. In the forward direction,
consider a solution $S^{\star}$ to $(G,k)$. Let $Y\subseteq S^{\star}$ be a
minimal subset that is a vertex-cover of $G^{\prime}$, and note that $|Y|\leq
k$. Then as $\mathcal{H}$ is hereditary, $S^{\star}-Y$ is a solution to the
instance $(G-Y,k-|Y|)$. Recall that our post-processing algorithm enumerates
all minimal vertex covers of $G^{\prime}$ of size at most $k$, and in
particular $Y$. Then for the vertex cover $Y$ of $G^{\prime}$, it computes a
solution to $(\widetilde{G}-Y,k-|Y|)$ using algorithm $\cal B$. Here, recall
that $\widetilde{G}-Y=G-Y$ and hence it admits a solution
$\widetilde{S}=S^{\star}\setminus Y$ of size at most $k-|Y|$. Therefore, by
invoking algorithm $\cal B$ on $(\widetilde{G}-Y,k-|Y|)$, we correctly
conclude that $(G,k)$ admits a solution. In the reverse direction, suppose
that our algorithm outputs $\widetilde{S}\cup X$ as a solution to $(G,k)$,
where $X$ is a vertex cover of $G^{\prime}$ and $\widetilde{S}$ is a solution
to $(\widetilde{G}-X,k-|X|)$. Recall that $\widetilde{G}-X=G-X$, and hence
$G-(\widetilde{S}\cup X)=\widetilde{G}-(\widetilde{S}\cup X)$. Hence it
follows that $G-(\widetilde{S}\cup X)\in\mathcal{H}$, i.e. $\widetilde{S}\cup
X$ is a solution $(G,k)$. This concludes the proof of this lemma. ∎

Finally, we remark that the results of this section also hold for digraphs
(with the same proof).

###  6.1 Proper Interval Vertex Deletion in ${\mathcal{O}}(\log^{2}n)$ Passes

Formally, the class of proper interval graphs can be defined as follows.

######  Definition 6.3 (Proper Interval Graph).

A graph $G$ is a proper interval graph if there exists a function $f$ that
assigns to each vertex in $G$ an open interval of unit length on the real line
such that every two vertices in $G$ are adjacent if and only if their
intervals intersect. Such a function $f$ is called a representation, and given
a vertex $v\in V(G)$, we let $\mathsf{begin}_{f}(v)$ and $\mathsf{end}_{f}(v)$
denote the beginning and end of the interval assigned to $v$ by $f$ (as if it
was closed).

Equivalently, the demand that each interval will be of unit length can be
replaced by the demand that no interval will properly contain another
interval.222To be more precise, when intervals are required to have unit
length, then the graph is called a unit interval graph, and when intervals
should not properly contain one another, it is called a proper interval graph.
However, these two notions are known to be equivalent.

We remark that whenever we have a representation, we can slightly perturb it
so that no two vertices will be assigned the same interval, or, more
generally, no two endpoints (start or end) of intervals will coincide.
Further, given a representation of the second “type” (where intervals can have
different lengths), it is possible to construct a representation of the first
“type” with the same ordering of the starting and ending points of all
intervals assigned, and that every representation of the first “type” is also
of the second “type”.

The purpose of this section is to prove the following theorems. The second
theorem implies the first but requires additional arguments.

######  Theorem 6.4.

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

To prove this lemma, we present the reconstruction and post-processing
algorithms for the class of proper interval graphs as required by Theorem 2.2.

####  6.1.1 Reconstruction Algorithm

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

######  Lemma 6.5.

The class of proper interval graphs admits an ${\mathcal{O}}(\log^{2}n)$-pass
reconstruction algorithm.

We first observe that it suffices to focus on the class of connected proper
interval graphs. Indeed, this follows by running an algorithm for the
connected case on all connected components simultaneously, and answering “yes”
if and only if the answer to all components is “yes”; in case the answer is
“yes”, the output representation is the union of the representations of the
connected components.

######  Observation 6.6.

The class of connected proper interval graphs admits an $x$-pass
reconstruction algorithm with polynomial post-processing time, then so does
the class of proper interval graphs.

In particular, dealing with connected proper interval graphs allows us to make
use of the following result regarding the number of connected components left
after the removal of any closed neighborhood.

######  Lemma 6.7.

Let $G$ be a connected proper interval graph with representation $f$. For any
$v\in V(G)$, the graph $G-N[v]$ consists of at most two connected components:
one on the set of vertices whose intervals end at or before the interval of
$v$ starts (according to $f$), and the other on the set of vertices whose
intervals start at or after the interval of $v$ ends.

###### Proof.

Let $L$ be the subgraph of $G$ induced by the set of vertices whose intervals
end at or before the interval of $v$ starts. Let $R$ be the subgraph of $G$
induced the set of vertices whose intervals start at or after the interval of
$v$ ends. Note that every vertex not in $V(L)\cup V(R)$ has an interval that
intersects that of $v$, and the set that consists of these vertices is
precisely $N[v]$. Further, the intervals of two vertices that belong to
different graphs among $L$ and $R$ do not intersect, and hence they are not
neighbors. So, to conclude the proof, it remains to argue that each graph
among $L$ and $R$ is connected. We will only show this for $L$ as the proof
for $R$ is symmetric. Consider two vertices $u,v\in V(L)$. Then, because $G$
is connected, there exists a (simple) path $P$ between $u$ and $v$ in $G$. If
$P$ belongs to $L$, we are done. Else, $P$ can be rewritten as $u-P_{1}-x-y-
P_{2}-z-w-P_{3}-v$ (possibly $y=z$ and $P_{1},P_{2},P_{3}$ can be empty) where
$V(P_{1})\cup V(P_{3})\cup\\{x,w\\}\subseteq V(L)$ and $y,z\in N[v]$. So, (i)
$\mathsf{start}_{f}(x)<\mathsf{start}_{f}(y)<\mathsf{end}_{f}(x)<\mathsf{start}_{f}(v)$,
and (ii)
$\mathsf{start}_{f}(w)<\mathsf{start}_{f}(z)<\mathsf{end}_{f}(w)<\mathsf{start}_{f}(v)$.

Without loss of generality, suppose that (iii)
$\mathsf{start}_{f}(z)<\mathsf{start}_{f}(y)$. We claim that
$\mathsf{start}_{f}(x)<\mathsf{start}_{f}(z)<\mathsf{end}_{f}(x)$, which will
imply (by (ii)) that $f(x)$ and $f(w)$ intersect. Clearly,
$\mathsf{start}_{f}(x)<\mathsf{start}_{f}(z)$ because $f(x)$ ends before
$f(v)$ starts while $f(z)$ does not. Moreover,
$\mathsf{start}_{f}(z)<\mathsf{end}_{f}(x)$, because otherwise, by (iii),
$\mathsf{end}_{f}(x)<\mathsf{start}_{f}(z)<\mathsf{start}_{f}(y)$ which is a
contradiction to (i). So, $u-P_{1}-x-w-P_{3}-v$ is a path within $L$. ∎

In order to proceed, we need to define an annotated version of the
reconstruction problem, where we only seek proper interval graphs with
representations that comply with a given order on the intervals assigned to
vertices. This annotation will be encountered since a step (which will be
encapsulated by a lemma ahead) of our algorithm will reduce a problem instance
to smaller annotated instances (and will reduce these smaller annotated
instances to even smaller annotated instances, and so on, based on divide on
conquer).

######  Definition 6.8.

The Annotated Proper Interval Reconstruction problem is defined as follows.
Given a graph $G$ and a partial ordering $<$ on $V(G)$, decide whether $G$ is
a proper interval graph that admits a representation $f$ where for every
different $u,v\in V(G)$, no endpoint of $f(u)$ coincides with an endpoint of
$f(v)$, and such that if $u<v$, then we have that
$\mathsf{begin}_{f}(u)<\mathsf{begin}_{f}(v)$ (such a representation is said
to comply with $<$). Moreover, in case $G$ is such a graph, output a succinct
representation of $G$ that is the permutation on
$\\{\mathsf{begin}_{f}(v):v\in V(G)\\}\cup\\{\mathsf{end}_{f}(v):v\in V(G)\\}$
corresponding to $f$.333Here, we mean that intervals are scanned from left to
right. Note that this is indeed a succinct representation because it takes
space $\widetilde{{\mathcal{O}}}(n)$, and to check whether two vertices $u,v$
are neighbors, we just need to check whether
$\mathsf{begin}_{f}(v)<\mathsf{begin}_{f}(u)<\mathsf{end}_{f}(v)$ or
$\mathsf{begin}_{f}(u)<\mathsf{begin}_{f}(v)<\mathsf{end}_{f}(u)$.

From now on, as we justify immediately, our objective will be to prove the
following lemma.

######  Lemma 6.9.

The Annotated Proper Interval Reconstruction problem admits an
${\mathcal{O}}(\log^{2}n)$-pass algorithm.

Indeed, to prove Lemma 6.5, it suffices to prove Lemma 6.9 because we can
choose the order $<$ to define all vertices as incomparable, and thereby make
$<$ immaterial.

The proof of Lemma 6.9 will be based on an inductive argument. The main part
of the proof is given by Lemma 6.13 ahead. Before this, we state the following
definition and lemmas that will be used in its proof.

######  Definition 6.10.

Let $G$ be an $n$-vertex graph. A vertex $v$ is a middle vertex if the size of
every connected component of $G-N[v]$ is at most $\frac{9}{10}n$.

######  Lemma 6.11.

Let $G$ be a connected proper interval graph. Then, by selecting a vertex
$v\in V(G)$ uniformly at random, $v$ is a middle vertex with probability at
least $\frac{4}{5}$.

###### Proof.

Let $f$ be a representation of $G$, and $n=|V(G)|$. For every vertex $v$, let
$L_{v}$ and $R_{v}$ be the first and second connected components (which may be
empty) defined in Lemma 6.7. Order $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ so
that $f(v_{i})$ starts at or before $f(v_{j})$ starts. Then, for any
$i\in\\{1,2,\ldots,n\\}$, $|V(L_{v_{i}})|\leq i-1$ and $|V(R_{v_{i}})|\leq
n-i$. So, whenever $\frac{1}{10}\leq i\leq\frac{9}{10}$,
$|V(L_{v_{i}})|\leq\frac{9}{10}n$ and $|V(R_{v_{i}})|\leq\frac{9}{10}n$, and
then $v_{i}$ is a middle vertex. So, there are at least $\frac{4}{5}n$ mid
vertices, which implies the desired probability. ∎

######  Lemma 6.12.

There exists a 1-pass $\widetilde{{\mathcal{O}}}(n)$-space polynomial-time
algorithm that given two graphs $G$ and $H$ on the same vertex set $V$ and a
succinct representation of $H$ (where the representation is stored in memory
and not part of the stream), decides whether $G$ is equal to $H$.444That is,
for any pair of vertices $u,v\in V$, we have that $u,v$ are adjacent in $G$ if
and only if they are adjacent in $H$.

###### Proof.

The algorithm works as follows. Using one pass on the stream, it computes the
degree of every vertex in $G$, and also for each edge in $G$ (when it appears
in the stream), it checks that it belongs to $H$ using the succinct
representation and if not it returns that $G\neq H$. Afterwards, it computes
the degree of every vertex in $H$ (using the succinct representation) and
checks that it equals the degree computed for $G$, and if not then it returns
that $G\neq H$. At the end, it returns that $G=H$.

Clearly, this is a 1-pass $\widetilde{{\mathcal{O}}}(n)$-space polynomial-time
algorithm. Moreover, correctness follows by observing that $G=H$ if and only
if $E(G)\subseteq E(H)$ and the degree of every vertex is the same in $G$ and
$H$. ∎

We now turn to state and proof the aforementioned Lemma 6.13.

######  Lemma 6.13.

Let $n,s\in\mathbb{N}$. Suppose that Annotated Proper Interval Reconstruction
admits a $5\cdot s\cdot\log_{\frac{10}{9}}\widetilde{n}$-pass algorithm on
$\widetilde{n}$-vertex graphs where $\widetilde{n}\leq\frac{9}{10}n$ with
success probability at least
$1-(\frac{1}{5})^{s}\cdot\widetilde{n}\log_{\frac{10}{9}}\widetilde{n}$. Then,
Annotated Proper Interval Reconstruction admits a $5\cdot
s\cdot\log_{\frac{10}{9}}n$-pass algorithm on $n$-vertex graphs with success
probability at least $1-(\frac{1}{5})^{s}\cdot n\log_{\frac{10}{9}}n$.555We
remark that the constant $5$ was not optimized. For example, just by
sacrificing modularity and not checking the validity of our reconstruction
here (at each step) but only once in the end, it reduces to $4$.

###### Proof.

Let $\mathfrak{A}$ denote the algorithm guaranteed by the supposition of the
lemma.

Algorithm. The algorithm works as follows.

  1. 1.

For $i=1,2,\ldots,s$:

    1. (a)

Select uniformly at random a vertex $v^{\star}\in V(G)$.

    2. (b)

Go over the stream once to compute $N(v^{\star})$.

    3. (c)

Go over the stream once using a connectivity sketch to compute the connected
components of $G-N[v^{\star}]$. By Lemma 6.7, there are at most two such
components, which we denote by $C_{1}$ and $C_{2}$ (where possibly one or both
of them are empty).

    4. (d)

If $|V(C_{1})|\leq\frac{9}{10}n$ and $|V(C_{2})|\leq\frac{9}{10}n$, then go
directly to Step 3.

  2. 2.

Return failure.

  3. 3.

Rename $C_{1}$ and $C_{2}$ as $L$ and $R$ (where $C_{1}$ can be either) such
that for every pair of comparable vertices $u,w\in V(G)$ such that $u<w$, at
least one of the following holds: (i) $u\in V(L)$; (ii) $w\in V(R)$; (iii)
$u,w\in N[v]$. If this is not possible, then return “no-instance”. Also,
denote $M=G[N[v]]$.

  4. 4.

Go over the stream once to compute for every $u\in V(G)$: $d_{L}(u)=|N(u)\cap
V(L)|$, $d_{R}(u)=|N(u)\cap V(R)|$ and $d_{M}(u)=|N(u)\cap V(M)|$.

  5. 5.

Here, we consider several cases:

    1. (a)

$V(L)\neq\emptyset$. Among all vertices $u\in M$ with maximum $d_{L}(u)$ and
that are smallest by $<$, let $a$ be one with minimum $d_{M}(u)$ (if there is
more than one choice, then select one arbitrarily). If $a$ cannot be chosen
(i.e., there is no vertex that has maximum $d_{L}(u)$ and is simultaneously
smallest by $<$ among all vertices in $M$), then return “no-instance”.
Afterwards:

      1. i.

Go over the stream once to compute $N(a)$.

      2. ii.

If $M\setminus N[a]\neq\emptyset$, then among all vertices $u\in M\setminus
N[a]$ with maximum $d_{R}(u)$ and that are largest by $<$, let $b$ be one with
minimum $d_{M}(u)$ (if there is more than one choice, then select one
arbitrarily). If $b$ cannot be chosen (i.e., there is no vertex that has
maximum $d_{R}(u)$ and is simultaneously largest by $<$ among all vertices in
$M\setminus N[a]$), then return “no-instance”.

      3. iii.

Else, among all vertices $u\in M$ with maximum $d_{R}(u)$ and that are largest
by $<$, choose some vertex $b$ arbitrarily. If $b$ cannot be chosen (i.e.,
there is no vertex that has maximum $d_{R}(u)$ and is simultaneously largest
by $<$ among all vertices in $M$), then return “no-instance”.

    2. (b)

$V(L)=\emptyset$ and $V(R)\neq\emptyset$. Among all vertices $u\in M$ with
maximum $d_{R}(u)$ and that are largest by $<$, let $b$ be one with minimum
$d_{M}(u)$ (if there is more than one choice, then select one arbitrarily). If
$b$ cannot be chosen (i.e., there is no vertex that has maximum $d_{R}(u)$ and
is simultaneously largest by $<$ among all vertices in $M$), then return “no-
instance”. Afterwards:

      1. i.

Go over the stream once to compute $N(b)$.

      2. ii.

If $M\setminus N[b]\neq\emptyset$, then among all vertices $u\in M\setminus
N[b]$ with maximum $d_{L}(u)$ and that are smallest by $<$, let $a$ be one
with minimum $d_{M}(u)$ (if there is more than one choice, then select one
arbitrarily). If $a$ cannot be chosen (i.e., there is no vertex that has
maximum $d_{R}(u)$ and is simultaneously smallest by $<$ among all vertices in
$M\setminus N[b]$), then return “no-instance”.

      3. iii.

Else, among all vertices $u\in M$ with maximum $d_{R}(u)$ and that are
smallest by $<$, choose some vertex $a$ arbitrarily. If $a$ cannot be chosen
(i.e., there is a conflict between having minimum $d_{M}(u)$ and being
smallest by $<$), then return “no-instance”.

    3. (c)

$V(L)=V(R)=\emptyset$. Among all vertices $u\in M$ that are smallest by $<$,
let $a$ be one of minimum $d_{M}(u)$ (if there is more than one choice, then
select one arbitrarily). Repeat Steps 5(a)i, 5(a)ii and 5(a)iii to define $b$.

  6. 6.

Call the algorithm in the supposition of the lemma on $L$ with $<_{L}$ defined
as follows: for all $u,v\in V(L)$, if $u<v$ or $d_{M}(u)<d_{M}(v)$, then
$u<_{L}v$. If a conflict arises in the definition of $<_{L}$ or the algorithm
returns “no-instance”, then return “no-instance”, and else let
$\mathsf{Perm}_{L}$ be the permutation it returns (supposedly corresponding to
some representation $g_{L}$ of $L$ that complies with $<_{L}$).
Simultaneously,666That is, use one pass on $G$ to simulate one pass on $L$ as
well as one pass on $R$. call the algorithm in the supposition of the lemma on
$R$ with $<_{R}$ defined as follows: for all $u,v\in V(R)$, if $u<v$ or
$d_{M}(u)>d_{M}(v)$, then $u<_{R}v$. If a conflict arises in the definition of
$<_{R}$ or the algorithm “no-instance”, then return “no-instance”, and else
let $\mathsf{Perm}_{R}$ be the permutation it returns (supposedly
corresponding to some representation $g_{R}$ of $R$ that complies with
$<_{R}$).

  7. 7.

Now, for some (unknown and possibly incorrect) representation $f$, we define
an ordering on starting points, $\mathsf{begin}_{f}(\cdot)$, as follows.
First, the starting points of the intervals of all vertices in $L$ and $R$ are
ordered exactly as in $\mathsf{Perm}_{L}$ and $\mathsf{Perm}_{R}$, and all
starting points of the intervals of vertices in $L$ appear before those in
$M$, and for those in $M$, they appear before those in $R$. Internally, the
starting points of the vertices in $M$ are ordered as follows. For every
$u,v\in M$, if at least one of the following conditions is true, then
$\mathsf{begin}_{f}(u)<\mathsf{begin}_{f}(v)$:

    1. (a)

$u<v$ (where $<$ is the input partial order on $V(G)$);

    2. (b)

$d_{L}(u)>d_{L}(v)$;

    3. (c)

$d_{R}(u)<d_{R}(v)$;

    4. (d)

$u,v\in N(a)$ and $d_{M}(u)<d_{M}(v)$;

    5. (e)

$u,v\notin N(a)$ and $d_{M}(u)>d_{M}(v)$;

    6. (f)

$u\in N(a)$ and $v\notin N(a)$.

In case a conflict occurs, that is, the above conditions imply that both
$\mathsf{begin}_{f}(u)<\mathsf{begin}_{f}(v)$ and
$\mathsf{begin}_{f}(v)<\mathsf{begin}_{f}(u)$ for some $u,v\in V(G)$, then we
return “no-instance”. Besides this, ties are broken arbitrarily.

  8. 8.

We proceed by inserting the ending points of the intervals of all vertices in
$V(L)\cup V(R)$ within the ordering of the starting points. First, the ending
points of the intervals of all vertices in $L$ with no neighbors in $M$ are
ordered exactly as in $\mathsf{Perm}_{L}$ (and are inserted before the
starting points of the intervals of all vertices in $M$). Second, the ending
points of the intervals of all vertices in $R$ are ordered exactly as in
$\mathsf{Perm}_{R}$ (and are inserted after the starting points of the
intervals of all vertices in $M$). Third, for every vertex $v\in V(L)$ with
neighbours in $M$, insert $\mathsf{end}_{f}(v)$ between
$\mathsf{begin}_{f}(x)$ and $\mathsf{begin}_{f}(y)$ where $x$ is the
$d_{M}(v)$-th vertex in $M$ according to the already established ordering of
starting points of intervals, and $y$ is the vertex whose starting point is
ordered immediately after that of $x$ (which might not exist, in which case
$\mathsf{end}_{f}(v)$ is just placed after all starting points of intervals of
vertices in $M$ and before all those of vertices in $R$).

  9. 9.

Lastly, we insert the ending points of the intervals of all vertices in $V(M)$
within the ordering of the starting points. For every vertex $v\in V(M)$ with
$d_{R}(v)>0$, insert $\mathsf{end}_{f}(v)$ between $\mathsf{begin}_{f}(x)$ and
$\mathsf{begin}_{f}(y)$ where $x$ is the $d_{R}(v)$-th vertex in $R$ according
to the already established ordering of starting points of intervals, and $y$
is the vertex whose starting point is ordered immediately after that of $x$
(which might not exist, in which case $\mathsf{end}_{f}(v)$ is just placed
after all starting points). Additionally, for every vertex $v\in V(M)$ with
$d_{R}(v)=0$, if the starting point of $f(v)$ was placed after the starting
point of $f(v^{\star})$, then place the ending point of $f(v)$ after the
starting point of all vertices in $M$ but before those of all vertices in $R$;
else, insert $\mathsf{end}_{f}(v)$ between $\mathsf{begin}_{f}(x)$ and
$\mathsf{begin}_{f}(y)$ where $x$ is the $d_{M}(v)$-th vertex in $M$ according
to the already established ordering of starting points of intervals, and $y$
is the vertex whose starting point is ordered immediately after that of $x$
(which might not exist, in which case $\mathsf{end}_{f}(v)$ is just placed
after all starting points of intervals of vertices in $M$ and before all those
of vertices in $R$).

  10. 10.

To complete the ordering of all starting points and ending points, it remains
only to define the ordering between ending points that were inserted between
the same two starting points—for every two such ending points
$\mathsf{end}_{f}(u)$ and $\mathsf{end}_{f}(v)$, we order
$\mathsf{end}_{f}(u)$ before $\mathsf{end}_{f}(v)$ if and only
$\mathsf{begin}_{f}(u)$ before $\mathsf{begin}_{f}(v)$.

  11. 11.

Check whether in the constructed succinct representation (that is the ordering
of starting and ending points) no interval properly contains another. If this
check fails, return “no-instance”.

  12. 12.

Go over the stream once using the algorithm in Lemma 6.12 to verify whether
the graph given by the constructed succinct representation yields a graph
equal to $G$. If the answer is yes, then return “yes-instance” and the
representation, and otherwise return “no-instance”.

This completes the description of the algorithm.

Space, Time, Number of Passes and Success Probability. Clearly, the space
complexity of the algorithm is $\widetilde{O}(n)$ and it works in polynomial
time. Regarding the number of passes, observe that the number of passes it
makes is at most

$\begin{array}[]{l}2s+3+\max_{\frac{1}{10}n\leq\ell\leq\frac{9}{10}n}5s\log_{\frac{10}{9}}\ell\\\
\leq
5s(1+\max_{\frac{1}{10}n\leq\ell\leq\frac{9}{10}n}\log_{\frac{10}{9}}\ell)\\\
=5s(1+\log_{\frac{10}{9}}\frac{9}{10}n)\\\
=5s\log_{\frac{10}{9}}n.\end{array}$

Moreover, by Lemma 6.11 and union bound, its failure probability is at most

$\begin{array}[]{l}\vskip 3.0pt plus 1.0pt minus
1.0pt(\frac{1}{5})^{s}+\max_{\frac{1}{10}n\leq\ell\leq\frac{9}{10}n}((\frac{1}{5})^{s}\cdot\ell\log_{\frac{10}{9}}\ell+(\frac{1}{5})^{s}\cdot(n-\ell)\log_{\frac{10}{9}}(n-\ell))\\\
\vskip 3.0pt plus 1.0pt minus
1.0pt\leq(\frac{1}{5})^{s}+(\frac{1}{5})^{s}\cdot\max_{\frac{1}{10}n\leq\ell\leq\frac{9}{10}n}(\ell\log_{\frac{10}{9}}\frac{9}{10}n+(n-\ell)\log_{\frac{10}{9}}\frac{9}{10}n)\\\
=(\frac{1}{5})^{s}+(\frac{1}{5})^{s}\cdot
n\log_{\frac{10}{9}}\frac{9}{10}n\leq(\frac{1}{5})^{s}\cdot
n\log_{\frac{10}{9}}n.\end{array}$

So, the success probability is at least $1-(\frac{1}{5})^{s}\cdot
n\log_{\frac{10}{9}}n$ as claimed.

Correctness: Reverse Direction. For correctness, first observe that by Steps
11 and 12, if the algorithm returns “yes-instance”, then this is correct and
so does the representation (because the answer and representation are verified
in these steps). The difficult part in the proof is to show the other
direction.

Correctness: Forward Direction. In the rest of the proof, we assume that $G$
is a proper interval graph that admits a representation that complies with
$<$, and aim to prove that in this case the algorithm returns “yes-instance”
(in which case, due to our verification, the representation will be correct).
To this end, we need to show that there exists some representation for $G$
that complies with $<$ and with our ordering of starting and ending
points—then, necessarily, the checks in the last two steps succeed and the
algorithm returns “yes-instance”. For this, we will have a sequence of claims
that will justify the decisions made in the different steps of the algorithm.
We begin by justifying Step 3 with the following claim, whose correctness
follows directly from the definition of a representation, and by observing
that taking the mirror image of a representation also gives a representation,
but which may not comply with $<$.

######  Claim 6.14.

The algorithm does not answer “no-instance” in Step 3, and there exists a
representation of $G$ that complies with $<$ and where all intervals of
vertices in $L$ begin before all intervals of vertices in $M$ begin, and all
intervals of vertices in $M$ begin before all intervals of vertices in $R$
begin.

Next, we claim that the vertices $a$ and $b$ have leftmost and rightmost
intervals among the vertices in $M$, addressing Step 5.

######  Claim 6.15.

The algorithm does not answer “no-instance” in Step 3, and there exists a
representation of $G$ that satisfies the conditions in Claim 6.14 and where
$a$ (resp. $b$) is the vertex in $M$ whose interval’s starting point is
leftmost (resp. rightmost).

Figure 1: The sub-interval where $y$ and $y$ intersect is flanked by dashed
yellow lines, and it is a sub-interval of $x$.

###### Proof.

We only consider now representations that satisfy the conditions in Claim 6.14
(and we know that at least one such representation exists). Clearly, given two
vertices $x,y$ in $M$ such that the interval of $x$ (in any of the
representations we consider) starts before that of $y$, it must be that (i)
$x$ has at least as many neighbors in $L$ as $y$, (ii) $y$ has at least as
many neighbors as $x$ in $R$, and (iii) either $x,y$ are incomparable or
$x<y$. Moreover, vertices in $M$ that have the same number of neighbors in $L$
(resp. $R$) have also the exact same neighbors in $L$ (resp. $R$)—to see this,
suppose that the interval of $y$ (resp. $x$) starts before that of $x$ (resp.
$y$), let $u$ be a neighbor of $y$ (resp. $x$) in $L$, and notice that every
intersection point of the intervals of $y$ (resp. $x$) and $u$ also belongs to
the interval of $x$ (resp. $y$); see Fig. 1 (the case of $R$ is symmetric). We
also note that no vertex can have neighbors in both $L$ and $R$.

We proceed to present arguments that justify the choices we make based on
$d_{M}(\cdot)$. For this purpose, let $a^{\prime}$ and $b^{\prime}$ be the
vertices in $M$ having the leftmost and rightmost intervals in some
representation that does not assign the same interval to two different
vertices. Then, notice that $V(M)\subseteq N[a^{\prime}]\cup N[b^{\prime}]$
(see Fig. 2). Moreover, notice that for every $u\in N(a^{\prime})\cap V(M)$,
we have that $N[a^{\prime}]\cap V(M)\subseteq N[u]\cap V(M)$—indeed, the
interval of every vertex in $N(a^{\prime})\cap V(M)$ must intersect the (open)
right endpoint of the interval of $a^{\prime}$, and the interval of $u$
intersects it as well, and hence the intervals of the neighbor and of $u$
intersect each other (see Fig. 2). Symmetrically, for every $u\in
N(b^{\prime})\cap V(M)$, we have that $N(b^{\prime})\cap V(M)\subseteq
N(u)\cap V(M)$. In particular, this means that when we look at vertices from
left to right according to the starting point of their intervals,
$d_{M}(\cdot)$ is non-decreasing, and after reaching some peak, becomes non-
increasing (see Fig. 2). Furthermore, two vertices that have minimum
$d_{M}(\cdot)$ and are neighbors themselves, have the exact same neighbors in
$M$.

Figure 2: Notice that $V(M)\subseteq N[a]\cup N[b]$, and for any $u\in
N(a)=\\{1,2,3,v^{\star}\\}$, $N[a]\subseteq N[u]$. Additionally, the degree of
each vertex, ordered from left to right, is shown on the right.

Overall, the above arguments justify our choice of $a$ and $b$ (i.e., that
there exists at least one representation among those we consider that makes
the same choice). For the sake of clarity, let us show this explicitly for the
case where $V(L)\neq\emptyset$ (the arguments for the other two cases follows
the same lines). As argued above, the leftmost vertex must have, among the
vertices in $M$, maximum $d_{L}(\cdot)$ (which is greater than $1$) and,
simultaneously, be smallest by $<$. Further, among these vertices with maximum
$d_{L}(\cdot)$ (which, therefore, are neighbors of each other and have the
same neighborhood in $L$) and that are smallest by $<$, it must have minimum
$d_{M}(\cdot)$. All the vertices that can be chosen in this manner also have
the same neighborhood also in $M$ (and no neighbors in $R$), and hence the
choice among them is arbitrary. This justifies the choice of $a$. Now, in the
easier case where $M\subseteq N[a]$, then $G[M]$ is in fact a clique. So,
among all vertoces with largest $d_{R}(\cdot)$ (all of which have the same
neighborhood in $R$) and which is largest by $<$, we can pick one as $b$
arbitrarily. In case $M\setminus N[a]\neq\emptyset$, then $G[M]$ is not a
clique, and, in particular, the leftmost vertex is not a neighbor of $a$, yet
it has minimum $d_{M}(\cdot)$ among all non-neighbors of $a$ (and all of the
vertices that satisfy this condition have the same neighborhood in $M$). So,
among the non-neighbors of $a$ vertices with maximum $d_{R}(\cdot)$ and that
are largest by $<$, we can choose $b$ as a vertex with minimum $d_{M}(\cdot)$
(we remark that $b$ might not have minimum $d_{M}(\cdot)$ among all vertices
in $M$, but it should have it among all the non-neighbors of $a$). Notice that
is some choice is not possible, then we have a “no-instance”. ∎

For the recursive calls in Step 6 on $L$ and $R$, we have the following claim.

######  Claim 6.16.

The algorithm does not answer “no-instance” in Step 6. Moreover, for any pair
of representations $g_{L}$ of $L$ and $g_{R}$ of $R$ that comply with $<_{L}$
and $<_{R}$, respectively, there exists a representation of $G$ that satisfies
the conditions in Claim 6.15 and that the restrictions of its ordering of
starting and ending points to $L$ and $R$ is the same as $g_{L}$ and $g_{R}$,
respectively.

###### Proof.

To prove the first part of the claim, let $f$ be a representation of $G$ that
complies with $<$. Let $f_{L}$ and $f_{R}$ be the restrictions of $f$ to $L$
and $R$, respectively. Then, $f_{L}$ and $f_{R}$ are clearly representations
of $L$ and $R$ that comply with the restrictions of $<$ to $V(L)$ and $V(R)$,
respectively. Further, for any $u,v\in V(L)$ such that $d_{L}(u)<d_{L}(v)$, it
must be that the starting point of $u$ is to the left of that of $v$—indeed,
this follows from the observation that for any two vertices $x,y\in V(L)$ such
that $f(x)$ starts before $f(y)$, every neighbor of $x$ in $M$ is also a
neighbor of $y$ in $M$. Symmetrically, for any $u,v\in V(R)$ such that
$d_{L}(u)>d_{L}(v)$, it must be that the starting point of $u$ is to the left
of that of $v$. So, $f_{L}$ and $f_{R}$ comply with $<_{L}$ and $<_{R}$,
respectively, which means that the recursive calls are made with yes-
instances. Therefore, the algorithm does not answer “no-instance” in Step 6.

To prove the second part of the claim, it suffices to show that there exists a
representation $f$ of $G$ that satisfies the conditions in Claim 6.15, and
whose restriction to $L$ (resp. $R$) is $g_{L}$ (resp. $g_{R}$). We will only
show a modification to ensure restriction to $L$ is $g_{L}$, since the
modification for $R$ is symmetric (and can be done after the the property for
$L$ is derived without altering it) Towards this, let $h$ be a representation
of $G$ that satisfies the conditions in Claim 6.15. Then, for some implicit
$f$ that is meant to be a representation (which, until proved below, maybe
incorrect), we define an ordering of the starting and ending points of the
intervals of vertices as follows. The internal ordering between endpoints
corresponding to vertices in $V(M)\cup V(R)$ is the same as in $f$, and the
ordering between endpoints corresponding to vertices in $V(L)$ is the same as
in $g_{L}$. All starting points corresponding to vertices in $V(L)$ appear
before all those of vertices in $V(M)$, and all ending points corresponding to
vertices in $V(L)$ appear before all those of vertices in $V(M)$ and before
all starting points corresponding to vertices in $V(R)$. It remains to specify
the relation between the ending points corresponding to $V(L)$ and the
starting points corresponding to $V(M)$. To this end, let
$v_{1},v_{2},\ldots,v_{\ell}$ where $\ell=|V(L)|$ be the ordering of the
vertices in $L$ by the starting points (from left to right) of the intervals
assigned to them by $g_{L}$. Let $u_{1},u_{2},\ldots,u_{\ell}$ be defined in
the same way but with respect to $h$. Additionally, let
$w_{1},w_{2},\ldots,w_{m}$ where $m=|V(M)|$ be the ordering of the vertices in
$M$ by the starting points (from left to right) of the intervals assigned to
them by $h$. Then, for any $i\in\\{1,2,\ldots,\ell\\}$:

  * •

If $d_{M}(v_{i})=0$, then place the ending point of $f(v_{i})$ before the
starting points of all intervals (assigned by $f$) of vertices in $M$.

  * •

If $d_{M}(v_{i})=|V(M)|$, then place the ending point of $f(v_{i})$ after the
starting points of all intervals (assigned by $f$) of vertices in $M$.

  * •

Else, place the ending point of $f(v_{i})$ between the starting points of
$f(w_{d_{M}(v_{i})})$ and $f(w_{d_{M}(v_{i+1})})$.

We need to argue that no conflicts arose, that is, that we do not have two
vertices $v_{i},v_{j}\in V(L)$ such that the ordering of their ending points
in $g_{L}$ is different than the ordering implied when we placed them between
starting points corresponding to vertices in $M$. Suppose, by contradiction,
that such a conflict arose. Then, there exist $v_{i},v_{j}\in V(L)$ such that
there exists $w_{t}\in V(M)$ so that we have ordered
$\mathsf{end}_{f}(v_{j})<\mathsf{start}_{f}(w_{t})<\mathsf{end}_{f}(v_{i})$,
but $i<j$ (i.e., $\mathsf{end}_{g_{L}}(v_{i})<\mathsf{end}_{g_{L}}(v_{j})$).
Having
$\mathsf{end}_{f}(v_{j})<\mathsf{start}_{f}(w_{t})<\mathsf{end}_{f}(v_{i})$
means that $d_{M}(v_{j})<d_{M}(v_{i})$, which, by the definition of $<_{L}$,
implies that $v_{j}<_{L}v_{i}$. But then, it cannot be that
$\mathsf{end}_{g_{L}}(v_{i})<\mathsf{end}_{g_{L}}(v_{j})$, because this
contradicts the demand that $g_{L}$ complies with $<_{L}$. So, we have reached
a contradiction, which means that no conflict arose.

Figure 3: Intervals of vertices in $L$ cannot intersect intervals of vertices
in $R$. (Note that the intervals are open.)

Clearly, if $f$ that corresponds to our ordering is a representation of $G$,
then it should be clear that $f$ satisfies the conditions in Claim 6.15 and
that the restriction of its ordering of starting and ending points to $L$ is
the same as $g_{L}$ and $g_{R}$. So, it remains to prove that $f$ is a
representation. Directly from the definition of the ordering for $f$, for
every pair of intervals such that one belongs to a vertex in $L$ and the other
to a vertex in $R$, their intervals do not intersect and indeed they are not
adjacent (see Fig. 3). Further, because $g_{L}$ and $h$ are representation,
directly from the definition of the ordering for $f$, every two vertices that
are both in $V(L)$ or both in $V(M)\cup V(R)$, their intervals (as assigned by
$f$) intersect if and only if they are adjacent. It remains to consider the
case where we have a vertex $v_{i}\in V(L)$ and a vertex $w_{j}\in V(M)$.
Then, we need to show that $\mathsf{start}_{f}(w_{j})<\mathsf{end}_{f}(v_{i})$
if and only if $v_{i}$ and $w_{j}$ are adjacent in $G$.

To prove the above, let $t\in\\{1,2,\ldots,\ell\\}$ be such that
$v_{i}=u_{t}$. We will claim that the placements of the ending point $u_{t}$
by $f$ and by $h$ among the starting points intervals of vertices in $M$ (as
assigned by $f$ or $h$—the ordering of these starting points by $f$ and $h$ is
the same) are the same. Given that this claim is correct, then because $h$ is
a representation, we can conclude that
$\mathsf{start}_{f}(w_{j})<\mathsf{end}_{f}(v_{i})$ if and only if $v_{i}$ and
$w_{j}$ are adjacent in $G$. So, it remains to prove this claim. This follows
from the observation that if $h(u_{t})$ intersects $h(w_{q})$ for some
$w_{q}\in\\{1,2,\ldots,m\\}$, then $h(u_{t})$ also intersect $h(w_{p})$ for
all $p\in\\{1,2,\ldots,m\\}$. Hence, because $u_{t}$ intersects exactly
$d_{M}(u_{t})$ vertices in $M$, the ending point of $h(u_{t})$ must be placed
within the starting points of the intervals of vertices in $M$ (as assigned by
$h$) exactly as we have placed the ending point of $f(v_{i})$ within them.
This completes the proof. ∎

Now, we consider the correctness of the ordering of starting points as defined
in Step 7.

######  Claim 6.17.

The algorithm does not answer “no-instance” in Step 7, and there exists a
representation of $G$ that satisfies the conditions in Claim 6.16 and where
the starting points of the intervals of all vertices are ordered in the way
defined in Step 7.

###### Proof.

Consider all represetations of $G$ that satisfy the conditions in Claim 6.15
(where we know that at least one such representation exists). So, by the
condition in Claim 6.14, all intervals of vertices in $L$ begin before all
intervals of vertices in $M$ begin, and all intervals of vertices in $M$ begin
before all intervals of vertices in $R$ begin. With respect to the internal
ordering of the starting points of the intervals of vertices in $V(L)$ and
$V(R)$, correctness is guaranteed by the condition in Lemma 6.16. Lastly, by
following the same lines of arguments as those given in the proof of Claim
6.15, we conclude that among the representation we consider, at least one has
the internal ordering of starting points of the intervals of vertices in
$V(M)$ as the one defined in Step 7. ∎

Next, we consider the correctness of the ordering of ending points for
vertices in $L$ and $R$ as defined in Step 8. With respect to vertices in $L$
with no neighbors in $M$, and vertices in $R$, correctness is immediate. With
respect to vertices in $L$ with neighbors in $M$, clearly the endpoints should
occur after the first starting point of intervals of vertices in $M$ and
before all starting points of intervals of vertices in $R$ (because no vertex
in $L$ can be a neighbor of a vertex in $R$; see Fig. 3). Moreover, in any
representation, if a vertex in $L$ has $d$ neighbors in $M$, then this $d$
must be the $d$ vertices in $M$ whose starting points are leftmost in that
representation. So, this justifies our placement of all ending points of
vertices in $L$ and $R$ within the starting points.

######  Claim 6.18.

There exists a representation of $G$ that satisfies the conditions in Claim
6.17 and where the ending points of the intervals of all vertices in $V(L)\cup
V(R)$ are ordered in the way defined in Step 8.

We proceed to consider the correctness of the ordering of ending points for
vertices in $M$ as defined in Step 9. For vertices in $M$ that have neighbors
in $R$ (i.e., $d_{R}(\cdot)>0$), the correctness follows the symmetric
arguments as for the vertices in $L$ that have neighbors in $M$ in the
previous claim. For vertices $u$ in $M$ with no neighbors in $R$, in case
their intervals start after that of $v^{\star}$, then they must end after the
ending point of the interval of $v^{\star}$ which is, in turn, after the
starting points of all vertices in $M$. Because such $u$ have no neighbors in
$R$, the ending points of their intervals must also be before the starting
points of all intervals in $R$. Now, in case their intervals start before the
interval of $v^{\star}$, then they must too intersect $a$, and so they
intersect the first $d_{M}(u)$ vertices in $M$, which justifies the placement
of the ends of their intervals.

######  Claim 6.19.

There exists a representation of $G$ that satisfies the conditions in Claim
6.18 and where the ending points of the intervals of all vertices in $V(M)$
are ordered in the way defined in Step 9.

We proceed to consider the correctness of the “internal ordering” of ending
points as defined in Step 10. This part is clear because if the starting point
of the interval of one vertex is more to the left than another, so is the
relation between their ending points (since all intervals are of the same unit
length).

######  Claim 6.20.

There exists a representation of $G$ that satisfies the conditions in Claim
6.19 and where the ending points of the intervals of all vertices are ordered
in the way defined in Step 10.

Overall, when we reach Claim 6.20, we have, in fact, defined a strict ordering
of the starting and ending points of the intervals of all vertices. As we
argued before this sequence of claims, this completes the proof. ∎

We are now ready to conclude the proof of Lemma 6.9, which, as argued earlier,
implies Lemma 6.5.

###### Proof of Lemma 6.9.

Let $s\in\mathbb{N}$. We claim that for any $n\in\mathbb{N}_{0}$, Annotated
Proper Interval Reconstruction admits a $5\cdot
s\cdot\log_{\frac{10}{9}}n$-pass algorithm on $n$-vertex graphs with success
probability at least $1-(\frac{1}{5})^{s}\cdot n\log_{\frac{10}{9}}n$. This
follows by induction on $n$, where at the basis $n$ is a constant (or just
$0$) and hence the claim is trivial, and the step follows from Lemma 6.13.

Now, we pick $s=\log_{5}(n^{2})$. Then, the number of passes is
$5\cdot\log_{5}(n^{2})\cdot\log_{\frac{10}{9}}n={\mathcal{O}}(\log^{2}n)$, and
the success probability is $1-(\frac{1}{5})^{\log_{5}(n^{2})}\cdot
n\log_{\frac{10}{9}}n=1-\frac{1}{n^{2}}\cdot
n\log_{\frac{10}{9}}n>\frac{9}{10}$ assuming that $n$ is larger than some
fixed constant. This completes the proof. ∎

####  6.1.2 Post-processing Algorithm

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

######  Lemma 6.21.

Proper Interval Vertex Deletion admits an $\widetilde{{\mathcal{O}}}(n)$-space
$2^{{\mathcal{O}}(k)}\cdot n^{{\mathcal{O}}(1)}$-time (static) algorithm.

Figure 4: The (infinite) family of forbidden induced subgraphs of proper
interval graphs. The figure was taken from [vtHV13].

Towards this proof, we need to recall the alternative characterization of
proper interval graphs in terms of forbidden induced subgraphs. For this
purpose, we remind that for any integer $i\geq 3$, $C_{i}$ in the induced
(i.e. chordless) cycle on $i$ vertices, and it is termed a hole. A claw, net
and tent are specific graphs on four, six and six, respectively, vertices, as
illustrated in Fig. 4.

######  Proposition 6.22 ([Weg67, BLS99]).

A graph $G$ is a proper interval graph if and only if is admits no claw, net,
tent and hole.

We also need the definition of a proper circular-arc graph (see Fig. 5).

######  Definition 6.23.

A graph $G$ is a proper circular-arc if there exist a circle $C$ on the
Euclidean plane and a function $f$ that assigns to each vertex in $G$ an open
interval of $C$ such that no interval properly contains another, and every two
vertices in $G$ are adjacent if and only if their intervals intersect. Such a
function $f$ is called a representation, and given a vertex $v\in V(G)$, we
let $\mathsf{begin}_{f}(v)$ and $\mathsf{end}_{f}(v)$ denote the beginning and
end (in clockwise order) of the interval assigned to $v$ by $f$ (as if it was
closed).

We note the the class of proper circular-arc graphs is not equivalent to the
class of unit circular-arc graphs.

Figure 5: A proper circular-arc graph.

Notice that any $C_{i}$ (hole on $i$ vertices) is a proper circular-arc graph,
and hence the class of proper arc-circular graphs is a strict superclass of
the class of proper interval graphs. Our proof will build upon two results by
van ’t Hof and Villanger [vtHV13]:

######  Proposition 6.24 ([vtHV13]).

Let $G$ be a graph that that admits no claw, net, tent, $C_{4}$, $C_{5}$ and
$C_{6}$ as induced subgraphs. Then, $G$ is a proper circular-arc graph.

######  Proposition 6.25 ([vtHV13]).

Let $G$ be a proper circular-arc graph with representation $f$. Then, any
minimal subset $U\subseteq V(G)$ such that $G-U$ is a proper interval graph
satisfies that there exists $v\in V(G)$ such that $U=\\{u\in
V(G):\mathsf{end}_{f}(v)\in f(u)\\}$.777Note that $v\notin U$ (as $f(v)$ is an
open interval). Moreover, for every $v\in V(G)$, we have that $U=\\{u\in
V(G):\mathsf{end}_{f}(v)\in f(u)\\}$ satisfies that $G-U$ is a proper interval
graph.

So, Propositions 6.24 and 6.25 present a straightforward way to prove Lemma
6.21 given that we know how to obtain a representation of a proper circular-
arc graph in $\widetilde{{\mathcal{O}}}(n)$ space and polynomial time. This
can indeed be done—for example, thee linear (in the number of vertices and
edges) algorithm for this purpose given in [DHH96] can be seen to work in
$\widetilde{{\mathcal{O}}}(n)$ space. In what follows, we given an alternative
approach, which shows that we can also solve the problem in
$\widetilde{{\mathcal{O}}}(n)$ space and polynomial time without the
representation—while the proof is not short, it yields a very simple algorithm
(see the proof of Lemma 6.21 ahead), which may be of independent interest.

We refine one direction of Proposition 6.25 as follows.

######  Lemma 6.26.

Let $G$ be a proper circular-arc graph with representation $f$ that has an
independent set of size at least $4$. Then, any minimal subset $U\subseteq
V(G)$ such that $G-U$ is a proper interval graph satisfies that there exists
$v\in V(G)$ such that $U=\\{u\in V(G):\mathsf{end}_{f}(v)\in f(u),N[v]\neq
N[u]\\}$.

Figure 6: A figure for the proof of Lemma 6.26. Here, $U=\\{2,v,3,4\\}$,
$N[w]=N[2]=N[v]=\\{1,w,2,v,3,4\\}$ and for all $u\notin\\{w,2,v\\}$, $N[u]\neq
N[w]$. So, $v$ is indeed leftmost among vertices in $U$ with the same closed
neighborhood as $v$. Notice that $T=\\{3,4\\}\subset U$.

###### Proof.