THM, University of Applied Sciences Mittelhessen, Giessen,
Germanyfrank.kammer@mni.thm.dehttps://orcid.org/0000-0002-2662-3471 THM,
University of Applied Sciences Mittelhessen, Giessen,
Germanyjohannes.meintrup@mni.thm.dehttps://orcid.org/0000-0003-4001-1153 THM,
University of Applied Sciences Mittelhessen, Giessen, Germany
andrej.sajenko@mni.thm.dehttps://orcid.org/0000-0001-5946-8087 Funded by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 379157101.
Frank Kammer, Johannes Meintrup and Andrej Sajenko [500]Mathematics of
computing Graph algorithms

###### Acknowledgements.

We thank the anonymous reviewers for their careful reading of our manuscript
and their helpful comments. 0

# Space-Efficient Vertex Separators for Treewidth

Frank Kammer  Johannes Meintrup  Andrej Sajenko

###### Abstract

For $n$-vertex graphs with treewidth $k=O(n^{1/2-\epsilon})$ and an arbitrary
$\epsilon>0$, we present a word-RAM algorithm to compute vertex separators
using only $O(n)$ bits of working memory. As an application of our algorithm,
we give an $O(1)$-approximation algorithm for tree decomposition. Our
algorithm computes a tree decomposition in $c^{k}n(\log\log n)\log^{*}n$ time
using $O(n)$ bits for some constant $c>0$.

We finally use the tree decomposition obtained by our algorithm to solve
Vertex Cover, Independent Set, Dominating Set, MaxCut and $q$-Coloring by
using $O(n)$ bits as long as the treewidth of the graph is smaller than
$c^{\prime}\log n$ for some problem dependent constant $0<c^{\prime}<1$.

###### keywords:

FPT, tree decomposition, network flow, subgraph stack

##  1 Introduction

For solving problems in the context of the ever-growing field of big data we
require algorithms and data structures that do not only focus on runtime
efficiency, but consider space as an expensive and valuable resource. Some
reasons for saving memory are that slower memory in the memory hierarchy has
to be used, less cache faults arise and the available memory allows us to run
more parallel tasks on a given problem.

As a solution researchers began to provide space-efficient algorithms and data
structures to solve basic problems like graph-connectivity problems [3, 5, 14,
19, 23], other graph problems [26, 31], memory initialization [25, 32],
dictionaries with constant-time operations [12, 15, 22] or graph interfaces
[6, 26] space efficiently, i.e., they designed practical algorithms and data-
structures that run (almost) as fast as standard solutions for the problem
under consideration while using asymptotically less space. Several space-
efficient algorithms and data structures mentioned above are implemented in an
open source GitHub project [30].

Our model of computation is the word RAM where we assume to have the standard
operations to read, write as well as arithmetic operations (addition,
subtraction, multiplication and bit shift) take constant time on a word of
size $\Theta(\log n)$ bits where $n\in I\\!\\!N$ is the size of the input. To
measure the total amount of memory that an algorithm requires we distinguish
between the input memory, i.e., the read-only memory that stores the input,
and the working memory, i.e., the read-write memory an algorithm additionally
occupies during the computation. In contrast, the _streaming model_ [34]
allows us to access the input only in a purely sequential fashion, and the
main goal is to minimize the number of passes over the input. There are
several algorithms for NP-hard problems on a streaming model, e.g., a
kernelization algorithm due to Fafianie and Kratsch [20]. Elberfeld, Jakoby,
and Tantau [18] proved that the problem of obtaining a so-called tree
decomposition is contained in LSPACE.

We continue the research of Banerjee, Chakraborty, Raman, Roy and Saurabh [4]
on space-efficient algorithm on the word RAM for NP-hard problems, but they
assumed that a tree decomposition is already given with the input.

One approach to solve NP-hard graph problems is to decompose the given graph
into a tree decomposition consisting of a tree where each node of the tree has
a bag containing a small fraction of the original vertices of the graph. The
quality of a tree decomposition is measured by its width, i.e., the number of
vertices of the largest bag minus 1. The treewidth of a graph is the smallest
width over all tree decompositions for the graph. Having a tree decomposition
$(T,B)$ of a graph, the problem is solved by first determining the solution
size of the problem in a bottom-up traversal on $T$ and second in a top-down
process computing a solution for the whole graph. Treewidth is also a topic in
current interdisciplinary research, such as smart contracts using
cryptocurrency [13] or computational quantum physics [17], which are fields
that often work with big data sets. So it is important to have space efficient
algorithms.

Several algorithms are known for computing a tree decomposition. For the
following, we assume that the given graphs have $n$ vertices and treewidth
$k$. Based on ideas in [38], Reed [36] showed an algorithm for computing a
tree decomposition of width $O(k)$ in time $O(c^{k}n\log n)$ for some constant
$c$. His algorithm repeatedly uses a so-called balanced separator that splits
the input graph into roughly equally sized subgraphs, each used as an input
for a recursive call of the algorithm. Further tree-decomposition algorithms
can be found in [2, 8, 11, 21, 33]. Recently, Izumi and Otachi [27] presented
an algorithm that runs with $o(n)$ bits, but $\Omega(n^{2})$ time on graphs
with treewidth $k=O(n^{1/2-\epsilon})$ for an arbitrary $\epsilon>0$. The
basic strategy of repeated separator searches is the foundation of all
treewidth approximation algorithms, as mentioned by Bodlaender et al. [10].
Using the same strategy, Bodlaender et al. also presented an algorithm that
runs in $2^{O(k)}n$ time and finds a tree decomposition having width $5k+4$.

To obtain a space-efficient approximation algorithm for treewidth we modify
Reed’s algorithm. We finally use a hybrid approach, which combines our new
algorithm and Bodlaender et al.’s algorithm [10] to find a tree decomposition
in $b^{k}n(\log^{*}n)\log\log n$ time for some constant $b$. The general idea
for the hybrid approach is to use our space-efficient algorithm for treewidth
only for constructing the nodes of height at most $b^{k}\log\log n$. For the
subgraph induces by the bags of the vertices below a node of height
$b^{k}\log\log n$, we use Bodlaender et al.’s algorithm. The most
computationally difficult task of this paper is the computation of the
separators with $O(n)$ bits.

Finding separators requires finding vertex-disjoint paths for which a DFS as a
subroutine is usually used. All recent space-efficient DFS require $\Omega(n)$
bits [3, 14, 19, 23] or $\Omega(n^{2})$ time due to $\Omega(n)$ separator
searches [27]. Thus, our challenge is to compute a separator and subsequently
a tree decomposition with $O(n)$ bits with a running time almost linear in
$n$.

To compute a separator of size at most $k$ with $O(n\log k)$ bits, the idea is
to store up to $k$ vertex disjoint paths by assigning a color
$c\in\\{0,\ldots,k\\}$ to each vertex $v$ such that we know to which path $v$
belongs. We also number the vertices along a path with $1,2,3,1,2,3,$ etc. so
that we know the direction of the path. Since we want to find separators with
only $O(n)$ bits, we further show that it suffices to store the color
information only at every $\Theta(\log k)$th vertex. We so manage to find
separators of size at most $k$ with $O(n+k^{2}(\log k)\log n)$ bits. If
$k=O(n^{1/2-\epsilon})$ for an arbitrary $\epsilon>0$, we thus use $O(n)$
bits.

Our solution to find a separator is in particular interesting because previous
space-efficient graph-traversal algorithms either reduce the space from
$O(n\log n)$ bits to $O(n)$, e.g., depth first search (DFS) or breath first
search (BFS) [14, 19, 23], or reduce the space from $O(m\log n)$ to $O(m)$,
e.g., Euler partition [26] and cut-vertices [28]. In contrast, we reduce the
space for the separator search from $O((n+m)\log n)$ bits to $O(n)$ bits for
small treewidth $k$.

Besides the separator search, many algorithms for treewidth store large
subgraphs of the $n$-vertex, $m$-edge input graph during recursive calls,
i.e., they require $\Omega((n+m)\log n)$ bits. We modify and extend the
algorithm presented by Reed with space-efficiency techniques (e.g., store
recursive graph instances with the so-called subgraph stack [26]) to present
an iterator that allows us to output the bags of a tree decomposition of width
$O(k)$ in an Euler-traversal order using $O(kn)$ bits in $c^{k}n\log
n\log^{*}n$ time for some constant $c$. To lower the space bound further, we
use the subgraph stack only to store the vertices of the recursive graph
instances. For the edges we present a new problem specific solution.

In Section 2, we summarize known data structures and algorithms that we use
afterwards. Our main result, the computation of $k$-vertex disjoint paths is
shown in Section 3. We sketch Reed’s algorithm in Section 4, where we also
show a space-efficient computation of a balanced vertex separator using $O(n)$
bits. In Section 5 we present an iterator that outputs the bags of a tree
decomposition using $O(kn)$ bits. In the following section we lower the space
bound to $O(n)$ bits for small treewidth, and show our hybrid approach. We
conclude the paper by showing in Section 8 that our tree decomposition
iterator can be used to solve NP-hard problems like Vertex Cover, Independent
Set, Dominating Set, MaxCut and $q$-Coloring with $O(n)$ bits on graphs with
small treewidth. The table below summarizes the space bound of the algorithms
described in this paper.

| standard | intermediate goal | final goal
---|---|---|---
$k$ vertex-disjoint paths | $\Omega(kn\log n)$ |  $\Theta(n)$ (Sect. 3)
balanced vertex separator | $\Omega(kn\log n)$ |  $\Theta(n)$ (Sect. 4)
subgraph stack | $\Omega(kn\log n)$ |  $\Theta(kn)$ (Sect. 5) |  $\Theta(n)$ (Sect. 6)
iterator for a t.d. | $\Omega(kn\log n)$ |  $\Theta(kn)$ (Sect. 5) |  $\Theta(n)$ (Sect. 7)
NP-hard problems above | $\Omega(kn\log n)$ |  $\Theta(n)$ (Sect. 8)
Table 1: The space requirements in bits to run the different parts of the
algorithm to compute a tree decomposition (t.d.) with applications for an
$n$-vertex graph with sufficiently small treewidth $k$.

##  2 Preliminaries

Let $G=(V,E)$ be an undirected $n$-vertex $m$-edge graph. If it is helpful, we
consider an edge $\\{u,v\\}$ as two directed edges (called arcs) $(u,v)$ and
$(v,u)$. As usual for graph algorithms we define $V=\\{1,\ldots,n\\}$. For
every vertex $v\in V$, we access the in- and out-degree of $v$ through
functions $\mathtt{deg}^{\rm{in}}_{G},\mathtt{deg}^{\rm{out}}_{G}:V\rightarrow
I\\!\\!N$ that returns the number of incoming and outgoing edges of vertex
$v$, respectively. Moreover,
$\mathtt{deg}_{G}=\mathtt{deg}^{\rm{in}}_{G}+\mathtt{deg}^{\rm{out}}_{G}$. We
denote by $N(v)\subset V$ the neighborhood of $v$. For $A=\\{(v,k)\in V\times
I\\!\\!N\ |\ 1\leq k\leq\mathtt{deg}_{G}(v)\\}$, let
$\mathtt{head}_{G}:A\rightarrow V$ be a function such that
$\mathtt{head}_{G}(v,k)$ returns the $k$th neighbor of $v$. Intuitively
speaking, each vertex has an adjacency array. If space is not a concern, it is
customary to store each graph that results from a transformation separately.
To save space, we always use the given graph $G$ and store only some auxiliary
information that helps us to implement the following graph interface for a
transformed graph.

######  Definition 2.1.

(graph interface) A data structure for a graph $G=(V,E)$ implements the graph
interface (with adjacency arrays) exactly if it provides the functions
$\mathtt{deg}_{G}:V\rightarrow I\\!\\!N$, $\mathtt{head}_{G}:A\rightarrow V$,
where $A=\\{(v,k)\in(V\times I\\!\\!N)\ |\ 1\leq k\leq\mathtt{deg}_{G}(v)\\}$,
and gives access to the number $n$ of vertices and the number $m$ of edges.

Let $G=(V,E)$ be a graph and let $V^{\prime}\subseteq V$. During our
computation, some of our graph interfaces can support $\mathtt{head}_{G}(v,k)$
and $\mathtt{deg}_{G}(v)$ only for vertices $v\notin V^{\prime}$. For vertices
in $V^{\prime}$, we can access their neighbors via adjacency lists, i.e., we
can use the functions $\mathtt{adjfirst}:V^{\prime}\rightarrow
P\cup\\{\mathtt{null}\\}$, $\mathtt{adjhead}:P\rightarrow V$ and
$\mathtt{adjnext}:P\rightarrow P\cup\\{\mathtt{null}\\}$ for a set of pointers
$P$ to output the neighbors of a vertex $v$ as follows:
$p:=\mathtt{adjfirst}(v)$; $\mathtt{while}$ $(p\neq\mathtt{null})$ {
$\mathtt{print}\ \mathtt{adjhead}(p)$; $p:=\mathtt{adjnext}(p)$; }. We then
say that we have a graph interface with $|V^{\prime}|$ access-restricted
vertices.

In an undirected graph it is common to store an edge at both endpoints, hence,
every undirected edge $\\{u,v\\}$ is stored as an arc (directed edge) $(u,v)$
at the endpoint $u$ and as an arc $(v,u)$ at the endpoint $v$. We also use the
two space-efficient data structures below.

######  Definition 2.2.

(subgraph stack [26, Theorem 4.7]) The subgraph stack is a data structure
initialized for an $n$-vertex $m$-edge undirected graph $G_{0}=(V,E)$ that
manages a finite list $(G_{0},\ldots,G_{\ell})$, called the client list, of
ordered graphs such that $G_{i}$ is a proper subgraph of $G_{i-1}$ for
$0<i\leq\ell$.

Each graph in the client list implements the graph-access interface supporting
the access operations from above in $O(\log^{*}n)$ time. Additionally, it
provides the following operations:

  * •

$\mathtt{push}(B_{V},B_{A})$: Appends a new graph
$G_{\ell+1}=(V_{\ell+1},E_{\ell+1})$ to the client list. The graph is
represented by two bit arrays $B_{V}$ and $B_{A}$, with $B_{V}[i]=1$,
$B_{A}[i]=1$ exactly if the vertex $i$ (or arc) of $G_{\ell}$ is still
contained in $G_{\ell+1}$. It runs in $O((|B_{V}|+|B_{A}|)\log^{*}n)$.

  * •

$\mathtt{pop}$: Removes $G_{\ell}$ from the client list in constant time.

  * •

$\mathtt{toptune}$: Subsequent accesses to the interface of $G_{\ell}$ can run
in $O(1)$ time. Runs in $O((|V_{\ell}|+|E_{\ell}|)\log^{*}n)$ time and uses
$O(n+m)$ bits additional space.

For the special case where we have a constant $\epsilon$ with $0<\epsilon<1$
such that $|V_{i+1}|<\epsilon|V_{i}|$ and $|E_{i+1}|<\epsilon|E_{i}|$ for all
$0\leq i<\ell$, the entire subgraph stack uses
$\sum_{i=0}^{\infty}(\epsilon_{1}^{i}n+\epsilon_{2}^{i}m)=O(n+m)$ bits of
space. We will use the subgraph stack only in this special case with
$\epsilon=2/3$.

Using fast rank-select data structures [7] one can easily support the
following data structure.

######  Definition 2.3.

(static space allocation) For $n\in I\\!\\!N$, let $V=\\{1,\ldots,n\\}$ be the
universe and $K\subset V$ a fixed set of keys with $|K|=O(n/\log b)$ for some
$b\leq n$. Assume that the keys are stored within an array of $n$ bits so that
a word RAM can read $K$ in $O(n/\log n)$ time. Then there is a data structure
using $O(n)$ bits that allows us to read and write $O(\log b)$ bits in
constant time for each $k\in K$ and the initialization of the data structure
can be done in $O(n/\log n)$ time.

We now formally define a tree decomposition.

######  Definition 2.4.

(tree decomposition [37], bag) A tree decomposition of a graph $G=(V,E)$ is a
pair $(T,B)$ where $T=(W,F)$ is a tree and $B$ is a mapping
$W\rightarrow\\{V^{\prime}\ |\ V^{\prime}\subseteq V\\}$ such that the
following properties hold: (TD1) $\bigcup_{w\in W}G[B(w)]=G$, and (TD2) for
each vertex $v\in V$, the nodes $w$ with $v\in B(w)$ induce a subtree in $T$.
For each node $w\in W$, $B(w)$ is called the bag of $w$.

We recall from the introduction that the width of a tree decomposition is
defined as the number of vertices in a largest bag minus 1 and the treewidth
of a graph $G$ as the minimum width among all possible tree decompositions for
$G$. We subsequently also use the well-known fact that an $n$-vertex graph $G$
with treewidth $k$ has $O(kn)$ edges [37].

Our algorithms use space-efficient BFS and DFS.

######  Theorem 2.5.

(BFS [19]) Given an $n$-vertex $m$-edge graph $G$, there is a BFS on $G$ that
runs in $O(n+m)$ time and uses $O(n)$ bits.

By taking the randomized DFS of Choudhari et al. [14] and replacing a
randomized dictionary [14, Lemma 3] by Hagerup’s dictionary [23, Corollary
5.3], we obtain the following.

######  Theorem 2.6.

Given an $n$-vertex $m$-edge graph $G$, there is a DFS on $G$ that runs in
$O(m+n\log^{*}n)$ time and uses $O(n)$ bits.

The DFS of Theorem 2.6 assumes that we provide a graph interface with
adjacency arrays. Later we run a DFS on an $n$-vertex graph $G$ with treewidth
$k$, but can only provide a graph interface with $O(k)$ access-restricted
vertices, i.e., $O(k)$ vertices are provided by a list interface.

######  Lemma 2.7.

Assume that a graph interface for an $n$-vertex, $m$-edge graph $G$ with
$O(k)$ access-restricted vertices for some $k\in I\\!\\!N$ is given. Assume
further that we can iterate over the adjacency list of an access-restricted
vertex $v$ in $O(f(n,m))$ time for some function $f$, whereas we can access an
entry in the adjacency array of another vertex still in $O(1)$ time. Then,
there is a DFS that runs in $O(k\cdot f(n,m)+m+n\log^{*}n)$ time and uses
$O(n+k\log n)$ bits.

######  Proof 2.8.

To get an idea consider first a standard DFS. Basically it starts from some
vertex $v\in V$, visits each vertex of the connected component of $G$, and
iterates over the incident edges of each visited vertex once. If the DFS
visits a vertex $w$, then the current $v$-$w$ path is managed in a stack that
stores the status of the current iteration over the incident edges of each
vertex on the path, i.e., for each vertex on the path, it stores the index of
the edges of the path such that the DFS can return to a vertex and proceed
with the next edge to explore another path. The space-efficient DFS (Theorem
2.6) stores only a small part of the entire DFS stack and uses further stacks
with approximations of the index pointers to reconstruct removed information
from the stack. The reason for storing only small parts of the stack as well
as approximate indices is to bound the space-usage by $O(n)$ bits. Let
$V^{\prime}$ be the set of access-restricted vertices with $|V^{\prime}|=k$.
For the access restricted vertices $V^{\prime}$ we are not able to use this
strategy, since we only provide a list interface i.e, we are unable to use
indices. Thus, for the vertices of $V^{\prime}$ we simply ignore the space
restrictions imposed by the storage scheme of the DFS and instead store a
pointer with $\Theta(\log n)$ bits into the adjacency list for each vertex
$v^{\prime}\in V^{\prime}$ additionally to the storage scheme already in place
for the DFS, just as any regular DFS working with adjacency lists would need.
This of course uses extra space and thus results in the space-efficient DFS
using $O(n+k\log n)$ bits instead of $O(n)$ bits. Since there is one iteration
over the incident edges of each of the $O(k)$ access-restricted vertices, the
running time of the DFS increases to $O(k\cdot f(n,m)+m+n\log^{*}n)$ time.

##  3 Finding $k$ Vertex-Disjoint Paths using $O(n+k^{2}(\log k)\log n)$ Bits

To compute $k$ vertex-disjoint $s$-$t$-paths we modify a standard network-flow
technique where a so-called residual network [1] and a standard DFS is used.

######  Lemma 3.1.

(Network-Flow Technique [1]) Given an integer $k$ as well as an $n$-vertex
$m$-edge graph $G=(V,E)$ with $k$ pairwise internal vertex-disjoint
$s$-$t$-paths for some vertices $s,t\in V$, there is an algorithm that can
compute $\ell\leq k$ internal pairwise vertex-disjoint $s$-$t$ paths using
$O((n+m)\log n)$ bits by executing $\ell$ times a depth-first search, i.e., in
$O(\ell(n+m))$ time.

The well-known network-flow technique increases the size of an initially empty
set of internal vertex-disjoint $s$-$t$-paths one by one in rounds. It makes
usage of (1) a so-called residual network for extending a set of edge-disjoint
paths by another edge disjoint path and (2) a simple reduction that allows us
to find vertex-disjoint paths by constructing edge-disjoint paths in a
modified graph. We can neither afford storing any copy of a the original
graph, a graph transformated nor the exact routing of several paths because it
would take $\Theta(n\log n)$ bits. Instead, we use graph interfaces that allow
access to a modified graph on the fly and we partition the paths in parts
belonging to small so-called regions that allow us to store exact path
membership on the boundaries and recompute the paths in between the boundaries
of the regions on the fly if required. For a sketch of the idea, see Fig.1.
Storing the exact path membership only for the boundaries has the drawback
that we cannot recompute the original paths inside a region, but using a
deterministic algorithm we manage to compute always the same one. It is
important for us to remark that the network-flow technique above also works
even if we change the exact routing of the $s$-$t$-paths (but not their
number) before or after each round.

$s\phantom{t}$ $t$

$\dots$

$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$ Figure 1: Vertex-disjoint
$s$-$t$-paths with colored boundaries. Some regions are exemplary sketched by
green rectangles.

For the rest of this section, let $G=(V,E)$ be an $n$-vertex $m$-edge graph
with treewidth $k\in I\\!\\!N$ such that $G$ has $k$ internal pairwise vertex-
disjoint $s$-$t$-paths for some vertices $s,t\in V$ and let $\mathcal{P}$ be a
set of $\ell\leq k$ pairwise internally vertex-disjoint $s$-$t$-paths. Let
$V^{\prime}$ be the set that consists of the union of all vertices over all
paths in $\mathcal{P}$.

Before we can present our algorithm, we present two lemmas that consider
properties of internal pairwise vertex-disjoint paths as given in
$\mathcal{P}$. To describe the properties we first define a special path
structure (with respect to $G$). A deadlock cycle in $G$ with respect to
$\mathcal{P}$ consists of a sequence $P_{1},\ldots,P_{\ell^{\prime}}$ of paths
in $\mathcal{P}$ for some $2\leq\ell^{\prime}\leq\ell$ such that there is a
subpath $x_{i},\ldots,y_{i}$ on every path $P_{i}$ ($1\leq
i\leq\ell^{\prime}$) and there is an edge
$\\{x_{i},y_{(i\mod\ell^{\prime})+1}\\}\in E$. We call a deadlock cycle simple
if every subpath consists of exactly two vertices, and otherwise extended (see
Fig. 2). Moreover, we call an $s$-$t$-path $P$ chordless if only subsequent
vertices of the path are connected by an edge called chord. In some sense, a
chord of a path is a deadlock cycle over only one path.

$P_{\ell}$$P_{\ell^{\prime}}$$P_{2}$$P_{1}$$\vdots$$\vdots$$\vdots$$\vdots$

$P_{\ell}$$P_{\ell^{\prime}}$$P_{2}$$P_{1}$$\vdots$$\vdots$$\vdots$$\vdots$

Figure 2: Illustration of a simple and extended deadlock cycle (left and
right, respectively).

######  Lemma 3.2.

Assume that the paths in $\mathcal{P}$ are chordless and that $G$ has no
extended deadlock cycle with respect to $\mathcal{P}$. Any other set
$\mathcal{Q}$ of $\ell$ internal pairwise vertex-disjoint $s$-$t$-paths in
$G[V^{\prime}]$ uses all vertices of $V^{\prime}$.

######  Proof 3.3.

Note that each path in $\mathcal{P}$ uses another neighbor of $s$ and since
the paths are chordless, $s$ can not have another neighbor in $V^{\prime}$. In
other words, $s$ has exactly $\ell$ neighbors in $V^{\prime}$ and each path in
$\mathcal{Q}$ must use exactly one of these neighbors. This allows us to name
the paths in $\mathcal{P}$ and in $\mathcal{Q}$ with $P_{1},\ldots,P_{\ell}$
and $Q_{1},\ldots,Q_{\ell}$, respectively, such that the second vertex of
$P_{i}$ and $Q_{i}$ are the same for all $i\in\\{1,\ldots,\ell\\}$.

The following description assumes suitable indices of the paths in
$\mathcal{P}$. Assume for a contradiction that the lemma is not true. This
means that $P_{1}$ uses a vertex $v$ whereas $Q_{1}$ leaves the vertices of
$P_{1}$ at some vertex $u$ to avoid using a vertex $v\in V^{\prime}$. Since
the paths are chordless, $Q_{1}$ must jump on a vertex of a path $P_{2}$.
Since the paths are chordless, this means that $Q_{2}$ must leave to a path
$P_{3}$. At the end, there must be a path $Q_{i}$ ($i\neq 1$) that jumps to a
vertex $w$ on $P_{1}$. If $w$ is before $v$ (while walking on $P_{1}$ from $s$
to $t$), then we rename the indices of the paths in $Q$ such that the paths
with the same index in $\mathcal{P}$ and in $\mathcal{Q}$ use the same vertex
strictly after the jumps in $\mathcal{Q}$. Afterwards, we can reapply the
paragraph. If $w$ is behind $v$, we have an extended deadlock cycle in $G$
with respect to $\mathcal{P}$; a contradiction.

######  Lemma 3.4.

Assume that the paths in $\mathcal{P}$ are chordless and that $G$ has no
extended deadlock cycle with respect to $\mathcal{P}$. Any other set
$\mathcal{Q}$ of $\ell$ internal pairwise vertex-disjoint $s$-$t$-paths in
$G[V^{\prime}]$ is chordless and $G$ has no extended deadlock cycle with
respect to $\mathcal{Q}$.

######  Proof 3.5.

For a contradiction assume that $\mathcal{Q}$ has a path $Q$ with a chord
$\\{u,w\\}$ such that some vertex $v$ is in between $u$ and $w$ on the path
$Q$. This allows us to construct a path $Q^{\prime}$ from $Q$ that uses the
edge $\\{u,w\\}$ instead of the subpath of $Q$ between $u$ and $w$, leaving
$v$ unused. We so get $\ell$ paths
$\\{Q^{\prime}\\}\cup(\mathcal{Q}\setminus\\{Q\\})$ that does not use $v\in
V^{\prime}$, which is a contradiction to Lemma 3.2.

Assume now that there is an extended deadlock cycle $Z$ in $G$ with respect to
$\mathcal{Q}$ and some vertex $v$ on $Z$ such that $v$ is in the middle of one
of the subpaths of $Z$. By removing the common edges of $Z$ and the paths in
$\mathcal{Q}$ from the paths in $\mathcal{Q}$ and adding the remaining edges
of $Z$ to the paths in $\mathcal{Q}$, we get a set of pairwise vertex-disjoint
$s$-$t$-paths $\mathcal{Q}^{\prime}$ in $G[V^{\prime}\setminus\\{v\\}]$. An
example is sketched in Fig. 3. The existence of $\mathcal{Q}^{\prime}$ is
again a contraction to Lemma 3.2.

$P_{\ell}$$P_{\ell^{\prime}}$$P_{2}$$P_{1}$$v$$\vdots$$\vdots$$\vdots$$\vdots$

$P_{\ell}$$P_{\ell^{\prime}}$$P_{2}$$P_{1}$$v$$\vdots$$\vdots$$\vdots$$\vdots$

Figure 3: On the left an extended deadlock cycle $Z$ is shown in red with
respect to $\ell^{\prime}$ paths in $Q$. On the right a rerouting is sketched
such that the new path $Q^{\prime}$ do not use vertex $v$ anymore.

We begin with a high-level description of our approach to compute
$\mathcal{P}$ space efficiently. Afterwards, we present the missing details. A
chordless $s$-$t$-path $P$ can be computed by a slightly extended DFS and to
identify the path it suffices to store its vertices in an $O(n)$-bit array $A$
(Lemma 3.6). However, if we want to store $\ell>1$ chordless pairwise
internally vertex-disjoint $s$-$t$-paths in $A$, we cannot distinguish them
without further information. For an easier description assume that each path
with its vertices is colored with a different color. Using an array of $n$
fields of $O(\log\ell)$ bits each we can easily store the coloring of each
vertex and thus $\ell$ chordless paths with $O(n\log\ell)$ bits in total.
However, our goal is to store $\ell$ paths with $O(n+f(\ell)\log n)$ bits for
some polynomial function $f$. We therefore define a so-called path data scheme
that stores partial information about the $\ell$ paths using $O(n)$ bits (Def.
3.8). The idea of our scheme is to select and color a set $B\subseteq
V^{\prime}$ of vertices along the paths with the property that $|B|=O(n/\log
k)$ and $G[V^{\prime}\setminus B]$ consists only of small connected components
of $O(k\log k)$ vertices. We later call these components regions.

Such a set $B$ exists if the paths have so-called good properties (Def. 3.14).
Once a path data scheme is created we lose the information about the exact
routing of the original paths, but are able to realize operations to construct
the same number of paths. These operations are summarized in a so-called path
data structure (Def. 3.9). In particular, it allows us to determine the color
of a vertex $v$ on a path $P$ or to run along the paths by finding the
successor or predecessor of $v$ in $O(\mathtt{deg}(v)+f(k))$ time for some
polynomial $f$ (Lemma 3.12). The idea here is to explore the region containing
$v$ and use Lemma 3.1 to get a fixed set of $\ell$ paths connecting the
equally colored vertices. By Lemma 3.4, the new paths still have our good
properties. However, assuming that we have a set $\mathcal{P}$ of good paths
and some new chordless path $P^{*}\notin\mathcal{P}$, whose computation is
shown in Lemma 3.19, $\mathcal{P}\cup\\{P^{*}\\}$ is not necessarily good. Our
approach to make the paths good is to find a rerouting
$R(\mathcal{P}\cup\\{P^{*}\\})$ that outputs a set $\mathcal{P}^{\prime}$ of
good paths where $|\mathcal{P}^{\prime}|=|\mathcal{P}|+1$ (Lemma 3.21). Let
$V^{*}$ be the vertices of $\mathcal{P}$ and $P^{*}$. We realize $R$ by a
mapping $\overrightarrow{r}:V^{*}\rightarrow\\{0,\ldots,k\\}$ that defines the
successor of a vertex $v$ as a vertex $u\in N(v)$ of another path with color
$\overrightarrow{r}(v)$. Intuitively speaking, we cut the paths in
$\mathcal{P}\cup\\{P^{*}\\}$ in pieces and reconnect them as defined in
$\overrightarrow{r}$.

The rerouting may consist of $O(n)$ successor information, each of $O(\log k)$
bits. Therefore, we compute a rerouting by considering only the
$s$-$p$-subpath $P^{\prime}$ of $P^{*}$ for some vertex $p$. We compute the
rerouting in $O(\log k)$ batches by moving $p$ closer to $t$ with each batch.
Each batch consists of $\Theta(n/\log k)$ successor information (or less for
the last batch). Using the rerouting $\overrightarrow{r}$ and path data
structures storing $\mathcal{P}$ and $P^{*}$, we realize a so-called weak path
data structure for the paths $R(P\cup\\{P^{\prime}\\}).$ We call it a weak
path data structure because it can not be used to determine the color of a
vertex. After that we use it to compute a new valid path data scheme for the
paths $R(P\cup\\{P^{\prime}\\})$ such that we need neither the rerouting
$\overrightarrow{r}$ nor $V^{*}$ anymore (Lemma 3.23). However, since
$P^{\prime}$ is only a subpath of $P^{*}$ we repeat the whole process
described in this paragraph with another subpath $P^{\prime\prime}$ of
$P^{*}$, i.e., the subpath of $P^{*}$ whose first vertex is adjacent to the
last vertex of $P^{\prime}$. Finally, we so get a valid path data structure
storing $|\mathcal{P}|+1$ good $s$-$t$ paths (Corollary 3.25).

We now describe our approach in detail. To store a single $s$-$t$-path we
number the internal vertices along the path with $1,2,3,1,2,3,$ etc. and store
the numbers of all vertices inside an array $A$ of $2n$ bits. For a vertex $v$
outside the paths, we set $A[v]=0$. We refer to this technique as path
numbering. By the numbering, we know the direction from $s$ to $t$ even if we
hit a vertex in the middle of the path. Note that $A$ completely defines
$V^{\prime}$.

To follow a path stored in $A$, begin at a vertex $v$ and look for a neighbor
$w$ of $v$ with $A[w]=(A[v]\mod 3)+1$. Note that this approach only works if
$v$ has only one such neighbor. To avoid ambiguities when following a path we
require that the path is chordless.

######  Lemma 3.6.

Assume that we are given access to a DFS that uses a stack to store a path
from $s$ to the current vertex and that runs in $f_{\rm{t}}(n,m)$ time using
$f_{\rm{b}}(n,m)$ bits. Then, there is an algorithm to compute a path
numbering for a chordless $s$-$t$-path $P$ in time $O((n+m)+f_{\rm{t}}(n,m))$
by using $O(n+f_{\rm{b}}(n,m))$ bits.

######  Proof 3.7.

We call the internal subpath $P^{\prime}\subseteq P$ from a vertex $v_{i}$ to
a vertex $v_{j}$ skippable exactly if $P^{\prime}$ consists of at least $3$
vertices and there exists a chord, i.e., an edge from $v_{i}$ to $v_{j}$. The
idea is to construct first an $s$-$t$-path $P$ in $G$ with the DFS and,
directly after finding $t$, we stop the DFS and then pop the vertices from the
DFS stack and remove skippable subpaths until we arrive at $s$.

Let $P=(s=v_{1},v_{2},\ldots,v_{x}=t)$ be the vertices on the DFS stack after
reaching $t$ and let $M$ be an $n$-bit array marking all vertices with a one
that are currently on the stack. (We say that a vertex $v$ is marked in $M$
exactly if $M[v]=1$.) The algorithm moves backwards from $t$ to $s$, i.e., by
first popping $t$, setting $v_{i+1}=t$ and then popping the remaining vertices
from the DFS stack as follows.

Pop the next vertex $v_{i}$ from the stack, unmark $v_{i}$ in $A$, and let
$v_{i-1}$ be the vertex that is now on top of the DFS stack. We check
$v_{i}$’s neighborhood $N(v_{i})$ in $G$ for all vertices
$u\notin\\{v_{i-1},v_{i+1}\\}$ that are marked in $M$, mark them in an $n$-bit
array $M^{\prime}$ as chords and remember their number in $x$. The internal
subpaths between $v_{i}$ and all vertices marked in $M^{\prime}$ are
skippable. We remove the skippable paths as follows: As long as $x\neq 0$, we
pop a vertex $u$ from the DFS stack. If $u$ is marked in $M^{\prime}$, we
unmark $u$ in $M^{\prime}$ and reduce $x$ by one. If $x\geq 1$, we unmark $u$
in $M$. When $x=0$, the edge $\\{u,v_{i}\\}$ is the last chord, we set
$v_{i}:=u$ and $v_{i+1}:=v_{i}$ and continue our algorithm as described in
this paragraph until $v_{i}=s$.

After removing skippable paths from $P$, we can output the path as follows.
Allocate an array $A$ with $2$ bits for each vertex and initialize all entries
with $0$. Let $i=1$. Starting from $u=s$ go to its only neighbor $w\neq u$
that is marked in $M$. Set $i:=(i\mod 3)+1$ and $A[w]:=i$. Unmark $u$ in $M$,
set $u:=w$, and continue assigning the path numbering until $w=t$. Finally
return $A$.

Observe that the DFS runs once to find a path $P$ from $s$ to $t$ and then we
only pop the vertices from the stack. During the execution of the DFS we
manage membership of vertices using only arrays of $O(n)$ bits. The
construction of $A$ uses a single run over the path by exploring the
neighborhood of each marked vertex. In total our algorithm runs in $O(n+m)$
time and uses $O(n)$ bits in addition to the time and space needed by the
given DFS.

Recall that the path numbering does not uniquely define $\ell>1$ chordless
vertex-disjoint paths since there can be edges, called cross edges, between
vertices of two different paths in $\mathcal{P}$. Due to the cross edges, the
next vertex of a path can be ambiguous (see again Fig. 1). Coloring these
vertices would solve the problem, but we may have to many to store their
coloring.

Our idea is to select a set $B\subseteq V^{\prime}$ of vertices that we call
boundary vertices such that $|B|=O(n/\log k)$ holds and by removing $B$ from
$G[V^{\prime}]$ we get a graph $G[V^{\prime}\setminus B]$ that consists of
connected components of size $O(k\log k)$. In particular, $B$ contains all
vertices with large degree, i.e., vertices with a degree strictly greater than
$k\log k$. Note that a graph with treewidth $k$ has at most $kn$ edges, and so
we have only $O(n/\log k)$ vertices of large degree. We store the color of all
boundary vertices $B$. This allows us to answer their color directly. A region
is a connected component in $G[V^{\prime}\setminus B]$. Note that a boundary
vertex can connect several regions. To avoid exploring several regions when
searching the predecessor/successor on the same path of a vertex $v\in B$, we
additionally store the color of the predecessor/successor $w\notin\\{s,t\\}$
of each $v\in B$. According to our described setting above, we formally define
our scheme.

######  Definition 3.8.

(Path Data Scheme) A path data scheme for $\mathcal{P}$ in $G$ is a triple
$(A,B,C)$ where

  * •

$A$ is an array storing the path numbering of all paths in $\mathcal{P}$,

  * •

$B$ is a set of all boundary vertices with $|B|=O(n/\log k)$ and $B$ defines
regions of size $O(k\log k)$, and

  * •

$C$ stores the color of every vertex in $B$ and of each of their predecessors
and successors.

We realize $A$ as well as $B$ as arrays of $O(n)$ bits, and $C$ as a
$O(n)$-bit data structure using static space allocation. Altogether our path
data scheme uses $O(n)$ bits.

A further crucial part of our approach is to (re-)compute paths fast (in
particular, we do not want to use a $k$-disjoint-path algorithm), but we also
want to guarantee that vertices of the same color get connected with a path
constructed by a deterministic network-flow algorithm. In other words, our
path data scheme must store the same color for each pair of colored vertices
that are connected by our fixed algorithm of Lemma 3.1. We call a path data
scheme that has this property valid (with respect to our fixed algorithm).

To motivate the stored information of our path data scheme, we first show how
it can be used to realize a path data structure that allows us to answer
queries on all vertices $V^{\prime}$ and not only a fraction of $V^{\prime}$.
Afterwards, we show the computation of a path data scheme.

######  Definition 3.9.

(Path Data Structure) A path data structure supports the following operations
where $v\in V^{\prime}$.

  * •

$\mathtt{prev}/\mathtt{next}(v)$: Returns the predecessor and the successor,
respectively, of $v$.

  * •

$\mathtt{color}(v)$: Returns the color $i$ of a path $P_{i}\in\mathcal{P}$ to
which $v$ belongs to.

To implement the path data structure, our idea is first to explore the region
in $G[V^{\prime}\setminus B]$ containing the given vertex $v$ by using a BFS
and second to construct a graph of the vertices and edges visited by the BFS.
We partition the visited colored vertices inside the region into two sets
$S^{\prime}$ (successors of $B$) and $T^{\prime}$ (predecessors of $B$), as
well as extend the graph by two vertices $s^{\prime}$ and $t^{\prime}$ that
are connected to $S^{\prime}$ and $T^{\prime}$, respectively. Then we sort the
vertices and its adjacency arrays by vertex ids and run the deterministic
network-flow algorithm of Lemma 3.1 to construct always the same fixed set of
paths (but not necessarily the original paths). The construction of the paths
in a region consisting of a set $U$ of vertices is summarized in the next
lemma, which we use subsequently to support the operations of our path data
structure. We use the next lemma also to make a path data scheme valid. We so
guarantee that our network-flow algorithm connects equally colored vertices
and no $k$-disjoint path algorithm is necessary. This is the reason why the
following lemma is stated in a generalized manner and does not simply assume
that a path data scheme is given.

######  Lemma 3.10.

Assume that we are given the vertices $U$ of a region in $G$ as well as two
sets $S^{\prime},T^{\prime}\subseteq U$ of all successors and predecessors
vertices of vertices on the boundary, respectively. Take $n^{\prime}=|U|$.
Then $O(n^{\prime}k^{2}\log^{2}k)$ time and $O(k^{2}(\log k)\log n)$ bits
suffice to compute paths connecting each vertex in $S^{\prime}$ with another
vertex in $T^{\prime}$.

######  Proof 3.11.

We construct a graph $G^{\prime}=G[U]$, add two new vertices $s^{\prime}$ and
$t^{\prime}$ and connect them with the vertices of $S^{\prime}$ and
$T^{\prime}$, respectively. To structurally get the same graph independent of
the permutation of the vertices in the representation of the set $U$ we sort
the vertices and the adjacency arrays of the graph representation for
$G^{\prime}$. The details to do that are described in the three subsequent
paragraphs. Finally we run the algorithm of Lemma 3.1 to compute all
$s^{\prime}$-$t^{\prime}$-paths in the constructed graph $G^{\prime}$. Since
$S^{\prime}$ and $T^{\prime}$ are the endpoints of disjoints subpaths of paths
in $\mathcal{P}$, we can indeed connect each vertex in $S^{\prime}$ with
another vertex in $T^{\prime}$.

We now show the construction of $G^{\prime}$. We choose an arbitrary $v\in U$
and run a BFS in graph $G[U]$ starting at $v$ three times. (We use a standard
BFS with the restriction that it ignores vertices of $G$ that are not in $U$.)

In the first run we count the number $n^{\prime}=O(k\log k)$ of explored
vertices. Knowing the exact number of vertices and knowing that all explored
vertices can have a degree at most $k\log k$ in $G[U]$, we allocate an array
$D$ of $n^{\prime}+2$ fields and, for each $D[i]$ ($i=1,\ldots,n^{\prime}+2$),
an array of $\lceil k\log k\rceil$ fields, each of $\lceil\log(k\log k)\rceil$
bits. We will use $D$ to store the adjacency arrays for $G^{\prime}$
isomorphic to $G[U]$. For reasons of performance, we want to use indirect
addressing when operating on $G^{\prime}$. Since the space requirement to
realize indirect addressing depends on the largest value in $U$, we use a
bidirectional mapping from $U$ to $\\{1,\ldots,n^{\prime}\\}$ and use vertex
names out of $\\{1,\ldots,n^{\prime}\\}$ for $G^{\prime}$. More exactly, to
translate the vertex names of $G^{\prime}$ to the vertex names of $G$, we use
a translation table $M:\\{1,\ldots,n^{\prime}\\}\rightarrow U$, and we realize
the reverse direction $M^{-1}:U\rightarrow\\{1,\ldots,n^{\prime}\\}$ by using
binary search in $M$, which can be done in $O(\log n^{\prime})$ time per
access. For the table we allocate an array $M$ of $n^{\prime}$ fields, each of
$\lceil\log n\rceil$ bits.

In a second run of the BFS we fill $M$ with the vertices explored by the BFS
and sort $M$ by the vertex names. In a third run, for each vertex $v$ explored
by the BFS, we determine the neighbors $u_{1},\ldots,u_{x}$ of $v$ sorted by
their ids and store $M^{-1}(u_{1}),\ldots,M^{-1}(u_{x})$ in $D[M^{-1}(v)]$.
During the third BFS run we want to store also two sets $S^{\prime}$ and
$T^{\prime}$ (using a standard balanced tree representation). Now, $D$ allows
constant time accesses to a graph $G^{\prime}$ isomorphic to $G[U]$.
Afterwards, we are able to compute the paths in $G[U]$ and using the mapping
$M$ translate the vertex ids in $G^{\prime}$ back to vertex ids in $G$.

Efficiency: We now analyze the space consumption and the runtime of our
algorithm. Since $G$ has treewidth $k$ and $G^{\prime}$ consists of vertices
of a region of $G$, we can follow that $G^{\prime}$ has $n^{\prime}=O(k\log
k)$ vertices and $O(n^{\prime}k)$ edges. $D$ uses $O(n^{\prime}\log n)$ bits
to store $P(n^{\prime})$ pointers, each of $O(\log n)$ bits, that point at
adjacency arrays. The adjacency arrays use $O(n^{\prime}k\log k)$ bits to
store $O(n^{\prime}k)$ vertex ids out of $\\{1,\ldots,k\\}$. The translation
table $M$ and the sets $S^{\prime}$ and $T^{\prime}$ use $O(n^{\prime}\log n)$
bits. The BFS can use $O(n^{\prime}k\log k)$ bits. The space requirement of an
in-place sorting algorithm is negligible. Lemma 3.1 runs with
$O((n^{\prime}+kn^{\prime})\log n^{\prime})=O(n^{\prime}k\log k)$ bits. In
total our algorithm uses $O(n^{\prime}k\log k)+O(n^{\prime}\log
n)=O(k^{2}(\log k)\log n)$ bits.

To compute the graph $G^{\prime}$ and fill $M$ we run a BFS. Running the BFS
comes with an extra time factor of $O(\log n^{\prime})$ to translate a vertex
ids of $G$ to a vertex ids of $G^{\prime}$ (i.e., to access values in
$M^{-1}$) and costs us $O(n^{\prime}k\log n^{\prime})$ time in total. Since
$G^{\prime}$ has $O(n^{\prime}k)$ edges $D$ has $O(n^{\prime}k)$ non-zero
entries and a sorting of $D$ can be done in $O(n^{\prime}k)$ time. Sorting $M$
can be done in the same time. Finally, Lemma 3.1 has to be executed once for
up to $O(k\log k)$ paths (every vertex of the region can be part of
$S^{\prime}\cup T^{\prime}$), which can be done in $O((n^{\prime}k)(k\log
k)\log k)$ time since $O(n^{\prime}k)$ bounds the edges of the region and
since we get an extra factor of $O(\log k)$ by using the translation table
$M$. In total our algorithms runs in time $O(n^{\prime}k^{2}\log^{2}k)$.

Since the number of vertices in a region is bound by $O(k\log k)$, we can use
Lemma 3.10 and the coloring $C$ to support the operations of the path data
structure in the bounds mentioned below.

######  Lemma 3.12.

Given a valid path data scheme $(A,B,C)$ we can realize $\mathtt{prev}$ and
$\mathtt{next}$ in time $O(\mathtt{deg}(v)+k^{3}\log^{3}k)$ as well as
$\mathtt{color}(v)$ in $O(k^{3}\log^{3}k)$ time. All operations use
$O(k^{2}(\log k)\log n)$ bits.

######  Proof 3.13.

In the case that a vertex $v$ is in $B$, we find its color and the color of
its predecessor and successor in $C$. (Vertices neighbored to $s$ or $t$ have
$s$ as the predecessor and $t$ as the successor, respectively.) Thus, we can
answer $\mathtt{prev}$ and $\mathtt{next}$ by iterating over $v$’s
neighborhood and determining the two neighbors $u,w\in V^{\prime}$ that are
colored the same as $v$. By using the numbering $A$ we know the incoming and
outgoing edge of the path through $v$ and so know which of the vertices $u$
and $w$ is the predecessor or successor of $v$.

For a vertex $v\notin B$, we explore $v$’s region in $G[V^{\prime}\setminus
B]$ by running a BFS in $G[V^{\prime}]$ with the restriction that we do not
visit vertices in $B$. We use a balanced heap to store the set $U$ of visited
vertices. Moreover, we partition all colored vertices of $U$ into the set
$S^{\prime}$ (of successors of $B$) and the set $T^{\prime}$ (of predecessors
of $B$) with respect to the information in $C$. In detail, if a colored vertex
$u\in U$ has an equally colored neighbor $w\in B$, then $u$ is the successor
of $w$ if $A[v]=(A[w]\mod 3)+1$ holds and the predecessor of $v$ if
$A[w]=(A[v]\mod 3)+1$ holds.

Having $U$, $S^{\prime}$ and $T^{\prime}$ we call Lemma 3.10 to get the paths
in the region. Note that a path within a region can be disconnected by
vertices with large degree so that we can have more than two vertices of each
color in $S^{\prime}$ and $T^{\prime}$. E.g., a path may visit
$s_{1},t_{1},s_{2},t_{2},s_{3},t_{3},\ldots\in U$ with $s_{1},s_{2},s_{3}\in
S^{\prime}$ and $t_{1},t_{2},t_{3}\in T^{\prime}$. Since our path data scheme
is valid, we can conclude the following: assume that we connect the computed
subpaths using their common equally colored boundary vertices. By Lemma 3.2
each solution has to use all vertices and the network-flow algorithm indeed
connects $s_{1}$ with $t_{1}$, $s_{2}$ with $t_{2}$, etc. By Lemma 3.4 the
paths and thus our computed subpaths are chordless and have no extended
deadlock cycles in $G$ with respect to $\mathcal{P}^{\prime}$. Using the paths
we can move along the path of $v$ to a colored vertex and so answer $v$’s
color and both of $v$’s neighbors on the path.

Efficiency: We now analyze the runtime of our algorithm and its space
consumption. Realizing the operations $\mathtt{prev}$ and $\mathtt{next}$ for
a vertex of $B$ can be done in $O(\mathtt{deg}(v))$ time since both colored
neighbors have to be found, and their color can be accessed in constant time
using $C$. The operation $\mathtt{color}$ runs in constant time. For the
remaining vertices we have to explore the region in $G[V^{\prime}\setminus
B]$. Since every region has $n^{\prime}=O(k\log k)$ vertices and also treewith
$k$, the exploration can be done in linear time per region, i.e., in
$O(n^{\prime}k)$ time using a standard BFS. Filling $U$, $S^{\prime}$ and
$T^{\prime}$ requires us to add $O(n^{\prime})$ vertices into balanced heaps,
which uses $O(n^{\prime}\log n^{\prime})$ time. The execution of Lemma 3.10
can be done in $O(n^{\prime}k^{2}\log^{2}k)$ time and running along the paths
to find the actual color runs in $O(n^{\prime})$ time. Thus, in total
$\mathtt{prev}$ and $\mathtt{next}$ run in time
$O(\mathtt{deg}(v)+k^{3}\log^{3}k)$ and $\mathtt{color}(v)$ in time
$O(k^{3}\log^{3}k)$.

A BFS to explore a region in $G[V^{\prime}\setminus B]$ uses
$O(n^{\prime}k\log n)=O(k^{2}(\log k)\log n)$ bits, while $U$, $S^{\prime}$
and $T^{\prime}$ use $O(n^{\prime}\log n)$ bits in total. The execution of
Lemma 3.10 uses $O(k^{2}(\log k)\log n)$ bits, which is also an upper bound
for all remaining operations.

To be able to compute a storage scheme for $\ell>1$ paths, $\mathcal{P}$ must
satisfy certain so-called good properties that we summarize in Definition
3.14.

######  Definition 3.14.

(good paths) We call a set $\mathcal{P}^{\prime}$ of $s$-$t$-paths good if and
only if

  1. 1.

all paths in $\mathcal{P}^{\prime}$ are pairwise internal vertex disjoint,

  2. 2.

each path in $\mathcal{P}^{\prime}$ is chordless, and

  3. 3.

there is no extended deadlock cycle in $G$ with respect to
$\mathcal{P}^{\prime}$.

The next lemma shows the computation of a valid path data scheme for one path
$P$. The computation is straightforward. Since there is only one path, this
path is uniquely defined by the path numbering in $A$ and we can run along it
and select every $k\lceil\log k\rceil$ vertex as a boundary vertex and compute
and store the remaining information required for a valid path data scheme.
After the lemma we always assume that a chordless path $P$ is given together
with a valid path data scheme and thus a path data structure so that we can
easily access the predecessor and successor of a vertex on the path.

######  Lemma 3.15.

Given a path numbering $A$ for one chordless $s$-$t$ path $P$, we can computes
a valid path data scheme $(A,B,C)$ for $P$ in $O(n)$ time using $O(n)$ bits.

######  Proof 3.16.

Since $A$ stores a single chordless path $P$, we can run along it from $s$ to
$t$ while adding every $\lceil k\log k\rceil$th vertex and every vertex of
large degree into an initially empty set $B$. We then can easily determine the
predecessor and successor. Thus, we can store $C$ using static space
allocation. A path data scheme storing a single path is valid by default since
there is no second path to that an algorithm could switch. We so get a path
storage scheme storing $\ell=1$ good $s$-$t$-path in $O(n)$ time using $O(n)$
bits.

Assume that, for some $\ell\leq k$, we have already computed $\ell$ good
$s$-$t$-paths, which are stored in a valid path data scheme. Our approach to
compute an $(\ell+1)$th $s$-$t$-path is based on the well-known network-flow
technique [1] described in the beginning of the section, which we now modify
to make it space efficient.

By the standard network-flow technique, we do not search for vertex-disjoint
paths in $G$. Instead, we modify $G$ into a directed graph $G^{\prime}$ and
search for edge-disjoint paths in $G^{\prime}$. To make the approach space
efficient, we do not store $G^{\prime}$ separately, but we provide a graph
interface that realizes $G^{\prime}$.

######  Lemma 3.17.

Given an $n$-vertex $m$-edge graph $G=(V,E)$ there is a graph interface
representing an directed $n^{\prime}$-vertex $m^{\prime}$-edge graph
$G^{\prime}=(V^{\prime},E^{\prime})$ where
$V^{\prime}=\\{v^{\prime},v^{\prime\prime}\ |\ v\in V\\}$ and
$E^{\prime}=\\{(u^{\prime\prime},v^{\prime}),(v^{\prime\prime},u^{\prime})|\\{u,v\\}\in
E\\}\cup\\{(v^{\prime},v^{\prime\prime})|v\in V\\}$ and thus $n^{\prime}=2n$
and $m^{\prime}=2m+n$. The graph interface allows us to access outgoing edges
and incoming edges of $G^{\prime}$, respectively, by supporting the operations
$\mathtt{head}^{\rm{out}}_{G^{\prime}}$,
$\mathtt{deg}^{\rm{out}}_{G^{\prime}}$ and
$\mathtt{head}^{\rm{in}}_{G^{\prime}}$, $\mathtt{deg}^{\rm{in}}_{G^{\prime}}$.
The graph interface can be initialized in constant time and the operations
have an overhead of constant time and $O(\log n)$ bits.

######  Proof 3.18.

We now show how to compute the operations for $G^{\prime}$ from $G$ on the
fly. For each vertex $v$ in $V$, we define two vertices $v^{\prime}=v$ and
$v^{\prime\prime}=v+n$ for $V^{\prime}$. By the transformation we can see that
every vertex $v^{\prime}$ (with $v^{\prime}\leq n$) has exactly one outgoing
edge to $v^{\prime\prime}=v^{\prime}+n$ and $\mathtt{deg}_{G}(v^{\prime})$
incoming edges from some vertices
$u^{\prime\prime}=\mathtt{head}_{G}(v^{\prime},j)+n$
($j\leq\mathtt{deg}_{G}(v^{\prime})$). Moreover, every vertex
$v^{\prime\prime}$ (with $v^{\prime\prime}>n$) has
$\mathtt{deg}_{G}(v^{\prime\prime}-n)$ outgoing edges to some vertices
$u^{\prime}=\mathtt{head}_{G}(v^{\prime\prime}-n,j)$
($j\leq\mathtt{deg}_{G}(v^{\prime\prime}-n)$) and one incoming edge from
$v^{\prime}=v^{\prime\prime}-n$. With these information we can provide our
stated operations for $G^{\prime}$.
$\displaystyle\mathtt{deg}^{\rm{out}}_{G^{\prime}}(v)=\begin{cases}1&v\leq
n\\\ \mathtt{deg}_{G}(v)&v>n\end{cases}$
$\displaystyle\mathtt{head}^{\rm{out}}_{G^{\prime}}(v,j)=\begin{cases}v+n&v\leq
n\\\ \mathtt{head}_{G}(v-n,j)&v>n\end{cases}$

$\displaystyle\mathtt{deg}^{\rm{in}}_{G^{\prime}}(v)=\begin{cases}\mathtt{deg}_{G}(v)&v\leq
n\\\ 1&v>n\end{cases}$

$\displaystyle\mathtt{head}^{\rm{in}}_{G^{\prime}}(v,j)=\begin{cases}\mathtt{head}_{G}(v,j)+n&v\leq
n\\\ v-n&v>n\end{cases}$

The operations $\mathtt{deg}^{\rm{out}}_{G^{\prime}}$,
$\mathtt{deg}^{\rm{in}}_{G^{\prime}}$ and
$\mathtt{head}^{\rm{out}}_{G^{\prime}}$,
$\mathtt{head}^{\rm{in}}_{G^{\prime}}$ have the same asymptotic bounds as
$\mathtt{deg}_{G}$ and $\mathtt{head}_{G}$, respectively.

We next show that we can compute an $(\ell+1)$st paths.

######  Lemma 3.19.

Given a valid path data scheme for a set $\mathcal{P}$ of $\ell\\!<\\!k$ good
$s$-$t$-paths in $G$, $O(n(k+\log^{*}n)k^{3}\log^{3}k)$ time and
$O(n+k^{2}(\log k)\log n)$ bits suffice to compute an array of $2n$ bits
storing a path numbering of an $(\ell+1)$th chordless $s$-$t$-path $P^{*}$,
which can be a dirty path with respect to $\mathcal{P}$.

######  Proof 3.20.

To solve the lemma, we adapt the standard network-flow approach as follows. We
first use the graph interface of the Lemma 3.17 to obtain a graph
$G^{\prime\prime}$ in that we can search for edge-disjoint paths instead of
vertex-disjoint paths in $G$. We provide the operations $\mathtt{prev}$,
$\mathtt{next}$, $\mathtt{color}$ and a virtual array $A$ that gives access to
the paths $\mathcal{P}$ adjusted to $G^{\prime}$ by using a simple translation
to the corresponding data structure of $G$.

According to the construction of $G^{\prime}$ a vertex $v$ in $G$ is
equivalent to two vertices, an in-vertex $v^{\prime}=v$ and an out-vertex
$v^{\prime\prime}=v+n$ in $G^{\prime}$. Moreover, every in-vertex $u^{\prime}$
in $G$ has a single outgoing edge and this edge points to its out-vertex
$u^{\prime\prime}=u^{\prime}+n$, which has only outgoing edges that all point
to some in-vertices in $G^{\prime}$. Taken our stored $\ell$ good paths into
account a path $(v_{1},v_{2},v_{3},\ldots)\in\mathcal{P}$ in $G$ translates
into a path
$(v_{1}^{\prime},v_{1}^{\prime\prime},v_{2}^{\prime},v_{2}^{\prime\prime},v_{3}^{\prime},v_{3}^{\prime\prime},\ldots)$
in $G^{\prime}$ and the edges between them must be reversed in $G^{\prime}$.

Next, we want to build the residual network of $G^{\prime}$ and $\mathcal{P}$.
This means that we have to reverse the edges on the paths of $\mathcal{P}$. To
identify the edges incident to a vertex $v$, it seems to be natural to use
$\mathtt{prev}(v)$ and $\mathtt{next}(v)$. Unfortunately, we cannot effort to
query these two operations many times to find out which of the incident edges
of $v$ is reversed since $v$ can be a large vertex and the runtime of both
operations depends on $\mathtt{deg}_{G^{\prime}}(v)$. This issue becomes
especially important when using a space-efficient DFS that may query
$\mathtt{prev}(v)$ more than a constant number of times (e.g., by running
several restorations of a stack segment including $v$).

To avoid querying $\mathtt{prev}(v)$ for any vertex $v$ of $G^{\prime}$, we
present the DFS a graph $G^{\prime\prime}$ where $v$ has as outgoing edges
first all outgoing edges of $v$ in $G^{\prime}$ and then all incoming edges of
$v$ in $G^{\prime}$. In detail, we present the DFS a graph $G^{\prime\prime}$
with all vertices of $G^{\prime}$ and one further vertex $d$ with no outgoing
edges. We also make sure that the DFS has colored $d$ black (e.g., start the
DFS on $d$ before doing anything else). A sketch of the graph $G^{\prime}$
with a blue path, graph $G^{\prime\prime}$ and the reversal of the edges in
$G^{\prime\prime}$ can be seen in Fig. 4. As we see in the next paragraph, we
will use $d$ as a kind of dead end.

Figure 4: From top left to buttom right, a sketch of $G$, $G^{\prime}$,
$G^{\prime\prime}$ and $G^{\prime\prime}$ with reversed edges. Each black
vertex is the same vertex $b$. The blue edges are edges of a path. The dashed
lines in the graphs sketches an edge connecting the middle rightmost with the
middle leftmost vertex.

Every vertex $v\neq d$ of $G^{\prime\prime}$ has
$\mathtt{deg}^{\rm{out}}_{G^{\prime}}(v)+\mathtt{deg}^{\rm{in}}_{G^{\prime}}(v)$
many outgoing edges defined as follows. The heads of the first
$\mathtt{deg}^{\rm{out}}_{G^{\prime}}(v)$ outgoing edges of $v$ in
$G^{\prime\prime}$ are the same as in $G^{\prime}$ with the exception that we
present edge $(v,d)$ for possibly one outgoing edge $(v,z)$ that is reversed
(i.e., $\mathtt{color}(v)=\mathtt{color}(z)\land A[z]=(A[v]-1)\mod 3)$). The
heads of the next $\mathtt{deg}^{\rm{in}}_{G^{\prime}}(v)$ incoming edges of
$v$ in $G^{\prime\prime}$ are presented as an edge $(v,d)$ with the exception
that we present possibly one incoming edge $(z,v)$ that is reversed as an
outgoing edge $(v,z)$.

Intuitively speaking, this ensures that a DFS backtracks immediately after
using edges that do not exist in the residual graph. Note that we so can
decide the head of an edge in $G^{\prime\prime}$ by only calling
$\mathtt{color}$ twice. The graph $G^{\prime\prime}$ has asymptotically the
same amount of vertices and edges as $G$. To guarantee our space bound we
compute a new $s$-$t$-path $P$ in $G^{\prime\prime}$ using a space-efficient
DFS on $G^{\prime\prime}$ and consecutively make $P$ chordless by Lemma 3.6.
Finally, we transform $P$ into a path $P^{*}$ with respect to $\mathcal{P}$ by
merging in and out vertices together.

Efficiency: Concerning the running time we use a space-efficient DFS (Lemma
2.6) to find a new $s$-$t$-path in $G^{\prime\prime}$. To operate in
$G^{\prime\prime}$ we need to query the color of vertices. We pay for that
with an extra factor of $O(k^{3}\log^{3}k)$ (Lemma 3.12) in the running time.
Since our graph has $O(n)$ vertices and $O(kn)$ edges we find a new $s$-$t$
path in $G^{\prime\prime}$ in time $O(n(k+\log^{*}n)k^{3}\log^{3}k)$. The time
to transform the found path into $P^{*}$ and store it can be done in the same
bound. The total space used for the algorithm is $O(n+k^{2}(\log k)\log n)$
bits—$O(n)$ bits for the space-efficient DFS, $O(k^{2}(\log k)\log n)$ bits
for Lemma 3.12, and $O(n)$ bits for storing $P^{*}$ and its transformation.

Let us call an $s$-$t$-path $P^{*}$ a clean path with respect to $\mathcal{P}$
if $\mathcal{P}\cup\\{P^{*}\\}$ is a set of good paths, and a dirty path with
respect to $\mathcal{P}$ if for all $P\in\mathcal{P}$, the common vertices and
edges of $P^{*}$ and $P$ build subpaths each consisting of at least two
vertices and used by the two paths in opposite direction when running from $s$
to $t$ over both paths. Intuitively, if we construct an $(\ell+1)$st path
$P^{*}$ in the residual network of $G$ with $\ell$ paths in $\mathcal{P}$,
then $P^{*}$ can run backwards on paths in $\mathcal{P}$, and we call $P^{*}$
a dirty path (see Fig. 5). After a rerouting, we obtain $\ell+1$ internal
vertex disjoint $s$-$t$ paths. To store the paths $\mathcal{P}\cup\\{P^{*}\\}$
with our path data structure, the paths must be good, which we can guarantee
through another rerouting. The details are described below.

$P^{*}$$P_{\ell}$$P_{3}$$P_{2}$$P_{1}$$u$$\vdots$$\vdots$ Figure 5: The green
subpath of $P^{*}$ is clean until it hits a common vertex $u$ with $P_{3}$,
then it is a dirty path.

Let $P^{*}$ be an $s$-$t$-path returned by Lemma 3.19. We first consider the
case where $P^{*}$ is a dirty path with respect to $\mathcal{P}$. To make the
paths good we cut the paths into subpaths and by using the subpaths we
construct a set of new $\ell+1$ good $s$-$t$-paths. To achieve that we have to
get rid of common vertices and extended deadlock cycles. We handle common
vertices and extended deadlock cycles in a single process, but we first
briefly sketch the standard network-flow technique to remove common vertices
of $P^{*}$ with a path $P^{c}\in\mathcal{P}$. By the construction of the
paths, the common vertices of an induced subpath are ordered on $P^{c}$ as
$v_{\sigma_{1}},v_{\sigma_{2}},\ldots,v_{\sigma_{x}}$ (for some function
$\sigma$ and $x\geq 2$) and on $P^{*}$ as
$v_{\sigma_{x}},v_{\sigma_{x-1}},\ldots,v_{\sigma_{1}}$. $P^{c}$ and $P^{*}$
can be split into vertex disjoint paths by (1) removing the vertices
$v_{\sigma_{2}},\ldots,v_{\sigma_{x-1}}$ from $P^{*}$ as well as from $P^{c}$,
(2) by rerouting path $P^{c}$ at $v_{\sigma_{1}}$ to follow $P^{*}$, and (3)
by rerouting $P^{*}$ at $v_{\sigma_{x}}$ to follow $P^{c}$.

We denote by $R(\mathcal{P}\cup\\{P^{*}\\})$ a rerouting function that returns
a new set of $|\mathcal{P}\cup\\{P^{*}\\}|$ good paths. We so change the
successor and predecessor information of some vertices of the paths
$\mathcal{P}\cup\\{P^{*}\\}$. Let $V^{*}$ be a set of all vertices in
$R(\mathcal{P}\cup\\{P^{*}\\})$. To define successor and predecessor
information for the vertices we use the mappings
$\overrightarrow{r},\overleftarrow{r}:V^{*}\rightarrow\\{0,\ldots,k\\}$ where
for each vertex $u\in V^{*}$ with $\overrightarrow{r}(u)\neq 0$, $u$’s new
successor is a vertex $v\in N(v)\cap V^{*}$ with
$\overrightarrow{r}(u)=\mathtt{color}(v)$. Similarly we use
$\overleftarrow{r}$ to define a new predecessor of some $u\in V^{*}$. The
triple $(V^{*},\overrightarrow{r},\overleftarrow{r})$ realizes a rerouting
$R$.

To avoid using too much space by storing rerouting information for too many
vertices our approach is to compute a rerouting
$R(\mathcal{P}\cup\\{P^{\prime}\\})$ only for an $s$-$p$-subpath $P^{\prime}$
of $P^{*}$ where $p$ is a vertex of $P^{*}$. This means that
$R(\mathcal{P}\cup\\{P^{\prime}\\})$ consists of $\ell$ $s$-$t$-paths and one
$s$-$p$-path. Moreover, we make the rerouting in such a way that, for all
paths $P_{i}\in R(\mathcal{P}\cup\\{P^{\prime}\\})$, there is a vertex $v_{i}$
with the following property: replacing the $v_{i}$-$t$-subpath of $P_{i}$ by
an edge $\\{v_{i},t\\}$ for all paths $P_{i}$ we get $\ell+1$ good paths. Let
$\mathcal{P}^{\rm{c}}$ consist of the $s$-$v_{i}$-subpaths for each $P_{i}$.
We then call the set of vertices part of the paths in $\mathcal{P}^{\rm{c}}$ a
clean area $Q$ for $R(\mathcal{P}\cup\\{P^{\prime}\\})$.

The idea is to repeatedly compute a rerouting in $O(\log k)$ batches and
thereby extend $Q$ with each batch by $\Theta(n/\log k)$ vertices—the last
batch may be smaller—such that we store $O(n/\log k)$ entries in
$\overrightarrow{r}$ and $\overleftarrow{r}$ with each batch. After each batch
we free space for the next one by computing a valid path storage scheme
storing good $s$-$t$ paths $R(\mathcal{P}\cup\\{P^{\prime}\\})\setminus
P^{\prime\prime}$, where $P^{\prime\prime}$ is the only path in
$R(\mathcal{P}\cup\\{P^{\prime}\\})$ not ending in $t$, and a valid path
storage scheme for the $s$-$t$ path $\mathcal{P}^{**}$ obtained from $P^{*}$
by replacing $P^{\prime}$ trough $P^{\prime\prime}$. (For an example consider
the $p$-$w$-subpath of $P^{*}$ in Fig. 6a, which is replaced by a beginning of
$P_{2}$ in Fig. 6d.)

We now sketch our ideas of the rerouting that removes extended deadlock cycles
in $\mathcal{P}\cup\\{P^{*}\\}$. Recall that every extended deadlock cycle
must contain parts of $P^{*}$ since all remaining paths are good. Hence by
moving along $P^{*}$ we look for an vertex $u$ of $P^{*}$ that is an endpoint
of a cross edge $\\{u,v\\}$. Since a deadlock cycle is a cycle, there must be
some vertex $w$ after $u$ on $P^{*}$ that is connected by subpaths of
$\mathcal{P}$ and cross edges connecting the paths in
$\mathcal{P}\cup\\{P^{*}\\}$.

Since common vertices and deadlock cycles may intersect, vertices $u$ and $w$
can have a cross edge or be common vertex on a path in $\mathcal{P}$ (Fig.
6a). To find $u$ and $w$, our idea is to move over $P^{*}$ starting from $s$
and stop at the first such vertex $u$ of $P^{*}$. Then use a modified DFS at
$u$ that runs over paths in $\mathcal{P}$ only in reverse direction and over
cross edges—but never over two subsequent cross edges—and so explores subpaths
of $\mathcal{P}$ (marked orange in Fig. 6b). Whenever a vertex $v$ of the
clean area is reached, the DFS backtracks, i.e., the DFS assumes that $v$ has
no outgoing edges. We so guarantee that the clean area is not explored again
and again. Afterwards we determine the latest vertex $w$ on $P^{*}$ that is a
common vertex or has a cross edge with one of the explored subpaths. If such a
vertex $w$ is found, we either have a common subpath from $u$ to $w$ between a
path $P^{c}\in\mathcal{P}$ and $P^{*}$ (which is removed as described above)
or a deadlock cycle. If it is an extended deadlock cycle, we have a subpath on
the cycle consisting of at least three vertices. As the proof of the following
lemma shows the extended deadlock cycle can be destroyed by removing the inner
vertices of the subpath and rerouting the paths via cross edges part of the
extended deadlock cycle. We find an extended deadlock cycle by an additional
run of the modified DFS from $u$ to $w$ (Fig. 6c) and reroute it along the
cross edges. Fig. 6d shows a rerouting where the path in
$R(\mathcal{P}\cup\\{P^{\prime}\\})$ starting with the vertices of the old
path $P_{2}$ becomes the “new” path $P^{*}$.

$P^{*}$$P_{1}$$P_{2}$$P_{3}$$P_{\ell}$$p$$u$$\vdots$$\vdots$$P$$0{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}{13}}}{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>0{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>0{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}{3}}}0{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}{1}}}0{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>bits (a) Look for common vertices or cross edges.

$P^{*}$$P_{1}$$P_{2}$$P_{3}$$P_{\ell}$$u$$w$$\vdots$$\vdots$$p$$A^{\prime}$${{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{1}}}0\ldots
0{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{1}}}0{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{1}}}\ldots
0{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{1}}}0\ldots
0{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{1}}}0$$n$
bits (b) Explore subpaths with extended deadlock c.

$P^{*}$$P_{1}$$P_{2}$$P_{3}$$P_{\ell}$$u$$w$$\vdots$$\vdots$$p$ (c) Run a DFS
to find a path from $u$ to $w$.

$P_{1}$$P_{2}$$P^{*}$$P_{3}$$P_{\ell}$$p$$u$$w$$\vdots$$\vdots$ (d) A
rerouting over cross edges.

Figure 6: Steps and data structures of the algorithm to create good paths.

An $s$-$p$-path $\widetilde{P}$ is called a clean subpath with respect to a
set of good paths $\mathcal{P}^{\prime}$ if, for the extension
$P^{\mathrm{ext}}$ of $\widetilde{P}$ by an edge $\\{p,t\\}$ and a vertex $t$,
$\mathcal{P}^{\prime}\cup\\{P^{\mathrm{ext}}\\}$ is a set of good paths. The
green path in Fig. 5 is a clean subpath. The next lemma summarizes the
computation of our rerouting $R$. We initially call the lemma with a clean
subarea $Q=\\{s\\}$ and a clean path that consists only of vertex $p=s$.

######  Lemma 3.21.

There is an algorithm that accepts as input a valid path data scheme for
$\ell$ good $s$-$t$-paths $\mathcal{P}$, a valid path data scheme for a
possibly dirty $s$-$t$ path $P^{*}$, as well as a clean area $Q$ for
$\mathcal{P}$ including a clean $s$-$p$ subpath $\widetilde{P}$ of $P^{*}$ and
outputs a rerouting $R$, a clean area $Q^{\prime}$ including a clean
$s$-$p^{\prime}$ subpath $\widetilde{P}^{\prime}$ with the properties that
$\widetilde{P}$ is a subpath of $\widetilde{P}^{\prime}$, and
$|Q^{\prime}|=|Q|+\Omega(n/\log k)\lor p^{\prime}=t$. The algorithm runs in
$O(nk^{3}\log^{3}k)$ time and uses $O(n+k^{2}(\log k)\log n)$ bits.

######  Proof 3.22.

We begin to describe our algorithm to detect common vertices and extended
deadlock cycles. Afterwards we compute the rerouting $R$ which is realized by
$(V^{*},\overrightarrow{r},\overleftarrow{r})$. Initially, $V^{*}$ is an array
of bits consisting of all vertices of $\mathcal{P}\cup\\{P^{*}\\}$. During the
algorithm we remove vertices from $V^{*}$ whenever we change our paths. We
want to use static space allocation to store the mappings $\overrightarrow{r}$
and $\overleftarrow{r}$, which requires us to know the key set of the mapping
in advance. We solve it by running the algorithm twice and compute the key set
in the first run, reset $Q$ and $p$ from a backup, and compute the values and
store them in a second run. For simplicity, we omit these details below and
assume that we can simply store the values inside $\overrightarrow{r}$ and
$\overleftarrow{r}$.

Starting from vertex $p$ we run along path $P^{*}$. We stop at the first
vertex $u$ if $u$ is a common vertex of $P^{*}$ and a path in $\mathcal{P}$
(Fig. 6a) or it is an endpoint of a cross edge. For a simpler notion, we call
such a vertex $u$ of $P^{*}$ a vertex touching the vertices in $\mathcal{P}$.
Next we use a DFS without restorations (due to our details described below,
the DFS stack consists of only $O(\ell)$ vertices, which are incident to cross
edges of the current DFS path). We so explore the vertices $Q^{\prime}$ from
$u$ that are reachable from $u$ via edges on the paths $\mathcal{P}$ used in
reverse direction and cross edges, but ignore a cross edge if it immediately
follows after another cross edge and ignore the vertices in the clean area
$Q$. To allow an economical way of storing the stack, the DFS prefers reverse
edges (edges on a path $P\in\mathcal{P}$) compared to cross edges when
iterating over the outgoing edges of a vertex. This guarantees that the
vertices on the DFS-stack consist of at most $\ell$ subpaths of paths in
$\mathcal{P}$. We store the vertices $Q^{\prime}$ processed by the DFS in a
choice dictionary [22, 24, 29] since a choice dictionary allows us to compute
$Q:=Q\cup Q^{\prime}$ in a time linear to the amount of elements in
$Q^{\prime}$. Moreover, we count the number $q$ of vertices of $P^{*}$ that
touch $Q^{\prime}$. Running over $P^{*}$ starting from $u$ we can determine
the last such vertex $w$ (Fig. 6b).

Then we run a modified DFS to construct a $u$-$w$ path $\widetilde{P}$ that
(1) consists only of vertices in $Q^{\prime}$, that (2) uses no subsequent
cross edges and that (3) uses every path in $\mathcal{P}$ only once (Fig. 6c).
Note that these restrictions (1) – (3) still allow us to reach all vertices of
$Q^{\prime}$. To ensure restriction (3) we maintain a bit array $F$ of
forbidden paths where $i\in F$ exactly if a subpath of $P_{i}\in\mathcal{P}$
is part of the currently constructed path. To construct $\widetilde{P}$ the
DFS starts at vertex $u$ and processes a vertex $v$ as follows:

  1. 1.

Stop the DFS if $w$ is reached.

  2. 2.

// To guarantee restriction (1):
If $v\notin Q^{\prime}$, then backtrack the DFS and color $v$ white.

  3. 3.

Iterate over all reversed edges $(v,v^{\prime})$: recursively process
$v^{\prime}$.

  4. 4.

// To guarantee restriction (2) and (3):
Iterate over all cross edges $\\{v,v^{\prime}\\}$:
If $\mathtt{color}(v^{\prime})\notin F$ and $v^{\prime}$ was not discovered by
a cross edge, recursively process $v^{\prime}$.

  5. 5.

Backtrack the DFS to the predecessor $\widetilde{v}$ of $v$ on
$\widetilde{P}$. If $\\{\widetilde{v},v\\}$ is a cross-edge, color $v$ white.
// Coloring $v$ white guarantees that we can explore outgoing cross-edges of
$v$ if we reach $v$ again over a reverse edges.

Let $1,\ldots,\ell$ be the colors of the paths in $\mathcal{P}$ and $(\ell+1)$
be the color of $P^{*}$. In the case that $u$ and $w$ are both on one path of
$\mathcal{P}$, we reroute the paths as follows. Set
$\overrightarrow{r}(u)=\overleftarrow{r}(w)=\mathtt{color}(u)$,
$\overleftarrow{r}(u)=\overrightarrow{r}(w)=\ell+1$ and update $V^{*}$
accordingly, i.e., remove all internal vertices of the $u$-$w$ subpath of
$P^{*}$ from $V^{*}$ (Fig. 7a). Afterwards, we set $Q:=Q\cup Q^{\prime}$ and
$p=\mathtt{next}(w)$ and repeat the whole algorithm above.

Recall that the construction of the $u$-$w$ path uses only one subpath of
every path in $\mathcal{P}$. Without loss of generality, let $\widetilde{P}$
be $w,x_{1},\ldots,y_{1},$ $x_{2},\ldots,y_{2},$
$x_{3},\ldots,y_{\ell^{\prime}},u$, where $(y_{i},x_{i+1})$ are cross edges
and $x_{i},\ldots,y_{i}$ are subpaths of a path $P_{i}\in\mathcal{P}$ (for
some order of $\mathcal{P}$ and some $\ell^{\prime}$ with
$0<i<\ell^{\prime}\leq\ell$).

We first assume that $(w,x_{1})$ and $(y_{\ell^{\prime}},u)$ are both cross
edges (Fig. 7b). If the $x_{i}$-$y_{i}$-subpath of every $P_{i}$ as well as
the $u$-$w$-subpath of $P^{*}$ consists of exactly two vertices, then we found
a simple deadlock cycle, in particular, $u$ and $w$ are the only vertices of
$P^{\prime}$ that touch $Q^{\prime}$. We keep the simple deadlock cycle by
setting $Q:=Q\cup Q^{\prime}$ and $p=\mathtt{next}(w)$ and repeat the whole
algorithm above.

Otherwise we have an extended deadlock cycle and we compute a rerouting as
follows. For every cross edge $(y_{i},x_{i+1})$ with $0<i<\ell^{\prime}$ on
the DFS stack, we set $\overrightarrow{r}(x_{i+1})=i$,
$\overleftarrow{r}(y_{i})=i+1$, remove all vertices of each path $P_{i}$ in
between $x_{i}$ and $y_{i}$ as well as all vertices of path $P^{*}$ in between
$u$ and $w$ from $V^{*}$. We now describe the rerouting at $w$. Vertex $u$ is
handled analogously. If as assumed $(w,x_{1})$ is a cross edge, set
$\overrightarrow{r}(x_{1})=\ell+1$ and $\overleftarrow{r}(w)=1$ (Fig. 7c).
Otherwise, $w$ is on path $P_{1}$ before vertex $y_{1}$, or $w=x_{1}$. Then
remove all vertices in between $w$ and $y_{1}$ on path $P_{1}$ from $V^{*}$
and set $\overrightarrow{r}(w)=\ell+1$ and $\overleftarrow{r}(w)=1$ (Fig. 7d).
For the case where neither $(w,x_{1})$ nor $(y_{\ell^{\prime}},u)$ is a cross
edge, as well as $u$ and $w$ are on different paths, see Fig. 7e for the
rerouting. After all cases described in this paragraph set $Q:=Q\cup
Q^{\prime}$, $p=\mathtt{next}(w)$ and repeat the whole algorithm above.

Note that in all cases above, we only add information for $O(k)$ predecessors
and successors with each extension of $Q$ to our rerouting. Thus, our
rerouting information increases in small pieces. Whenever $\overrightarrow{r}$
is defined for $\Theta(n/\log k)$ vertices ($R$ uses $O(n)$ bits) or we
reached $t$ while moving over $P^{*}$, we break the algorithm above. By
applying Lemma 3.6 on each rerouted path (the graph induced by the vertices of
the paths is taken as input graph), we can make all paths chordless without
introducing further cross edges or extended deadlock cycles. Finally, return
the rerouting $(V^{*},\overrightarrow{r},\overleftarrow{r})$ as well as the
new clean area $Q$ and the end vertex $p$ of a new clean path in
$R(\mathcal{P}\cup{P^{\prime}})$.

$P_{\ell+1}$$P_{\ell^{\prime}}$$P_{3}$$P_{2}$$P_{1}$ $w$$u$$\vdots$$\vdots$
(a) $u,w$ are on same path $P\in\mathcal{P}$.

$P_{\ell+1}$$P_{\ell^{\prime}}$$P_{3}$$P_{2}$$P_{1}$$u$$w$$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{\ell^{\prime}}$$y_{\ell^{\prime}}$$\vdots$$\vdots$
(b) $(w,x_{1})$ and $(y_{\ell^{\prime}},u)$ are cross edges.

$P_{\ell+1}$$P_{\ell^{\prime}}$$P_{3}$$P_{2}$$P_{1}$$u$$w$$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{\ell^{\prime}}$$\vdots$$\vdots$
(c) $(w,x_{1})$ is a cross edge and $y_{\ell^{\prime}}=u$.

$P_{\ell+1}$$P_{\ell^{\prime}}$$P_{3}$$P_{2}$$P_{1}$$u$$w$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{\ell^{\prime}}$$y_{\ell^{\prime}}$$\vdots$$\vdots$
(d) $(y_{\ell^{\prime}},u)$ is a cross edge and $x_{1}=w$.

$P_{\ell+1}$$P_{\ell^{\prime}}$$P_{3}$$P_{2}$$P_{1}$$u$$w$$y_{1}$$x_{2}$$y_{2}$$x_{3}$$y_{3}$$x_{\ell^{\prime}}$$\vdots$$\vdots$
(e) Neither $(w,x_{1})$ nor $(y_{\ell^{\prime}},u)$ is a cross edge.

Figure 7: Sketch of rerouted paths to remove common vertices and extended
deadlock cycles. The dotted and dashed subpaths are removed from the paths and
the red lines with an arrow show a switch to another path.

Correctness. One can see that our algorithm discovers every common subpath of
$P^{*}$ with a path $P^{c}\in\mathcal{P}$ as well as every extended deadlock
cycle since, in both cases, we have a vertex $u$ followed by $w$ on $P^{*}$
such that $w$ is discovered from $u$ while running backwards on $\mathcal{P}$.
Since $V^{*}$ only shrinks (no new cross edges can occur), since by
construction the new paths have no common vertices accept $s$ and $t$ (here it
is important that the constructed $u$-$w$ path has no subsequent cross edges)
and since we choose $w$ as the latest vertex of $P^{*}$ touching $Q^{\prime}$,
$Q$ maintains a clean area when adding $Q^{\prime}$ to it. Note that each
vertex with a rerouting information becomes part of $Q$. Thus, the size of $Q$
increases by $\Omega(n/\log k)$ when our algorithm stops unless we reach $t$
while running on $P^{*}$.

Efficiency. Concerning the running time, note that we travel along $P^{*}$ as
well as construct a set $Q^{\prime}$ with a DFS on the paths in $\mathcal{P}$.
Note that we process all vertices of $Q^{\prime}$ at most once by each of the
two standard DFS runs (once to construct $Q^{\prime}$ as well as once to find
a $u$-$w$ path for computing the rerouting) before $Q^{\prime}$ is added into
$Q$. Within the processing of each vertex $v$, we call $\mathtt{prev}(v)$ only
once. Since each access to a vertex $v$ can be realized in
$O(\deg(v)+k^{3}\log^{3}k)$ time (Lemma 3.12), the total running time is
$O(nk^{3}\log^{3}k)$.

Concerning the space consumption observe that $\overrightarrow{r}$ and
$\overleftarrow{r}$, a backup of $Q$ and $p$ as well as all arrays use $O(n)$
bits. To run the DFS, $O(n+\ell\log n)$ bits suffice (storing the colors
white, grey and black in $O(n)$ bits and $O(\ell\log n)$ bits for the DFS
stack since we only have to store the endpoints of $O(\ell)$ subpaths that are
part of the stack). Together with the space used by Lemma 3.12, our algorithm
can run with $O(n+k^{2}(\log k)\log n)$ bits.

We can not store our rerouted paths directly in a valid path data scheme. To
follow the path with respect to the rerouting we next provide a so-called weak
path data structure for all $s$-$t$ paths of
$R(\mathcal{P}\cup\\{P^{\prime}\\})$.

Recall that we have a path data scheme storing the single path $P^{*}$ and a
path data scheme storing the set $\mathcal{P}$ of paths. Let $Q$, $p$ as well
as $R$ (realized by $(V^{*},\overrightarrow{r},\overleftarrow{r})$) be
returned by the previous lemma. Our valid path data scheme can only store
$s$-$t$-paths, but $R(\mathcal{P}\cup\\{P^{\prime}\\})$ may contain an
$s$-$p^{\prime}$ path $P^{\prime\prime}$ with $p^{\prime}\neq t$. In the case
that $p^{\prime}\neq t$, we compute a path numbering and a valid path data
scheme for the path $P^{**}$ obtained from $P^{*}$ by replacing the subpath
$P^{\prime}$ by $P^{\prime\prime}$. (The path $P^{**}$ replaces the path
$P^{*}$ in the computation of the next batch.) Furthermore, we remove the path
$P^{\prime\prime}$ from $R(\mathcal{P}\cup\\{P^{\prime}\\})$ by removing its
vertices from $V^{*}$. It is easy to see that this modification of the paths
can be done in the same bounds as stated in Lemma 3.21.

After the modification of the paths we show how to follow the paths with
respect to $R$. Since we can find out in $O(1)$ time if a vertex $u$ belongs
to $P^{*}$, a call of $\mathtt{prev}$ and $\mathtt{next}$ below is forwarded
to the correct path data scheme. We now overload the $\mathtt{prev}$ and
$\mathtt{next}$ operations of our path data structure as follows, and so get a
weak path data structure for
$R(\mathcal{P}\cup\\{P^{\prime}\\})\setminus\\{P^{\prime\prime}\\}$ that
supports $\mathtt{prev^{\prime}}$ and $\mathtt{next^{\prime}}$ in time
$O(\mathtt{deg}(v)+k^{3}\log^{3}k)$ by using $O(n+k^{2}(\log k)\log n)$ bits
and that supports access to $V^{*}$ in constant time. To obtain the runtime we
realize $\mathtt{prev^{\prime}}$ and $\mathtt{next^{\prime}}$ by computing the
paths within at most one region, from which we know the color of all neighbors
of $u$. In detail, the weak path data structure supports the following
operations where $u\in V^{*}$.

  * •

$\mathtt{prev^{\prime}}(u)$: If $\overleftarrow{r}(u)=0$, return
$\mathtt{prev}(u)$. Else, return $v\in N(u)\cap V^{*}$ with
$\mathtt{color}(v)=\overleftarrow{r}(u)$.

  * •

$\mathtt{next^{\prime}}(u)$: If $\overrightarrow{r}(u)=0$, return
$\mathtt{next}(u)$. Else, return $v\in N(u)\cap V^{*}$ with
$\mathtt{color}(v)=\overrightarrow{r}(u)$.

  * •

$\mathtt{inVStar}$$(u)$: Returns true exactly if $u\in V^{*}$.

To compute a valid path data scheme for $1<\ell\leq k$ good $s$-$t$-paths we
have to partition $G[V^{*}]$ into regions. More exactly we have to find a set
$B^{\prime}\subseteq V^{*}$ of boundary vertices such that $G[V^{*}\setminus
B^{\prime}]$ consists of regions (i.e., connected components) of size $O(k\log
k)$. To find the boundary we start with the set $S$ of neighbors of $s$ that
belong to $V^{*}$ and move $S$ to the right “towards” $t$ such that $S$ always
is a separator that disconnects $s$ and $t$ in $G[V^{*}]$. Whenever there are
$O(k\log k)$ vertices “behind” the previous separator that was added to our
boundary, we add $S$ to our boundary—see also Fig. 8. While moving $S$ towards
$t$, we always make sure that the endpoints of a cross edge are not in
different components in $G[V^{*}\setminus S]$. This means, we do not move $S$
over an endpoint of a cross edge unless the other endpoint is also in $S$. We
show in the next lemma that this is possible if we have no extended deadlock
cycles and if we use the following trick for simple deadlock cycles: move $S$
one vertex further along the path for all vertices part of the simple deadlock
cycle.

$s\phantom{t}$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 3 18 4 5 1 6 7 8 9
10 11 13 12 14 15 16 17 18 19 1 2 3 $t$

$\dots$

Figure 8:  Our algorithm determines a boundary by moving from $s$ along all
paths with respect to the cross edges (colored edges), i.e., it cannot move
from a vertex that is an endpoint of a cross edge if the other endpoint is not
yet reached. In the example, we assume that $k\log k=18$. The number in the
vertices denotes the seen vertices since adding vertices to the boundary the
last time.

In the case that the previous lemma returned paths containing an
$s$-$p^{\prime}$ path with $p^{\prime}\neq t$, then our weak path data
structure gives access to $\ell$ good $s$-$t$ paths. Otherwise, $p^{\prime}=t$
and we have access to $\ell:=\ell+1$ good $s$-$t$ paths.

######  Lemma 3.23.

Given a weak path data structure for accessing $\ell$ good $s$-$t$ paths
$\mathcal{P}^{\prime}$ there is an algorithm that computes a valid path data
scheme storing $\ell$ good $s$-$t$ paths. The algorithm runs in
$O(nk^{3}\log^{3}k)$ time and uses $O(n+k^{2}(\log k)\log n)$ bits.

######  Proof 3.24.

Let $V^{*}$ be the vertices of $P^{*}$ and $\mathcal{P}^{\prime}$ obtained
from the weak path data structure. As in the last proof, we assume that the
paths in $\mathcal{P}^{\prime}$ are colored from $1,\ldots,\ell$. For the case
that $p^{\prime}\neq t$, we compute a new path data scheme for $P^{*}$ by
Lemma 3.15. Moreover, we remove the vertices of $P^{*}$ from $V^{*}$ and start
to compute our path data scheme for $\mathcal{P}^{\prime}$. Our algorithm
works in three steps. First we compute the boundary, then a path data scheme,
and finally make it valid.

Compute the boundary. Start with the set $S$ of all $|\mathcal{P}^{\prime}|$
neighbors $u$ of $s$ in $G[V^{*}]$. Note that the vertices in $S$ are
candidates for a boundary because $S$ has the property that it cuts all
$s$-$t$-paths; in other words, there is no path in $G[V^{*}\setminus S]$ that
connects $s$ and $t$. For performance reasons, we cache
$\mathtt{next}^{\prime}(u)$ for each vertex $u$ in $S$ as long as $u$ is in
$S$ so that we have to compute it only once. From $S$ we can compute the next
set $S^{\prime}$ of candidates for a boundary. The idea is to try to put for
each vertex $u\in S$ the vertex $v=\mathtt{next}^{\prime}(u)$ of the same path
into $S^{\prime}$. However, we cannot simply do this if $u$ has a cross edge
that can bypass $S^{\prime}$. In that case we take $u$ into $S^{\prime}$. If
$S=S^{\prime}$, then one (or multiple) deadlock cycles restrain us to add new
vertices to $S^{\prime}$. We are either able to take the next vertex of every
vertex of $S$ that is part of a a simple deadlock cycle into $S^{\prime}$ or
show that an extended deadlock cycle exists, which is a contradiction to our
property that our paths are good.

We now focus on the structures that we use in the subsequent algorithm. Let
$D$ (initially $D:=S\cup\\{s\\}$) be a set consisting of all vertices of the
connected component of $G[V^{*}\setminus S]$ that contains $s$ as well as the
vertices of $S$. (Intuitively speaking, $D$ is the set of vertices for which
the membership in a boundary was already decided.) We associate the index of a
vertex with its path membership (not its color since a weak path data scheme
does not provide color information). Technically we realize $S$ and
$S^{\prime}$ as arrays of $|\mathcal{P}^{\prime}|$ fields such that $S[i]$ and
$S^{\prime}[i]$ store vertices $u_{i}$ and $v_{i}$, respectively, of
$P_{i}\in\mathcal{P}^{\prime}$ ($1\leq i\leq|\mathcal{P}^{\prime}|$).
Moreover, for each $u_{i}\in S$ on path $P_{i}\in\mathcal{P}^{\prime}$ we
store the number $\mathtt{d}(i)=|(N(u_{i})\cap V^{*})\setminus D|$ in an array
of $|\mathcal{P}^{\prime}|$ fields. These numbers represents the number of
edges whose head does point at a vertex outside of $D$. If $\mathtt{d}(i)\neq
1$, then $u_{i}$ has a cross edge to some vertex not in $D$ and we cannot
simply put $v_{i}:=\mathtt{next}^{\prime}(u_{i})$ inside $S^{\prime}$, because
we might get a cross edge that can be used by an $s$-$t$ path in
$G[V^{*}\setminus S^{\prime}]$. Otherwise, if $\mathtt{d}(i)=1$, then $u_{i}$
has no cross edge possibly bypassing $S^{\prime}$ and we can take $v_{i}$ into
$S^{\prime}$. Let $B^{\prime}$ be an initially empty set of boundary vertices.
To know when the next set $S$ can be added to the boundary $B^{\prime}$ such
that the property that the boundary defines regions of size $O(k\log k)$
holds, we use a counter $c$ (initially $c:=0$) to count the number of vertices
that we have seen until extending the boundary the last time.

We now show our algorithm to compute $S^{\prime}$ given $S$. Take
$B^{\prime}:=S$, initialize $\mathtt{d}(i)$ as $|(N(u_{i})\cap V^{*})\setminus
D|$ for each $u_{i}\in S$, and compute a set $S^{\prime}$ in phases as
follows. For each $u_{i}\in S$, if $\mathtt{d}(i)=1$, take
$v_{i}=\mathtt{next^{\prime}}(u_{i})$ into $S^{\prime}$, increment $c$ by one,
and set $\mathtt{d}(i)=|(N(v_{i})\cap V^{*})\setminus D|$. Moreover, for each
$w_{j}\in(N(v_{i})\cap S)$ decrement $\mathtt{d}(j)$ by one. If
$\mathtt{d}(i)\neq 1$, take $u$ into $S^{\prime}$. If $S\neq S^{\prime}$, add
$S^{\prime}$ into $D$, set $S:=S^{\prime}$ and repeat the phase.

Otherwise (i.e., $S=S^{\prime}$) we run into the special case where we have
encountered a deadlock cycle (possible a combination of deadlock cycles),
which we can handle as follows. Since $\mathcal{P}^{\prime}$ is good and
$\widetilde{P}$ is clean, we have one or more simple deadlock cycles with
vertices in $S$. Set $c=c+|\mathcal{P}^{\prime}|$ and take
$\widetilde{S}=\\{\mathtt{next^{\prime}}(u)\ |\ u\in S\\}$. Note that all
these simple deadlock cycles have only vertices in $S\cup\widetilde{S}$, but
not all vertices of $\widetilde{S}$ have to be part of a simple deadlock
cycle. To compute $S^{\prime}$ from $\widetilde{S}$, we have to remove the
vertices from $\widetilde{S}$ that are not part of the simple deadlock cycle,
which we can do as follows. Take $S^{\prime}:=\widetilde{S}$. Check in rounds
if $S^{\prime}$ separates $S$ from $t$, i.e., for each $v_{i}\in S^{\prime}$
with $1\leq i\leq|\mathcal{P}^{\prime}|$, choose $u_{i}=S$ and check if
$\mathtt{d}(j)>\ell$. If not, additionally check if a $w_{j}\in(N(u_{i})\cap
V^{*})\setminus(D\cup\\{S^{\prime}[j]\\})$ exists. If one of the check passes,
some edge of $u_{i}$ bypasses $S^{\prime}$ and we replace $v_{i}$ by $u_{i}$
in $S^{\prime}$ and decrement $c$ by one. Then repeat the round until no such
$w$ can be found for any vertex. Afterwards, set $S^{\prime}$ as the new $S$,
add $S$ into $D$, and compute the $d$-values for the new vertices in $S$, and
proceed with the next phase.

If $c>k\log k$ after adding $S$ into $D$, add the vertices of $S$ to
$B^{\prime}$, and reset $c:=0$. Repeat the algorithm until $S=N(t)\cap V^{*}$
and add the vertices of $S$ to $B^{\prime}$. Finally, add all vertices of
$V^{*}$ with large degree to $B^{\prime}$.

Correctness of the boundary. We show the following invariant whenever we
update $S$: the removal of $S$ in $G[V^{*}]$ disconnects $s$ and $t$.
Initially, this is true for the neighbors of $s$ because their removal
disconnects each chordless path in $G[V^{*}]$. If we have a vertex $u\in S$ on
$P_{i}\in\mathcal{P}$ with only one neighbor in $G[V^{*}\setminus D]$, i.e.,
we have $\mathtt{d}(i)=1$, then
$S^{\prime}=(S\setminus\\{u\\})\cup\\{\mathtt{next^{\prime}}(u)\\}$ is again a
valid separator. If we have no such vertex $u$, then we construct a set
$S^{\prime}$ and we check for each vertex in $S$ if it has a cross edge that
destroys $S^{\prime}$ being a separator. Thus, we set $S:=S^{\prime}$ only if
$S^{\prime}$ is again a separator.

We next show that we make progress with each separator $S$ over all phases,
i.e., we find a new separator so that $D$ increases. For a simpler notation,
let us say that a vertex on a path is behind another vertex on the path if the
latter is closer to $s$. As long as we do not run into the special case having
a deadlock cycle, we can clearly make progress. Let $S^{\prime}$ be defined as
in the beginning of the special case, i.e., $S^{\prime}$ consists of the
successors on the paths of each vertex in $S$. Let us consider a deadlock
cycle $Z$ whose subpaths all begin with a vertex in $S$. Let $S^{Z}$ be the
endpoints of the subpaths. Choose $Z$ such that no cross edge of a vertex
$v\in S^{Z}$ ends at a vertex $w$ on a path that is part of another deadlock
cycle $Z^{\prime}$ such that $w$ is behind the subpath part of $Z^{\prime}$.

Assume for a contradiction that no such $Z$ exists. Then we must have a cyclic
sequence of $x\geq 2$ deadlock cycles where each deadlock cycle has a vertex
in $S$ with a cross edge $e^{\prime}$ to a vertex of the next deadlock cycle
(Fig. 9a shows an example for $x=2$). But then we can use the cross edges to
build an extended deadlock cycle. (Fig. 9b).

$P_{1}$$P_{2}$$P_{3}$$P_{4}$$P_{5}$$P_{6}$
$e^{\prime}$$e^{\prime\prime}$$S$$S^{\prime}$ (a) Two simple deadlock cycles
$Z^{\prime}$ and $Z^{\prime\prime}$.

$P_{1}$$P_{2}$$P_{3}$$P_{4}$$P_{5}$$P_{6}$
$e^{\prime}$$e^{\prime\prime}$$S$$S^{\prime}$ (b) An extended deadlock cycle.

Figure 9: Illustration of the construction of an extended deadlock cycle if
our algorithm can not compute $S$ and $S^{\prime}$ with $S\neq S^{\prime}$.
The colored vertices are the vertices in $S^{Z^{\prime}}$ and
$S^{Z^{\prime\prime}}$ of the deadlock cycles $Z^{\prime}$ and
$Z^{\prime\prime}$ with the same color, respectively.

For a path $P_{i}\in\mathcal{P}$, let us consider the successor $v_{i}$ on
$P_{i}$ of a vertex $u_{i}$ in $S^{Z}$ that is replaced first among all
vertices in $S^{Z}$ in the current phase. Clearly, it is replaced by $u_{i}$
in $S^{\prime}$. Then we have a cross edge $e$ from $u_{i}$ either to (Case 1)
a path $P^{\prime}$ that does not begin with a vertex in $S^{Z}$ or (Case 2)
$e$ ends behind a vertex of $S^{\prime}$. In the Case 1, by the property of
$Z$, $P^{\prime}$ can not be part of a deadlock cycle and we are not in the
special case. In the Case 2, by the property of $Z$, $e$ must end on a vertex
that belongs to the deadlock cycle. Since $e$ ends behind a vertex of
$S^{\prime}$, we have an extended deadlock cycle; a contradiction. Thus, the
vertices being successors of $S^{Z}$ remain in $S^{\prime}$ and we make
progress in the special case.

Computing the new valid path data scheme. We know $V^{*}$ and the new boundary
$B^{\prime}$. For a valid path data scheme it remains to compute a path
numbering $A^{\prime}$, the colors for the boundary vertices and their
predecessors and successors that we store in an $O(n)$-bit structure
$C^{\prime}$ using static space allocation. We can compute $A^{\prime}$ by
moving along each path from $s$ to $t$.

It is important that all vertices of an $s$-$t$ path are colored with the same
color, however we want to use Lemma 3.10 that computes path inside one region.
Since $s$-$t$ paths are disconnected by boundary vertices our approach is to
start with an arbitrary coloring of the neighbors $W$ of $s$ part of the paths
that are the first boundary vertices and from these make a parallel run over
the paths. Whenever we enter a region we explore it and compute paths within
the region. Using the paths we propagate the colors of the boundary vertices
along the paths to the next boundary vertices, their predecessors and
successors and repeat our algorithm.

Let $D\subseteq V^{*}$ (initially $D:=W\cup\\{s\\}$) be the set of vertices
for that we have already decided their color. To find a fixed routing within a
region we explore the region of every neighbor of $W$ in
$G[V^{*}\setminus(B^{\prime}\cup D)]$ using a BFS that skips over vertices in
$B^{\prime}\cup D$. We collect all visited vertices of one region in a set $U$
realized by a balanced heap. (If $U$ is empty, the region was already explored
from another neighbor of a vertex of $W$ and we continue with the next vertex
$v\in W$.) In addition we construct two sets $S^{\prime}$ and $T^{\prime}$.
Each visited vertex $u\in U$ is put in $S^{\prime}$ if
$\mathtt{prev^{\prime}}(u)\in B^{\prime}$ holds and put in $T^{\prime}$ if
$\mathtt{next^{\prime}}(u)\in B^{\prime}$ holds (a vertex $u$ can be part of
$S^{\prime}$ as well as $T^{\prime}$ if both holds). We apply Lemma 3.10 with
$U$, $S^{\prime}$ and $T^{\prime}$ as input and get paths connecting each
vertex of $S^{\prime}$ with another vertex of $T^{\prime}$. We set $D:=D\cup
U$ to avoid the exploration of explored regions again.

Let $F$ be a set of vertices whose successors of $W$ are in $U$. Intuitively,
by having $F$ we can avoid computing the paths of a region again and gain. For
each vertex $v\in F$ we use $\mathtt{next^{\prime}}(v)$ and so move to a
vertex $u$ of $S^{\prime}$—we are now on a path computed by Lemma 3.10. We
store the color $q$ of $v$ for this vertex and run along the path until it
ends. We store the color $q$ for the last vertex $w$ of the path and use
$\mathtt{next^{\prime}}(w)$ to move to a boundary vertex $v^{\prime}$ that we
also color with $q$. If the vertex
$u^{\prime}=\mathtt{next^{\prime}}(v^{\prime})$ is on a computed path we
repeat this paragraph with $v:=v^{\prime}$. Otherwise, we put $u^{\prime}$
into a set $W^{\prime}$ and remove $v$ from $F$. If $F$ loses its last vertex
we set $W:=W^{\prime}$ and $F=W^{\prime}=\emptyset$ and repeat the iteration.
Otherwise, we proceed with the next vertex $v\in W$.

While moving over the paths we extend $D$ by the visited vertices. Moreover we
compute the path numbering for $A^{\prime}$ and all colors are stored in
$C^{\prime}$. Recall that in order to use static space allocation we first
need to know the set of all vertices in advance that we afterwards want to
color. Do get that set we can run the algorithm in two steps. In the first we
do not store the colors but only compute a set of vertices that must be
colored. Using it as a key set for static space allocation we repeat our
algorithm in a second step and store the coloring. The triple
$(A^{\prime},B^{\prime},C^{\prime})$ represents the new valid path data
structure.

Correctness of the new valid path data scheme. The boundary and the rerouted
paths represented by the weak path data structure fixes the boundary vertices
and their predecessor and successors. Hence our selection of the vertices for
$U$, $S^{\prime}$ and $T^{\prime}$ is also fixed for each region. Computing
the paths using Lemma 3.10 fixes the path numbering. Since a (re)computation
with the same algorithm produces the same paths (being subpaths of our $s$-$t$
paths) and since we used the paths to propagate the coloring, the endpoints of
a path and thus, all all colored vertices along a path are equally colored in
$C^{\prime}$. Therefore our path data scheme is valid. Moreover, $S^{\prime}$
and $T^{\prime}$ consists of the endpoints of subpaths of good paths. Hence, a
network-flow algorithm can connect each vertex of $S^{\prime}$ with another
vertex of $T^{\prime}$ and by Lemma 3.4 our paths are chordless and deadlock
free paths, it also holds for the paths of them.

Efficiency. We first consider the time to compute the boundary. For each new
vertex $u$ in $S$, we spend $O(\mathtt{deg}(u))$ time to determine once its
degree in $G[V^{*}\setminus D]$ and to decrement already stored degrees of the
neighbors of $u$. In each phase we iterate over all elements of $S$ and make
$|S\Delta S^{\prime}|=\Omega(1)$ progress on at least one path, which means
that we need at most $O(n\ell)$ phases. Determining the previous / next vertex
$u$ on a path can be done in time $O(\mathtt{deg}(u)+k^{3}\log^{3}k)$. Dealing
with simple deadlock cycles requires us to compute the $\ell$ initial members
of $S^{\prime}$, which cost us $O(\ell(\mathtt{deg}(u)+k^{3}\log^{3}k))$ time
and roundwise replace members in $S^{\prime}$ by their predecessors. Because
$|S^{\prime}|=O(\ell)$, this can cause $O(\ell)$ rounds. We spend
$O(\ell^{2})$ time to check if $S^{\prime}$ is a separator. Thus,
$O(\ell^{3})$ time allows us to compute a separator $S^{\prime}$ in the
special case, and $O(\ell)$ time allows us to add the at most $\ell$ vertices
to $D$ within each phase.

To construct a valid path data scheme we need to explore all regions once,
which can be done in time linear to the size of each region plus the number of
edges that leave the region, i.e., in $O(nk)$ time. The construction of
$S^{\prime}$ and $T^{\prime}$ requires the execution of
$\mathtt{prev^{\prime}}$ and $\mathtt{next^{\prime}}$ on each vertex once,
which runs in $O(nk^{3}\log^{3}k)$ time. Lemma 3.10 uses
$O(n^{\prime}k^{2}\log^{2}k)$ time for a region of size $n^{\prime}$. Using it
on every region once can be done in $O(nk^{2}\log^{2}k)$ time. Propagating the
color requires us to move along the paths, which can be done in in time
$O(nk^{3}\log^{3}k)$ time. The total time of the algorithm is
$O(nk^{3}\log^{3}k)$.

Our space bound is mainly determined by $D$, $V^{*}$, $A^{\prime}$,
$B^{\prime}$ and $C^{\prime}$ each of $\Theta(n)$ bits and the application of
Lemma 3.12 ($O(k^{2}(\log k)\log n)$ bits), which is used in the weak path
data structure whenever we access a previous or next vertex on a path. For
$S$, $W$ and $F$ (and their copies) we need $\Theta(\ell\log n)$ bits. The
construction of the paths inside regions uses $O(k^{2}(\log k)\log n)$ bits
(Lemma 3.10). In total, we use $O(n+k^{2}(\log k)\log n)$ bits.

Given path storage scheme storing $\ell<k$ good $s$-$t$-paths and an
$(\ell+1)$th path $P^{*}$ we can batchwise compute a path storage scheme
storing $(\ell+1)$ good $s$-$t$ paths by subsequently executing $O(\log k)$
times Lemma 3.21 and Lemma 3.23.

######  Corollary 3.25.

Given a path storage scheme storing $\ell<k$ good $s$-$t$-paths $\mathcal{P}$
and an $(\ell+1)$th dirty path with respect to $\mathcal{P}$ we can compute a
path storage scheme storing $(\ell+1)$ good $s$-$t$ paths in
$O(nk^{4}\log^{4}k)$ time using $O(n+k^{2}(\log k)\log n)$ bits.

Initially our set of $s$-$t$-paths $\mathcal{P}$ is empty. Then a repeated
execution of Lemma 3.19 and Corollary 3.25 allows us to show our final theorem
for computing vertex-disjoint $s$-$t$-paths in
$O(k((n(k+\log^{*}n)k^{3}\log^{3}k)+(nk^{4}\log^{4}k)))=O(n(k\log
k+\log^{*}n)k^{4}\log^{3}k)$ time.

######  Theorem 3.26.

Given an $n$-vertex graph $G=(V,E)$ with treewidth $k$ and two vertices
$s,t\in V$ there is an algorithm that can compute a maximum amount of $k$
chordless vertex-disjoint paths from $s$ to $t$ in $O(n(k\log
k+\log^{*}n)k^{4}\log^{3}k)$ time using $O(n+k^{2}(\log k)\log n)$ bits.

Knowing a maximum set of $k$ vertex-disjoint paths between two vertices $s$
and $t$, we can easily construct a vertex separator for $s$ and $t$.

######  Corollary 3.27.

Given an $n$-vertex graph $G=(V,E)$ with treewidth $k$, and two vertices $s\in
V$ and $t\in V$, $O(n(k\log k+\log^{*}n)k^{4}\log^{3}k)$ time and
$O(n+k^{2}(\log k)\log n)$ bits suffice to construct a bit array $S$ marking
all vertices of a vertex separator for $s$ and $t$.

######  Proof 3.28.

First construct the maximum number $k$ of possible chordless pairwise vertex-
disjoint paths from $s$ to $t$ (Theorem 3.26). Then try to construct a further
$s$-$t$ path with a DFS as describe in the proof of Lemma 3.19 and store the
set $Z$ of vertices that are processed by the DFS. Finally run along the paths
from $s$ to $t$ and compute the set $S$ consisting of the last vertex on each
path that is part of $Z$. These vertices are an $s$-$t$-separator.

Many practical applications that use treewidth algorithms have graphs with
treewidth $k=O(n^{1/2-\epsilon})$ for an arbitrary $\epsilon>0$, and then our
space consumption is $O(n)$ bits.

##  4 Sketch of Reed’s Algorithm

In this section we first sketch Reed’s algorithm to compute a tree
decomposition and then the computation of a so-called balanced $X$-separator.
In the following sections, we modify his algorithm to make it space efficient.

Reed’s algorithm [36] takes an undirected $n$-vertex $m$-edge graph $G=(V,E)$
with treewidth $k$ and an initially empty vertex set $X$ as input and outputs
a balanced tree decomposition of width $8k+6$. To decompose the tree he makes
use of separators. An $X$-separator is a set $S\subset V$ such that $S$
separates $X$ among the connected components of $G[V\setminus S]$ and no
component contains more than $2/3|X|$ vertices of $X$. A balanced
$X$-separator $S$ is an $X$-separator with the additional property that no
component of $G[V\setminus S]$ contains more than $2/3|V|$ vertices.

The decomposition works as follows. If $n\leq 8k+6$, we return a tree
decomposition $(T,B)$ consisting of a tree with one node $r$ (the root node)
and a mapping $B$ with $B(r)=V$. Otherwise, we search for a so-called balanced
$X$-separator $S$ of size $2k+2$ that divides $G$ such that $G[V\setminus S]$
consists of $x\geq 2$ connected components $\Gamma=\\{G_{1},\ldots,G_{x}\\}$.
Then, we create a new tree $T$ with a root node $r$, a mapping $B$, and set
$B(r)$ to $X\cup S$. For each graph $G_{i}\in\Gamma$ with $1\leq i\leq x$, we
proceed recursively with $G^{\prime}=G_{i}[V(G_{i})\cup S]$ and
$X^{\prime}=((X\cap V(G^{\prime}))\cup S)$. Every recursive call returns a
tree decomposition $(T_{i},B_{i})$ ($i=1,\ldots,x$). We connect the root of
$T_{i}$ to $r$, we then set $B(w)=B_{i}(w)$ for all nodes $w\in T_{i}$. After
processing all elements of $\Gamma$ return the tree decomposition $(T,B)$.

Since a balanced $X$-separator is used, the tree has a depth of $O(\log n)$,
and thus the recursive algorithm produces at most $O(\log n)$ stack frames on
the call stack—each stack frame is associated with a node $w$ of $T$. A
standard implementation of the algorithm needs a new graph structure for each
recursive call. In the worst-case, each of these graphs contains $2/3$ of the
vertices of the previous graph. Thus, the graphs on the stack frame use
$\Theta((n+m)\log n)=\Theta(kn\log n)$ bits. Storing the tree decomposition
$(T,B)$ requires $\Theta(kn\log n)$ bits as well. The various other structures
needed can be realized within the same space bound. In conclusion, a standard
implementation of Reed’s algorithm requires $\Theta(kn\log n)$ bits.

The next lemma shows a space-efficient implementation for finding a balanced
$X$-separator.

######  Lemma 4.1.

Given an $n$-vertex graph $G=(V,E)$ with treewidth $k$ and $X\subseteq V$ of
at most $6k+6$ vertices, there is an algorithm for finding a balanced
$X$-separator of size $2k+2$ in $G$ that, for some constant $c$, runs in
$O(c^{k}n\log^{*}n)$ time and uses $O(n+k^{2}(\log k)\log n)$ bits.

######  Proof 4.2.

We now sketch Reed’s ideas to compute a balanced $X$-separator. To compute a
balanced $X$-separator we compute first an $X$-separator $S_{1}$. To make it
balanced, we compute an additional $R$-separator $S_{2}$ where $R$ is a set of
vertices that is in some sense equally distributed in $G$. Then $S=S_{1}\cup
S_{2}$ is a balanced $X$-separator.

Reed computes an $X$-separator by iterating over all $3^{|X|}$ possibilities
to split $X$ into three vertex-disjoints sets $X_{1}$, $X_{2}\subseteq V$ and
$X_{S}$ with $|X_{S}|\leq k$ and $|X_{1}|,|X_{2}|\leq\max\\{k,2/3|X|\\}$. For
each iteration connect two new vertices $s^{\prime}$ and $t^{\prime}$ with all
vertices of $X_{1}$ and $X_{2}$, respectively, compute vertex disjoint paths
with Corollary 3.27 to find a separator $S$ and check if $X_{S}\subseteq S$
holds.

We now shortly describe Reed’s computation of the set $R$. Run a DFS on the
graph $G$ and compute in a bottom up process for each vertex $v$ of the
resulting DFS tree the number of descendants of $v$. Whenever this number
exceeds $n/(8k+6)$, add $v$ to the initially empty set $R$ and reset the
number of descendants of $v$ to zero. At the end of the DFS, the set $R$
consist of at most $8k+6$ vertices, which can be used to compute a balanced
$X$-separator as described above. Similar to the $X$-separator, we compute an
$R$-separator.

We now show how to compute $R$ using $O(n)$ bits. To prove the lemma, we use
the following observation. Whenever the number of descendants for a node $u$
is computed, the numbers of $u$’s children are not required anymore. The idea
is to use a balanced parentheses representation, which consists of an open
parenthesis for every node $v$ of a tree, followed by the balanced parentheses
representation of the subtrees of every child of $v$, and a matching closed
parenthesis. Consequently, if $v$ is a vertex with $x$ descendants having its
open parenthesis at position $i$ and its closed parenthesis at position $j$,
then the difference between $i$ and $j$ is $2x$. Note that, taking an array
$A$ of $2n$ bits, we can store the number of descendants of $v$ in $A[i\ldots
j]$ as a so-called self-delimiting number by writing $x$ as $1^{x}0$. This
means that we overwrite the self-delimiting numbers stored fo the descendants
of the children of $v$.

To construct $R$ we run a space-efficient DFS twice, first to construct a
balanced parentheses representation of the DFS tree, which is used to compute
the descendants of each vertex in the DFS tree and so choose vertices for the
set $R$, and a second time to translate the ids of the chosen vertices since
the balanced parentheses representation is an ordinal tree, i.e., we lose our
original vertex ids and the vertices get a numbering in the order the DFS
visited the vertices. After choosing the vertices that belong to the set $R$
and marking them in a bit array $R^{\prime}$, we run the DFS again and create
a bit array $R^{*}$ that marks every vertex $v$ that the DFS visits as the
$i$th vertex if and only if $i$ is marked in $R^{\prime}$.

It remains to show how to compute the bit array $R^{\prime}$. Let $P$ be a bit
array of $2n$ bits storing the balanced parentheses representation, and let
$A$ be a bit array of $2n$ bits that we use to store the numbers of
descendants for some vertices. Note that a leaf is identified by an open
parenthesis followed by an immediately closed parenthesis. Moreover, since the
balanced representation is computed via a DFS in pre-order, we will visit the
vertices by running through $P$ in the same order. Note that Munro and Raman
[35] showed a succinct data structure for balanced representation that
initializes in $O(n)$ time and allows to compute the position of a matching
parenthesis, i.e., given an index $i$ of an open (closed) parenthesis there is
an operation $\mathtt{findclose}(i)$ ($\mathtt{findopen}(i)$) that returns the
position $j$ of the matching closed (open) parenthesis.

The algorithm starts in Case $1$ with $i=1$ ($i\in\\{1,\ldots,2n\\}$). We
associate $0$ with an open parenthesis and $1$ with a closed parenthesis.

Case 1

Iterate over $P$ until a leaf is found at position $i$, i.e., find an $i$ with
$P[i]=0\land P[i+1]=1$. Since we found a leaf we write a $1$ as a self-
delimiting number in $A[i\ldots i+1]$. Set $i:=i+2$ and check if $P[i]=1$. If
so, move to Case 2, otherwise repeat Case $1$.

Case 2

At position $i$ is a closing parenthesis, i.e., $P[i]=1$. In this cases we
reached the end of a subtree with $j=\mathtt{findopen}(i)$ being the position
of a corresponding open parenthesis. That means we have already computed all
numbers for the whole subtree. Using an integer variable $x$, sum up all the
self-delimiting numbers in $A[j+1\ldots i-1]$. Check if the sum $x+1$ exceeds
$\ell$. If it does write $0$ as a self-delimiting number in $A[j\ldots i]$ and
set $R^{\prime}[j]=1$, otherwise write $x+1$ in $A[j\ldots i]$. Note that we
store only one self-delimiting number between an open parenthesis and its
matching closed parenthesis, and this number does not necessary occupy the
whole space available. Hence, using $\mathtt{findclose}$ operation we jump to
the end of the space that is reserved for a number and start reading the
second.

After writing the number we set $i:=i+1$. We end the algorithm if $i$ is out
of $P$, otherwise we check in which case we fall next and proceed with it.

Efficiency: To compute the set $R$, we run two space-efficient DFS with $O(n)$
bits in $O(m+n\log^{*}n)=O(nk\log^{*}n)$ time (Lemma 2.7). The required
$X$-separator and $R$-separator are computed in $O(n(k\log
k+\log^{*}n)k^{4}\log^{3}k)$ time (Corollary 3.27). We so get a balanced
$X$-separator in $(3^{|X|}((nk\log^{*}n)+(n(k\log
k+\log^{*}n)k^{4}\log^{3}k)))=O(c^{k}n\log^{*}n)$ time for some constant $c$.

The structures $P$, $A$, and the space-efficient DFS use $O(n)$ bits. The size
of the sets $X_{1}$, $X_{2}$, $X_{S}$ and $R$ are bound by $O(k)$ and so use
$O(k\log n)$ bits. Corollary 3.27 uses $O(n+k^{2}(\log k)\log n)$ bits, which
is the bottleneck of our space bound.

##  5 Iterator for Tree Decompositions using $O(kn)$ bits

We now introduce our iterator by showing a data structure, which we call tree-
decomposition iterator. We think of it as an agent moving through a tree
decomposition $(T,B)$, one node at a time in a specific order. We implement
such an agent to traverse $T$ in the order of an Euler-traversal and, when
visiting some node $w$ in $T$, to return the tuple $(B(w),d_{w})$ with $d_{w}$
being the depth of the node $w$.

The tree-decomposition iterator provides the following operations:

  * •

$\mathtt{init}(G,k)$: Initializes the structure for an undirected $n$-vertex
graph $G$ with treewidth $k$.

  * •

$\mathtt{next}$: Moves the agent to the next node according to an Euler-
traversal and returns true unless the traversal of $T$ has already finished.
In that case, it returns false.

  * •

$\mathtt{show}$: Returns the tuple $(B(w),d_{w})$ of the node $w$ where the
agent is currently positioned.

We refer to initializing such an iterator and using it to iterate (call
$\mathtt{show}()$ after every call of $\mathtt{next}()$) over the entire tree
decomposition $(T,B)$ of a graph $G$ as iterating over a tree-decomposition
$(T,B)$ of $G$. Our goal in this section is to show that we can iterate over
the bags of a tree decomposition by using $O(kn)$ bits and $c^{k}n\log
n\log^{*}n$ time for some constant $c$. Recall that Reed’s algorithm computes
a tree decomposition using separators. Assume we are given a separator $S$ in
$G$. The separator divides $G$ into several connected components, which we
have to find for a recursive call. We refer to a data structure that
implements the functionality of the lemma below as a connected-component
finder. In the next lemma we use a choice dictionary [22, 24, 29] that manages
a subset $U^{\prime}$ of a universe $U=\\{1,\ldots,n\\}$ and provides—besides
constant-time operations contains, add and remove—a linear-time iteration over
$U^{\prime}$.

######  Lemma 5.1.

Given an undirected $n$-vertex $m$-edge graph $G=(V,E)$ and a vertex set
$S\subseteq V$, there is an algorithm that iterates over all connected
components of $G[V\setminus S]$. The iterator is realized by the following
operations.

  * •

$\mathtt{init}(G,S)$: Initializes the iterator.

  * •

$\mathtt{next}$: Returns true exactly if there is another connected component
left to iterate over. Returns false otherwise.

  * •

$\mathtt{show}$: Returns the triple $(C,p,n^{\prime})$ where $C$ is choice
dictionary containing all $n^{\prime}$ vertices of a connected component, and
$p\in C$.

The total runtime of all calls of next is $O(n+m)$ unless $\mathtt{next}$
returns false, and the running time of $\mathtt{init}(G,S)$ as well as of
$\mathtt{show}$ is $O(1)$. All operations use $O(n)$ bits.

######  Proof 5.2.

The iterator is initialized by creating a bit array $D$ to mark all vertices
that are part of connected components over which we already have iterated. To
hold the current state of the iterator and answer a call of $\mathtt{show}$ we
store the triple $(C=\emptyset,p=0,n^{\prime}=0)$ (as defined in the lemma).
Technically, to avoid modifications of the internal state of the iterator, we
maintain a copy of $C$ that we return if $\mathtt{show}$ is called.

If $\mathtt{next}$ is called, we iterate over $V$ starting at vertex $p$ until
we either find a vertex $p^{\prime}\in V\setminus(S\cup D)$ or reach $|V|+1$
(out of vertices). If $p^{\prime}$ exists, we have found a connected component
whose vertices are not part of $D$. We prepare a possible call of
$\mathtt{show}$ by computing new values for $(C,p,n^{\prime})$ as follows:
using a space-efficient BFS explore the connected component in $G[V\setminus
S]$ starting at $p^{\prime}$. Collect all visited vertices in a choice
dictionary $C^{\prime}$ as well as add them to $D$. Set
$C:=C^{\prime},p:=p^{\prime}$ and $n^{\prime}=|C^{\prime}|$. Finally output
true. Otherwise, $p^{\prime}$ does not exits and we reached $|V|+1$, set
$p^{\prime}=|V|+1$ and return false. For a call of $\mathtt{show}$ return
$(C,p,n^{\prime})$.

A choice dictionary can be initialized in constant time, thus $\mathtt{init}$
as well as $\mathtt{show}$ run in constant time. The operation $\mathtt{show}$
has to scan $V$ for the vertex $p^{\prime}$ in $O(n)$ time and runs a BFS in
$O(n+m)$ time to explore the connected component containing $p^{\prime}$.
However, the total time of all $\mathtt{next}$ operation is $O(n+m)$ since the
operation continues the scan in $V$ from $p$ (the last found $p^{\prime}$) and
avoids the exploration all vertices in $D$, i.e., all already explored
connected components. The bit array $D$ as well as the choice dictionary $C$
use $O(n)$ bits.

To implement our tree-decomposition iterator we turn Reed’s recursive
algorithm [36] into an iterative version. For this we use a stack structure
called record-stack that manages a set of data structures to determine the
current state of the algorithm. Informally, the record-stack allows us to
pause Reed’s algorithm at specific time-points and continue from the last
paused point. With each recursive call of Reed’s algorithm we need the
following information:

  * •

an undirected $n_{i}$-vertex graph $G_{i}=(V_{i},E_{i})$ ($i=0,1,2,\ldots$) of
treewidth $k$,

  * •

a vertex set $X_{i}$, a separator $S_{i}$, and

  * •

an instance $F_{i}$ of the connected-component-finder data structure that
iterates over the connected components of $G[V_{i}\setminus S_{i}]$ and that
outputs the vertices of each component in a bit array.

We call the combination of these elements a record. Although we use a record-
stack structure, often we think of it to be a combination of specialized stack
structures: a subgraph-stack, which manages to store the recursive graphs used
as a parameter for the call of Reed’s algorithm, a stack for iterating over
the connected components of $G[V\setminus S]$, called component-finder stack,
a stack containing the separators as bit arrays, called $\mathcal{S}$-stack, a
stack containing the vertex sets $X$ as bit arrays, called
$\mathcal{X}$-stack. The bit arrays $S_{i}$, $X_{i}$ and $F_{i}$ contain
information referring to $G_{i}$ and are thus of size $O(n_{i})$. On top of
$S_{i}$ and $X_{i}$ we create rank-select data structures. Pushing a record
$r_{\ell+1}=(G_{\ell+1},S_{\ell+1},X_{\ell+1},F_{\ell+1})$ to the record-stack
is equivalent to pushing each element in $r_{\ell+1}$ to the corresponding
stack (and analogous for popping).

######  Lemma 5.3.

When a record-stack $R$ is initialized for an undirected $n$-vertex graph $G$
with treewidth $k$ such that each subgraph $G_{i}$ of $G_{0}=G$ on the
subgraph-stack of $R$ contains 2/3 of the vertices of $G_{i-1}$ for $0<i<\ell$
and $\ell=O(\log n)$, then the record-stack occupies $O(n+k\log^{2}n)$ bits
plus $O(kn)$ bits for the subgraph stack.

######  Proof 5.4.

Let $m$ be the number of edges in $G$. We know that the size of the subgraph-
stack structure is $O(n+m)$ bits when the number of vertices of the subgraphs
shrink with every push by a factor $0<c<1$. Since each subgraph of $G_{0}$ has
also a treewidth $k$, the number of edges of each subgraph is bound by $k$
times the number of vertices. Thus, the subgraph stack uses $O(n+m)=O(kn)$
bits.

The size of the bit arrays $X_{i}$, $S_{i}$ (including the respective rank-
select structures) and the component-finder $F_{i}$ is $O(n_{i})$ for $0\leq
i\leq\ell$. This means the total size of the stacks containing these elements
is $O(n)$ bits since they shrink in the same way as the vertex sets of the
subgraphs. Storing the bag that is currently being output uses $O(k\log n)$
bits. Thus, the size of the record-stack without the subgraph stack is
$O(n+k\log^{2}n)$ bits.

We call a tree decomposition $(T,B)$ balanced if $T$ has logarithmic height,
and binary if $T$ is binary. Using our space-efficient separator computation
for finding a balanced $X$-separator we are now able to show the following
theorem.

######  Theorem 5.5.

Given an undirected $n$-vertex graph $G$ with treewidth $k$, there exists an
iterator that outputs a balanced and binary tree decomposition $(T,B)$ of
width $8k+6$ in Euler-traversal order using $O(kn)$ bits and $c^{k}n\log
n\log^{*}n$ time for some constant $c$.

######  Proof 5.6.

We implement our tree-decomposition iterator by showing $\mathtt{init}$,
$\mathtt{next}$ and $\mathtt{show}$. We initialize the iterator for a graph
$G$ with $n>8k+6$ vertices, by initializing a flag $f=0$, which indicates that
the agent is not yet finished, and initialize a record-stack. The record stack
is initialized by first initializing its subgraph stack with a reference to
$G$ as the first graph $G_{0}$. Next, we push the empty vertex set $X_{0}$ on
the $\mathcal{X}$-stack in form of an initial-zero bit array $X_{0}$ of length
$n$. Now, using the techniques described in Lemma 4.1, we find a balanced
$X_{0}$-separator $S_{0}$ of $G_{0}$ and push it on the $\mathcal{S}$-stack.
Then we create a new connected-component-finder instance $F_{0}$ (Lemma 5.1)
and push $F_{0}$ on the component-finder stack.

We now view our implementation of $\mathtt{next}()$, which has the task to
calculate the next bag on the fly. Since the tree $T$ of our tree
decomposition does not exist as a real structure, we only virtually move the
agent to the next node by advancing the state of Reed’s algorithm. If $f=1$,
we return false (the agent can not be moved) and do not change the state of
the record-stack. Otherwise, we first virtually move the agent and then return
true.

Move to parent: If $n_{\ell}\leq 8k+6$ (we leave a leaf), we pop the record
stack.

Otherwise, if the connected-component-finder instance $F_{\ell}$ has iterated
over all connected components and the record-stack contains more than one
record, we pop it. If afterwards the record-stack contains only one record, we
set $f=1$ (the agent moved to the root from the rightmost child; the traversal
is finished).

Move to next child: If $F_{\ell}$ has not iterated over all connected
components (the agent is moving to a previously untraversed node), we use
$F_{\ell}$ to get the next connected-component $C$ in
$G_{\ell}[V_{\ell}\setminus S_{\ell}]$, we push the vertex-induced subgraph
$G[C\cup S_{\ell}]$ on the subgraph stack as
$G_{\ell+1}=(V_{\ell+1},E_{\ell+1})$ and proceed with one of the next two
cases.

  * •

If $n_{\ell+1}\leq 8k+6$, we are calculating the bag of a leaf of $T$ by
setting $B(w)=V_{\ell+1}$. We do this by pushing a bit array with all bits set
to $1$ on the $\mathcal{S}$-stack and $\mathcal{X}$-stack and an empty
component-finder on the component-finder stack.

  * •

If $n_{\ell+1}>8k+6$, the agent is moving to a new internal node whose bag we
are calculating as follows: we push a new bit array $X_{\ell+1}=(X_{\ell}\cap
V_{\ell+1})\cup S_{\ell}$ on the $\mathcal{X}$-stack. We then find the
balanced $X_{\ell+1}$-separator $S_{\ell+1}$ of $G_{\ell+1}$ and push it on
the $\mathcal{S}$-stack. Then, create a new connected component-finder
$F_{\ell+1}$ for $G_{\ell+1}$ and $S_{\ell+1}$ and push it on the component-
finder stack and return true.

Anytime we pop or push a new record, we call the $\mathtt{toptune}$ function
of the subgraph stack to speed up the graph-access operations. This finishes
our computation of $\mathtt{next}()$.

To implement $\mathtt{show}()$, we return the tuple $(B(w),d_{w})$ with $B(w)$
being the current bag, and $d_{w}$ being the number of records of the record-
stack. The current bag is defined as $S\cup X$. Thus, we iterate over all
elements of $S\cup X$ via their rank-select data structures. Note that, since
the subgraph $G_{\ell}$ on top of the record stack is toptuned, we can return
the bag as vertices of $G_{0}$ or $G_{\ell}$ in $O(k)$ time.

Efficiency: The iterator uses a record-stack structure, which occupies $O(kn)$
bits. Since the running time of Lemma 4.1 is $O(c^{k}n\log^{*}n)$, for some
constant $c$, and the input graphs are split in each recursion level into
vertex disjoint subgraphs, the running time in each recursion level is
$O(c^{k}n\log^{*}n)$. Summed over all $O(\log n)$ recursion levels we get a
running time of $O(c^{k}n\log n\log^{*}n)$.

Make $T$ binary. The balanced $X$-separator $S$ partitions $V\setminus S$ into
any number of vertex disjoint sets between $2$ and $n$ such that no set
contains more than $2/3$ of the vertices of $V$ (and $X$). The idea is to
combine these vertex sets into exactly two sets such that neither contains
more than $2/3|V|$ vertices. For this we change our usage of the connected
component finder slightly. After we initialize $F_{\ell}$ we also initialize
two bit arrays $C_{1}$ and $C_{2}$ of size $n_{\ell}$ each with all bits set
to $0$. We also store the number of bits set to $1$ for each of the bit arrays
as $s_{1}$ and $s_{2}$, i.e., the number of vertices contained in them
(initially $0$). We now want to collect the vertices of all connected
components of $G_{\ell}[V_{\ell}\setminus S_{\ell}]$ in $C_{1}$ and $C_{2}$.
While there are still connected components to be returned by $F_{\ell}$, this
is done by obtaining the size of the next connected component via $F_{\ell}$
as $s$. If $s_{1}+s\leq 2/3|V_{\ell}|$, we collect the next connected
component in $C_{1}$ and increment $s_{1}=s_{1}+s$. Otherwise, we do the same
but for $C_{2}$ and $s_{2}$. Doing this until all connected components are
found results in $C_{1}$ and $C_{2}$ to contain all connected components of
$G_{\ell}[V_{\ell}\setminus S_{\ell}]$. For $(C_{1},C_{2})$ we implement a
function that returns $C_{1}$ if it was not yet returned, or $C_{2}$ if it was
not yet returned, or null otherwise. We store $(C_{1},C_{2})$ with the
respective functions on the connected component finder stack (instead of
$F_{\ell}$). Any time we do this during our iterator, the graph $G_{\ell}$ is
toptuned, resulting in constant time graph access operations. The previous
runtime and space bounds still hold.

Often it is needed to access the subgraph $G[B(w)]$ induced by a bag $B(w)$ of
a tree decomposition $(T,B)$ for further computations. We call such a subgraph
bag-induced. For this we show the following:

######  Lemma 5.7.

Given an undirected $n$-vertex graph $G$ with treewidth $k$ and an iterator
$\mathcal{A:G\rightarrow(T,B)}$ that iterates over a balanced tree
decomposition of width $O(k)$ we can additionally output the bag-induced
subgraphs using $O(k^{2}\log n)$ bits additional space and $O(kn\log n)$
additional time.

######  Proof 5.8.

To obtain the edges we use a bit matrix $M_{\ell}$ of size $O(k^{2})$ whose
bit at index $[v][u]$ is set to $1$ exactly if there exists an edge
$\\{v,u\\}$ in $G[B(w)_{\ell}]$. To quickly find the edges in $G[B(w)_{\ell}]$
we use $M_{\ell}$ together with rank-select data structures on $S_{\ell}$ and
$X_{\ell}$ that allow us to map the vertices in $B(w)_{\ell}=S_{\ell}\cup
X_{\ell}$, names as vertices of $G_{\ell}$, to $\\{1,\ldots,k\\}$. We create
$M_{\ell}$ anytime a new record $r_{\ell}$ is pushed on the record stack, and
anytime $r_{\ell}$ is popped, we throw away $M_{\ell}$. For reasons of
performance relevant in Section 7, we want to avoid accessing vertices
multiple times in a graph. Hence, when we push a bit matrix $M_{\ell}$, we
first use $M_{\ell-1}$ to initialize edges that were contained in
$B(w)_{\ell-1}$ and are still contained in $B(w)_{\ell}$. To obtain the edges
of a vertex $v$ in $B(w)_{\ell}$, we can iterate over all the edges of $v$ in
$G_{\ell}$ and check if the opposite endpoint is in $B(w)_{\ell}$. However, by
using definition (TD2) of a tree decomposition, it suffice to iterate only
over the edges of such a vertex once, i.e., the first time they are contained
in a bag to create $M_{\ell}$.

Efficiency: We can see that we store at most $O(\log n)$ matrices this way
since the record stack contains $O(\log n)$ records (i.e., the height of the
treedecomposition). Storing all bit matrices uses $O(k^{2}\log n)$ bits and
initializing all bit matrices takes $O(kn\log n)$ time, including initializing
and storing the rank-select structures if not already present.

We conclude the section with a remark on the output scheme of our iterator.
The specific order of an Euler-traversal encompasses many other orders of tree
traversal such as pre-order, in-order or post-order. To achieve these orders