problem*[1][]
Instance: Question:

11institutetext: A. Biswas () 22institutetext: The Institute of Mathematical
Sciences, HBNI, Chennai, India
22email<EMAIL_ADDRESS>33institutetext: V. Raman 44institutetext: The
Institute of Mathematical Sciences, HBNI, Chennai, India
44email<EMAIL_ADDRESS>55institutetext: S. Saurabh 66institutetext: The
Institute of Mathematical Sciences, HBNI, Chennai, India 77institutetext:
University of Bergen, Bergen, Norway
77email<EMAIL_ADDRESS>
∎

# Approximation in (Poly-) Logarithmic Space††thanks: A preliminary version
BRS2020MFCS  of this article appeared in the proceedings of MFCS 2020.

Arindam Biswas  Venkatesh Raman  Saket Saurabh

###### Abstract

We develop new approximation algorithms for classical graph and set problems
in the RAM model under space constraints. As one of our main results, we
devise an algorithm for $d\text{--}\textsc{Hitting Set}{}$ that runs in time
$n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$, uses
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits of space, and
achieves an approximation ratio of
$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$ for any positive
$\epsilon\leq 1$ and any $d\in\mathbb{N}$. In particular, this yields a
factor-$\operatorname{O}\left(\log{n}\right)$ approximation algorithm which
runs in time $n^{\operatorname{O}\left(\log{n}\right)}$ and uses
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space (for constant $d$).
As a corollary, we obtain similar bounds for Vertex Cover and several graph
deletion problems.

For bounded-multiplicity problem instances, one can do better. We devise a
factor-$2$ approximation algorithm for Vertex Cover on graphs with maximum
degree $\Delta$, and an algorithm for computing maximal independent sets, both
of which run in time $n^{\operatorname{O}\left(\Delta\right)}$ and use
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space. For the more
general $d\text{--}\textsc{Hitting Set}{}$ problem, we devise a factor-$d$
approximation algorithm which runs in time
$n^{\operatorname{O}\left(d{\delta}^{2}\right)}$ and uses
$\operatorname{O}\left(d{\delta}^{2}\log{n}\right)$ bits of space on set
families where each element appears in at most $\delta$ sets.

For Independent Set restricted to graphs with average degree $d$, we give a
factor-$(2d)$ approximation algorithm which runs in polynomial time and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space. We also devise a
factor-$\operatorname{O}\left(d^{2}\right)$ approximation algorithm for
Dominating Set on $d$-degenerate graphs which runs in time
$n^{\operatorname{O}\left(\log{n}\right)}$ and uses
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space. For $d$-regular
graphs, we show how a known randomized
factor-$\operatorname{O}\left(\log{d}\right)$ approximation algorithm can be
derandomized to run in time $n^{\operatorname{O}\left(1\right)}$ and use
$\operatorname{O}\left(\log n\right)$ bits of space.

Our results use a combination of ideas from the theory of kernelization,
distributed algorithms and randomized algorithms.

###### Keywords:

approximation logspace logarithmic log space small limited memory ROM read-
only

##  1 Introduction

This paper examines the classical approximation problems Vertex Cover, Hitting
Set and Dominating Set in the RAM model under additional polylogarithmic space
constraints. We devise approximation algorithms for these problems which use
polylogarithmic space in general and $\operatorname{O}\left(\log{n}\right)$
bits of space on certain special input types.

In the absence of space constraints, the greedy heuristic is a good starting
point for many approximation algorithms. For Set Cover, it even yields optimal
(under certain complexity-theoretic assumptions) approximation ratios
AMS2006TALG ; DS2014STOC . However, the heuristic inherently changes the input
in some way. In a space-constrained setting, this is asking for too much: the
input is immutable, and the amount of auxiliary space available (in our case,
polylogarithmic in the input size) is not sufficient to register changes to
the input.

Linear programming is another tool that plays a central role in the design of
approximation algorithms. While it yields competitive approximations in
polynomial time when space is not constrained, it is known that under
logarithmic-space reductions, it is P-complete to approximate Linear
Programming to any constant factor Ser1991IPL . Such a result even holds for
Linear Programming instances where all coefficients are positive
TX1998ParallelProcessLett .

##### Machine Model.

We use the standard RAM model with an additional polylogarithmic space
constraint. For inputs $n$ bits in length, memory is organized as words of
length $\operatorname{O}\left(\log{n}\right)$, which allows any input element
to be addressed using a single word of memory. Integer arithmetic operations
on pairs of words and single-word memory access operations take constant time.
This is referred to in the literature as the _word_ RAM model.

The input (a graph or family of sets) is provided to the algorithm using some
canonical encoding, which can be read but not modified, i.e. the algorithm has
read-only access to the input. The algorithm uses some auxiliary memory, to
which it has read-write access, and in the setting of this paper, the amount
of such memory available is bounded by a polynomial in $\log{n}$. Output is
written to a stream: once something is output, the algorithm cannot read it
back later on as it executes. We count the amount of auxiliary memory used in
units of $1$ bit, and the objective is to use as little auxiliary memory as
possible.

### Our Results

#####  $d\text{--}\textsc{Hitting Set}{}$ and Vertex Deletion Problems.

An instance of the
$d\text{--}\textsc{Hitting Set}{}$ problem consists of a ground set $U$ and a
family $\mathcal{F}$ of subsets of $U$ of size at most $d\in\mathbb{N}$, and
the objective is to find a subset of the ground set that intersects every set
in the family.

  * •

We develop a factor-$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$
approximation algorithm for $d\text{--}\textsc{Hitting Set}{}$ which runs in
time $n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$ and uses
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits of space
(Section 4), where $\epsilon\leq 1$ is an arbitrary positive number and $d$ is
a fixed positive integer. In particular, this yields a
factor-$\operatorname{O}\left(d\log n\right)$ approximation algorithm for the
problem which uses $\operatorname{O}\left(\log^{2}{n}\right)$ bits of space.
As an application, we show how the algorithm can be used to approximate
various _deletion_ problems with similar space bounds. From this, we derive a
factor-$\operatorname{O}\left((1/\epsilon)n^{\epsilon}\right)$ (for arbitrary
positive $\epsilon\leq 1$) approximation algorithm for Vertex Cover that runs
in time $n^{\operatorname{O}\left(1/\epsilon)\right)}$ and uses
$\operatorname{O}\left((1/\epsilon)\log{n}\right)$ bits of space.

  * •

We give a simple factor-$2$ approximation algorithm for Vertex Cover on graphs
with maximum degree $\Delta$ which runs in time
$n^{\operatorname{O}\left(\Delta\right)}$ and uses
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space (Section 3.1).

  * •

For $d\text{--}\textsc{Hitting Set}{}$ instances where each element appears in
at most $\delta$ sets, we devise a factor-$d$ approximation algorithm (Section
3.2), generalizing the above result. The algorithm runs in time
$n^{\operatorname{O}\left(d{\delta}^{2}\right)}$ and uses
$\operatorname{O}\left(d{\delta}^{2}\log{n}\right)$ bits of space.

#####  Dominating Set.

In the Dominating Set problem, the objective is to find a vertex set of
minimum size in a graph such that all other vertices are adjacent to some
vertex in the set.

  * •

We give a factor-$\operatorname{O}\left(\sqrt{n}\right)$ approximation
algorithm for graphs excluding $C_{4}$ (a cycle on $4$ vertices) as a
subgraph, which runs in polynomial time and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space (Section 4.2.1).

  * •

Graphs of bounded degeneracy form a large class which includes planar graphs,
graphs of bounded genus, graphs excluding a fixed graph $H$ as a (topological)
minor and graphs of bounded expansion. For graphs with degeneracy $d$, we give
a factor-$\operatorname{O}\left(d^{2}\right)$ approximation algorithm which
uses $\operatorname{O}\left(\log^{2}{n}\right)$ bits of space. (Section
4.2.2).

  * •

Additionally, for graphs in which each vertex has degree $d$, i.e. $d$-regular
graphs, we exhibit a factor-$\operatorname{O}\left(\log{d}\right)$
approximation algorithm for
Dominating Set (Section 5.2) which is an adaptation of known results to the
constrained-space setting.

#####  Independent Set.

An instance of the Independent Set problem consists of a graph, and the
objective is to find an _independent set_ of maximum size i.e. a set of
vertices with no edges between them.

  * •

We show how a known factor-$(2d)$ approximation algorithm for
Independent Set on graphs with average degree $d$ can be implemented to run in
polynomial time and use $\operatorname{O}\left(\log n\right)$ bits of space
(Section 5.1).

  * •

For the related problem of finding maximal independent sets, we devise an
algorithm which runs in time $n^{\operatorname{O}\left(\Delta\right)}$ and
uses $\operatorname{O}\left(\Delta\log{n}\right)$ bits of space (Theorem 3.2)
on graphs with maximum degree $\Delta$.

##### Remark.

In various statements, we use the verb _enumerate_ to explicitly indicate that
the structures being computed are produced in serial fashion, and read by
other procedures later on or output as a stream.

### Related Work

Small-space models such as the streaming model and the in-place model have
been the subject of much research over the last two decades (see
McG2014SIGMODRec ; CMR2018TALG ; CMRS2018ESA  and references therein). In the
streaming model, in addition to the space constraint, the algorithm is also
required to read the input in a specific (possibly adversarial) sequence in
one or more passes. The in-place model, on the other hand, allows the memory
used for storing the input to be modified. The read-only RAM model we use is
distinct from both these models.

Historically, the read-only model has been studied from the perspective of
time–space tradeoff lower bounds, particularly for problems like Sorting
BC1982SICOMP ; BFK+1981JCSS ; Bea1991SICOMP ; PR1998FOCS ; PP2002SODA  and
Selection MP1980TCS ; Fre1987JCSS ; MR1996TCS ; RR1999NordJComput .

The earliest graph problems studied in this model were the undirected and
directed graph reachability problems (resp. USTCON and STCON) in connection
with the complexity classes L and NL. Savitch Sav1970JCSS  showed that on
input graphs with $n$ vertices, STCON (and therefore also USTCON) can be
solved using $\operatorname{O}\left(\log^{2}{n}\right)$ bits of space. This
bound was gradually whittled down over more than two decades, and eventually
Reingold Rei2008JACM  showed that that USTCON can be solved using
$\operatorname{O}\left(\log{n}\right)$ bits of space. Graph recognition
problems for classes such as bipartite Rei1984JACM  and planar AM2004InfComput
graphs have been shown to reduce in logarithmic space to USTCON, which implies
logarithmic-space algorithms for these problems as well. The more general
problem of recognizing bounded-genus graphs is also known to be solvable in
logarithmic space, by an algorithm of Elberfeld and Kawarabayashi EK2014STOC .

For the task of enumerating BFS and DFS traversal sequences, a number of
algorithms have been developed EHK2015STACS ; AIK+2014ISAAC ; CRS2017JCSS ;
Hag2020Algorithmica  which run in polynomial (many of them close to linear)
time and their space usage in bits is linear in the number of vertices or
edges. The read-only RAM model has also been studied in relation to
polynomial-time-solvable search problems Yam2013COCOA  and the approximation
properties of search problems that can be solved in nondeterministic
logarithmic space Tan2007TheoryComputSyst .

Algorithms for the PRAM model—where a number of processors run in parallel and
access a common area of memory to solve problems—can sometimes be translated
into sequential algorithms that use small space. A known reduction Pap1994book
allows one to convert any PRAM algorithm with parallel running time $s(n)$ to
a sequential algorithm that uses $s(n)\log^{c}{n}$ ($c=1$ or $2$, depending on
the PRAM variant) bits of space. These algorithms, however, do not necessarily
have polynomial running times. The PRAM algorithm of Luby Lub1986SICOMP  for
finding maximal independent sets in a graph can be used to $2$-approximate
Vertex Cover (better approximation ratios are unlikely KR2008JCSS ).
Implemented in the sequential RAM model, it uses
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space. For the more general
problem of finding maximal independent sets in hypergraphs, the recent PRAM
algorithm of Harris Har2019TALG  yields a polylogarithmic-space algorithm for
hypergraphs with edges of fixed size.

Our scheme for $d\text{--}\textsc{Hitting Set}{}$ trades approximation factor
against space to yield a family of algorithms that use
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log n)\right)$ bits of space and
produce $\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$-approximate
solutions for any positive $\epsilon\leq 1$. As a corollary, we obtain an
$\operatorname{O}\left(d\log{n}\right)$-approximation algorithm that uses
$\operatorname{O}\left(\log^{2}n\right)$ bits of space. On graphs with maximum
degree $\Delta$, our approximation algorithm for Vertex Cover uses
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space and produces
$2$-approximate solutions.

Berger et al. BRS1994JCSS  gave a PRAM algorithm for Set Cover which can be
implemented in the sequential RAM model to
$\operatorname{O}\left(\log{n}\right)$-approximate Dominating Set in
$\operatorname{O}\left(\log^{4}{n}\right)$ bits of space. See also
Tre1998Algorithmica ; LN1993STOC , which give parallel approximation
algorithms for Linear Programming, and see LO2017SPAA , which gives tight
approximation ratios for CSP’s using semi-definite programming in the PRAM
model. Our algorithms for Dominating Set are simpler and more direct, and work
for a large class of graphs while using
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space.

### Our Techniques

As noted earlier, the greedy heuristic causes changes to the input, which our
model does not permit. To get around this, we use a _staggered_ greedy
approach in which the solution is constructed in a sequence of greedy steps to
approximate Vertex Cover and $d\text{--}\textsc{Hitting Set}{}$ on bounded-
multiplicity instances (Section 3). By combining this with data reduction
rules from kernelization algorithms, we also obtain approximations for Vertex
Cover and more generally $d\text{--}\textsc{Hitting Set}{}$ (Section 4), and
restricted versions of Dominating Set (Sections 4.2.1 and 4.2.2). In Section
5, we use $2$-universal hash families constructible in logarithmic space to
derandomize certain randomized sampling procedures for approximating
Independent Set on graphs of bounded average degree and Dominating Set on
regular graphs.

##  2 Preliminaries

##### Notation.

$\mathbb{N}$ denotes the set of natural numbers $\left\\{0,1,\dotsc\right\\}$
and $\mathbb{Z}^{+}$ denotes the set of positive integers
$\left\\{1,2,\dotsc\right\\}$. For $n\in\mathbb{Z}^{+}$, $[n]$ denotes the set
$\left\\{1,2,\dotsc,n\right\\}$. Let $G$ be a graph. Its vertex set is denoted
by $\operatorname{V}\left(G\right)$, and its edge set by
$\operatorname{E}\left(G\right)$. The degree of a vertex $v$ is denoted by
$\deg\left(v\right)$, and for a set $S\subseteq\operatorname{V}\left(G\right)$
or a subgraph $H$ of $G$, $\deg_{S}\left(v\right)$ denotes the degree of $v$
in $G[S]$ and $\deg_{H}\left(v\right)$ denotes the degree of $v$ in $H$.

##### Known Results.

The following result combines a known logarithmic-space implementation of the
Buss kernelization rule BG1993SICOMP  for Vertex Cover with the observation
that the kernel produced is itself a vertex cover.

######  Proposition 1 (Cai et al. CCDF1997AnnPureApplLogic , Theorem 2.3).

There is an algorithm which takes as input a graph $G$ and $k\in\mathbb{N}$,
and either determines that $G$ has no vertex cover of size at most $k$ or
enumerates a vertex cover for $G$ with at most $2k^{2}$ edges. The algorithm
runs in time $\operatorname{O}\left(kn\right)$ and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space.

Vertex Cover is a special case of $d\text{--}\textsc{Hitting Set}{}$
($d\in\mathbb{N}$, a constant), an instance of which comprises a family
$\mathcal{F}$ of subsets of a ground set which all have size at most $d$. The
objective is to compute a minimum _hitting set_ for $\mathcal{F}$, i.e. a
subset of the ground set which intersects each set in $\mathcal{F}$. The next
proposition shows that a result similar to the one above also holds for this
generalization.

######  Proposition 2 (Fafianie and Kratsch FK2015MFCS , Theorem 1).

There is an algorithm which takes as input a family $\mathcal{F}$ of
$d$-subsets ($d\in\mathbb{N}$, a constant) of a ground set $U$ and
$k\in\mathbb{N}$, and either determines that $\mathcal{F}$ has no hitting set
of size at most $k$ or enumerates a subfamily $\mathcal{F}^{\prime}$ of
$\mathcal{F}$ with $\operatorname{O}\left({(k+1)}^{d}\right)$ sets which is
equivalent to it: $\mathcal{F}$ has a hitting set of size at most $k$ if and
only if $\mathcal{F}^{\prime}$ has a hitting set of size at most $k$. The
algorithm runs in time $n^{\operatorname{O}\left(d^{2}\right)}$ and uses
$\operatorname{O}\left(d^{2}\log n\right)$ bits of space.

###  2.1 Solving Vertex Cover and Independent Set on trees

When the input is a tree on $n$ vertices, one can enumerate _exact_ solutions
for Vertex Cover and Independent Set in time
$n^{\operatorname{O}\left(1\right)}$ and
$\operatorname{O}\left(\log{n}\right)$ bits of space, as we show below.

The decision versions of both problems can be expressed in monadic second-
order logic (MSOL), allowing them to be solved using Courcelle’s theorem
Cou1990InfComput , and a result of Elberfeld et al. EJT2010FOCS  shows that
this can be done in polynomial time and logarithmic space on graphs of
constant treewidth. Consequently, there are polynomial-time logarithmic-space
algorithms for the decision versions of Vertex Cover and Independent Set on
trees. Using pre-existing algoritihms, the search versions of these problems
can be solved in polynomial time using
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space BCR+2015COCOON . For
completeness, we give here elementary algorithms for the special case of
trees.

######  Lemma 1.

Given a tree $T$ on $n$ vertices, TreeVtxCover enumerates a minimum vertex
cover for $T$ in time $n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

In any graph, the complement of a vertex cover is an independent set, so if
TreeVtxCover outputs a minimum vertex cover $C$ for a tree $T$, its complement
$\operatorname{V}\left(T\right)\setminus C$ is a maximum independent set in
$T$. Combining this with the fact that given oracles for
$\operatorname{V}\left(T\right)$ and $C$, the complement can be enumerated in
time $n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of additional space, we have the
following corollary.

######  Corollary 1.

In a tree of order $n$, one can enumerate a maximum independent set in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

Input: $T=(V,E)$, a tree

Output: a mininmum vertex cover for $T$

1

2let $r$ be an arbitrary vertex of $T$;

3 foreach  _$v\in\operatorname{V}\left(T\right)$_ do

4 if  _IsInVC($v,r,T$)_ then

5 output $v$;

6

7

8 Procedure  _IsInVC(_$v,r,T$_) // $T$ a tree rooted at $r$, $v$ a vertex in
$\operatorname{V}\left(T\right)$_

9 generate a post-order traversal $L$ for $T$ with $r$ as the root;

10 seek $L$ to the first leaf in the subtree of $T$ rooted at $v$;

11 $visited\\_vertex\leftarrow\texttt{NULL}{}$;

12 $visited\\_included\leftarrow\texttt{NO}{}$;

13 foreach  _$u\in L$_ do

14 if  _$u$ is a leaf_ then

15 $visited\\_vertex\leftarrow u$;

16 $visited\\_included\leftarrow\texttt{NO}{}$;

17

18 else // $u$ is not a leaf; $u$ is the parent of $visited\\_vertex$

19 $visited\\_vertex\leftarrow u$;

20 if  _not $visited\\_included$_ then

21 if  _$u=v$_ then

22 return _YES_ ;

23

$visited\\_included\leftarrow\texttt{YES}{}$;

// include $u$

24

25 else // last-visited vertex was included

26 if  _$u=v$_ then

27 return _NO_ ;

28

$visited\\_included\leftarrow\texttt{NO}{}$;

// do not include $u$

seek $L$ to $u$’s parent;

// vertices in subtrees of $u$’s unvisited siblings can be ignored

29

30

31

32

33

Algorithm 1 TreeVtxCover: enumerate a minimum vertex cover

We now prove Lemma 1. TreeVtxCover operates by rooting $T$ at an arbitrary
vertex $r\in\operatorname{V}\left(T\right)$ and enumerates a vertex cover $S$
obtained by repeatedly applying the following rule.

> Rule VCT _Include the the parents of leaves on the bottom level of $T$ in
> $S$, then delete from $T$ the included vertices, their children, and all
> edges incident with them._

The fact that $S$ is a minimum vertex cover follows directly from the
observation that to cover the edges of $T$ incident with the leaves at the
bottom level, picking the parents of those leaves is at least as good as any
other choice of covering vertices.

###### Proof of Lemma 1.

Observe that at any intermediate stage in the repeated application of Rule
VCT, a vertex is a leaf on the bottom level of $T$ if a previous application
of the rule deleted all of its children, i.e. all of them were included in
$S$. Thus, any vertex $v\in\operatorname{V}\left(T\right)$, is in $S$ if and
only if $S$ does not contain all of its children.

Instead of repeatedly deleting vertices from $T$, Procedure IsInVC in the
algorithm determines membership in $S$ by performing what is essentially a
post-order traversal of $T$. In the post-order traversal, to determine if a
vertex $v$ is in $S$, the only information necessary is whether at least one
of $v$’s children is not in $S$, which the procedure stores in the variable
$visited\\_included$. If such a child vertex is encountered, the procedure
determines that $v$ is in $S$, and skips the rest of the subtree rooted at
$v$.

The post-order traversal used by the procedure can be generated from a DFS
traversal of $T$, which can be enumerated using
$\operatorname{O}\left(\log{n}\right)$ bits of space CM1987JAlgorithms . The
constantly-many variables appearing in the algorithm also use
$\operatorname{O}\left(\log{n}\right)$ bits of space total. Therefore, the
overall space usage of the algorithm is $\operatorname{O}\left(\log{n}\right)$
bits and it runs in time $n^{\operatorname{O}\left(1\right)}$. ∎

###  2.2 Presenting modified structures using oracles

Our algorithms repeatedly “delete” vertices (or elements), but as they only
have read-only access to the graph (or set family), we require a way to
implement these deletions using a small amount of auxiliary space. Towards
that, we prove the following theorem.

######  Theorem 2.1.

Let $G=G_{0}=(V,E)$ be a graph on $n$ vertices and let $G_{i}$ ($i\in[k]$) be
obtained from $G_{i-1}$ by deleting a set
$S_{i}\subseteq\operatorname{V}\left(G_{i-1}\right)$ consisting of all
vertices $v\in\operatorname{V}\left(G_{i-1}\right)$ which satisfy a property
that can be checked (given access to $G_{i-1}$) using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

Given read-only access to $G$, one can, for each $i\in[k]$, enumerate and
answer membership queries for $S_{i}$,
$V_{i}=\operatorname{V}\left(G_{i}\right)$ and
$E_{i}=\operatorname{E}\left(G_{i}\right)$ in time
$n^{\operatorname{O}\left(i\right)}$ using
$\operatorname{O}\left(i\log{n}\right)$ bits of space.

###### Proof.

For each $i\in[k]$ let $\texttt{Check}_{i}(G_{i-1},v)$ be the algorithmic
check which, given (oracle) access to $G_{i-1}$, determines whether $v\in
V_{i-1}$ satisfies the condition for inclusion in $S_{i}$.

To provide oracle access to $G_{i},V_{i}$ and $E_{i}$, it suffices to compute,
for $v\in V$ and $uw\in E$, the predicates $\left[v\in V_{i}\right]$ and
$\left[uw\in E_{i}\right]$. A vertex is in $V_{i}$ if and only if it is in
$V_{i-1}$ and it is not in $S_{i}$. Similarly, an edge is in $E_{i}$ if and
only if it is in $E_{i-1}$ and neither of its endpoints are in $S_{i}$. Thus,
we have the following relations.

$\displaystyle\left[v\in V_{i}\right]$ $\displaystyle\equiv\left[v\in
V_{i-1}\right]\wedge\neg\texttt{Check}_{i}(G_{i-1},v)$ (1)
$\displaystyle\left[uw\in E_{i}\right]$ $\displaystyle\equiv\left[uw\in
E_{i-1}\right]\wedge\neg(\texttt{Check}_{i}(G_{i-1},u)\vee\texttt{Check}_{i}(G_{i-1},w))$
(2)

To compute each of these predicates for $G_{i}$, we require oracle access to
$G_{i-1}$, which in turn involves computing the predicates $\left[v\in
V_{i-1}\right]$ and $\left[uw\in E_{i-1}\right]$. Since
$\texttt{Check}_{i}(G_{i-1},v)$ uses $\operatorname{O}\left(\log{n}\right)$
bits of space, the number of operations needed to compute it is at most
$n^{\operatorname{O}\left(1\right)}$.

Let $p_{i}$ (resp. $q_{i}$) be the amount of space used to compute the
predicate $\left[v\in V_{i}\right]$ (resp. $\left[uw\in E_{i}\right]$), and
let $s_{i}$ (resp. $t_{i}$) be the time needed to compute the predicate
$\left[v\in V_{i}\right]$ (resp. $\left[uw\in E_{i}\right]$). From Relations 1
and 2 and the fact that $\texttt{Check}_{i}$ accesses $G_{i-1}$ at most
$n^{\operatorname{O}\left(1\right)}$ times, we see that these quantities
satisfy the following relations.

$\displaystyle p_{i}=p_{i-1}+\operatorname{O}\left(\log{n}\right),\ $
$\displaystyle q_{i}=q_{i-1}+\operatorname{O}\left(\log{n}\right)$ (3)
$\displaystyle
s_{i}=s_{i-1}+n^{\operatorname{O}\left(1\right)}(s_{i-1}+t_{i-1}),\ $
$\displaystyle
t_{i}=t_{i-1}+n^{\operatorname{O}\left(1\right)}(s_{i-1}+t_{i-1})$ (4)

It is easy to see that these recurrences solve to
$p_{i},q_{i}=\operatorname{O}\left(i\log{n}\right)$ and
$s_{i},t_{i}=n^{\operatorname{O}\left(i\right)}$, so both predicates can be
computed in time $n^{\operatorname{O}\left(i\right)}$ using
$\operatorname{O}\left(i\log{n}\right)$ bits of space.

With oracle access to $G_{i-1}$, the predicate $\left[v\in S_{i}\right]$ can
be computed simply as $\texttt{Check}_{i}(G_{i-1},v)$, from which enumerating
$V_{i}$ (resp. $E_{i}$ and $S_{i}$) is straightforward: enumerate $V$ (resp.
$E$ and $V$) and suppress vertices $v$ (resp. edges $uw$ and vertices $z$)
which fail the predicate $\left[v\in V_{i}\right]$ (resp. $\left[uw\in
E_{i}\right]$ and $\left[z\in S_{i}\right]$).

As the most space-hungry operations are the membership queries, the
enumeration can also be performed using
$\operatorname{O}\left(i\log{n}\right)$ bits of space. The enumeration needs
time $n^{\operatorname{O}\left(i\right)}$ for each element of $V$ and $E$, and
since $\left\lvert V\right\rvert,\left\lvert
E\right\rvert=\operatorname{O}\left(n^{2}\right)$, the total time needed is
also $n^{\operatorname{O}\left(i\right)}$. ∎

The above result also generalizes to set families if we assume that at each
stage where elements are deleted, the algorithmic check which determines the
elements to be deleted uses $\operatorname{O}\left(c\log{n}\right)$ bits of
space ($c>0$).

######  Theorem 2.2.

Let $U$ be a ground set with $n$ elements and $\mathcal{F}=\mathcal{F}_{0}$ be
a family of subsets of $U$, each of size at most $d$ ($d\in\mathbb{N}$, a
constant). Let $\mathcal{F}_{i}$ ($i\in[k]$) be a subfamily of
$\mathcal{F}_{i-1}$ obtained by deleting all sets in $\mathcal{F}_{i-1}$ which
intersect some set $S_{i}\subseteq U_{i-1}$ and let $U_{i}=U_{i-1}\setminus
S_{i}$. Suppose additionally that given access to $U_{i-1}$ and
$\mathcal{F}_{i-1}$, $S_{i}$ can be determined using
$\operatorname{O}\left(c\log{n}\right)$ bits of space.

Given read-only access to $\mathcal{F}$, one can, for each $i\in[k]$,
enumerate and answer membership queries for $S_{i}$, $U_{i}$ and
$\mathcal{F}_{i}$ in time $n^{\operatorname{O}\left(ic\right)}$ using
$\operatorname{O}\left(ic\log{n}\right)$ bits of space.

###### Proof.

The proof is essentially the same as that of Theorem 2.1. For each $i\in[k]$
let $\texttt{Check}_{i}(U_{i-1},\mathcal{F}_{i-1},e)$ be the algorithmic check
which, given (oracle) access to $U_{i-1}$ and $\mathcal{F}_{i-1}$, determines
whether $e\in U_{i-1}$ satisfies the condition for inclusion in $S_{i}$.

As in the proof of Theorem 2.1, it suffices to compute, for $e\in U$ and
$A\in\mathcal{F}$, the predicates $\left[e\in U_{i}\right]$ and
$\left[A\in\mathcal{F}_{i}\right]$. An element is in $U_{i}$ if and only if it
is in $U_{i-1}$ and it is not in $S_{i}$. Similarly, a set is in
$\mathcal{F}_{i}$ if and only if it is in $\mathcal{F}_{i-1}$ and it does not
intersect $S_{i}$. Thus, we have the following relations.

$\displaystyle\left[e\in U_{i}\right]$ $\displaystyle\equiv\left[e\in
U_{i-1}\right]\wedge\neg\texttt{Check}_{i}(U_{i-1},\mathcal{F}_{i-1},e)$ (5)
$\displaystyle\left[A\in\mathcal{F}_{i}\right]$
$\displaystyle\equiv\left[A\in\mathcal{F}_{i-1}\right]\wedge\neg\left(\bigvee_{e\in
A}\texttt{Check}_{i}(U_{i-1},\mathcal{F}_{i-1},e)\right)$ (6)

To compute these predicates for $U_{i}$ and $\mathcal{F}_{i}$, we require
oracle access to $U_{i-1}$ and $\mathcal{F}_{i-1}$, which in turn involves
computing the predicates $\left[u\in U_{i-1}\right]$ and
$\left[A\in\mathcal{F}_{i-1}\right]$. Since
$\texttt{Check}_{i}(U_{i-1},\mathcal{F}_{i-1},e)$ uses
$\operatorname{O}\left(c\log{n}\right)$ bits of space, the number of
operations needed to compute it is at most
$n^{\operatorname{O}\left(c\log{n}\right)}$.

Let $p_{i}$ (resp. $q_{i}$) be the amount of space used to compute the
predicate $\left[e\in U_{i}\right]$ (resp.
$\left[A\in\mathcal{F}_{i}\right]$), and let $s_{i}$ (resp. $t_{i}$) be the
time needed to compute the predicate $\left[e\in u_{i}\right]$ (resp.
$\left[A\in\mathcal{F}_{i}\right]$). From Relations 5 and 6 and the fact that
$\texttt{Check}_{i}$ accesses $\mathcal{F}_{i-1}$ at most
$n^{\operatorname{O}\left(c\log{n}\right)}$ times, we see that these
quantities satisfy the following relations.

$\displaystyle p_{i}=p_{i-1}+\operatorname{O}\left(c\log{n}\right),\ $
$\displaystyle q_{i}=q_{i-1}+\operatorname{O}\left(c\log{n}\right)$ (7)
$\displaystyle
s_{i}=s_{i-1}+n^{\operatorname{O}\left(c\log{n}\right)}(s_{i-1}+t_{i-1}),\ $
$\displaystyle
t_{i}=t_{i-1}+n^{\operatorname{O}\left(c\log{n}\right)}(s_{i-1}+t_{i-1})$ (8)

It is easy to see that these recurrences solve to
$p_{i},q_{i}=\operatorname{O}\left(ic\log{n}\right)$ and
$s_{i},t_{i}=n^{\operatorname{O}\left(ic\right)}$, so both predicates can be
computed in time $n^{\operatorname{O}\left(ic\right)}$ using
$\operatorname{O}\left(ic\log{n}\right)$ bits of space.

With oracle access to $U_{i-1}$, the predicate $\left[e\in S_{i}\right]$ can
be computed as $\texttt{Check}_{i}(U_{i-1},\mathcal{F}_{i-1},e)$, from which
enumerating $U_{i}$ (resp. $\mathcal{F}_{i}$ and $S_{i}$) is straightforward:
enumerate $U$ (resp. $\mathcal{F}$ and $U$) and suppress elements $e$ (resp.
sets $A$ and elements $f$) which fail the predicate $\left[e\in U_{i}\right]$
(resp. $\left[A\in\mathcal{F}_{i}\right]$ and $\left[f\in S_{i}\right]$).

The most space-hungry operations are the membership queries, so the
enumeration can also be performed using
$\operatorname{O}\left(ic\log{n}\right)$ bits of space. The enumeration needs
time $n^{\operatorname{O}\left(ic\right)}$ for each element of $U$ and
$\mathcal{F}$. Since $\left\lvert
U\right\rvert,\left\lvert\mathcal{F}\right\rvert=\operatorname{O}\left(n^{d}\right)$,
and $d$ is constant, the total time needed is
$n^{\operatorname{O}\left(ic\right)}$. ∎

###  2.3 Derandomization using universal hash families

Some of our algorithms use the trick of randomized sampling to obtain a
certain structure with good probability and then derandomize this procedure by
using a $2$-_universal_ family of hash functions. A $2$-_universal hash
family_ is a family $\mathcal{F}$ of functions from $[n]$ to $[k]$
($n,k\in\mathbb{N}$ and $k\leq n$) such that for any pair $i$ and $j$ of
elements in $[n]$, the number of functions from $\mathcal{F}$ that map $i$ and
$j$ to the same element in $[k]$ is at most $|\mathcal{F}|/k$.

The following proposition is a combination of a result of Carter and Wegman
CW1979JCSS  showing the existence of such families, and the observation that
these families can be enumerated in logarithmic space Vol1999book . Later on,
we use it to derandomize sampling procedures in some of our algorithms.

######  Proposition 3 (Carter and Wegman CW1979JCSS , Proposition 7).

Let $n,k\in\mathbb{N}$ with $n\geq k$. One can enumerate a $2$-universal hash
family for $\left[[n]\to[k]\right]$ in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

##  3 Approximation by layering

We begin this section with the observation that in a directed graph with
maximum out-degree $1$, every connected component contains (as an induced
subgraph or otherwise) at most one (undirected) cycle. For such a directed
graph $D$, consider the graph $G$ obtained by ignoring arc directions. Because
every connected component in $G$ also has at most one cycle, one can find a
_minimum_ vertex cover for $G$ in polynomial time and logarithmic space using
a modified post-order traversal procedure on the connected components. The
following lemma formalizes this discussion.

######  Lemma 2.

Let $D$ be a digraph on $n$ vertices with maximum out-degree $1$ and let $G$
be the undirected graph obtained by ignoring arc directions in $D$. One can
find a minimum vertex cover for $G$ in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

###### Proof.

We prove the result via a sequence of claims about the structure of $D$ which
enables us to apply TreeVtxCover to $G$ and enumerate a minimum vertex cover.

######  Claim.

Every connected component of $G$ has at most one cycle.

Observe that any path in $G$ corresponds to a directed path in $D$: every
vertex of the path except the last has out-degree exactly $1$ in $D$.
Similarly, every vertex in a cycle also has out-degree exactly $1$ in $D$. Now
consider a connected component in $G$. If it contains two cycles, then the
corresponding subgraph of $D$ also contains two directed cycles. They cannot
overlap, as this would mean that one of the vertices common to both cycles has
out-degree more than $1$ in $D$. In the other case, i.e. there is a directed
path from a vertex of one cycle to a vertex of the other, the start vertex of
this path has out-degree greater than $1$ which is also a contradiction. Thus,
the claim is true.

######  Claim.

One can enumerate a minimum vertex cover for every component of $G$ in
polynomial time using $\operatorname{O}\left(\log{n}\right)$ bits of space.

Consider the following procedure, which finds the cycle (if it exists) in any
connected component $C$ of $G$.

  1. 1.

For each vertex $v\in\operatorname{V}\left(C\right)$ with out-degree $1$, set
$c\leftarrow 1$ and perform the following steps.

  2. 2.

    1. (a)

Let $u$ be $v$’s out-neighbour. Set $v\leftarrow u$ and $c\leftarrow c+1$.

    2. (b)

If $c>n$, return $u$.

    3. (c)

If $v$ has an out-neighbour, go back to Step 2a.

  3. 3.

Return NO.

If the above procedure returns NO, then $C$ is cycle-free, i.e. $C$ is a tree.
In this case, using Algorithm 1 on $C$, one can enumerate a minimum vertex
cover in polynomial time using $\operatorname{O}\left(\log{n}\right)$ bits of
space.

In the other case, i.e. where the procedure returns a vertex $u$, the
component $C$ contains a cycle and $u$ is a vertex in the cycle. Observe that
the edge from $u$ to its unique out-neighbour $w$ (in $D$) must be covered by
any minimum vertex cover for $C$, i.e. either $u$ or $w$ must be in the vertex
cover. The graph obtained by deleting either endpoint from $C$ is a tree,
since $C$ contains exactly one cycle. We construct two vertex covers, obtained
by running Algorithm 1 on $C-u$ (resp. $C-w$) and augmenting the result with
$u$ (resp. $w$) to obtain a vertex cover $S_{u}$ (resp. $S_{w}$) for $C$. One
of the two is clearly a minimum vertex cover for $C$, and we enumerate the
smaller of the two as the minimum vertex cover.

The overall process consists merely of running Algorithm 1 in a loop where the
iteration stops after $\operatorname{O}\left(n\right)$ steps. Thus, the
process takes polynomial time and uses $\operatorname{O}\left(\log{n}\right)$
bits of space.

We now prove the main claim, i.e. one can enumerate a minimum vertex cover for
$G$ in polynomial time using $\operatorname{O}\left(\log{n}\right)$ bits of
space. Observe that combining minimum vertex covers for each component of $G$
produces a minimum vertex cover for all of $G$. Thus, by enumerating the
connected components of $G$, one can enumerate a minimum vertex cover for each
component in sequence, producing a minimum vertex cover for all of $G$.

To determine the components and enumerate them, we use the connectivity
algorithm of Reingold Rei2008JACM , which runs in polynomial time and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space. This process has a
polynomial time overhead and an $\operatorname{O}\left(\log{n}\right)$-bit
space overhead, and thus the entire vertex cover can be enumerated in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space as claimed. ∎

The next result follows directly from Lemma 2 using the fact that in any
graph, the complement of a vertex cover an independent set.

######  Lemma 3.

Let $D$ be a digraph on $n$ vertices with maximum out-degree $1$ and let $G$
be the undirected graph obtained by ignoring arc directions in $D$. One can
find a maximum independent set in $G$ in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

###  3.1 Vertex Cover on graphs of bounded degree

We now show that by layering multiple applications of Lemma 2, one can compute
a $2$-approximate minimum vertex cover in a bounded-degree graph. Our approach
is inspired by a distributed algorithm of Polishchuk and Suomela PS2009IPL
which computes $3$-approximate solution.

######  Theorem 3.1.

There is an algorithm which takes as input a graph $G$ on $n$ vertices with
maximum degree $\Delta$, and enumerates a $2$-approximate minimum vertex cover
for $G$. The algorithm runs in time $n^{\operatorname{O}\left(\Delta\right)}$
and uses $\operatorname{O}\left(\Delta\log{n}\right)$ bits of space.

###### Proof.

Set $G_{0}=G$ and $V_{0}=\operatorname{V}\left(G\right)$. The algorithm works
in stages $1,\dotsc,\Delta$ as follows. In Stage $i$, it enumerates the
subgraph $H_{i-1}$ of $G_{i-1}$ in which each vertex of $u$ of $G_{i-1}$ only
retains the edge to its $i$th neighbour $v$ (if it exists) in $G$. Observe
that directing every such edge from $u$ to $v$ yields a directed graph $R$
with maximum out-degree $1$.

Applying the procedure of Lemma 2 with $D=R$ and $G=H_{i-1}$, the algorithm
now enumerates a minimum vertex cover $S_{i}$ for $H_{i-1}$ in polynomial time
using $\operatorname{O}\left(\log{n}\right)$ bits of space. It then enumerates
the graph $G_{i}$ by removing the vertex set $S_{i}$ from $G_{i-1}$ and
outputs the vertices in $S_{i}$. At the end of Stage $\Delta$, the algorithm
terminates.

We now prove the bounds in the claim. Observe that the vertex set of $G_{i}$
($i\in[\Delta]$) is precisely $\operatorname{V}\left(G_{i-1}\right)\setminus
S_{i}$. In Stage $i$, the algorithm only considers the vertices in $G_{i-1}$,
so the vertex cover generated by it has no neighbours in vertex covers
generated in earlier stages, i.e. $S_{i}\cap S_{j}=\emptyset$ for $j<i$.

For each $H_{i-1}$, consider a maximal matching $M_{i}$ in $H_{i-1}$. From the
way the various sets $S_{i}$ are generated, it is easy to see that
$S=\bigcup_{i=1}^{\Delta}S_{i}$ forms a vertex cover for $G$ and additionally,
$M=\bigcup_{i=1}^{\Delta}M_{i}$ is a maximal matching in $G$. Observe that the
each set $S_{i}$ also covers the matching $M_{i}$ in $H_{i-1}$. Since $S_{i}$
is a minimum vertex cover for $H_{i-1}$, and the endpoints of edges in $M_{i}$
form a vertex cover for $H_{i-1}$, we have $\left\lvert S_{i}\right\rvert\leq
2\left\lvert M_{i}\right\rvert$.

As $M$ is a maximal matching in $G$, the endpoints of edges in $M$ form a
vertex cover for $G$, and we have $\left\lvert
S\right\rvert=\sum_{i=1}^{\Delta}\left\lvert S_{i}\right\rvert\leq
2\cdot\sum_{i=1}^{\Delta}\left\lvert M_{i}\right\rvert\leq
2\cdot\sum_{i=1}^{\Delta}\tau(G)$, where $\tau(G)$ is the vertex cover number
of $G$. Thus, the set $S$ output by the algorithm is a $2$-approximate vertex
cover.

Now observe that for all $i\in[\Delta]$, $G_{i}$ and $S_{i}$ satisfy the
hypothesis of Theorem 2.1. Thus, one can enumerate each of the sets $S_{i}$ in
time $n^{\operatorname{O}\left(i\right)}$ using
$\operatorname{O}\left(i\log{n}\right)$ bits of space. Since the maximum value
$i$ takes on is $\Delta$, the algorithm runs in time
$n^{\operatorname{O}\left(\Delta\right)}$ and uses a total of
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space. ∎

###  3.2 $d\text{--}\textsc{Hitting Set}{}$ on families with bounded element
multiplicity

We now consider the $d\text{--}\textsc{Hitting Set}{}$ problem, where an
instance consists of a finite ground set $U$, a family $\mathcal{F}$ of
subsets of $U$ of size at most $d$ and the objective is to compute a hitting
set of minimum size for $\mathcal{F}$.

######  Theorem 3.2.

There is an algorithm which takes as input a graph $G$ on $n$ vertices with
maximum degree $\Delta$ and enumerates a maximal independent set in $G$. The
algorithm runs in time $n^{\operatorname{O}\left(\Delta\right)}$ and uses
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space.

###### Proof.

The argument here is essentially the same as that in the proof of Theorem 3.1
with suitable modifications to compute an independent set instead of a vertex
cover.

Set $G_{0}=G$ and $V_{0}=\operatorname{V}\left(G\right)$. The algorithm works
in stages $1,\dotsc,\Delta$ as follows. In Stage $i$, it enumerates the
subgraph $H_{i-1}$ of $G_{i-1}$ where each vertex $u$ of $G_{i-1}$ only
retains the edge to its $i$th neighbour $v$ (if it exists) in $G$. Observe
that directing every such edge from $u$ to $v$ yields a directed graph $R$
with maximum out-degree $1$.

Applying the procedure of Lemma 3 with $D=R$ and $G=H_{i-1}$, the algorithm
now enumerates a maximum independent set $S_{i}$ in $H_{i-1}$ in polynomial
time using $\operatorname{O}\left(\log{n}\right)$ bits of space. It then
enumerates the graph $G_{i}$ by removing the vertex set
$S_{i}\cup\operatorname{N}\left(S_{i}\right)$ from $G_{i-1}$ and outputs the
vertices in $S_{i}$. At the end of Stage $\Delta$, the algorithm terminates.

We now show that $S=\bigcup_{i=1}^{\delta}S_{i}$ forms a maximal independent
set in $G$. Observe that the vertex set of $G_{i}$ ($i\in[\delta]$) is
precisely the set obtained by removing $S_{i}$ and all vertices incident with
$S_{i}$ from $\operatorname{V}\left(G_{i-1}\right)$. In Stage $i$, the
algorithm only considers the vertices in $G_{i-1}$, whose vertices have no
neighbours in $G_{j}$ for any $j<i-1$. Thus, $S_{i}$ has no neighbours in
independent sets generated in earlier stages and
$S=\bigcup_{i=1}^{\delta}S_{i}$ is an independent set in $G$ as well.

Assume for a contradiction that $S$ is not maximal. Then there is a vertex
$v\in\operatorname{V}\left(G\right)$ which is not incident with any vertex in
$S$. Suppose $v$ is the $i$th neighbour of another vertex in $G$. Either $v$
appears in $H_{i-1}$ or it is excluded because at an earlier stage, some
neighbour of $v$ was included in an independent set $S_{j}$ for some subgraph
$H_{j-1}$ with $j<i$. In the latter case, $v$’s neighbour is in $S$,
contradicting the assumption. In the former case, if $v$ is not included in
the maximum independent set $S_{i}$ for $H_{i-1}$, there is a vertex in
$S_{i}$ adjacent to $v$, which is again a contradiction. Thus, $S$ is a
maximal independent set in $G$.

Now observe that for all $i\in[\Delta]$, $G_{i}$ and $S_{i}$ satisfy the
hypothesis of Theorem 2.1. Thus, one can enumerate each of the sets $S_{i}$ in
time $n^{\operatorname{O}\left(i\right)}$ using
$\operatorname{O}\left(i\log{n}\right)$ bits of space. Since the maximum value
$i$ takes on is $\Delta$, the algorithm runs in time
$n^{\operatorname{O}\left(\Delta\right)}$ and uses a total of
$\operatorname{O}\left(\Delta\log{n}\right)$ bits of space. ∎

What follows is the main result of this section, which extends Theorem 3.1 to
$d\text{--}\textsc{Hitting Set}{}$. Observe that for any instance of
$d\text{--}\textsc{Hitting Set}{}$, the elements of a maximal non-intersecting
subfamily of the input forms a $d$-approximate solution. We show that an input
family $\mathcal{F}$ of sets can be decomposed into multiple smaller families
where it is possible to find maximal non-intersecting subfamilies in
polynomial time and logarithmic space using the algorithm of Theorem 3.2.
These maximal non-intersecting subfamilies can then be combined to obtain a
maximal non-intersecting subfamily of $\mathcal{F}$ whose elements form a
$d$-approximate solution.

######  Theorem 3.3.

There is an algorithm which takes as input a ground set $U$ with $n$ elements,
a family $\mathcal{F}$ of subsets of $U$ of size at most $d\in\mathbb{N}$
where each element of $U$ appears at most $\delta$ times, and enumerates a
$d$-approximate minimum hitting set for $\mathcal{F}$. The algorithm runs in
time $n^{\operatorname{O}\left(d{\delta}^{2}\right)}$ and uses
$\operatorname{O}\left(d{\delta}^{2}\log{n}\right)$ bits of space.

###### Proof.

Set $\mathcal{F}_{0}=\mathcal{F}$ and $U_{0}=U$. Let $e\in U$ be an element
that appears $\delta_{e}$ times in $\mathcal{F}$. From the ordering of the
sets in the input, it is possible to determine (in polynomial time and
logarithmic space) the $i$th ($i\in[\delta_{e}]$) set in which $e$ appears. We
call this the $i$th set for $e$. The algorithm works in stages
$1,\dotsc,\Delta$ as follows. In Stage $i$, it enumerates the subfamily
$\mathcal{H}_{i-1}$ of $\mathcal{F}_{i-1}$ which includes all sets
$A\in\mathcal{F}_{i-1}$ such that $A$ is the $i$th set for some element in
$U_{i-1}$.

The algorithm now enumerates a maximal non-intersecting subfamily
$\mathcal{K}_{i}$ of $\mathcal{H}_{i-1}$. Observe that this can be obtained as
a maximal independent set in the intersection graph of $\mathcal{H}_{i-1}$:
each set is represented by a vertex in the intersection graph, and an
intersection between any two sets is represented by an edge between the
corresponding vertices. One can enumerate this graph by producing
$[\mathcal{H}_{i-1}]$ as the vertex set and producing $ij$ ($1\leq
i<j\leq\left\lvert\mathcal{H}_{i-1}\right\rvert$) as an edge whenever the
$i$th and $j$th sets in $\mathcal{H}_{i-1}$ intersect. Thus, the graph can be
enumerated in polynomial time and logarithmic space. Using Theorem 3.2 on this
graph with $\Delta=d(\delta-1)$, the algorithm computes a maximal non-
intersecting subfamily of $\mathcal{H}_{i-1}$. This step takes time
$n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(d(\delta-1)\log{n}\right)$ bits of space. The algorithm
then outputs $S_{i}=\bigcup\mathcal{K}_{i}$ and enumerates
$U_{i}=U_{i-1}\setminus S_{i}$ as the ground set and
$\mathcal{F}_{i}=\left\\{A\in\mathcal{F}_{i-1}\mid A\cap
S_{i}=\emptyset\right\\}$ as the subfamily for the next stage. At the end of
Stage $\delta$, the algorithm terminates.

Observe that at each stage, the sets in the maximal subfamily computed do not
intersect those in any maximal subfamily computed at later stages.
Additionally, each set in $\mathcal{F}$ appears in some subfamily
$\mathcal{H}_{i}$. Using arguments similar to those in the proof of Theorem
3.2, one can show that the family
$\mathcal{K}=\bigcup_{i=1}^{\delta}\mathcal{K}_{i}$ is a maximal non-
intersecting subfamily of $\mathcal{F}$. Thus, any hitting set $T$ for
$\mathcal{F}$ must contain at least one element from each set in $\mathcal{K}$
and $\left\lvert T\right\rvert\geq\left\lvert\mathcal{K}\right\rvert$. Because
$\mathcal{K}$ is a maximal non-intersecting subfamily of $\mathcal{F}$, any
set in $\mathcal{F}\setminus\mathcal{K}$ intersects some set in $\mathcal{K}$,
i.e. each set in $\mathcal{F}$ contains an element appearing in $\mathcal{K}$.
The algorithm outputs $S=\bigcup_{i\in[\delta]}S_{i}$, the set of elements
appearing in $\mathcal{K}$, which is a hitting set for $\mathcal{F}$, and
since each set in $\mathcal{K}$ has at most $d$ elements, the size of the set
output by the algorithm is at most
$d\cdot\left\lvert\mathcal{K}\right\rvert\leq d\cdot\left\lvert
T\right\rvert$. Thus, the set output is a $d$-approximate minimum hitting set
for $\mathcal{F}$.

We now prove the resource bounds. Observe that for all $i\in[\delta]$,
$S_{i}$, $U_{i}$ and $\mathcal{F}_{i}$ satisfy the hypothesis of Theorem 2.2
with $c=d(\delta-1)$. Thus, one can enumerate each of the sets $S_{i}$ in time
$n^{\operatorname{O}\left(id(\delta-1)\right)}$ using
$\operatorname{O}\left(id(\delta-1)\log{n}\right)$ bits of space. Since the
maximum value $i$ takes on is $\delta$, the algorithm runs in time
$n^{\operatorname{O}\left(d{\delta}^{2}\right)}$ and uses a total of
$\operatorname{O}\left(d{\delta}^{2}\log{n}\right)$ bits of space. ∎

##  4 Staggered Greedy Heuristics

In this section, we consider the $d\text{--}\textsc{Hitting Set}{}$ and
Dominating Set problems. We show that by combining greedy strategies with
certain kernelization rules, one can devise space-efficient approximation
algorithms for both problems. Algorithms for $d\text{--}\textsc{Hitting
Set}{}$ can be used as subroutines in solving various _deletion_ problems,
where the objective is to delete the minimum possible number of vertices from
a graph so that the resulting graph satisfies a certain property. As a
corollary, we devise approximation algorithms for such problems as well.

###  4.1 $d\text{--}\textsc{Hitting Set}{}$

The algorithm of Proposition 2 can be used to approximate
$d\text{--}\textsc{Hitting Set}{}$ as we show below.

######  Corollary 2.

Let $U$ be a ground set with $n$ elements and $\mathcal{F}$ be a family of
subsets of $U$ of size at most $d\in\mathbb{N}$. One can enumerate an
$\operatorname{O}\left(dn^{1-1/d}\right)$-approximate minimum hitting set for
$\mathcal{F}$ in time $n^{\operatorname{O}\left(d^{2}\right)}$ using
$\operatorname{O}\left(d^{2}\log{n}\right)$ bits of space.

###### Proof.

Consider the following algorithm. Starting at $k=1$, run the algorithm of
Proposition 2 and repeatedly increment the value of $k$ until $k=n^{1/d}$ or
the algorithm returns a solution of size
$\operatorname{O}\left(d{(k+1)}^{d}\right)$ (i.e. it does not return a NO
answer) for the first time. If $k$ is incremented until $n^{1/d}$, then simply
return the entire universe as the solution. Clearly, the approximation ratio
is $n^{1-1/d}$, as $OPT\geq n^{1/d}$ (and so the size of the solution returned
is $n=n^{1-1/d}\cdot n^{1/d}\leq n^{1-1/d}\cdot OPT$, where $OPT$ is the size
of the minimum hitting set).

If $k<n^{1/d}$, then the size of the solution produced is
$\operatorname{O}\left(d{(k+1)}^{d}\right)$, and we know that $OPT\geq k$,
since the algorithm had returned NO answers until this point. So the size of
the solution produced is
$\operatorname{O}\left(d{(k+1)}^{d}\right)=\operatorname{O}\left(d(k+1)^{d-1}\cdot(OPT+1)\right)=\operatorname{O}\left(dn^{1-1/d}\cdot(OPT+1)\right)$.
Thus, we have an $\operatorname{O}\left(dn^{1-1/d}\right)$-approximation. The
bounds on running time and space used follow from the fact that the algorithm
of Proposition 2 runs in time $n^{\operatorname{O}\left(d^{2}\right)}$ and
uses $\operatorname{O}\left(d^{2}\log{n}\right)$ bits of space. ∎

What follows is the key result en route to developing a space-efficient
approximation algorithm for $d\text{--}\textsc{Hitting Set}{}$.

######  Lemma 4.

Let $0<\epsilon\leq 1$. There is an algorithm which takes as input a family
$\mathcal{F}$ of $d$-subsets of a ground set $U$ with $n$ elements and
$k\in\mathbb{N}$, and either determines correctly that $\mathcal{F}$ has no
hitting set of size at most $k$ or enumerates a hitting set of size
$\operatorname{O}\left((d/\epsilon)k^{1+\epsilon}\right)$. The algorithm runs
in time $n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$ and uses
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits of space.

###### Proof.

Let $i=\left\lceil(d-1)/\epsilon\right\rceil$. The algorithm performs $i$
rounds of computation, each using $\operatorname{O}\left(\log{n}\right)$ bits
of space to determine a set of elements (accessible by oracle) to be removed
in the next round, or determine that $\mathcal{F}$ has no hitting set of size
at most $k$.

  1. 1.

Use the algorithm of Proposition 2 to obtain a subfamily
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ over the ground set
$U^{\prime}\subseteq U$ such that

     * •

$\left\lvert\mathcal{F}^{\prime}\right\rvert\leq c{(k+1)}^{d},\ \left\lvert
U^{\prime}\right\rvert=cd{(k+1)}^{d}$, and

     * •

there exists a hitting set $S\subseteq U$ of size at most $k$ in $\mathcal{F}$
if and only if there exists a hitting set $S^{\prime}\subseteq U^{\prime}$ and
$S^{\prime}$ is a hitting set for $\mathcal{F}^{\prime}$.

  2. 2.

Set $U_{0}=U^{\prime}$ and $\mathcal{F}_{0}=\mathcal{F}^{\prime}$. For
$j=\left\\{1,2,\dotsc,i-1\right\\}$, perform the following steps.

     * •

Determine $S_{j}$, the set of all elements in $U_{j-1}$ which appear in at
least $c{(k+1)}^{d-1-j\epsilon}$ sets in $\mathcal{F}_{j-1}$.

     * •

Let $U_{j}=U_{j-1}\setminus S_{j}$ and
$\mathcal{F}_{j}=\left\\{A\in\mathcal{F}_{j-1}\mid A\cap
S_{j}=\emptyset\right\\}$. If there are more than $c(k+1)^{d-j\epsilon}$ sets
in $\mathcal{F}_{j}$, then return NO.

  3. 3.

Determine $S_{i}$, the set of all elements in $U_{i-1}$ which are in some set
in $\mathcal{F}_{i-1}$. Output $S=\bigcup_{j=1}^{i}S_{j}$.

We now prove the correctness of the algorithm. In Step 1, the algorithm
obtains the ground set $U^{\prime}$ and the family$\mathcal{F}^{\prime}$,
using the algorithm of Proposition 2. Let $l\in[i-1]$ such that the algorithm
answers NO in Step 2 for $j=l$, and otherwise let $l=i$ if it never returns a
NO answer in Step 2.

######  Claim.

For all $j\in[l]$, $\mathcal{F}_{j}$ has at most $c{(k+1)}^{d-j\epsilon}$
sets.

Consider the case when the algorithm does not return a NO answer. Observe that
the claim holds for the base case $j=1$: $\mathcal{F}_{0}$ has $c{(k+1)}^{d}$
sets, and since the algorithm does not return a NO answer, we have
$\left\lvert\mathcal{F}_{1}\right\rvert\leq c{(k+1)}^{d-j\epsilon}$. For
induction, observe that whenever $\left\lvert\mathcal{F}_{j}\right\rvert\leq
c{(k+1)}^{d-j\epsilon}$, the algorithm ensures that
$\left\lvert\mathcal{F}_{j+1}\right\rvert\leq c(k+1)^{d-(j+1)\epsilon}$;
otherwise, it returns a NO answer.

Suppose the algorithm returns a NO answer at some value of $j$ in Step 2, then
there are more than $c{(k+1)}^{d-j\epsilon}$ sets in $\mathcal{F}_{j}$, which
have survived the repeated removal of sets from $\mathcal{F}_{0}$ up to this
point, and they cannot be hit by any $k$ of the elements in $U_{j}$, since
each element can hit at most $c{(k+1)}^{d-1-j\epsilon}$ sets in
$\mathcal{F}_{j}$. Thus, the algorithm correctly infers that the input does
not have a hitting set of size at most $k$.

Once the algorithm has reached Step 3, the number of sets in the residual
family, $\mathcal{F}_{i-1}$ is at most
${(k+1)}^{d-\left(\left\lceil(d-1)/\epsilon\right\rceil-1\right)\cdot\epsilon}<k^{d-\left((d-1)/\epsilon-1\right)\cdot\epsilon}=k^{1+\epsilon}$.
The set $S_{i}$ of elements in $U_{i-1}$ that appear in some set in
$\mathcal{F}_{i-1}$ is trivially also a hitting set. Observe that the sets of
elements removed in earlier stages, i.e. $S_{0},\dotsc,S_{i-1}$ together hit
all sets in $\mathcal{F}$ not appearing in $\mathcal{F}_{i-1}$. Thus, the set
$S=\bigcup_{j=0}^{i}S_{j}$ output by the algorithm is a hitting set for
$\mathcal{F}$.

######  Claim.

The set $S$ output by the algorithm has at most
$\left({(d-1)/\epsilon}+d\right)k^{1+\epsilon}$ elements.

For each $j\in[i-1]$, the algorithm ensures that
$\left\lvert\mathcal{F}_{j-1}\right\rvert\leq c{(k+1)}^{d-(j-1)\epsilon}$
(otherwise, it returns a NO answer). Thus, the number of elements which appear
in at least $c{(k+1)}^{d-1-j\epsilon}$ sets is at most
$\left(c{(k+1)}^{d-(j-1)\epsilon}\right)/\left(c{(k+1)}^{d-1-j\epsilon}\right)=k^{1+\epsilon}$,
i.e. $\left\lvert S_{j}\right\rvert\leq k^{1+\epsilon}$.

In Step 3, the algorithm ensures that
$\left\lvert\mathcal{F}_{i-1}\right\rvert\leq k^{d-(i-1)\epsilon}\leq
k^{1+\epsilon}$. Each set in $\mathcal{F}_{i-1}$ edges and each of these edges
can span at most $d$ elements. Thus, the number of elements in $U_{i-1}$ which
appear in some set in $\mathcal{F}_{i-1}$ $dk^{1+\epsilon}$, i.e. $\left\lvert
S_{i}\right\rvert\leq dk^{1+\epsilon}$. Therefore, the total number of
elements output by the algorithm in all three phases is $\left\lvert
S\right\rvert=\sum_{j=1}^{i}\left\lvert
S_{j}\right\rvert\leq(i-1)k^{1+\epsilon}+dk^{1+\epsilon}\leq\left(\left\lceil(d-1)/\epsilon\right\rceil+d\right)k^{1+\epsilon}$.

######  Claim.

The algorithm runs in time
$n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$ and uses
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits of space.

Observe that in Step 1, the family $\mathcal{F}_{0}$ is obtained using the
algorithm of Proposition 2, which runs in time
$n^{\operatorname{O}\left(d^{2}\right)}$ and uses
$\operatorname{O}\left(d^{2}\log{n}\right)$ bits of space (for any constant
$d$). The output of the algorithm can now be used as an oracle for $G_{0}$.

In Step 2, each successive family $\mathcal{F}_{j}$ ($j\in[i-1]$) is obtained
from $\mathcal{F}_{j-1}$ by deleting sets containing elements which appear in
at least $k^{1-j\epsilon}$ sets (this test can be performed using
$\operatorname{O}\left(\log{n}\right)$ bits of space). Thus, given oracle
access to $\mathcal{F}_{j-1}$, an oracle for $\mathcal{F}_{j}$ can be provided
which runs in polynomial time and uses $\operatorname{O}\left(\log{n}\right)$
bits of space.

Step 3 involves writing out all elements in $U_{i-1}$ that appear in some set
in $\mathcal{F}_{i-1}$, which can also be done in
$\operatorname{O}\left(\log{n}\right)$ bits of space given oracle access to
$G_{i-1}$. Since the number of oracles created in Step 2 is $i-1$, the various
oracles together run in time $n^{\operatorname{O}\left(i\right)}$ and use
$\operatorname{O}\left(i\log{n}\right)=\operatorname{O}\left((d/\epsilon)\log{n}\right)$
bits of space (Theorem 2.1). Combined with the
$n^{\operatorname{O}\left(d^{2}\right)}$ time and
$\operatorname{O}\left(d^{2}\log{n}\right)$ bits of space used by the oracle
of Step 1, this gives bounds of
$n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$ on the running time and
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits on the total
space used by the algorithm. ∎

The next result follows from the above lemma.

######  Theorem 4.1.

Let $0<\epsilon\leq 1$. For instances $(U,\mathcal{F})$ of
$d\text{--}\textsc{Hitting Set}{}$ with $\left\lvert U\right\rvert=n$, one can
enumerate an
$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$-approximate minimum
hitting set in time $n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}$
using $\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits of
space.

###### Proof.

Consider the following algorithm. Starting with $k=1$, iteratively apply the
procedure of Lemma 4 and increment $k$’s value until it returns a family of
size $\operatorname{O}\left((d/\epsilon)k^{1+\epsilon}\right)$ or
$k=\left\lceil n^{1-\epsilon}\right\rceil$. When $k=\left\lceil
n^{1-\epsilon}\right\rceil$ return the entire universe as the solution. In
this case, $OPT\geq n^{1-\epsilon}$, the size of the solution produced is $n$
and $n\leq n^{\epsilon}\cdot OPT$, so we have a factor-$n^{\epsilon}$
approximation.

In the other case, the algorithm returns a family of size
$\operatorname{O}\left((d/\epsilon)k^{1+\epsilon}\right)$ for some $k$. Note
that $OPT\geq k$ (as the algorithm returned NO so far), so the solution
produced is of size $\operatorname{O}\left((d/\epsilon)k^{\epsilon}k\right)$,
which is $\operatorname{O}\left((d/\epsilon)n^{\epsilon}OPT\right)$, i.e. we
have a factor-$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$
approximation. As we merely reuse the procedure of Lemma 4, the overall
running time is $n^{\operatorname{O}\left((d^{2}+(d/\epsilon))\right)}$ and
the amount of space used is
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)$ bits. ∎

The above theorem allows us to devise space-efficient approximation algorithms
for a number of _graph deletion_ problems. Let $\Pi$ be a hereditary class of
graphs, i.e. a class closed under taking induced subgraphs. Let $\Phi$ be a
set of forbidden graphs for $\Pi$ such that a graph $G$ is in $\Pi$ if and
only no induced subgraph of $G$ is isomorphic to a graph in $\Phi$. Consider
the problem $\textsc{Del--}\Pi_{fin}$ (described below), defined for classes
$\Pi$ with finite sets $\Phi$ of forbidden graphs.

> Instance
>
>
> $G$, a graph
>
> Solution
>
>
> a minimum-size set of vertices whose deletion yields a graph in $\Pi$

The next result is a combination of the fact that $\textsc{Del--}\Pi$ can be
formulated as a certain hitting set problem and the procedure of Theorem 4.1.

######  Lemma 5.

Let $\epsilon\leq 1$ be a positive number. On graphs with $n$ vertices, one
can enumerate
$\operatorname{O}\left((1/\epsilon)n^{\epsilon}\right)$-approximate solutions
for $\textsc{Del--}\Pi_{fin}$ in time
$n^{\operatorname{O}\left(1/\epsilon\right)}$ using
$\operatorname{O}\left((1/\epsilon)\log{n}\right)$ bits of space.

###### Proof.

Let $\Phi$ be the (finite) set of forbidden subgraphs characterizing $\Pi$,
$d$ be the maximum number of vertices in any graph in $\Phi$ and $G$ be the
input graph with $n$ vertices. Start by enumerating the following family.

$\mathcal{F}_{G}=\left\\{S\subseteq\operatorname{V}\left(G\right)\mid G[S]\
\text{contains a graph from}\ \Phi\right\\}$

This can be done by running over all subsets of $V(G)$ of size at most $d$,
and checking for each subset $S$ whether $G[S]$ is isomorphic to some graph in
$\Phi$. Since there are constantly many graphs in $\Phi$, this procedure takes
time $\operatorname{O}\left(n^{d}\right)$ and uses
$\operatorname{O}\left(d\log{n}\right)$ bits of space. Now using the procedure
of Theorem 4.1, enumerate an
$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)$-approximate minimum
hitting set for $\mathcal{F}_{G}$.

Observe that any set of vertices is a hitting set for $\mathcal{F}_{G}$ if and
only if it is a deletion set for $G$ (as an instance of
$\textsc{Del--}\Pi_{fin}$). Thus, the hitting set enumerated is an
$\operatorname{O}\left((d/\epsilon)n^{\epsilon}\right)=\operatorname{O}\left((1/\epsilon)n^{\epsilon}\right)$-approximate
($d$ is constant) minimum deletion set for $G$. The procedure runs in time
$n^{\operatorname{O}\left(d^{2}+(d/\epsilon)\right)}=n^{\operatorname{O}\left(1/\epsilon\right)}$
and uses
$\operatorname{O}\left((d^{2}+(d/\epsilon))\log{n}\right)=\operatorname{O}\left((1/\epsilon)\log{n}\right)$
bits of space. Combined with the enumeration procedure, the overall running
time is
$n^{\operatorname{O}\left(d\cdot(1/\epsilon)\right)}=n^{\operatorname{O}\left(1/\epsilon\right)}$
and the amount of space used is
$\operatorname{O}\left(d\log{n}+(1/\epsilon)\log{n}\right)=\operatorname{O}\left((1/\epsilon)\log{n}\right)$
bits. ∎

The following list defines problems for which we obtain polylogarithmic-space
approximation algorithms using the preceding lemma.

Triangle-Free Deletion

Instance: $(G,k)$, where $G$ is a graph and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(G\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ has no triangles?

Tournament FVS

Instance: $(D,k)$, where $D$ is a a tournament and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(D\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ is acyclic?

Cluster Deletion

Instance: $(G,k)$, where $G$ is a graph and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(G\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ is a disjoint union of
cliques, i.e. a cluster graph?

Split Deletion

Instance: $(G,k)$, where $G$ is a graph and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(G\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ can be partitioned into a
clique and an independent set, i.e. such that $(G-S)$ is a split graph?

Threshold Deletion

Instance: $(G,k)$, where $G$ is a graph and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(G\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ is threshold graph? A
threshold graph is one which can be constructed from a single vertex by a
sequence of operations that either add an isolated vertex, or add a vertex
which dominates all the other vertices.

Cograph Deletion

Instance: $(G,k)$, where $G$ is a graph and $k\in\mathbb{N}$
Question: Is there a set $S\subseteq\operatorname{V}\left(G\right)$ with
$\left\lvert S\right\rvert\leq k$ such that $G-S$ contains no induced paths of
length $4$, i.e. it is a cograph?

For all the problems appearing above, the target graph classes are known to be
characterized by a finite set of forbidden induced subgraphs (see e.g. Cygan
et al. CFK+2015book ) and so the problems can be formulated as
$\textsc{Del--}\Pi$. By setting $\epsilon$ to a small positive constant or
$(1/\log{n})$, we obtain the following corollary to Lemma 5.

######  Corollary 3.

On graphs with $n$ vertices, one can enumerate

  * •

$\operatorname{O}\left(n^{\epsilon}\right)$-approximate solutions in time
$n^{\operatorname{O}\left(1/\epsilon\right)}=n^{\operatorname{O}\left(1\right)}$
using
$\operatorname{O}\left((1/\epsilon)\log{n}\right)=\operatorname{O}\left(\log{n}\right)$
bits of space for any positive constant $\epsilon\leq 1$, and

  * •

$\operatorname{O}\left(\log n\right)$-approximate solutions in time
$n^{\operatorname{O}\left(\log{n}\right)}$ using
$\operatorname{O}\left(\log^{2}n\right)$ bits of space

for the problems Vertex Cover, Triangle-Free Deletion,
Threshold Deletion, Cluster Deletion, Split Deletion,
Cograph Deletion and Tournament FVS.

###  4.2 Dominating Set

In this section, we describe approximation algorithms for Dominating Set
restricted to certain graph classes. A problem instance consists of a graph
$G=(V,E)$ and $k\in\mathbb{N}$, and the objective is to determine if there is
a _dominating set_ of size at most $k$, i.e. a set $S\subseteq V$ of at most
$k$ vertices such that $S\cup\operatorname{N}\left(S\right)=V$.

The first result of this section concerns graphs excluding $C_{4}$ (a cycle on
$4$ vertices) as a subgraph. On such graphs, one can enumerate
$\operatorname{O}\left(\sqrt{n}\right)$-approximations in time
$n^{\operatorname{O}\left(1\right)}$ and
$\operatorname{O}\left(\log{n}\right)$ bits of space using a known
kernelization algorithm RS2008Algorithmica .

####  4.2.1 $C_{4}$-Free Graphs

Any vertex $v\in\operatorname{V}\left(G\right)$ of degree at least $2k+1$ must
be in any dominating set of size at most $k$, as any other vertex (including a
neighbour of $v$) can dominate at most $2$ vertices in the neighbourhood (as
there will be a $C_{4}$ otherwise). Using this, we establish the following
result.

######  Lemma 6.

There is an algorithm which takes as input a $C_{4}$-free graph $G$ on $n$
vertices and $k\in\mathbb{N}$, and either determines that $G$ has no
dominating set of size at most $k$, or outputs a dominating set of size
$\operatorname{O}\left(k^{2}\right)$. The algorithm runs in time
$n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space.

###### Proof.

Consider the following algorithm.

  1. 1.

Let $S$ be the set of vertices with degree more than $2k$. If $|S|$ is more
than $k$, return NO.

  2. 2.

The set $S$ dominates all vertices in $\operatorname{N}\left(S\right)$. If
$\left\lvert
V\setminus(S\cup\operatorname{N}\left(S\right))\right\rvert>(2k+1)\cdot(k-\left\lvert
S\right\rvert)$ return NO, as each vertex in $V\setminus S$ can dominate at
most $2k+1$ vertices including itself.

  3. 3.

Output $S\cup(V\setminus(S\cup\operatorname{N}\left(S\right)))$.

Recall that any vertex $v\in\operatorname{V}\left(G\right)$ of degree at least
$2k+1$ must be in any dominating set of size at most $k$. Correctness is now
immediate from the the description of the algorithm. When it outputs vertices,
it outputs $S$, which has at most $k$ vertices from Step 1, and the number of
remaining vertices in Step 2 is $\operatorname{O}\left(k^{2}\right)$, so it
outputs $\operatorname{O}\left(k^{2}\right)$ vertices overall. To see that the
space used is $\operatorname{O}\left(\log{n}\right)$ bits, observe that
membership in each of the sets output is determined by predicates that test
degrees of vertices individually, and these predicates can by computed in
logarithmic space. Thus, by Theorem 2.1, the algorithm uses a total of
$\operatorname{O}\left(\log{n}\right)$ bits of space. ∎

The proof of the following corollary uses arguments very similar to those in
the proof of Theorem 4.1, so we omit it.

######  Corollary 4.

There is an algorithm which takes as input a $C_{4}$-free graph $G$ on $n$
vertices, and enumerates an
$\operatorname{O}\left(\sqrt{n}\right)$-approximate minimum dominating set for
$G$. The algorithm runs in polynomial time and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space.

####  4.2.2 Bounded-Degeneracy Graphs

A graph is called $d$-degenerate if there is a vertex of degree at most $d$ in
every subgraph of $G$. Examples include planar graphs, which are
$5$-degenerate and graphs with maximum degree $d$, which are trivially
$d$-degenerate.

There is a generalization of the polynomial kernel for Dominating Set on
$C_{4}$-free graphs (used in Section 4.2.1) to $K_{i,j}$-free graphs for any
fixed $i,j\in\mathbb{N}$ PRS2012TALG  ($K_{i,j}$ is the complete bipartite
graph with $i$ vertices in one part and $j$ vertices in the other). The class
of $K_{i,j}$-free graphs includes $C_{4}$-free graphs and for $i\leq j$,
$(i+1)$-degenerate graphs. This kernel however, does not seem amenable to
modifications that would allow its use in computing approximate solutions
using logarithmic or even polylogarithmic space. To design a space-efficient
approximation algorithm for $d$-degenerate graphs, we resort instead to the
factor-$\operatorname{O}\left(d^{2}\right)$ approximation algorithm of Jones
et al. JLR+2017SIDMA . We make several adaptations to achieve an
$\operatorname{O}\left(\log^{2}{n}\right)$ bound on the space used.

Let $G$ be a $d$-degenerate graph on $n$ vertices. As every subgraph of $G$
has a vertex with degree at most $d$, the number of edges in $G$ is at most
$dn$. The following lemma is an immediate consequence of this.

######  Lemma 7.

In any $p$-vertex subgraph of a $d$-degenerate graph, at least $p/2$ vertices
are of degree at most $2d$.

The following is a description of our algorithm.

Input: $G=(V,E)$, a $d$-degenerate graph

Output: $S$, an $\operatorname{O}\left(d^{2}\right)$-approximate minimum
dominating set for $G$

1

2$W,W_{h}\leftarrow V$;

3 $W_{l},Y,B,B_{h},B_{l}\leftarrow\emptyset$;

4 while  _$W_{h}\neq\emptyset$_ do // there are vertices in $W_{h}$ to be
dominated

5 $W^{*}\leftarrow W\cup B_{h}$;

6 $S\leftarrow\left\\{v\in W_{h}\mid\deg_{G[W^{*}]}\left(v\right)\leq
2d\right\\}$;

7 $Y\leftarrow Y\cup\operatorname{N}_{G[W^{*}]}\left(S\right)$ // $Y$ is the
partial solution;

8 $B\leftarrow\operatorname{N}\left(Y\right)$;

9 $W\leftarrow V\setminus(Y\cup B)$;

10 $B_{h}\leftarrow\left\\{v\in B\mid\deg_{G[W]}\left(v\right)\geq
2d+1\right\\}$;

11 $B_{l}\leftarrow B\setminus B_{h}$;

12 $W^{*}\leftarrow W\cup B_{h}$;

13 $W_{h}\leftarrow\left\\{v\in W\mid v\ \text{is not isolated in}\
G[W^{*}]\right\\}$;

14 $W_{l}\leftarrow W\setminus W_{h}$;

15

16return _$Y\cup W_{l}$_

Algorithm 2 DgnDomSet: find an approximate minimum dominating set

The algorithm starts by picking the neighbours of all vertices (they form the
set $S$) of degree at most $2d$, and repeatedly finds such vertices in smaller
and smaller subgraphs of $G$, picking all their neighbours into the solution
as well. As each such vertex or one of its neighbours must be in any
dominating set, this will result in an
$\operatorname{O}\left(d\right)$-approximate solution if we manage to find a
vertex that dominates (at least one and) at most $2d$ of the non-dominated
vertices (set $W$ on Line 2). This may not happen in the intermediate steps as
more and more vertices are dominated by those vertices picked earlier. So the
algorithm carefully partitions the set of undominated vertices.

Figure 1: Partitioning of the vertices in the algorithm for Dominating Set on
$d$-degenerate graphs.

Let $Y$ be the set of vertices picked at any point, $B$ be the set of vertices
(other than those in $Y$) dominated by $Y$, and $W$ be the set of vertices in
$V\setminus(Y\cup B)$ (see Figure 1). The goal is to dominate vertices in $W$,
and we try to do so by finding (the neighbours of) low degree vertices from
$B\cup W$. So we start finding low degree (at most $2d$) vertices in $B\cup W$
to pick their neighbours. First we look for such vertices in $B$, and so we
further partition $B$ into $B_{h}$, those vertices of $B$ with at least $2d+1$
neighbours in $W$ and $B_{l}=B\setminus B_{h}$.

First, we remove (for later consideration) vertices of $W$ that have no
neighbours in $W\cup B_{h}$, let they be $W_{l}$ and focus on the induced
subgraph $G[B_{h}\cup W_{h}]$ where $W_{h}=W\setminus W_{l}$. Here, we are
bound to find low degree vertices from $W_{h}$ (as vertices in $B_{h}$ have
high degree) as long as $W_{h}$ is non-empty, and so we repeat the above
procedure of picking the neighbours of all low degree vertices from $W_{h}$.
Eventually, when $W_{h}$ becomes empty, if $W_{l}$ is non-empty, we simply
pick all vertices of $W_{l}$ into the solution. What follows is a pseudocode
description of the algorithm.

If we treat a round as the step where we find all vertices in $W_{h}$ with at
most $2d$ neighbours in $W_{h}$, then as at least a fraction of the vertices
of $W_{h}$ are dominated in each round (Lemma 7), the number of rounds is
$\operatorname{O}\left(\log n\right)$. Each round just requires identifying
vertices based on their degrees in the resulting subgraph, the $i$-th round
can be implemented in $\operatorname{O}\left(i\log n\right)$ bits using
Theorem 2.1 resulting in an $\operatorname{O}\left(\log^{2}n\right)$ bits
implementation.

The approximation ratio of $\operatorname{O}\left(d^{2}\right)$ can be proved
formally using a charging argument (see Jones et al. JLR+2017SIDMA , Theorem
4.9). We give an informal explanation here. First we argue the approximation
ratio of $(2d+1)$ for the base case when $W_{h}$ is empty. Isolated vertices
in $W_{l}$ are isolated vertices in $G$ and hence they need to be picked in
the solution. The number of non-isolated vertices in $W_{l}$ is at most
$2d|B_{l}|$ as their neighbours are only in $B_{l}$ (otherwise, by definition,
those vertices will be in $W_{h}$). As vertices in $B_{l}$ have degree at most
$2d$, $|W_{l}|\leq 2d|B_{l}|$ and as at least one vertex of $B_{l}\cup W_{l}$
must be picked to dominate a vertex in $W_{l}$, we have the approximation
ratio of $(2d+1)$ for those vertices.

In the intermediate step, if we did not ignore vertices in $B_{l}$ to dominate
a vertex in $W_{h}$, a $(2d+1)$\- approximation is clear. For, a vertex or one
of its at most $2d$ neighbours must be picked in the dominating set. However,
a vertex in $W_{h}$ maybe dominated by a vertex in $B_{l}$, but by ignoring
$B_{l}$, we maybe picking $2d$ vertices to dominate it. As a vertex in $B_{l}$
can dominate at most $2d$ such vertices of $W_{h}$, we get an approximation
ratio of $\operatorname{O}\left(d^{2}\right)$.

The next theorem formalizes the above discussion.

######  Theorem 4.2.

There is an algorithm which takes as input a $d$-degenerate graph on $n$
vertices and enumerates an $\operatorname{O}\left(d^{2}\right)$-approximate
minimum dominating for it. The algorithm runs in time
$n^{\operatorname{O}\left(\log{n}\right)}$ and uses
$\operatorname{O}\left(\log^{2}{n}\right)$ bits of space.

##  5 Randomization

In this section, we devise approximation algorithms for restricted versions of
Independent Set and Dominating Set using hash families constructible in
logarithmic space to derandomize known randomized sampling procedures.

###  5.1 Independent Set on graphs with bounded average degree

On general graphs, the problem is unlikely to have a non-trivial
(factor-$(n^{1-\epsilon})$) approximation algorithm Has1999ActaMath . However,
if the graph has average degree $d$, then an independent set satisfying the
bound of the next lemma is a $(2d)$-approximate solution. Note that graphs of
bounded average degree encompass planar graphs and graphs of bounded
degeneracy. It is also known that $2d$ is the best approximation ratio
possible up to polylogarithmic factors in $d$ AKS2011TOC ; Cha2016JACM .

######  Proposition 4 (Alon and Spencer AS2008book , Theorem 3.2.1).

If a graph on $n$ vertices has average degree $d$, then it has an independent
set of size at least $n/(2d)$.

In what follows, we develop a logarithmic-space procedure that achieves the
above bound. Let $G=(V,E)$ be a graph on $n$ vertices with average degree $d$.
Consider a set $S\subseteq V$ obtained by picking each vertex in $V$
independently with probability $p=1/d$. Let $m_{S}$ be the number of edges
with both endpoints in $S$. The following bound appears as an intermediate
claim in the proof of Proposition 4 (see Alon and Spencer AS2008book , Theorem
3.2.1). We use it here without proof.

######  Lemma 8.

$\operatorname{\mathbb{E}}\left[\left\lvert S\right\rvert-
m_{S}\right]=n/(2d)$.

Consider the set $I$ obtained by arbitrarily eliminating an endpoint of each
edge in $G[S]$. Observe that $G[I]$ has no edges, i.e. $I$ is an independent
set whose expected size is $\operatorname{\mathbb{E}}\left[\left\lvert
S\right\rvert-m_{S}\right]=n/(2d)$.

Derandomizing this sampling procedure is simple: simply run through the
functions of a $2$-universal hash family $\mathcal{F}$ for
$\left[[n]\to[d]\right]$ and for each $f\in\mathcal{F}$, pick a vertex $v\in
V$ into $S$ if and only if $f(v)=1$. Because the range of the functions is
$[d]$, the sampling probability is $\operatorname{P}\left(v\in S\right)=1/d$.
Recall that Lemma 8 only requires the sampling procedure to be pairwise
independent, so the expectation bound remains the same:
$\operatorname{\mathbb{E}}\left[\left\lvert S\right\rvert-
m_{S}\right]=n/(2d)$. While going through $\mathcal{F}$, select the function
$f\in\mathcal{F}$ which maximizes $|S|-m_{S}$, where $S=\left\\{v\in V\mid
f(v)=1\right\\}$ and $m_{S}$ is the number of edges $uv\in E$ with
$f(u)=f(v)=1$. Using the construction of Proposition 3, this step can be
performed in polynomial time using $\operatorname{O}\left(\log{n}\right)$ bits
of space and $f$ can be used as an oracle for $S$ at the same space cost.

The next step, in which vertices are deleted arbitrarily from each pair of
adjacent vertices in the sample $S$, is tricky to carry out in small space.
This is because for any edge $uv$ in $G[S]$, it is not possible to determine
whether either of the endpoints survive the deletion procedure without
additional information about the other edges incident with $u$ and $v$.
However, we can achieve this by using the ordering induced on the vertices by
the input encoding to ensure that vertices in $S$ are retained only if they
are the smallest (in the input ordering) vertices in their neighbourhoods in
$G[S]$. Using this, we prove the following lemma.

######  Lemma 9.

Let $T$ be the set of vertices $v\in S$ such that $v$ is the smallest vertex
in its neighbourhood in $G[S]$. The set $T$ is independent in $G$, has size
$\left\lvert T\right\rvert\geq\left\lvert S\right\rvert-m_{S}$, and one can
enumerate $T$ in polynomial time using $\operatorname{O}\left(\log n\right)$
bits of space.

###### Proof.

Determining if $v\in S$ is the smallest vertex in its neighbourhood in $G[S]$
involves enumerating the neighbourhood of $v$ in the induced subgraph $G[S]$
which can be performed in polynomial time using
$\operatorname{O}\left(\log{n}\right)$ bits of additional space. As we pick
only one vertex from each neighbourhood, the picked set $T$ is independent and
it is trivial to see that the overall procedure is polynomial-time and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space.

Let $C_{1},\dotsc,C_{t}$ be the connected components of $G[S]$. Consider the
difference between the number of vertices and the number of edges in each
component. Any component with $l$ vertices contains at least $l-1$ edges. For
$i\in[t]$, denote by $n_{i}$ the number of vertices in $C_{i}$ and by $m_{i}$,
the number of edges. We have $\sum_{i=1}^{t}(n_{i}-1)\leq\sum_{i=1}^{t}m_{i}$,
i.e. $\sum_{i=1}^{t}n_{i}-t\leq\sum_{i=1}^{t}m_{i}=m_{S}$, which implies that
$t\geq n-m_{S}$. As we pick at least one vertex (the smallest vertex) from
each component in $T$, we have $\left\lvert T\right\rvert\geq t\geq n-m_{S}$.
∎

We now have the following theorem as a direct consequence of the above
results.

######  Theorem 5.1.

There is a an algorithm which takes as input a graph $G$ on $n$ vertices with
average degree $d$, and enumerates a $(2d)$-approximate maximum independent
set in $G$. The algorithm runs in time $n^{\operatorname{O}\left(1\right)}$
and uses $\operatorname{O}\left(\log{n}\right)$ bits of space.

###  5.2 Dominating Set on $d$-regular graphs

In what follows, we use similar techniques as above to devise a
factor-$(\log{(d+1)}+1)$ approximation algorithm for Dominating Set restricted
to $d$-regular graphs.

######  Proposition 5 (Alon and Spencer AS2008book , Theorem 1.2.2).

Any graph on $n$ vertices with minimum degree $d$ has a dominating set of size
at most $n(\log{(d+1)}+1)/(d+1)$.

On a $d$-regular graph, because the size of any dominating set is at least
$n/(d+1)$, the approximation ratio achieved is $\log{(d+1)}+1$.

Now we outline the proof of the above proposition to show how it can be
derandomized. Consider a $d$-regular graph $G$ on $n$ vertices. Picking each
vertex of $G$ with probability $p=\log{(d+1)}/(d+1)$ yields a set $S$ with
expected size $\operatorname{\mathbb{E}}\left[\left\lvert
S\right\rvert\right]=np$. By adding in the vertices not dominated by $S$, we
obtain a dominating set
$W=S\cup(V\setminus(S\cup\operatorname{N}\left(S\right)))$. The expected size
of this set is $\operatorname{\mathbb{E}}\left[\left\lvert
W\right\rvert\right]\leq n(p+{(1-p)}^{d+1})$, and it can be shown that this
quantity is $n(\log{(d+1)}+1)/(d+1)$.

Note that the expectation bounds only need the sampling of the vertices to be
pairwise independent. Consider a $2$-universal hash family $\mathcal{F}$ for
$\left[[n]\to[d+1]\right]$, and define
$S_{f}=\left\\{v\in\operatorname{V}\left(G\right)\mid
f(v)\leq\log{(d+1)}+1\right\\}$ and
$W_{f}=S_{f}\cup(V\setminus(S_{f}\cup\operatorname{N}\left(S_{f}\right)))$.
Over functions $f=\mathcal{F}$, the sampling probability
$\operatorname{P}\left(v\in S_{f}\right)$ is
$\left\lfloor(\log{(d+1)}+1)/(d+1)\right\rfloor$. Because $\mathcal{F}$ is a
$2$-universal hash family, there is a function $f\in\mathcal{F}$ for which
$W_{f}$ achieves the expectation bound for $\left\lvert W\right\rvert$ above.

The sampling procedure can now be derandomized as follows. Begin by
enumerating $\mathcal{F}$ in logarithmic space using Proposition 3. For each
$f\in\mathcal{F}$, determine $\left\lvert W_{f}\right\rvert$, and output
$W_{f}$ for the first function $f$ for which $\left\lvert
W_{f}\right\rvert\geq n(\log{(d+1)}+1)/(d+1)$.

We thus have the following result.

######  Theorem 5.2.

There is an algorithm which takes as input a $d$-regular graph $G$ on $n$
vertices and enumerates a $(\log{(d+1)}+1)$-approximate minimum dominating set
for $G$. The algorithm runs in time $n^{\operatorname{O}\left(1\right)}$ and
uses $\operatorname{O}\left(\log{n}\right)$ bits of space.

##  6 Conclusion

We devised space efficient approximation algorithms for
$d\text{--}\textsc{Hitting Set}{}$ (and its restriction Vertex Cover),
Independent Set and Dominating Set in some special classes of graphs.

The algorithms all require random access to their inputs. It is possible to
translate them for the streaming model: each time the algorithm reads an
element from the input, it makes a single pass. In this way, the space bounds
for the translated algorithms remain essentially the same (additive overhead
of $\operatorname{O}\left(\log{n}\right)$ bits for reading in passes), but
they require as many passes over their inputs as the running times of the
original algorithms.

We consider our contribution as simply drawing attention to a direction in the
study of approximation algorithms, and believe that it should be possible to
improve the approximation ratios and the space used for the problems
considered here. Obtaining a constant-factor or even
factor-$\operatorname{O}\left(\log{n}\right)$ approximation algorithm for
Vertex Cover and a factor-$\operatorname{O}\left(\log n\right)$ approximation
algorithm for Dominating Set on general graphs using
$\operatorname{O}\left(\log{n}\right)$ bits of space are some specific open
problems of interest.

## References

  * (1) Allender, E., Mahajan, M.: The complexity of planarity testing 189(1), 117–134.  DOI 10.1016/j.ic.2003.09.002
  * (2) Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions 2(2), 153–177.  DOI 10.1145/1150334.1150336
  * (3) Alon, N., Spencer, J.H.: The Probabilistic Method, 3 edn.  Wiley
  * (4) Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-First Search Using O(n) Bits.  In: 25th International Symposium on Algorithms and Computation, vol. 8889, pp. 553–564. Springer-Verlag.  DOI 10.1007/978-3-319-13075-0˙44
  * (5) Austrin, P., Khot, S., Safra, M.: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs 7(1), 27–43.  DOI 10.4086/toc.2011.v007a003
  * (6) Banerjee, N., Chakraborty, S., Raman, V., Roy, S., Saurabh, S.: Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs.  In: Computing and Combinatorics, vol. 9198, pp. 349–360. Springer International Publishing.  DOI 10.1007/978-3-319-21398-9˙28
  * (7) Beame, P.: A general Sequential Time-Space Tradeoff for Finding Unique Elements 20(2), 270–277.  DOI 10.1137/0220017
  * (8) Berger, B., Rompel, J., Shor, P.W.: Efficient NC algorithms for set cover with applications to learning and geometry 49(3), 454–477.  DOI 10.1016/S0022-0000(05)80068-6
  * (9) Biswas, A., Raman, V., Saurabh, S.: Approximation in (Poly-) Logarithmic Space.  In: 45th International Symposium on Mathematical Foundations of Computer Science, vol. 170, p. 15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  DOI 10.4230/LIPIcs.MFCS.2020.16
  * (10) Borodin, A., Cook, S.A.: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation 11(2), 287–297.  DOI 10.1137/0211022
  * (11) Borodin, A., Fischer, M.J., Kirkpatrick, D.G., Lynch, N.A., Tompa, M.: A time-space tradeoff for sorting on non-oblivious machines 22(3), 351–364.  DOI 10.1016/0022-0000(81)90037-4
  * (12) Buss, J.F., Goldsmith, J.: Nondeterminism within P 22(3), 560–572.  DOI 10.1137/0222038
  * (13) Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability 84(1), 119–138.  DOI 10.1016/S0168-0072(95)00020-8
  * (14) Carter, J.L., Wegman, M.N.: Universal classes of hash functions 18(2), 143–154.  DOI 10.1016/0022-0000(79)90044-8
  * (15) Chakraborty, S., Mukherjee, A., Raman, V., Satti, S.R.: A Framework for In-place Graph Algorithms.  In: 26th Annual European Symposium on Algorithms, vol. 112, pp. 13:1 – 13:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  DOI 10.4230/lipics.esa.2018.13
  * (16) Chakraborty, S., Raman, V., Satti, S.R.: Biconnectivity, st-numbering and other applications of DFS using O(n) bits 90, 63–79.  DOI 10.1016/j.jcss.2017.06.006
  * (17) Chan, S.O.: Approximation Resistance from Pairwise-Independent Subgroups 63(3), 1–32.  DOI 10.1145/2873054
  * (18) Chan, T.M., Munro, J.I., Raman, V.: Selection and Sorting in the “Restore” Model 14(2), 1–18.  DOI 10.1145/3168005
  * (19) Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space 8(3), 385–394.  DOI 10.1016/0196-6774(87)90018-6
  * (20) Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs 85(1), 12–75.  DOI 10.1016/0890-5401(90)90043-H
  * (21) Cygan, M., Fomin, F.V., Kowalik, L.u., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms.  Springer-Verlag
  * (22) Dinur, I., Steurer, D.: Analytical approach to parallel repetition.  In: Proceedings of the 46th Annual Symposium on Theory of Computing, pp. 624–633. ACM Press.  DOI 10.1145/2591796.2591884
  * (23) Elberfeld, M., Jakoby, A., Tantau, T.: Logspace Versions of the Theorems of Bodlaender and Courcelle.  In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science, pp. 143–152. IEEE Comput. Soc. Press.  DOI 10.1109/FOCS.2010.21
  * (24) Elberfeld, M., Kawarabayashi, K.i.: Embedding and canonizing graphs of bounded genus in logspace.  In: Proceedings of the 46th Annual Symposium on Theory of Computing, pp. 383–392. ACM Press.  DOI 10.1145/2591796.2591865
  * (25) Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient Basic Graph Algorithms.  In: Proceedings of the 32nd Annual Symposium on Theoretical Aspects of Computer Science, vol. 30, pp. 288–301. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  DOI 10.4230/lipics.stacs.2015.288
  * (26) Fafianie, S., Kratsch, S.: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time.  In: Mathematical Foundations of Computer Science, vol. 9235, pp. 299–310. Springer-Verlag.  DOI 10.1007/978-3-662-48054-0˙25
  * (27) Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection 34(1), 19–26.  DOI 10.1016/0022-0000(87)90002-X
  * (28) Hå stad, J.: Clique is hard to approximate within n(̂1 - $\epsilon$) 182(1), 105–142.  DOI 10.1007/BF02392825
  * (29) Hagerup, T.: Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster 82(4), 1033–1056.  DOI 10.1007/s00453-019-00629-x
  * (30) Harris, D.G.: Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set 15(3), 1–29.  DOI 10.1145/3326171
  * (31) Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Suchý, O.: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs 31(2), 1294–1327.  DOI 10.1137/15M103618X
  * (32) Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 - $\epsilon$ 74(3), 335–349.  DOI 10.1016/j.jcss.2007.06.019
  * (33) Li, J., O’Donnell, R.: Bounding Laconic Proof Systems by Solving CSPs in Parallel.  In: Proceedings of the 29th Annual Symposium on Parallelism in Algorithms and Architectures, pp. 95–100. ACM Press.  DOI 10.1145/3087556.3087557
  * (34) Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem 15(4), 1036–1053.  DOI 10.1137/0215074
  * (35) Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming.  In: Proceedings of the 25th Annual Smposium on Theory of Computing, pp. 448–457. ACM Press.  DOI 10.1145/167088.167211
  * (36) McGregor, A.: Graph stream algorithms: A survey 43(1), 9–20.  DOI 10.1145/2627692.2627694
  * (37) Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage 12(3), 315–323.  DOI 10.1016/0304-3975(80)90061-4
  * (38) Munro, J.I., Raman, V.: Selection from read-only memory and sorting with minimum data movement 165(2), 311–323.  DOI 10.1016/0304-3975(95)00225-1
  * (39) Pagh, R., Pagter, J.: Optimal time-space trade-offs for non-comparison-based sorting.  In: Proceedings of the 13th Annual Symposium on Discrete Algorithms, pp. 9–18. SIAM.  DOI 10.5555/545381.545383
  * (40) Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting.  In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 264–268. IEEE Comput. Soc. Press.  DOI 10.1109/SFCS.1998.743455
  * (41) Papadimitriou, C.H.: Computational Complexity.  Addison-Wesley
  * (42) Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond 9(1), 1–23.  DOI 10.1145/2390176.2390187
  * (43) Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover 109(12), 642–645.  DOI 10.1016/j.ipl.2009.02.017
  * (44) Raman, V., Ramnath, S.: Improved upper bounds for time-space trade-offs for selection 6(2), 162–180.  DOI 10.5555/762350.762354
  * (45) Raman, V., Saurabh, S.: Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles 52(2), 203–225.  DOI 10.1007/s00453-007-9148-9
  * (46) Reif, J.H.: Symmetric Complementation 31(2), 401–421.  DOI 10.1145/62.322436
  * (47) Reingold, O.: Undirected connectivity in log-space 55(4), 1–24.  DOI 10.1145/1391289.1391291
  * (48) Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities 4(2), 177–192.  DOI 10.1016/S0022-0000(70)80006-X
  * (49) Serna, M.: Approximating linear programming is log-space complete for P 37(4), 233–236.  DOI 10.1016/0020-0190(91)90194-M
  * (50) Tantau, T.: Logspace Optimization Problems and Their Approximability Properties 41(2), 327–350.  DOI 10.1007/s00224-007-2011-1
  * (51) Trevisan, L.: Parallel Approximation Algorithms by Positive Linear Programming 21(1), 72–88.  DOI 10.1007/PL00009209
  * (52) Trevisan, L., Xhafa, F.: The Parallel Complexity of Positive Linear Programming 08(04), 527–533.  DOI 10.1142/S0129626498000511
  * (53) Vollmer, H.: Introduction to Circuit Complexity.  Springer-Verlag
  * (54) Yamakami, T.: Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems.  In: Combinatorial Optimization and Applications, vol. 8287, pp. 318–329. Springer-Verlag.  DOI 10.1007/978-3-319-03780-6˙28