# Sparse Outerstring Graphs Have Logarithmic Treewidth

Shinwoo An111Pohang University of Science and Technology, Korea. Email:
<EMAIL_ADDRESS>Eunjin Oh222Pohang University of Science and
Technology, Korea. Email<EMAIL_ADDRESS>Jie Xue333New York
University Shanghai, China. Email<EMAIL_ADDRESS>
###### Abstract

An outerstring graph is the intersection graph of curves lying inside a disk
with one endpoint on the boundary of the disk. We show that an outerstring
graph with $n$ vertices has treewidth $O(\alpha\log n)$, where $\alpha$
denotes the arboricity of the graph, with an almost matching lower bound of
$\Omega(\alpha\log(n/\alpha))$. As a corollary, we show that a $t$-biclique-
free outerstring graph has treewidth $O(t(\log t)\log n)$. This leads to
polynomial-time algorithms for most of the central NP-complete problems such
as Independent Set, Vertex Cover, Dominating Set, Feedback Vertex Set,
Coloring for sparse outerstring graphs. Also, we can obtain subexponential-
time (exact, parameterized, and approximation) algorithms for various NP-
complete problems such as Vertex Cover, Feedback Vertex Set and Cycle Packing
for (not necessarily sparse) outerstring graphs.

##  1 Introduction

The _intersection graph_ of a family $\mathcal{F}$ of geometric objects is the
graph $G=(V,E)$ such that every vertex of $G$ corresponds to an object of
$\mathcal{F}$, and two vertices of $G$ are connected by an edge if and only if
their corresponding objects intersect. In this case, $\mathcal{F}$ is called a
_geometric representation_ of $G$. Notice that a geometric representation of
an intersection graph is not necessarily unique. There are several popular
classes of intersection graphs such as string graphs, unit disk graphs, and
disk graphs. In the case that $\mathcal{F}$ is a family of curves in the
plane, its intersection graph is called a _string graph_. Similarly, the
intersection graph of a family of unit disks (or disk graphs) is called a
_unit disk graph_ (or a _disk graph_). Notice that a unit disk graph is a disk
graph, and a disk graph is a string graph444We can represent each disk as a
densely spiral-shaped string that covers the interior of the disk..

Geometric intersection graphs have been studied extensively as early as in the
1960s, motivated by the connection with integrated RC circuits [19, 44]. Most
NP-complete problems on general graphs remain NP-complete in geometric
intersection graphs (or even in unit disk graphs). However, recently, it is
known that lots of NP-complete problems can be solved in subexponential time
on geometric intersection graphs [3, 4, 5, 9, 16, 17, 30, 36, 40]. For
instance, Vertex Cover, 3-Coloring and Feedback Vertex Set can be solved in
$2^{O(n^{2/3}\text{polylog }n)}$ time for string graphs with $n$ vertices [9].
In the case of disk graphs and unit disk graphs, one can obtain even stronger
results. There are subexponential-time _parameterized_ algorithms for numerous
NP-complete problems in this case. For instance, one can solve Vertex Cover
and Feedback Vertex Set in $2^{O(\sqrt{k})}n^{O(1)}$ time for unit disk graphs
[4, 16], and in $2^{O(k^{c})}n^{O(1)}$ time for disk graphs [3, 36] for some
constant $c<1$, where $k$ denotes the output size.

All of the algorithms mentioned above use the fact that string graphs have
treewidth sublinear in the number of vertices if they do not have a large
clique (or biclique).555The definition of the treewidth is given in Section 2.
For a string graph $G$ with $n$ vertices that does not contain a biclique of
size $t$ has a balanced separator of size $O(\sqrt{t(\log t)n})$ [35], and
thus its treewidth is $O(\sqrt{t(\log t)n})$. For most central NP-complete
problems, there are $2^{O(tw)}n^{O(1)}$-time algorithms for any graphs of
treewidth $tw$. For subexponential-time algorithms for string graphs given in
[9], the authors produce several instances of _sparse_ string graphs using the
branching technique. Then they apply $2^{O(tw)}n^{O(1)}$-time algorithms to
the instances. The subexponential-time parameterized algorithms for unit disk
graphs and disk graphs mentioned above use similar approaches. Using
branching, they produce several instances of _sparse_ disk graphs. In this
case, using the sparsity and the geometric properties of disk graphs, they
show that the treewidth of the resulting disk graph depends only on the
parameter and the measure for the sparsity of the graph.

Motivated by these algorithmic applications, an optimal bound on the treewidth
of a sparse string graph has been studied extensively for the last two decades
[22, 35, 37, 38]. A $t$-biclique-subgraph-free ($K_{t,t}$-free) string graph
with $n$ vertices has treewidth $O_{t}(\sqrt{n})$, while a general (not
necessarily sparse) string graph with $m$ edges has treewidth $O(\sqrt{m})$.
These bounds are tight for string graphs [35]. One might hope to obtain a
better bound for a special subclass of string graphs, which might lead to
faster algorithms for central NP-hard problems. However, this bound is tight
even for sparse unit disk graphs and the intersection graph of axis-parallel
segments. In particular, a $\sqrt{n}\times\sqrt{n}$ grid is a unit disk graph
of treewidth $\Theta(\sqrt{n})$. Also, there is an axis-parallel segment graph
of treewidth $\Theta(\sqrt{n})$ which does not contain a $K_{2,2}$ as a
subgraph. See Figure 1.

Figure 1: (a) A $\sqrt{n}\times\sqrt{n}$ grid is a unit disk graph of
treewidth $\Theta(\sqrt{n})$. (b) A sparse axis-parallel segment graph of
treewidth $\Theta(\sqrt{n})$. It does not contain $K_{2,2}$ as a subgraph. The
horizontal segments form $\sqrt{n}$ rows, and each row consists of
$\Theta(\sqrt{n})$ horizontal segments.

In this paper, we focus on outerstring graphs. An _outerstring graph_ is the
intersection graph of curves lying inside a disk with one endpoint on the
boundary of the disk. Outerstring graphs have been studied for about 30 years
since they were introduced by Kratochvíl [33]. There are numerous works on the
combinatorial properties of outerstring graphs [7, 12, 23, 24, 27, 42], and
efficient algorithms for outerstring graphs [6, 10, 29]. Basically,
Recognition is NP-hard for outerstring graphs [33, 39], and all combinatorial
properties and algorithms of [6] are applicable to outerstring graphs without
explicitly provided geometric representation. On the other hand, the
algorithms presented in [10, 29] run in time polynomial in the complexity of a
geometric representation. Despite these efforts, we are not able to find any
(exact, parameterized, or approximation) polynomial-time algorithms for
central NP-hard problems specialized to outerstring graphs.

As the concept of the treewidth is a key to obtaining efficient algorithms for
geometric intersection graphs, a natural direction for this problem is to
analyze a tight bound on the treewidth of an outerstring graph. Fox and Pach
[23] showed that an outerstring graph with $m$ edges has treewidth
$O(\min\\{\Delta,\sqrt{m}\\})$, where $\Delta$ denotes the maximum degree of
the graph.666Precisely, they showed that an outerstring has a balanced
separator of size $O(\min\\{\Delta,\sqrt{m}\\})$. By [18], this implies that
the treewidth of an outerstring graph is $O(\min\\{\Delta,\sqrt{m}\\})$.
Moreover, they showed that this bound is tight for outerstring graphs as a
split graph containing a clique of size $\Theta(m)$ has treewidth $\Theta(m)$,
and the Cayley graph with vertex set $\mathbb{Z}_{n}$ such that any two
vertices of cyclic distance at most $\Delta/2$ are adjacent has treewidth
$\Theta(\Delta)$. A split graph and such a Cayley graph are all outerstring
graphs. Although these examples show that the bound of
$O(\min\\{\Delta,\sqrt{m}\\})$ is tight, these are dense graphs that contain a
clique of size $\Theta(\sqrt{m})$. Indeed, what we need for algorithmic
applications is a bound on the treewidth of sparse outerstring graphs, for
instance, $t$-biclique-free outerstring graphs. There is still room for the
improvement of the bound in the sparse regime.

#### Our results.

In this paper, we show that an outerstring graph $G$ has treewidth
$O(\alpha\log n)$, where $\alpha$ is the arboricity of $G$. The arboricity of
$G$ is defined as the maximum average degree of the subgraphs of $G$. Using
the previous structural results about outerstring graphs [24, 35], we show
that an outerstring graph which does not contain $K_{t,t}$ as a subgraph has
arboricity $O(t\log t)$. Thus our main result implies that a $t$-biclique-free
outerstring graph $G$ has treewidth $O(t(\log t)\log n)$. We emphasize that
all of our algorithmic applications mentioned below work even without a
geometric representation of an outerstring graph.

First, we can obtain polynomial-time algorithms for any problem that admits a
single-exponential-time algorithm parameterized by treewidth, including
Independent Set, Hamiltonian Cycle, Dominating Set, and Feedback Vertex Set,
for $t$-biclique-free outerstring graphs for a fixed constant $t$. All
algorithms but the algorithm for Independent set are the first polynomial-time
algorithms for these problems in $t$-biclique-free outerstring graphs.
Moreover, the algorithm for Independent set is the first polynomial-time
_robust_ algorithm that does not require the geometric representation of the
graph777Our algorithms for the other problems are also robust. There is an FPT
algorithm on Independent Set parameterized by the complexity of the geometric
representation of an outerstring graph [29]..

Our main result can be used for obtaining various algorithms for (possibly
dense) outerstring graphs. We design subexponential-time FPT algorithms for
Vertex Cover and Feedback Vertex Set on general outerstring graphs work in
$2^{O(\sqrt{k}\log^{2}k)}n^{O(1)}$ time, where $k$ is the solution size. It is
known that Vertex Cover can be solved in time polynomial in the complexity of
a geometric representation of an outerstring graph [6, 10, 29]. But the
complexity of a geometric representation of an outerstring graph can be
exponential in the number of vertices [7]. For string graphs, Vertex Cover can
be solved in $2^{O(k^{2/3})}n^{O(1)}$ time [9]. On the other hand, Feedback
Vertex Set can be solved in $2^{O(n^{2/3})}$ time for string graphs, and no
subexponential-time algorithm parameterized by the solution size was known for
this problem on string graphs and outerstring graphs prior to our work.

In addition, we can obtain (non-parameterized) $2^{O(\sqrt{n}\log^{2}n)}$-time
algorithms for Maximum Induced Matching and List 3-Coloring on (general)
outerstring graphs. These improve the algorithms for these problems running in
$2^{O(n^{2/3})}$ time [9]. (But the algorithms in [9] also work for string
graphs.) Finally, we can design a 4-approximation algorithm for Cycle Packing
works in $n^{O(\log\log n)}$ time. Prior to this work, neither approximation
nor parameterized algorithms for Cycle Packing on outerstring graphs were
known. For general graphs, Cycle Packing admits an $O(\sqrt{\log
n})$-approximation algorithm [34], and it is quasi-NP-hard to approximate
within a factor of $O(\log^{1/2-\varepsilon}n)$ for any $\varepsilon>0$ [25].

We believe that our result can serve as a starting point for designing
efficient algorithms for outerstring graphs. Apart from these applications, we
also believe that the main result itself is interesting. Only a few natural
classes of graphs such as sparse $O_{k}$-free graphs, even-hole-free graphs of
bounded degree, even-hole-free graphs of bounded clique number, and (theta,
triangle)-free graphs are known to have logarithmic treewidth [1, 2, 8, 13].

#### Related work.

Outerstring graphs were introduced by [33]. The class of outerstring graphs is
a broad subclass of string graphs, which includes split graphs (graphs whose
vertex set can be decomposed into a clique and an independent set),
incomparability graphs (graphs representing the incomparability of elements in
a partially ordered set), circle graphs (intersection graphs of chords of a
circle), and ray graphs (intersection graph of rays starting from the
$x$-axis). Moreover, several real-world problems such as PCP routing and
railway dispatching can be stated in terms of outerstring graphs [20, 31].

Lots of NP-hard problems remain NP-hard on outerstring graphs. For instance,
Minimum Clique Cover, Coloring, and Dominating Set, and Hamiltonian Cycle are
NP-hard even on circle graphs [15, 26, 28]. Also, Maximum Clique is NP-hard
even on ray graphs [11]. Recognition is also NP-hard for outerstring graphs
[33, 39]. On the other hand, Independent Set can be solved in time polynomial
in the complexity of a geometric representation of an outerstring graph if its
geometric representation is given [29]. However, there is an outerstring graph
that does not admit geometric representation of polynomial complexity [7]. It
is still unknown if Independent Set can be solved in time polynomial in the
number of vertices in the case that geometric representation is not given. All
missing proofs and details can be found in the Appendices.

##  2 Preliminaries

A _curve_ is the _image_ of a continuous function from a unit interval to
$\mathbb{R}^{2}$. Under this definition, note that the union of pairwise
intersecting curves is also a curve. A simple closed curve $C$ partitions the
plane into two disjoint regions. We call the bounded region the _interior_ of
$C$ and denote it by $\textsf{int}(C)$. We say a collection $\Gamma$ of curves
are _grounded_ on a simple closed curve $C$ if every curve is contained in the
closure of $\textsf{int}(C)$, and one of its endpoints is contained in $C$. In
this case, we say $C$ is a _ground_ of the collection of curves. Also, for a
curve of $\Gamma$, one of its endpoints lying on $C$ is called a _ground
point_ of the curve. For an index set $I=\\{1,2,3\ldots\\}$ and a collection
$\Gamma=\\{\gamma_{i}\\}_{i\in I}$ of curves grounded on $C$, we say a graph
$G$ as an _outerstring graph_ if it is identical to the intersection graph of
$\Gamma$. In this case, we say $\Gamma$ is a _geometric representation_ of
$G$. Throughout this paper, we assume the general position assumption that no
three curves of $\Gamma$ intersect at a single point, and two curves of
$\Gamma$ cross at their intersection points. These assumptions can be achieved
by slightly adjusting the curves without changing the intersection graph. See
Figure 2. In the following, to distinguish the curves of $\Gamma$ from other
curves not necessarily in $\Gamma$, we call the curves of $\Gamma$ the
_strings_ of $\Gamma$.

Figure 2: We can always assume the general position assumption.

An induced subgraph of an outerstring graph is also an outerstring graph as an
outerstring graph is a geometric intersection graph. Similarly, an _induced
minor_ of an outerstring graph is also an outerstring graph although a minor
of an outerstring graph is not necessarily an outerstring graph. An induced
minor of a graph $G$ is a graph that can be obtained from $G$ by deleting
vertices and contracting edges. Whenever we deal with an induced subgraph of
$G$, we assume that its underlying geometric representation is a subset of
$\Gamma$. Similarly, the underlying geometric representation of an induced
minor of $G$ is a set of curves obtained from $\Gamma$ by removing curves and
taking the union of curves. In the case that several curves are merged into a
single curve, we choose the ground point of any of them as the ground point of
the new curve.

Let $G$ be the intersection graph of a collection $\Gamma$ of grounded curves.
For a subset $\Gamma^{\prime}$ of $\Gamma$, the intersection graph of
$\Gamma^{\prime}$ is an induced subgraph of $G$ by curves in
$\Gamma^{\prime}$. We use $G[\Gamma^{\prime}]$ to denote the intersection
graph of $\Gamma^{\prime}$. Recall that a vertex of $G$ corresponds to a curve
of $\Gamma$. For any subset $U$ of the vertex set of $G$, the _geometric
representation_ of $U$ is defined as the union of the curves corresponding to
the vertices of $U$.

#### Treewidth and brambles.

A key notion we use in this paper is the _treewidth_ of a graph, which is
defined as follows. A _tree decomposition_ of an undirected graph $G=(V,E)$ is
defined as a pair $(T,\beta)$, where $T$ is a tree and $\beta$ is a mapping
from nodes of $T$ to subsets of $V$ (we call $\beta(t)$ of $t\in T$ bag) with
the following conditions.

  * •

For any vertex $u\in V$, there is at least one bag which contains $u$.

  * •

For any edge $(u,v)\in E$, there is at least one bag which contains both $u$
and $v$.

  * •

For any vertex $u\in V$, the nodes of $T$ containing $u$ in their bags are
connected in $T$.

The width of $(T,\beta)$ is defined as the size of its largest bag minus one,
and the treewidth of $G$ is the minimum width of a tree decomposition of $G$.
Notice that the treewidth of $K_{t,t}$ is $\Theta(t)$, and thus any graph
containing $K_{t,t}$ as a subgraph has treewidth $\Omega(t)$.

Although our main focus is to analyze a tight bound of the treewidth of an
outerstring graph, we do not use this definition directly. Instead, we use an
alternative characterization of treewidth using the notion of _brambles_. A
_bramble_ $\mathcal{X}$ of a graph $G$ is a family of connected subgraphs of
$G$ that all touch each other. Here, we say a subgraph $X$ of $G$ _touches_ a
subgraph $X^{\prime}$ of $G$ if there is a common vertex in $V(X)\cap
V(X^{\prime})$, or there is an edge with one endpoint in $V(X)$ and one
endpoint in $V(X^{\prime})$. A subset $Y$ of $V(G)$ is a _hitting set_ of the
bramble if $V(X)\cap V(Y)$ contains a common vertex for each subgraph $X$ of
$\mathcal{X}$. Then the _order_ of bramble is defined as the smallest size of
a hitting set of the bramble. Let $\mathcal{X}$ be a bramble of $G$ of maximum
order. Then it is known that the order of $\mathcal{X}$ is exactly the
treewidth of $G$ plus one [14].

#### Sparse outerstring graphs.

Our main result focuses on _sparse_ outerstring graphs. There are several
different definitions of the sparsity of a graph. As the measure for the
sparsity of a graph, we mainly use the _arboricity_ , which is defined as the
minimum number of forests into which its edges can be partitioned.
Equivalently, it is half of the maximum average degree of the subgraphs of the
graph.

Other notions for measuring the sparsity of graphs are _biclique-freeness_ and
_degeneracy_. For an integer $t$, we say a graph is _$t$ -biclique-free_ if it
does not contain a (not necessarily induced) subgraph isomorphic to $K_{t,t}$.
We say $t$ as the _size_ of the biclique $K_{t,t}$. We say a graph $G$ is _t-
degenerate_ if every subgraph of $G$ has a vertex of degree at most $t$. In
the case of outerstring graphs, all concepts mentioned above are equivalent up
to log factors as we will see in Lemma 1. Moreover, the bounds stated in the
following lemma are all tight up to constant factors. For the first two
statements, as mentioned in [22], the construction of [21, 41] shows that
there are $t$-biclique-free incomparability graphs with $n$ vertices and
$\Theta((t\log t)n)$ edges. Moreover, every vertex in this graph has degree
$\Omega(t\log t)$. It is known that an incomparability graph is an outerstring
graph [23], and thus the first two bounds in the following lemma are tight.
The construction in Section 4 gives a tight lower bound for the last two
cases.

######  Lemma 1.

For an outerstring graph $G$, the following statements hold.

  * •

If $G$ is $t$-biclique-free, then $G$ is $O(t\log t)$-degenerate.

  * •

If $G$ is $t$-biclique-free, $G$ has arboricity $O(t\log t)$.

  * •

If $G$ has arboricity $t$, then $G$ is $2t$-biclique-free.

  * •

If $G$ is $t$-degenerate, then $G$ is $2t$-biclique-free.

###### Proof.

For the first two statements, assume that $G$ is $t$-biclique-free. Consider
an induced subgraph $H$ of $G$. Note that $H$ is also a $t$-biclique-free
outerstring graph. By [24] and [35], the number of edges of $H$ is $O(t(\log
t)|V(H)|)$. Therefore, the average degree of $H$ is $O(t\log t)$, and thus $H$
has a vertex of degree $O(t\log t)$. This implies that $G$ is $O(t\log
t)$-degenerate, and it has arboricity $O(t\log t)$.

Now we consider the contrapositives of the last two statements. If $G$
contains a subgraph $H$ isomorphic to $K_{2t,2t}$, the average degree of $H$
is large than $t$. Therefore, $G$ has arboricity greater than $t$, and thus
the third statement holds. Moreover, it does not contain a vertex of degree at
most $t$, and thus $G$ is not $t$-degenerate. Therefore, the lemma holds. ∎

##  3 Upper Bound on the Treewidth of an Outerstring Graph

In this section, we show that an outerstring graph $G$ has treewidth
$O(\alpha\log n)$, where $\alpha$ denotes the arboricity of $G$. Let $\Gamma$
be a geometric representation of $G$, which is a collection of curves grounded
on a ground $C$. A key of our proof lies in defining a new notion, called the
_crossing-level_ , which is a variant of the level in an arrangement. The
_arrangement_ of $\Gamma$ is the subdivision of $\textsf{int}(C)$ formed by
the curves of $\Gamma$ into vertices, edges, and faces. Note that the degree
of each vertex of the arrangement is at most four by the general position
assumption. For an illustration of the crossing-level, see Figure 3(a).

######  Definition 1.

For a point $p$ in $\textsf{int}(C)$, the _crossing-level_ of $p$ in $\Gamma$
is the smallest number of different strings that one must cross to reach the
ground from $p$.888In the case that $p$ lies on a curve of $\Gamma$, the
starting point $p$ is not considered as a crossing point. The _maximum
crossing-level_ of $\Gamma$ is the maximum of the crossing-levels of all
points of $\textsf{int}(C)$.

Our proof consists of three steps. We first show that the maximum crossing-
level of $\Gamma$ is at most $3\alpha\log n$. In the second step, we show that
an outerstring graph $G$ contains a clique minor of size $\Omega(tw)$, where
$tw$ denotes the treewidth of $G$. Then in the third step, using the result of
the second step, we show that the maximum crossing-level of $\Gamma$ is at
least $\Omega(tw)$. By combining the two claims, we conclude that the
treewidth of $G$ is $O(\alpha\log n)$.

###  3.1 Step 1. Upper Bound on the Maximum Crossing-Level

In this subsection, we show that the maximum crossing-level of $\Gamma$ is
$O(\alpha\log n)$. We use the following observation which immediately comes
from the definition of the crossing-level.

######  Observation 1.

Any two points in the same face of the arrangement of $\Gamma$ have the same
crossing-level. Also, any two points of the same edge of the arrangement of
$\Gamma$ have the same crossing-level unless one of the points is an endpoint
of the edge.

Let $p$ be a point of $\textsf{int}(C)$ that achieves the maximum crossing-
level of $\Gamma$, and let $r$ be the crossing-level of $p$. For each index
$0\leq i\leq r$, let $U_{i}$ be the set of points in $\textsf{int}(C)$ of
crossing-level at least $i$. Clearly, $U_{0}$ coincides with
$\textsf{int}(C)$. Notice that $U_{i}$ contains $p$ for all indices $0\leq
i\leq r$. Let $R_{i}$ be the boundary of the connected component of $U_{i}$
containing $p$. Due to Observation 1, $R_{i}$ is a Jordan curve consisting of
parts of strings of $\Gamma$ for $i>1$, and $R_{0}$ coincides with the ground.
See also Figure 3(a). Then let $\Gamma_{i}$ be the set of strings of $\Gamma$
intersecting $R_{i}$. Since $R_{0},R_{1},\ldots R_{r}$ are concentric,
$\Gamma_{r}\subseteq\Gamma_{r-1}\subseteq\ldots\subseteq\Gamma_{0}=\Gamma$. In
the following lemma, we show that the size of $\Gamma_{i}$ is (almost)
geometrically decreasing. Since $|\Gamma_{0}|=n$, this gives an upper bound of
$r$ in terms of input size $n$ and arboricity $\alpha$.

Figure 3: (a) The red region depicts $U_{2}$. Jordan curve $R_{2}$ consists of
the parts of four strings. (b) All black strings are contained in both
$\Gamma_{i}$ and $\Gamma_{i-4\alpha}$, and the red string is contained in
$\Gamma_{i}$ only.

######  Lemma 2.

For each index $i\geq 4\alpha$, where $\alpha$ is the arboricity of $G$, we
have $2|\Gamma_{i}|\leq|\Gamma_{i-4\alpha}|$.

###### Proof.

We consider the region bounded by $R_{i}$ and $R_{i-4\alpha}$. See Figure
3(b). Note that a string of $\Gamma_{i}$ intersects both $R_{i}$ and
$R_{i-4\alpha}$ by definition. Each string $\gamma$ of $\Gamma_{i}$ is
intersected by at least $4\alpha$ _different_ strings of $\Gamma$ in the
region bounded by $R_{i}$ and $R_{i-4\alpha}$. Otherwise, the first
intersection point of $\gamma$ with $R_{i}$ from the ground point of $\gamma$
would have the crossing-level less than $i$, which contradicts the fact that
this intersection point lies on $R_{i}$. Also, observe that a string of
$\Gamma$ intersecting $\gamma$ in the region bounded by $R_{i}$ and
$R_{i-4\alpha}$ is contained in $\Gamma_{i-4\alpha}$. Let $\mathcal{P}$ be the
set of all pairs $(\gamma,\gamma^{\prime})$ such that a string $\gamma$ of
$\Gamma_{i}$ is intersected by a string $\gamma^{\prime}$ of
$\Gamma_{i-4\alpha}$. Due to the previous observation, we have
$|\mathcal{P}|\geq 4\alpha\cdot|\Gamma_{i}|$.

Now we show that $|\mathcal{P}|\leq 2\alpha\cdot|\Gamma_{i-4\alpha}|$. To see
this, observe that a pair $(\gamma,\gamma^{\prime})$ of $\mathcal{P}$
corresponds to an edge of $G[\Gamma_{i-4\alpha}]$. This is because
$\gamma\in\Gamma_{i}\subseteq\Gamma_{i-4\alpha}$, and
$\gamma^{\prime}\in\Gamma_{i-4\alpha}$. Moreover, by construction, an edge of
$G[\Gamma_{i-4\alpha}]$ corresponds to at most two different pairs of
$\mathcal{P}$. Here, notice that two strings of $\Gamma$ may intersect more
than once, but in the construction of $\mathcal{P}$, for all pairs of
$\mathcal{P}$ whose first elements are the same, there second elements must be
distinct. Therefore, an edge of $G[\Gamma_{i-4\alpha}]$ corresponds to at most
two pairs of $\mathcal{P}$. Since the arboricity of $G$ is $\alpha$, any
subgraph $H$ of $G$ has at most $\alpha\cdot|V(H)|$ edges. Then the number of
edges of $G[\Gamma_{i-4\alpha}]$ is at most $\alpha\cdot|\Gamma_{i-4\alpha}|$.
Therefore, we have $|\mathcal{P}|\leq 2\alpha\cdot|\Gamma_{i-4\alpha}|$, and
thus the lemma holds. ∎

######  Lemma 3.

The maximum crossing-level of $\Gamma$ is at most $O(\alpha\log n)$.

###### Proof.

For the maximum crossing-level $r$ of $\Gamma$, we have
$\Gamma_{r}\neq\emptyset$. By Lemma 2, $2|\Gamma_{i}|\leq|\Gamma_{i-4\alpha}|$
for all indices $i\geq 4\alpha$. Therefore, $2^{\lfloor
r/(4\alpha)\rfloor}\cdot|\Gamma_{r}|\leq|\Gamma_{0}|=n$. Thus, $r\leq
4\alpha(\log n+1)$. ∎

###  3.2 Step 2. Existence of a Clique Minor of Size $tw$

In this subsection, we show that an outerstring graph has a clique minor of
size $\Omega(tw)$. A _clique minor_ of $G$ is a clique formed from $G$ by
deleting edges, vertices, and contracting edges. Note that a general “string"
graph may not contain a clique minor of size $\Omega(tw)$. For instance, an
$n$ by $n$ rectangular grid graph is a string graph since it is a planar graph
and all planar graphs are string graphs [43]. The treewidth of this graph is
$\sqrt{n}$ but it does not have a size-five clique minor. For any two disjoint
sets $A$ and $B$ of vertices of a general graph $H$ with $|A|=|B|$, an
$(A,B)$-_linkage_ of $H$ is defined as a set of $|A|$ vertex-disjoint paths
connecting every vertex of $A$ and every vertex of $B$. See Figure 4(a). We
say a set $Q$ of vertices of $H$ is _well-linked_ if for any two disjoint
subsets $A$ and $B$ of $Q$ with $|A|=|B|$, there is an $(A,B)$-linkage of $H$.
The following lemma is frequently used in literature without formal proof, but
to make our paper self-contained, we add a short proof in Appendix
LABEL:apd:sparsity.

######  Lemma 4 (Folklore).

Any graph $H$ of treewidth $tw$ has a well-linked set of size $\Theta(tw)$.

###### Proof.

Let $\mathcal{X}$ be a bramble of $H$ of maximum order. Recall that the order
of $\mathcal{X}$ is $tw+1$ by the characterization of the treewidth mentioned
in Section 2. Let $Q$ be the smallest hitting set of $\mathcal{X}$ with
$|Q|=tw+1$. We show that $Q$ is well-linked. If this is not the case, there is
a witness $(A,B)$ for two disjoint sets $A$ and $B$ of $Q$ with $|A|=|B|$.
That is, the maximum number of vertex-disjoint paths between $A$ and $B$ is
less than $|A|$. Among all such witnesses $(A,B)$, we choose the one that
minimizes $|A|$. Then no two vertices, one from $A$ and one from $B$, are
adjacent. Then by Menger’s theorem, there is a vertex set $X$ of size less
than $|A|$ such that every path between $A$ and $B$ intersects $X$.

We show that $X\cup(Q\setminus A)$ or $X\cup(Q\setminus B)$ is a hitting set
of $\mathcal{X}$, which contradicts that $H$ is the smallest hitting set of
$\mathcal{X}$. To show this, observe that for an element $X$ of $\mathcal{X}$,
either $X$ intersects $X$, or it is fully contained in a connected component
of $G-X$. The elements of $\mathcal{X}$ of the first type are hit by $X$, and
thus it is hit by both $X\cup(H\setminus A)$ and $X\cup(H\setminus B)$. The
elements of $\mathcal{X}$ of the second type must be contained in the same
connected component of $G-X$ as they touch each other. Then either
$(H\setminus A)$ or $(H\setminus A)$ hits all such elements. Therefore, either
$X\cup(H\setminus A)$ or $X\cup(H\setminus B)$ is a hitting set of
$\mathcal{X}$, and thus the lemma holds. ∎

Let $X$ be a well-linked set of $G$ of size $\Theta(tw)$. Without loss of
generality, we may assume that the size of $X$ is a power of four. Assume
further that they are sorted along $C$ with respect to the ground points of
their corresponding curves of $\Gamma$. Then we partition $X$ into four equal-
sized subsets $X_{1},X_{2},X_{3},X_{4}$ so that each subset consists of
consecutive vertices of $X$ with respect to their corresponding ground points.
See Figure 4(b). By the well-linkedness of $X$, there are an
$(X_{1},X_{3})$-linkage $\mathcal{P}_{h}$ and an $(X_{2},X_{4})$-linkage
$\mathcal{P}_{v}$ of $G$. Observe that if all vertices in the paths of
$\mathcal{P}_{h}\cup\mathcal{P}_{v}$ are distinct, the geometric
representation of every path of $\mathcal{P}_{h}$ crosses the geometric
representation of every path of $\mathcal{P}_{v}$. Then we simply pair each
path of $\mathcal{P}_{h}$ with a path of $\mathcal{P}_{v}$ and then contract
all the edges in the two paths to form a single vertex. In this way, we have
$\Omega(tw)$ contracted vertices, which form a clique. However, a vertex in a
path of $\mathcal{P}_{h}$ might appear in a path of $\mathcal{P}_{v}$. To
handle this case, we choose new sets
$\tilde{X}_{1},\tilde{X}_{2},\tilde{X}_{3}$ and $\tilde{X}_{4}$ using
$X_{1},X_{2},X_{3},X_{4}$ as follows.

Figure 4: (a) Illustration of an $(A,B)$-linkage. (b) Partition of $X$ into
$X_{1},X_{2},X_{3}$ and $X_{4}$. (c) The case that $C_{\pi}\subseteq
C_{\pi^{\prime}}$. An internal vertex of $\pi^{\prime}$ (corresponding to the
pink dotted curve) intersects the geometric representation of $\pi$.

#### Construction of new sets.

Recall that the sizes of $X_{i}$’s are the same. Let $k$ be the size of these
sets. For $i\in\\{1,2,3,4\\}$, let $C_{i}$ be the minimal subarc of $C$
containing the ground points of all curves corresponding to $X_{i}$ but not
containing the ground point of any curve corresponding to a vertex of
$X\setminus X_{i}$. See Figure 4(b). Notice that $C_{1},C_{2},C_{3}$ and
$C_{4}$ are pairwise disjoint. We say two vertex sets $A$ and $B$ of $G$ are
_separated_ by $C_{1}$ and $C_{3}$ if the ground points of the curves
corresponding to the vertices of $A$ are contained in one component of
$C\setminus\\{C_{1},C_{3}\\}$, and the ground points of the curves
corresponding to the vertices of $B$ are contained in the other component of
$C\setminus\\{C_{1},C_{3}\\}$. An $(A,B)$-linkage of $G$ is called a
_shortest_ $(A,B)$-linkage if its total length is minimum over all $(A,B)$
linkages of $G$. Here, the length of a path is defined as the number of
vertices in the path.

Among all pairs $(X_{2}^{\prime},X_{4}^{\prime})$ of disjoint vertex sets of
$V(G)\setminus(X_{1}\cup X_{3})$ separated by $C_{1}$ and $C_{3}$ with
$|X_{2}^{\prime}|=|X_{4}^{\prime}|=k$, we choose the one that minimizes the
total length of the shortest $(X_{2}^{\prime},X_{4}^{\prime})$-linkage. Notice
that such a pair always exists since $(X_{2},X_{4})$ satisfies the conditions
for being a candidate. Let $\tilde{X}_{2}$ and $\tilde{X}_{4}$ be the
resulting sets. Then let $\tilde{C}_{2}$ (and $\tilde{C}_{4}$) be the minimal
subarc of $C$ containing the ground points of all curves corresponding to
$\tilde{X}_{2}$ (and $\tilde{X}_{4}$) and not containing any other curve of
$\tilde{X}_{4}$ (and $\tilde{X}_{2}$). Then among all pairs
$(X_{1}^{\prime},X_{3}^{\prime})$ of disjoint vertex sets of
$V(G)\setminus(\tilde{X}_{2}\cup\tilde{X}_{4})$ separated by $\tilde{C}_{2}$
and $\tilde{C}_{4}$ with $|X_{1}^{\prime}|=|X_{3}^{\prime}|=k$, we choose the
one that minimizes the total length of the shortest
$(X_{1}^{\prime},X_{3}^{\prime})$-linkage. Notice that such a pair always
exists since $(X_{1},X_{3})$ satisfies the conditions for being a candidate.
Let $\tilde{X}_{1}$ and $\tilde{X}_{3}$ be the resulting sets. By
construction, all resulting sets are pairwise disjoint.

Then a shortest $(\tilde{X}_{1},\tilde{X}_{3})$-linkage satisfies the
following property. By changing the roles of $\tilde{C}_{2}\cup\tilde{C}_{4}$
and $C_{1}\cup C_{3}$, we can show that the following also holds for a
shortest $(\tilde{X}_{2},\tilde{X}_{4})$-linkage.

######  Lemma 5.

Let $\mathcal{P}$ be a shortest $(\tilde{X}_{1},\tilde{X}_{3})$-linkage. Then
the set of paths of $\mathcal{P}$ of length at least three can be decomposed
into two subsets such that for any two paths of $\mathcal{P}$ in the same
subset, their geometric representations intersect.

###### Proof.

Let $\pi$ be a path of $\mathcal{P}$ of length at least three. For any
internal vertex of $\pi$, its corresponding curve of $\Gamma$ has the ground
point on $\tilde{C}_{2}\cup\tilde{C}_{4}$. Otherwise, we partition $\pi$ into
two subpaths $\pi_{1}$ and $\pi_{2}$ whose common endpoint $v$ lies outside of
$\tilde{C}_{2}\cup\tilde{C}_{4}$. Assume, without loss of generality, it lies
the subarc of $C\setminus(\tilde{C}_{2}\cup\tilde{C}_{4})$ containing $C_{1}$.
In this case, the other endpoint of $\pi_{i}$($i$=1 or 2) lies in the other
subarc of $C\setminus(\tilde{C}_{2}\cup\tilde{C}_{4})$. Then we simply replace
$\pi$ with $\pi_{i}$. In this way, we can decrease the total length of paths
of $\mathcal{P}$ without any conditions for $\mathcal{P}$. This contradicts
the choice of $\mathcal{P}$. Then we decompose the paths of $\mathcal{P}$ of
length at least three into two subsets $\mathcal{P}^{\prime}$ and
$\mathcal{P}^{\prime\prime}$ such that $\mathcal{P}^{\prime}$ consists of all
paths of $\mathcal{P}$ of length at least three containing at least one
internal vertex whose corresponding curve has its ground point on
$\tilde{C}_{2}$, and $\mathcal{P}^{\prime\prime}$ consists of all paths of
$\mathcal{P}$ of length at least three not contained in
$\mathcal{P}^{\prime}$.

Now we show that for any two paths $\pi$ and $\pi^{\prime}$ of
$\mathcal{P}^{\prime}$, their geometric representations intersect. The other
case can be handled symmetrically by changing the roles of $\tilde{C}_{2}$ and
$\tilde{C}_{4}$. Let $C_{\pi}$ be the subarc of $C$ containing $\tilde{C}_{2}$
lying between the ground points of the strings corresponding to the endpoints
of $\pi$. See Figure 4(c). Similarly, let $C_{\pi^{\prime}}$ be the subarc of
$C$ containing $\tilde{C}_{2}$ lying between the ground point of the strings
corresponding to the endpoints of $\pi$. If neither $C_{\pi}$ nor
$C_{\pi^{\prime}}$ contains the other, $\pi$ and $\pi^{\prime}$ cross because
the geometric representation of $\pi$ (and $\pi^{\prime}$) is connected. If
this is not the case, without loss of generality, assume that $C_{\pi}$ is
contained in $C_{\pi^{\prime}}$. Since $\pi^{\prime}$ has an internal vertex
whose corresponding string has its ground point on $\tilde{C}_{2}$, the
geometric representation of $\pi$ must intersect the string. See the pink
dotted curve in Figure 4(c). Therefore, the lemma holds. ∎

Figure 5: (a) Illustration of $\tilde{X}_{1},\tilde{X}_{2},\tilde{X}_{3}$ and
$\tilde{X}_{4}$. (b) Illustration of length-two paths of $\mathcal{P}_{v}$ and
$\mathcal{P}_{h}$. Two geometric representations of two pairs of paths of
$\mathcal{P}_{h}$ and $\mathcal{P}_{v}$ intersect.

Now we are ready to show that $G$ has a clique minor of size $\Omega(tw)$.
Recall that $\tilde{X}_{i}$’s have size $k=\Omega(tw)$. Let $\mathcal{P}_{v}$
be a shortest $(\tilde{X}_{1},\tilde{X}_{3})$-linkage, and $\mathcal{P}_{h}$
be a shortest $(\tilde{X}_{2},\tilde{X}_{4})$-linkage. If $\mathcal{P}_{v}$
(or $\mathcal{P}_{h}$) contains $k/2$ paths of length at least three, then we
are done. To see this, observe that $\mathcal{P}_{v}$ (or $\mathcal{P}_{h}$)
contains at least $k/4$ paths whose geometric representations intersect by
Lemma 5. For each such path, we contract all edges in the path into a single
vertex. Then at least $k/4$ vertices form a clique, and thus $G$ has a clique
minor of size $k/4$.

Thus we assume each of $\mathcal{P}_{v}$ and $\mathcal{P}_{h}$ contains at
least $k/2$ paths of length _at most_ two. Recall that
$\tilde{X}_{i}\cap\tilde{X}_{j}=\emptyset$ for any two distinct indices
$i,j\in\\{1,2,3,4\\}$. This implies that every such path of $\mathcal{P}_{v}$
and $\mathcal{P}_{h}$ has length _exactly_ two. Moreover, the paths of
$\mathcal{P}_{v}\cup\mathcal{P}_{h}$ of length exactly two are pairwise
vertex-disjoint since $\tilde{X}_{i}\cap\tilde{X}_{j}=\emptyset$. Since the
geometric representation of every path of $\mathcal{P}_{h}$ crosses the
geometric representation of every path of $\mathcal{P}_{v}$, we pair each path
of $\mathcal{P}_{h}$ with a path of $\mathcal{P}_{v}$ and then contract all
the edges in the two paths to form a single vertex. In this way, we have $k/2$
contracted vertices, which form a clique. See Figure 5. Therefore, in any
case, $G$ has a clique minor of size $k/2=\Omega(tw)$.

###  3.3 Step 3. Lower Bound on the Maximum Crossing-Level

As the third step, we show that the maximum crossing-level of $\Gamma$ is
$\Omega(tw)$. First, we reduce the general case to the case that $\Gamma$
consists of _double-grounded circularly ordered curves_ , and then we analyze
the maximum crossing-level of $\Gamma$ in this case. A _double-grounded_ curve
is a curve having both endpoints on $C$. We say that double-grounded curves
$\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$ are _circularly ordered_ if
$x_{1},x_{2},\ldots,x_{k},y_{1},y_{2},\ldots,y_{k-1}$ and $y_{k}$ lie on $C$
in the counterclockwise order, where $x_{i}$ and $y_{i}$ denote two endpoints
of $\gamma_{i}$ for $i=1,\ldots,k$. See Figure 6(a).

Figure 6: (a) Illustration of double-grounded circularly ordered curves. The
colored region is $h_{2}$. (b-c) Illustrates $P_{1}$ (black curve) and $P_{2}$
(red curve). The crossing-level of $p$ is at least $k/2$.

#### Reduction to the double-grounded circularly ordered case.

Let $k$ be the largest integer such that $G$ has a clique minor of size $4k$.
Notice that $k=\Omega(tw)$ by Section 3.2. Then $G$ has a _model_ $\mu$ of
$K_{4k}$, that is, there is a function $\mu$ that maps the vertices of
$K_{4k}$ to vertex-disjoint connected subgraphs of $G$ such that, for any two
vertices $u$ and $v$ of $K_{k}$, $\mu(u)$ and $\mu(v)$ are adjacent in $G$. In
other words, the edges of $\mu(v)$ are contracted into $v$ in the construction
of the clique minor of $G$ of size $k$.

For a vertex $v$ of $K_{4k}$, recall that the geometric representation of $v$
is defined as the union of the strings of $\Gamma$ corresponding to the
vertices of $\mu(v)$. We choose an arbitrary one as its ground point of $v$
(and its geometric representation). Let $\langle
v_{1},v_{2},\ldots,v_{4k}\rangle$ be the sequence of vertices of $K_{4k}$
sorted with respect to their ground points along $C$ in the counterclockwise
order. We pair a vertex $v_{i}$ in the first half of the sequence with
$v_{i+2k}$, and then find a curve in the union of their geometric
representations. More specifically, for each index $i$ with $i=1,\ldots,2k$,
consider the union of the geometric representations of $v_{i}$ and $v_{i+2k}$.
Notice that the union consists of a single connected component since $v_{i}$
and $v_{i+2k}$ are adjacent in $K_{4k}$. Let $x_{i}$ be the ground point of
$v_{i}$, and let $y_{i}$ be the ground point of $v_{i+2k}$. Then the union
contains a curve with endpoints $x_{i}$ and $y_{i}$. Let $\gamma_{i}$ be a
curve between $x_{i}$ and $y_{i}$ contained in the union. By construction,
$\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}$ are doubly-grounded circularly
ordered curves. Due to the following lemma, it is sufficient to show that the
maximum crossing-level of $k$ double-grounded circularly ordered curves is
$\Omega(k)$.

######  Lemma 6.

The max crossing-level of $\Gamma$ is at least the max crossing-level of
$\\{\gamma_{1},\ldots,\gamma_{2k}\\}$.

###### Proof.

Let $q$ be a point in $\textsf{int}(C)$, and let $\ell(q)$ be the crossing-
level of $q$ in $\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}\\}$. We show that
the crossing-level of $q$ in $\Gamma$ is at least $\ell(q)$, which implies the
lemma. Consider a curve $\pi$ connecting $q$ and $C$. The number of curves of
$\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}\\}$ intersected by $\pi$ is at
least $\ell(q)$. By the construction of
$\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}\\}$, for any point in
$\gamma_{i}$ and any point in $\gamma_{j}$ with $i\neq j$, they come from
different strings of $\Gamma$. Therefore, the number of strings of $\Gamma$
intersected by $\pi$ is at least $\ell(q)$, and thus the lemma holds. ∎

#### Analysis of the double-grounded circularly ordered case.

In the following, we focus on the set $\\{\gamma_{1},\ldots,\gamma_{2k}\\}$ of
double-grounded circularly ordered curves along $C$. To make the description
easier, we assume that $k$ is even. We give a direction to each path
$\gamma_{i}$ from $x_{i}$ to $y_{i}$. Then every edge of the arrangement of
$\\{\gamma_{1},\ldots,\gamma_{2k}\\}$ has its direction. By the general
position assumption, every vertex of the arrangement has two incoming arcs and
two outgoing arcs. Then $\gamma_{i}$ subdivides $\textsf{int}(C)$ into two
regions. The (closed) region lying locally to the right of $\gamma_{i}$ is
denoted by $h_{i}$. See Figure 6(a). Let $H_{1}=\\{h_{1},h_{2},\ldots
h_{k}\\}$ and $H_{2}=\\{h_{k+1},h_{k+2},\ldots,h_{2k}\\}$. Let $P_{i}$ be the
set of points contained in exactly $k/2$ regions of $H_{i}$ and lying on the
boundary curves of the regions of $H_{i}$ for $i=1,2$. Then $P_{i}$ forms a
simple curve, but in the following, we prove the weaker property that $P_{i}$
_contains_ a curve as it is sufficient for our purpose.

######  Lemma 7.

The set $P_{i}$ contains a simple curve connecting two points on $C$ for
$i=1,2$.

###### Proof.

We prove this for $P_{1}$ only. The other case can be handled similarly. We
traverse the arrangement of the curves of $\\{\gamma_{1},\ldots,\gamma_{k}\\}$
along a simple curve as follows. Starting from $x_{k/2}$, we move along
$\gamma_{k/2}$ until we reach a vertex of the arrangement. Whenever we meet a
vertex of the arrangement, this vertex is an intersection point between the
curve we are traversing and another curve in
$\\{\gamma_{1},\ldots,\gamma_{k}\\}$. Then we follow the outgoing arc of the
vertex lying on the new curve. We repeat this until we reach a point of $C$.
Let $\rho$ be the set of points we have visited in this way. We claim that
$\rho$ is contained in $P_{i}$, and it is a simple curve, which implies the
lemma.

We first show that each (directed) arc of $\rho$ is contained in $P_{i}$. As
$x_{k/2}$ is contained in exactly $k/2$ regions of $H_{1}$, the claim holds
for the first arc. Consider two consecutive arcs $\eta$ and $\eta^{\prime}$ of
$\rho$. Assume that the claim holds for $\eta$, and we show that the claim
also holds for $\eta^{\prime}$. Let $h$ and $h^{\prime}$ be the two regions of
$H_{1}$ such that the boundary curve of $h$ contains $\eta$, and the boundary
curve of $h^{\prime}$ contains $\eta^{\prime}$. The regions of
$H_{1}\setminus\\{h,h^{\prime}\\}$ containing $\eta$ also contains
$\eta^{\prime}$, and vice versa. On the other hand, there are two
possibilities: (1) $h$ contains both $\eta$ and $\eta^{\prime}$, and
$h^{\prime}$ contains both $\eta$ and $\eta^{\prime}$, or (2) $h$ contains
$\eta$ only, and $h^{\prime}$ contains $\eta^{\prime}$ only. Therefore, the
number of regions of $H_{1}$ containing $\eta^{\prime}$ (and $\eta$) are the
same, and thus $\rho$ is contained in $P_{i}$. See also Figure 6(b).

Moreover, $\rho$ is a simple curve, that is, it does not contain a cycle. If
this is not the case, $\rho$ contains three arcs of the arrangement sharing a
common vertex. Two of them are contained in the boundary curve of the same
region $h$ of $H_{1}$. Let $h^{\prime}$ be the region of $H_{1}$ whose
boundary curve contains the other arc. The regions of
$H_{1}\setminus\\{h^{\prime}\\}$ containing one arc coming from $h$ contain
the other arc coming from $h$, and vice versa. On the other hand, one arc
coming from $h$ is not contained in $h^{\prime}$, and the other arc coming
from $h$ is contained in $h^{\prime}$. Therefore, not both arcs coming from
$h$ are contained in $P_{1}$, which contradicts that $\rho$ contains both
arcs. Therefore, $\rho$ does not contain a cycle, and thus it ends at a point
on $C$. ∎

######  Lemma 8.

We have $P_{1}\cap P_{2}\neq\emptyset$, and a point in $P_{1}\cap P_{2}$ has a
crossing-level at least $k/2$.

###### Proof.

Notice that $P_{1}\cap C$ consists of two points $x_{k/2}$ and $y_{k/2+1}$.
Therefore, $P_{1}$ contains a simple curve connecting $x_{k/2}$ and
$y_{k/2+1}$. Similarly, $P_{2}$ contains a simple curve connecting $x_{3k/2}$
and $y_{3k/2+1}$. Since $x_{k/2},x_{3k/2},y_{k/2+1}$ and $y_{3k/2+1}$ lie on
$C$ in the counterclockwise order, the two simple curves cross. See Figure
6(c). Notice that an intersection point $p$ of the two simple curves is
contained in exactly $k/2$ regions of $H_{i}$ for $i=1,2$.

Now we show that the crossing-level of $p$ is at least $k/2$. Let $z$ be a
point in $C$. It suffices to show that any curve connecting $p$ and $z$
intersects at least $k/2$ curves of $\\{\gamma_{1},\ldots,\gamma_{2k}\\}$. For
two points $x^{\prime}$ and $y^{\prime}$ on $C$, we let
$C[x^{\prime},y^{\prime}]$ be the circular arc of $C$ from $x^{\prime}$ to
$y^{\prime}$ in the counterclockwise direction. We show this through case
studies of the position of $z$. Consider the case that $z\in C[x_{2k},y_{1}]$.
Recall that the common intersection of all regions of $H_{1}\cup H_{2}$
contains $C[x_{2k},y_{1}]$. Recall also that the number of regions of $H$ not
containing $p$ is exactly $k$. The region $h_{i}$ of $H$ not containing $p$ is
defined by the double-grounded curve $\gamma_{i}$. Then $\gamma_{i}$ separates
$p$ and $z$. In this case, any curve connecting $p$ and $z$ intersects at
least $k$ different curves of
$\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}\\}$, and thus we are done.

Now consider the case that $z\in C[x_{1},x_{k}]\cup C[y_{1},y_{k}]$. Then the
regions of $H_{2}$ containing $p$ do not contain $z$. Therefore, at least
$k/2$ curves of $\\{\gamma_{k+1},\gamma_{2},\ldots,\gamma_{2k}\\}$ separate
$p$ and $z$, and thus any curve connecting $p$ and $z$ intersects at least
$k/2$ different curves of $\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{2k}\\}$.

The other cases can be handled similarly. Specifically, the case that $z\in
C[y_{2k},x_{1}]$ can be handled symmetrically to the first case by changing
the roles of the regions of $H$ not containing $p$ and the regions of $H$
containing $p$. The case that $z\in C[x_{k},x_{2k}]\cup C[y_{k},y_{2k}]$ can
be handled symmetrically to the second case by changing the roles of $H_{1}$
and $H_{2}$. ∎

In this way, we can show that for an outerstring graph $G$ with a geometric
representation $\Gamma$, the maximum crossing-level in $\Gamma$ is
$\Omega(tw)$, where $tw$ denotes the treewidth of $G$.

######  Theorem 1.

The treewidth of an outerstring graph is $O(\alpha\log n)$, where $\alpha$ and
$n$ denote the arboricity and the number of vertices of the graph,
respectively.

######  Corollary 1.

The treewidth of a $K_{t,t}$-free outerstring graph is $O(t(\log t)\log n)$.

##  4 Lower Bound of the Treewidth of an Outerstring Graph

In this section, we show that the bound of Theorem 1 is almost tight by
constructing an _outersegment graph_ $G$ with treewidth
$\Theta(\alpha\log(n/\alpha))$, where $\alpha$ is the arboricity of $G$. An
outersegment graph $G$ is the intersection graph of _segments_ grounded on
$C$. We say an outersegment graph is $k$-directional if it has a geometric
representation consisting of grounded segments of $k$ orientations. To make
the description easier, we first present a 2-directional outersegment graph
with arboricity $O(1)$ of treewidth $\Omega(\log n)$.

######  Lemma 9.

There is a 2-directional outersegment graph with arboricity $O(1)$ and
treewidth $\Omega(\log n)$, where $n$ denotes the number of its vertices.

###### Proof.

Let $n=2^{m}$. We consider the $x$-axis as the ground, and the region lying
above the $x$-axis as the interior of the ground. A _V-shape curve_ is the
union of two equal-length outersegments sharing a common ground point, with
the other endpoints having the same $y$-coordinates. Note that the angle of
the two outersegments is $\pi/3$. The width of a V-shaped curve is defined as
the length of each outersegment. A _folk_ is the union of equal-width V-shaped
curves which form a simple curve. See Figure 7(a). The _size_ of folk is the
number of V-shaped curves in the fork, and the _width_ of a folk is the size
of each V-shaped curve in the folk. For an index $i$ with $1\leq i\leq m$, let
$F_{i}$ be the folk of width $2^{i}$ and size $n/2^{i}$ whose leftmost point
lies on the $y$-axis. Then we set $\Gamma$ as the set of all outersegments of
the folks $F_{1},F_{2},\ldots,F_{m}$. See Figure 7(b). Notice that the ground
points of the outersegments of $F_{i}$ have $x$-coordinates
$2^{i-1}+2^{i}\cdot j$ for integers $j$ with $0\leq j<n/2^{i}-1$. Therefore,
no two segments from different folks share their ground points.

Its intersection graph $G$ is clearly a 2-directional outersegment graph. The
number of vertices of $G$ is $\Theta(n)$ since the number of segments of
$F_{i}$ is $2\cdot(n/2^{i})$. The arboricity of $G$ is $O(1)$ since each
segment of $F_{i}$ intersects at most one segment of $F_{i+1}\cup
F_{i+2}\cup\ldots\cup F_{m}$ for any index $i$ with $1\leq i\leq m$. Then the
number of edges of any subgraph of $G$ is linear in the number of its
vertices, and thus the arboricity of $G$ is $O(1)$. Consider the minor of $G$
obtained by contracting all edges coming from $F_{i}$ for each index $i$ with
$1\leq i\leq m$. Since the folks are pairwise intersecting, the resulting
minor is a clique of size $m=\log n$. Since the treewidth of $G$ is at least
the treewidth of any of its minors, the treewidth of $G$ is $\Omega(\log n)$.
∎

Figure 7: (a) A folk of width $2^{i-1}$ and size $n/2^{i}$. (b) Illustration
of $F_{1},F_{2}$ and $F_{3}$.

Notice that this example is $2$-biclique-free. We can generalize this example
to an outersegment graph with an arbitrary arboricity $\alpha$ whose treewidth
is $\Theta(\alpha\log(n/\alpha))$ by simply copying all segments $\alpha$
times. Notice that we can slightly perturb the copied segments without
changing their intersection graphs so that any two segments intersect at most
once.

######  Lemma 10.

For any integer $\alpha$, there is an outersegment graph with arboricity
$\alpha$ and treewidth $\Omega(\alpha\log(n/\alpha))$, where $n$ denotes the
number of its vertices.

###### Proof.

Let $\Gamma$ be the set of outersegments we constructed in Lemma 9. We copy
each outersegment of $\Gamma$ into $\alpha$ copies. Then these $\alpha$ curves
are pairwise intersecting. Then the intersection graph of the resulting
outersegments has arboricity $\alpha$, and it has $\alpha n$ vertices.
Moreover, the resulting set $\Gamma$ can be decomposed into $\alpha\log n$
pairwise intersecting folks, and they form a clique minor of size $\alpha\log
n$. Therefore, the treewidth of the resulting graph is $\alpha\log(N/\alpha)$,
where $N$ denotes the number of vertices of the resulting graph. ∎

##  5 Algorithmic Applications

In this section, we present algorithmic applications of Corollary 1. Immediate
consequences of Corollary 1 are as follows. We compute a tree decomposition of
width $2\cdot tw$ in $2^{O(tw)}n$ time [32]. Then lots of central NP-hard
problems can be solved in $2^{O(tw)}n^{O(1)}$ time [14] including the problems
mentioned in the following corollary (except for Coloring). The definitions of
the problems are as follows. We are given a graph $G$. Then

  * •

Independent Set asks for a maximum-sized set of pairwise non-adjacent
vertices.

  * •

Hamiltonian Cycle asks for a cycle that visits all the vertices of the graph.

  * •

Vertex Cover asks for a minimum-sized set of vertices that cover all the
edges.

  * •

Dominating Set asks for a minimum-sized set $D$ of vertices such that every
other vertex is adjacent to $D$.

  * •

Feedback Vertex Set asks for a minimum-sized vertex set whose removal makes
$G$ acyclic.

  * •

Coloring asks for a coloring of the vertices of $G$ with the smallest number
of colors.

  * •

Maximum Induced Matching asks for a maximum-sized edge set $S$ such that no
two such edges are joined by an edge of $G$.

  * •

List 3-Coloring asks for a function $\bar{f}:V(G)\rightarrow\\{1,2,3\\}$ such
that $\bar{f}(v)\in f(v)$ for all vertices $v$ of $V(G)$, and
$\bar{f}(u)\neq\bar{f}(v)$ for all edges $(u,v)$ of $G$. An input of this
problem consists of a graph $G$ and a function $f:V(G)\rightarrow
2^{\\{1,2,3\\}}$.

  * •

Cycle Packing asks for a maximum-sized set of vertex-disjoint cycles of $G$.

  * •

Minimum Clique Cover asks for a partition of $V(G)$ into a smallest number of
cliques.

  * •

Maximum Clique asks for a set of pairwise adjacent vertices.

  * •

Recognition asks for checking if $G$ is an outerstring graph.

######  Corollary 2.

Independent Set, Hamiltonian Cycle, Dominating Set, Feedback Vertex Set and
Coloring can be solved in polynomial time on $t$-biclique-free outerstring
graphs for a constant $t$.

###### Proof.

All problems mentioned above, except for Coloring, admit polynomial-time
algorithms for graphs with logarithmic treewidth. More specifically, they are
based on dynamic programming over a tree decomposition of width $tw=O(\log
n)$, and they run in $2^{O(tw)}n^{O(1)}=n^{O(1)}$ time in our case. For
details, see [14, Chapter 7.3 and Chapter 11.2].

In the case of Coloring, recall that a $t$-biclique-free outerstring graph is
$O(t\log t)$-degenerate by Lemma 1. Thus it is $O(t\log t)$-colorable. To see
this, consider the following constructive argument. In each iteration, we find
a minimum degree vertex $v$ and compute a minimum coloring of $G-\\{v\\}$
recursively. Then since the degree of $v$ is $O(t\log t)$, we can color $v$
using a color not used by any neighbor of $v$ once we have $\Omega(t\log t)$
colors. This implies that $G$ is $O(t\log t)$-colorable. For a fixed constant
$q$, we can compute a coloring of a graph with treewidth $tw$ with $q$ colors
in $2^{O(tw)}n^{O(1)}$ time [14, Chapter 7.3]. Therefore, we can solve
Coloring in polynomial time in the case that $t$ is a constant. ∎

#### Subexponential-time FPT algorithms for (not necessarily sparse)
outerstring graphs.

We can obtain subexponential-time FPT algorithms for Vertex Cover and Feedback
Vertex Set on general outerstring graphs. To do this, we first compute the
polynomial kernel with respect to the solution size $k$. Then we compute
biclique of size $t=\sqrt{k}$ in a brute-force manner, and then apply
branching with respect to the partial solution in the biclique.

######  Corollary 3.

Vertex Cover parameterized by the solution size $k$ can be solved in
$2^{O(\sqrt{k}\log^{2}k)}n^{O(1)}$ time for (not necessarily sparse)
outerstring graphs.

###### Proof.

Let $G$ be an outerstring graph with $n$ vertices. Vertex Cover admits a
kernel of size $k$ [14], that is, there is an instance $(H,k^{\prime})$
consisting of an induced minor $H$ of $G$ with $O(k)$ vertices and an integer
$k^{\prime}\leq k$ such that $H$ has a vertex cover of size $k^{\prime}$ if
and only if $G$ has a vertex cover of size $k$. Thus it is sufficient to solve
Vertex Cover for $(H,k^{\prime})$. Notice that $H$ is also an outerstring
graph.

Let $t=\sqrt{k}$. Given an instance $(H,k^{\prime})$, we first compute a
biclique of size $t$ in $H$ in a brute-force fashion if it exists. This takes
$k^{t}=2^{O(\sqrt{k}\log k)}$ time. Let $A,B$ be the sets of $V(H)$ which form
a biclique of size $t$. Notice that a vertex cover of $H$ must contain either
$A$ or $B$. We branch on whether $A$ is contained in an optimal vertex cover,
or $B$ is contained in an optimal vertex cover. For this, we produce two
instances $(H-A,k^{\prime}-t)$ and $(H-B,k^{\prime}-t)$. If $H$ does not
contain a biclique of size $t$, we apply a polynomial-time algorithm for
computing a minimum vertex cover for a $t$-biclique-free outerstring graph.

The number of instances we produce is $2^{O(k/t)}$, which is
$2^{O(\sqrt{k})}$. For each instance, we compute a biclique of size $t$ in
$2^{O(\sqrt{k}\log k)}$ time. If it does not exist, we compute a minimum
vertex cover in $O(2^{t(\log t)\log k})=2^{O(\sqrt{k}\log^{2}k)}$ time. ∎

######  Corollary 4.

Feedback Vertex Set parameterized by the solution size $k$ can be solved in
$2^{O(\sqrt{k}\log^{2}k)}n^{O(1)}$ time for (not necessarily sparse)
outerstring graphs.

###### Proof.

Let $G$ be an outerstring graph with $n$ vertices. Feedback Vertex Set admits
a kernel of size $k^{2}$ [14]. More specifically, there is an instance
$(H,k^{\prime})$ consisting of an induced minor $H$ of $G$ with $O(k^{2})$
vertices and an integer $k^{\prime}\leq k$ such that $H$ has a feedback vertex
set of size $k^{\prime}$ if and only if $G$ has a feedback vertex set of size
$k$. Thus it is sufficient to solve Feedback Vertex Set for $(H,k^{\prime})$.
Notice that $H$ is also an outerstring graph.

Let $t=\sqrt{k}$. Given an instance $(H,k^{\prime})$, we first compute a
biclique of size $t$ in $H$ in a brute-force fashion if it exists. This takes
$|V(H)|^{2t}=2^{O(\sqrt{k}\log k)}$ time. Let $A,B$ be the sets of $V(H)$
which form a biclique of size $t$. Notice that a feedback vertex set of $H$
must contain either all but one vertex of $A$ or all but one vertex of $B$. In
this case, we produce $2t$ instances for branching on which vertices of $A\cup
B$ are contained in an optimal feedback vertex set. For this, we produce $t$
instances $(H\setminus(A\setminus\\{v\\}),k^{\prime}-(t-1))$ for all vertices
$v\in A$ and $t$ instances
$(H\setminus(B\setminus\\{v^{\prime}\\}),k^{\prime}-(t-1))$ for all vertices
$v^{\prime}\in B$. If $H$ does not contain a biclique of size $t$, we apply a
polynomial-time algorithm for computing a minimum feedback vertex set for a
$t$-biclique-free outerstring graph.

The number of instances we produce is $(2t)^{O(k/t)}$, which is
$2^{O(\sqrt{k}\log k)}$. For each instance, we compute a biclique of size $t$
in $2^{O(\sqrt{k}\log k)}$ time. If it does not exist, we compute a minimum
feedback vertex set in $O(2^{t(\log t)\log k})=2^{O(\sqrt{k}\log^{2}k)}$ time.
∎

#### Subexponential-time algorithms for (not necessarily sparse) outerstring
graphs.

Apart from Corollary 1, the main tools we use for Vertex Cover and Feedback
Vertex Set are branching and kernelization. For the following two problems, we
are not aware of any polynomial kernel although we can apply branching. In
this case, we can obtain subexponential-time (non-parameterized) algorithms
for those problems.

######  Corollary 5.

Maximum Induced Matching on outerstring graphs with $n$ vertices can be solved
in $2^{O(\sqrt{n}\log^{2}n)}$ time.

###### Proof.

Let $G$ be an outerstring graph with $n$ vertices. Let $t=\sqrt{n}$. We first
compute a biclique of size $t$ in $H$ in a brute-force fashion if it exists.
This takes $n^{t}=2^{O(\sqrt{n}\log n)}$ time. Let $A,B$ be the sets of $V(G)$
which form a biclique of size $t$. Notice that for any induced matching $M$ of
$G$, at most one edge of $M$ is incident to $A\cup B$. We produce $t^{2}$
instances for branching on which vertices of $A\cup B$ are involved in a
maximum induced matching. For this, we produce two instances $G\setminus A$
and $G\setminus B$, and $t^{2}$ instances $(G\setminus(A\cup B))\cup\\{u,v\\}$
for all pairs $(u,v)$ with $u\in A$ and $v\in B$. If $G$ does not contain a
biclique of size $t$, we apply a $2^{O(tw)}n^{O(1)}$-time algorithm for
computing a maximum-cardinality induced matching for a $t$-biclique-free
outerstring graph.

The number of instances we produce is $(t^{2})^{O(n/t)}$, which is
$2^{O(\sqrt{n}\log n)}$. For each instance, we compute a biclique of size $t$
in $2^{O(\sqrt{n}\log n)}$ time. If it does not exist, we compute a maximum
induced matching in $O(2^{t(\log t)\log n})=2^{O(\sqrt{n}\log^{2}n)}$ time. ∎

######  Corollary 6.

List 3-Coloring on outerstring graphs with $n$ vertices can be solved in
$2^{O(\sqrt{n}\log^{2}n)}$ time.

###### Proof.

Let $G$ be an outerstring graph with $n$ vertices, and let $f:V(G)\rightarrow
2^{\\{1,2,3\\}}$ be a function. Our goal is to choose one vertex from $f(v)$
for each vertex $v$ such that for any edge $uv$ of $G$, $f(v)\neq f(u)$. Let
$t=\sqrt{n}$. We first compute a biclique of size $t$ in $H$ in a brute-force
fashion if it exists. This takes $n^{t}=2^{O(\sqrt{n}\log n)}$ time. Let $A,B$
be the sets of $V(G)$ which form a biclique of size $t$. Notice that for any
feasible coloring of $V(G)$, either all vertices of $A$ have the same color,
or all vertices of $B$ have the same color. This holds since we have only
three colors. We produce six instances for branching on which vertices of
$A\cup B$ have the same color. For this, we produce six instances
$(G-A,f_{B\rightarrow i})$ and $(G-B,f_{A\rightarrow i})$ for $i=1,2,3$, where
$f_{A\rightarrow i}$ (and $f_{B\rightarrow i}$) denotes the function that maps
the vertices $v$ of $V(G)-(A\cup B)$ to $f(v)$ and all vertices $x$ of $B$
(and of $A$) to $f(x)\setminus\\{i\\}$. If $G$ does not contain a biclique of
size $t$, we apply a $2^{O(tw)}n^{O(1)}$-time algorithm for computing a list
3-coloring of $G$.

The number of instances we produce is $6^{O(n/t)}$, which is
$2^{O(\sqrt{n})}$. For each instance, we compute a biclique of size $t$ in
$2^{O(\sqrt{n}\log n)}$ time. If it does not exist, we compute a list
3-coloring in $O(2^{t(\log t)\log n})=2^{O(\sqrt{n}\log^{2}n)}$ time. In
total, the running time of the algorithm is $2^{O(\sqrt{n}\log^{2}n)}$. ∎

#### Approximation algorithms for (not necessarily sparse) outerstring graphs.

We present the first constant-factor approximation algorithm for the Cycle
Packing running in quasi-polynomial time. Our algorithm repeatedly computes a
cycle of length at most four and removes it from $G$ until no such cycle
exists. Then the remaining graph is 2-biclique-free, and thus we can find a
maximum number of cycles in the remaining graph in $2^{O(tw\log tw)}$ time.
Then we show that the total number of cycles we have found so far is at least
$\textsf{OPT}/4$.

######  Corollary 7.

Cycle Packing on outerstring graphs with $n$ vertices can be solved
approximately with an approximation factor of 4 in $n^{O(\log\log n)}$ time.

###### Proof.

Let $G$ be an outerstring graph with $n$ vertices. As the first step, we
repeatedly compute a cycle of length at most four. For a cycle of length at
most four, we add it to the solution and remove it from $G$. Then finally we
have a graph $G_{\textsf{final}}$ whose shortest cycle has a length larger
than four. Notice that this graph does not contain $K_{2,2}$ as a subgraph,
and thus its treewidth is $O(\log n)$. It is known that Cycle Packing can be
solved in $2^{O(tw\log tw)}n^{O(1)}$ time. As the second step, we find a
maximum-cardinality set of vertex-disjoint cycles in $G_{\textsf{final}}$ in
$n^{O(\log\log n)}$ time, and return all cycles we computed in the first and
second steps as output.

We can obtain at least $\textsf{OPT}/4$ vertex-disjoint cycles in this way,
where OPT is the maximum number of vertex-disjoint cycles. Let
$\mathcal{C}_{\textsf{OPT}}$ be a set of vertex-disjoint cycles with
$|\mathcal{C}_{\textsf{OPT}}|=\textsf{OPT}$. A cycle of
$\mathcal{C}_{\textsf{OPT}}$ not contained in $G_{\textsf{final}}$ intersects
at least one cycle we computed in the first step. Since the length of a cycle
we computed in the first step is at most four, each such cycle intersects at
most four cycles of $\mathcal{C}_{\textsf{OPT}}$. On the other hand, the
number of cycles of $\mathcal{C}_{\textsf{OPT}}$ contained in
$G_{\textsf{final}}$ is at most the number of cycles we computed in the second
step since we compute a maximum number of vertex-disjoint cycles of
$G_{\textsf{final}}$ in the second step. Therefore, the number of vertex-
disjoint cycles we have is at least $\textsf{OPT}/4$. ∎

## References

  * [1] Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, and Nicolas Trotignon.  On the tree-width of even-hole-free graphs.  European Journal of Combinatorics, 98:103394, 2021.
  * [2] Tara Abrishami, Maria Chudnovsky, and Kristina Vušković.  Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree.  Journal of Combinatorial Theory, Series B, 157:144–175, 2022.
  * [3] Shinwoo An, Kyungjin Cho, and Eunjin Oh.  Faster algorithms for cycle hitting problems on disk graphs.  In Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), pages 29–42, 2023.
  * [4] Shinwoo An and Eunjin Oh.  Feedback vertex set on geometric intersection graphs.  In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), 2021.
  * [5] Shinwoo An and Eunjin Oh.  Eth-Tight Algorithm for Cycle Packing on Unit Disk Graphs.  In 40th International Symposium on Computational Geometry (SoCG 2024), 2024.
  * [6] Sujoy Bhore, Satyabrata Jana, Supantha Pandit, and Sasanka Roy.  The balanced connected subgraph problem for geometric intersection graphs.  Theoretical Computer Science, 929:69–80, 2022.
  * [7] Therese Biedl, Ahmad Biniaz, and Martin Derka.  On the size of outer-string representations.  In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), pages 10:1–10:14, 2018.
  * [8] Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, and Alexandra Wesolek.  Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 3006–3028. SIAM, 2023.
  * [9] Édouard Bonnet and Paweł Rzążewski.  Optimality program in segment and string graphs.  Algorithmica, 81:3047–3073, 2019.
  * [10] Prosenjit Bose, Paz Carmi, J Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, and Michiel Smid.  Computing maximum independent set on outerstring graphs and their relatives.  Computational Geometry, 103:101852, 2022.
  * [11] Sergio Cabello, Jean Cardinal, and Stefan Langerman.  The clique problem in ray intersection graphs.  Discrete & Computational Geometry, 50:771–783, 2013.
  * [12] Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber.  Intersection graphs of rays and grounded segments.  Journal of Graph Algorithms and Applications, 22(2):273–295, 2018.
  * [13] Maria Chudnovsky, Tara Abrishami, Sepehr Hajebi, and Sophie Spirkl.  Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth.  Advances in Combinatorics, 2022:6, 2022.
  * [14] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized Algorithms, volume 5.  Springer, 2015.
  * [15] Peter Damaschke.  The Hamiltonian circuit problem for circle graphs is NP-complete.  Information Processing Letters, 32(1):1–2, 1989.
  * [16] Mark De Berg, Hans L Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C Van Der Zanden.  A framework for exponential-time-hypothesis–tight algorithms and lower bounds in geometric intersection graphs.  SIAM Journal on Computing, 49(6):1291–1331, 2020.
  * [17] Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous.  Clique-based separators for geometric intersection graphs.  Algorithmica, 85(6):1652–1678, 2023.
  * [18] Zdeněk Dvořák and Sergey Norin.  Treewidth of graphs with balanced separations.  Journal of Combinatorial Theory, Series B, 137:137–144, 2019.
  * [19] Gideon Ehrlich, Shimon Even, and Robert Endre Tarjan.  Intersection graphs of curves in the plane.  Journal of Combinatorial Theory, Series B, 21(1):8–20, 1976.
  * [20] Holger Flier, Matúš Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych.  Vertex disjoint paths for dispatching in railways.  In Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’10), 2010.
  * [21] Jacob Fox.  A bipartite analogue of Dilworth’s theorem.  Order, 23(2-3):197–209, 2006.
  * [22] Jacob Fox and János Pach.  A separator theorem for string graphs and its applications.  Combinatorics, Probability and Computing, 19(3):371–390, 2010.
  * [23] Jacob Fox and János Pach.  Coloring $K_{k}$-free intersection graphs of geometric objects in the plane.  European Journal of Combinatorics, 33:853–866, 2012.
  * [24] Jacob Fox and János Pach.  String graphs and incomparability graphs.  Advances in Mathematics, 230(3):1381–1401, 2012.
  * [25] Zachary Friggstad and Mohammad R Salavatipour.  Approximability of packing disjoint cycles.  Algorithmica, 60(2):395–400, 2011.
  * [26] Michael R Garey, David S Johnson, Gary L Miller, and Christos H Papadimitriou.  The complexity of coloring circular arcs and chords.  SIAM Journal on Algebraic Discrete Methods, 1(2):216–227, 1980.
  * [27] Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek, Pavel Klavík, and Jan Kratochvíl.  Cops and robbers on intersection graphs.  European Journal of Combinatorics, 72:45–69, 2018.
  * [28] J Mark Keil.  The complexity of domination problems in circle graphs.  Discrete Applied Mathematics, 42(1):51–63, 1993.
  * [29] J Mark Keil, Joseph SB Mitchell, Dinabandhu Pradhan, and Martin Vatshelle.  An algorithm for the maximum weight independent set problem on outerstring graphs.  Computational Geometry, 60:19–25, 2017.
  * [30] Sándor Kisfaludi-Bak, Karolina Okrasa, and Paweł Rzążewski.  Computing list homomorphisms in geometric intersection graphs.  In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), pages 313–327. Springer, 2022.
  * [31] Hui Kong, Qiang Ma, Tan Yan, and Martin DF Wong.  An optimal algorithm for finding disjoint rectangles and its application to PCB routing.  In Proceedings of the 47th Design Automation Conference (DAC 2010), pages 212–217, 2010.
  * [32] Tuukka Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  SIAM Journal on Computing, pages FOCS21–174, 2023.
  * [33] Jan Kratochvíl.  String graphs I. The number of critical nonstring graphs is infinite.  Journal of Combinatorial Theory, Series B, 52(1):53–66, 1991.
  * [34] Michael Krivelevich, Zeev Nutov, Mohammad R Salavatipour, Jacques Verstraete, and Raphael Yuster.  Approximation algorithms and hardness results for cycle packing problems.  ACM Transactions on Algorithms (TALG), 3(4):48–es, 2007.
  * [35] James R Lee.  Separators in region intersection graphs.  In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 2017.
  * [36] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi.  Subexponential parameterized algorithms on disk graphs.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 2005–2031. SIAM, 2022.
  * [37] Jiří Matoušek.  Near-optimal separators in string graphs.  Combinatorics, Probability and Computing, 23(1):135–139, 2014.
  * [38] Jiří Matoušek.  String graphs and separators.  In Geometry, Structure and Randomness in Combinatorics, pages 61–97. Springer, 2014.
  * [39] Matthias Middendorf and Frank Pfeiffer.  Weakly transitive orientations, Hasse diagrams and string graphs.  Discrete Mathematics, 111(1-3):393–400, 1993.
  * [40] Karolina Okrasa and Paweł Rzążewski.  Subexponential algorithms for variants of the homomorphism problem in string graphs.  Journal of Computer and System Sciences, 109:126–144, 2020.
  * [41] János Pach and Géza Tóth.  Comment on fox news.  Geombinatorics, 15:150–154, 2006.
  * [42] Alexandre Rok and Bartosz Walczak.  Outerstring graphs are $\chi$-bounded.  SIAM Journal on Discrete Mathematics, 33(4):2181–2199, 2019.
  * [43] Marcus Schaefer and Daniel Štefankovič.  Decidability of string graphs.  Journal of Computer and System Sciences, 2(68):319–334, 2004.
  * [44] Frank W. Sinden.  Topology of thin film RC circuits.  Bell System Technical Journal, 45:1639–1662, 1966.


# Reducing NEXP-complete problems to DQBF††thanks: To appear in the
proceedings of FMCAD 2022.

Fa-Hsun Chen  National Taiwan University
<EMAIL_ADDRESS>Shen-Chang Huang  National Taiwan University
<EMAIL_ADDRESS>Yu-Cheng Lu  National Taiwan University
<EMAIL_ADDRESS>Tony Tan  National Taiwan University
<EMAIL_ADDRESS>
###### Abstract

We present an alternative proof of the NEXP-hardness of the satisfiability of
Dependency Quantified Boolean Formulas (DQBF). Besides being simple, our proof
also gives us a general method to reduce NEXP-complete problems to DQBF. We
demonstrate its utility by presenting explicit reductions from a wide variety
of NEXP-complete problems to DQBF such as (succinctly represented)
3-colorability, Hamiltonian cycle, set packing and subset-sum as well as NEXP-
complete logics such as the Bernays-Schönfinkel-Ramsey class, the two-variable
logic and the monadic class. Our results show the vast applications of DQBF
solvers which recently have gathered a lot of attention among researchers.

###### Index Terms:

Dependency quantified boolean formulas (DQBF), NEXP-complete problems,
polynomial time (Karp) reductions, succinctly represented problems

##  I Introduction

The last few decades have seen a tremendous development of boolean SAT solvers
and their applications in many areas of computing [sat-handbook]. Motivated by
applications in verification and synthesis of hardware/software designs
[Jiang09, BalabanovJ15, SchollB01, GitinaRSWSB13, BloemKS14, ChatterjeeHOP13,
KuehlmannPKG02], researchers have recently looked at the generalization of
boolean formulas known as dependency quantified boolean formulas (DQBF).

While solving boolean SAT is “only” NP-complete, for DQBF the complexity jumps
to NEXP-complete [PetersonR79]. This makes solving DQBF quite a challenging
research topic. Nevertheless there has been exciting progress. See, e.g.,
[BalabanovCJ14, FrohlichKB12, Ge-ErnstSW19, KullmannS19, WimmerSB19,
WimmerWSB16, WimmerRM017, Kovasznai16, SchollW18] and the references within,
as well as solvers such as iDQ [FrohlichKBV14], dCAQE [TentrupR19], HQS
[GitinaWRSSB15, WimmerKBS017] and DQBDD [SicS21]. A natural question to ask is
if we can use DQBF solvers to solve any NEXP-complete problems – similar to
how SAT solvers are used to solve any NP-complete problems.

In this short paper we show how to reduce a wide variety of NEXP-complete
problems to DQBF, especially the succinctly represented problems that recently
have found applications in hardware/software engineering [avi-succ-83,
KiniM018, PavlogiannisSSC20]. We present another proof for the NEXP-hardness
of DQBF. We actually give two proofs. The first is by a very simple reduction
from succinct 3-colorability [yanna-succ-86]. The second is by utilizing the
notion that we call succinct projection. It is the second one that we view
more interesting since it gives us a general method to reduce any NEXP-
complete problem to DQBF.

The main idea is quite standard: We encode the accepting runs of a non-
deterministic Turing machine (with exponential run time) with boolean
functions of polynomial arities. However, we observe that the input-output
relation of these functions can actually be “described” by small
circuits/formulas. Succinct projections are simply deterministic algorithms
that construct these circuits efficiently. This simple observation is a
deviation from the standard definition of NEXP, that a language in NEXP is a
language with an exponentially long certificate.

Using succinct projections, we present reductions from various NEXP-complete
problems such as (succinct) Hamiltonian cycle, set packing and subset sum. We
believe our technique can be easily modified for many other natural problems.
Note that the reduction in [PetersonR79] gives little insight on how it can be
used to obtain explicit reductions from concrete NEXP-complete problems.

We also present the reductions from well known NEXP-complete logics such as
the Bernays-Schönfinkel-Ramsey class, two-variable logic
($\small\textsf{FO}^{2}$) and the Löwenheim class [Lewis80, Furer83, gkv,
bgg97, llt21]. In fact we show that they are essentially equivalent to DQBF.
Note that these are logics that have found applications in AI [dl-handbook03],
databases [kotek-paper] and automated reasoning [aut-reasoning], but lack
implementable algorithms. Prior to our work, the only algorithm known for
these logics is to “guess” a model (of exponential size) and then verify that
it is indeed a model of the input formula. Recent work in [kotek-paper]
reduces $\small\textsf{FO}^{2}$ formulas to exponentially long SAT instances,
but the experimental results are not promising.

We hope that the technique introduced in this short paper can lead to richer
applications of DQBF solvers as well as a wide variety of benchmarks which in
turn can lead to further development. It is also open whether the class NEXP
has a bona-fide problem [yanna-succ-86]. Our paper demonstrates that DQBF can
be a good candidate – akin to how boolean SAT is the central problem in the
class NP.

This paper is organized as follows. In Sect. II we review some definitions and
terminology. In Sect. III we reprove the NEXP-completeness of solving DQBF. In
Sect. LABEL:sec:reduction and LABEL:sec:logic we present concrete reductions
from some NEXP-complete problems and logics to DQBF instances. Missing details
can be found in the appendix.

##  II Preliminaries

Let $\Sigma=\\{0,1\\}$. We usually use the symbol $\bar{a},\bar{b},\bar{c}$
(possibly indexed) to denote a string in $\Sigma^{*}$ with $|\bar{a}|$
denoting the length of $\bar{a}$. We use
$\bar{x},\bar{y},\bar{z},\bar{u},\bar{v}$ to denote vectors of boolean
variables. The length of $\bar{x}$ is denoted by $|\bar{x}|$. We write
$C(\bar{u})$ to denote a (boolean) circuit $C$ with input gates $\bar{u}$.
When the input gates are not relevant or clear from the context, we simply
write $C$. For $\bar{a}\in\Sigma^{|\bar{u}|}$, $C(\bar{a})$ denotes the value
of $C$ when we assign the input gates $\bar{u}$ with $\bar{a}$. All logarithms
have base $2$.

A dependency quantified boolean formula (DQBF) in prenex normal form is a
formula of the form:

$\displaystyle\Psi$ $\displaystyle:=\forall x_{1}\cdots\ \forall x_{n}\
\exists y_{1}(\bar{z}_{1})\cdots\ \exists y_{m}(\bar{z}_{m})\quad\psi$ (1)

where each $\bar{z}_{i}$ is a vector of variables from
$\\{x_{1},\ldots,x_{n}\\}$ and $\psi$, called the matrix, is a quantifier-free
boolean formula using variables $x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}$. The
variables $x_{1},\ldots,x_{n}$ are called the universal variables,
$y_{1},\ldots,y_{m}$ the existential variables and each $\bar{z}_{i}$ the
dependency set of $y_{i}$.

A DQBF $\Psi$ in the form (1) is satisfiable, if for every $1\leqslant
i\leqslant m$, there is a function $s_{i}:\Sigma^{|\bar{z}_{i}|}\to\Sigma$
such that by replacing each $y_{i}$ with $s_{i}(\bar{z}_{i})$, the formula
$\psi$ becomes a tautology. The function $s_{i}$ is called the Skolem function
for $y_{i}$. In this case, we also say that $\Psi$ is satisfiable by the
Skolem functions $s_{1},\ldots,s_{m}$. The problem $\textsf{\small
SAT}(\text{DQBF})$ is defined as: On input DQBF $\Psi$ in the form (1), decide
if it is satisfiable.

Since many NEXP-complete problems use circuits as the succinct representations
of the inputs, we allow the matrix $\psi$ to be in circuit form, i.e., $\psi$
is given as a (boolean) circuit with input gates
$x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}$. This does not effect the generality
of our results, since every DQBF in circuit form can be converted to one in
the standard formula form as stated in Proposition 1.

######  Proposition 1.

Every DQBF $\Psi$ in the form of (1) in circuit form can be converted in
polynomial time into an equisatisfiable DQBF formula $\Psi^{\prime}$ whose
matrix is in DNF. Moreover, $\Psi$ and $\Psi^{\prime}$ have the same
existential variables (with the same dependency set).

The proof is by standard Tseitin’s transformation [tseitin]. As an example,
consider the following DQBF.

$\displaystyle\forall x_{1}\forall x_{2}\ \exists y_{1}(x_{1})\exists
y_{2}(x_{2})\ \neg\big{(}x_{2}\vee(y_{1}\wedge x_{1}\wedge y_{2})\big{)}$

It is equisatisfiable with the following DQBF.

$\displaystyle\forall x_{1}\forall x_{2}\ \forall u_{1}\forall u_{2}\forall
u_{3}\ \forall v_{1}\forall v_{2}\ \exists y_{1}(x_{1})\exists y_{2}(x_{2})$
$\displaystyle\left(\begin{array}[]{l}(v_{1}\leftrightarrow
y_{1})\wedge(v_{2}\leftrightarrow y_{2})\wedge(u_{1}\leftrightarrow
v_{1}\wedge x_{1}\wedge v_{2})\\\ \wedge(u_{2}\leftrightarrow x_{2}\vee
u_{1})\wedge(u_{3}\leftrightarrow\neg u_{2})\end{array}\right)\to u_{3}$

Intuitively, we use the extra variable $v_{1}$ to represent the value $y_{1}$,
$v_{2}$ the value $y_{2}$, $u_{1}$ the value $y_{1}\wedge x_{1}\wedge y_{2}$,
$u_{2}$ the value $x_{2}\vee(y_{1}\wedge x_{1}\wedge y_{2})$ and $u_{3}$ the
value $\neg(x_{2}\vee(y_{1}\wedge x_{1}\wedge y_{2}))$. Note that the matrix
can be easily rewritten into DNF.

##  III The NEXP-completeness of $\textsf{\small SAT}(\text{DQBF})$

In this section we present two new proofs that $\textsf{\small
SAT}(\text{DQBF})$ is NEXP-complete, originally proved in [PetersonR79].

######  Theorem 2.

[PetersonR79] $\textsf{\small SAT}(\text{DQBF})$ is NEXP-complete.

Note that the membership is straightforward. So we will focus only on the
hardness.

###  III-A The first proof: Reduction from succinct 3-colorability

The reduction is from the problem graph 3-colorability where the input graphs
are given in a succinct form [avi-succ-83]. A (boolean) circuit
$C(\bar{u},\bar{v})$, where $|\bar{u}|=|\bar{v}|=n$, represents a graph
$G(C)=(V,E)$ where $V=\Sigma^{n}$ and $(\bar{a},\bar{b})\in E$ iff
$C(\bar{a},\bar{b})=1$. The problem succinct 3-colorability is defined as: On
input circuit $C$, decide if $G(C)$ is 3-colorable. This problem is NEXP-
complete [yanna-succ-86].

The reduction to $\textsf{\small SAT}(\text{DQBF})$ is as follows. Let
$C(\bar{u},\bar{v})$ be the input circuit, where $|\bar{u}|=|\bar{v}|=n$. We
represent a 3-coloring of $G(C)$ as a function $g:\Sigma^{n}\to\\{01,10,11\\}$
which can be encoded by the following DQBF.

$\displaystyle\Psi:=$ $\displaystyle\forall\bar{x}_{1}\forall\bar{x}_{2}\
\exists y_{1}(\bar{x}_{1})\exists y_{2}(\bar{x}_{1})\ \exists
y_{3}(\bar{x}_{2})\exists y_{4}(\bar{x}_{2})$ $\displaystyle\hskip
35.56593pt\bar{x}_{1}=\bar{x}_{2}\ \to\ (y_{1},y_{2})=(y_{3},y_{4})$ (2)
$\displaystyle\hskip 21.33955pt\wedge\ (y_{1},y_{2})\neq(0,0)\ \wedge\
(y_{3},y_{4})\neq(0,0)$ (3) $\displaystyle\hskip 21.33955pt\wedge\
C(\bar{x}_{1},\bar{x}_{2})=1\ \to\ (y_{1},y_{2})\neq(y_{3},y_{4})$ (4)

Intuitively, we use $y_{1},y_{2}$ and $y_{3},y_{4}$ to represent the first and
the second bits of the image $g(\bar{x}_{1})$ and $g(\bar{x}_{2})$,
respectively. Lines (2) and (3) state that $(y_{1},y_{2})$ and $(y_{3},y_{4})$
must represent the same function from $\Sigma^{n}$ to $\Sigma^{2}$ and that
their images do not inclue $00$. Line (4) states that the colors of two
adjacent vertices must be different. Thus, $G(C)$ is 3-colorable iff $\Psi$ is
satisfiable.

###  III-B The second proof: Reduction via succinct projections

Our second proof uses the notion of succinct projection. We need some
terminology. Let $C(\bar{u}_{1},\bar{v}_{1},\bar{u}_{2},\bar{v}_{2})$ be a
circuit with input gates $\bar{u}_{1},\bar{v}_{1},\bar{u}_{2},\bar{v}_{2}$
where $|\bar{u}_{1}|=|\bar{u}_{2}|=n$ and $|\bar{v}_{1}|=|\bar{v}_{2}|=m$. We
say that a function $g:\Sigma^{n}\to\Sigma^{m}$ agrees with the circuit $C$,
if $C(w_{1},g(w_{1}),w_{2},g(w_{2}))=1$, for every $w_{1},w_{2}\in\Sigma^{n}$.
In this case, we also say that the circuit $C$ describes the function $g$. In
the following whenever we say that a function $g:\Sigma^{n}\to\Sigma^{m}$
agrees with $C(\bar{u}_{1},\bar{v}_{1},\bar{u}_{2},\bar{v}_{2})$, we
implicitly assume that $n=|\bar{u}_{1}|=|\bar{u}_{2}|$ and
$m=|\bar{v}_{1}|=|\bar{v}_{2}|$.

######  Definition 3.

A succinct projection for a language $L$ is a polynomial time deterministic
algorithm $\mathcal{M}$ such that on input $w\in\Sigma^{*}$, $\mathcal{M}$
outputs a circuit $C$ such that $w\in L$ iff there is a function $g$ that
agrees with $C$.

Intuitively, we can view the function $g$ as the certificate for the
membership of $w$ in $L$ and the circuit $C$ as the succinct description of
$g$. Since succinct projection runs in polynomial time, the output circuit can
only have polynomially many gates. The following theorem is a new
characterization of languages in NEXP.

######  Theorem 4.

A language $L\in\textsc{NEXP}$ iff it has a succinct projection.

###### Proof.

(if) Suppose that $L$ has a succinct projection. Consider the following
algorithm. On input $w$, first use the succinct projection to construct the
circuit $C$. Then, guess a function $g$ (of exponential size) and verify that
it agrees with $C$. It is obvious that it runs in non-deterministic
exponential time. That it is correct follows from the definition of succinct
projection.

(only if) It is essentially the Cook-Levin reduction disguised in the form of
function certificates. We only sketch it here. Let $L\in\textsc{NEXP}$ and $M$
be a 1-tape NTM that accepts $L$ in time $2^{p(n)}$ for some polynomial
$p(n)$. For a word $w\in L$ of length $n$, its accepting run can be
represented as a function
$g:\Sigma^{p(n)}\times\Sigma^{p(n)}\to\Sigma^{\ell}$, where $g(i,j)$ denotes
the content of cell $i$ in time $j$. The tuples in the codomain
$\Sigma^{\ell}$ encode the states and the tape symbols of $M$. To verify that
$g$ represents an accepting run, it is sufficient to verify that for every
$i_{1},j_{1},i_{2},j_{2}\in\Sigma^{p(n)}$, the tuple
$(i_{1},j_{1},g(i_{1},j_{1}),i_{2},j_{2},g(i_{2},j_{2}))$ satisfies a certain
property $P$ which depends only on the input word $w$ and the transitions of
$M$. The desired succinct projection constructs in polynomial time a circuit
$C$ describing this property $P$. ∎

The second proof of the NEXP-hardness of $\textsf{\small SAT}(\text{DQBF})$:
Let $L\in\textsc{NEXP}$. The polynomial time (Karp) reduction from $L$ to
$\textsf{\small SAT}(\text{DQBF})$ is described as Algorithm 1 below.

Algorithm 1: Reducing $L\in\textsc{NEXP}$ to $\textsf{\small
SAT}(\text{DQBF})$
---
Input: $w\in\Sigma^{*}$.
1: Run the succinct projection of $L$ on $w$.
2: Let $C(\bar{x}_{1},\bar{y}_{1},\bar{x}_{2},\bar{y}_{2})$ be the output
circuit where
$|\bar{x}_{1}|=|\bar{x}_{2}|=n$, $|\bar{y}_{1}|=|\bar{y}_{2}|=m$,
$\bar{y}_{1}=(y_{1,1},\ldots,y_{1,m})$
and $\bar{y}_{2}=(y_{2,1},\ldots,y_{2,m})$.
3: Output the following DQBF $\Psi$:
$\forall\bar{x}_{1}\forall\bar{x}_{2}\ \exists
y_{1,1}(\bar{x}_{1})\cdots\exists y_{1,m}(\bar{x}_{1})\ \exists
y_{2,1}(\bar{x}_{2})\cdots\exists y_{2,m}(\bar{x}_{2})$
$\qquad\;\;\;\ C(\bar{x}_{1},\bar{y}_{1},\bar{x}_{2},\bar{y}_{2})\ \wedge\
\big{(}\bar{x}_{1}=\bar{x}_{2}\to\bar{y}_{1}=\bar{y}_{2}\big{)}$

We show $w\in L$ iff $\Psi$ is satisfiable. Suppose $w\in L$. Let
$g:\Sigma^{n}\to\Sigma^{m}$ be a function that agrees with $C$. For each
$1\leqslant i\leqslant m$, define the Skolem function
$s_{i}:\Sigma^{n}\to\Sigma$ where $s_{i}(\bar{a})$ is the $i$-th component of
$g(\bar{a})$, for every $\bar{a}\in\Sigma^{n}$. It is routine to verify that
$\Psi$ is satisfiable with each $s_{i}$ being the Skolem function for
$y_{1,i}$ and $y_{2,i}$.

Conversely, suppose $\Psi$ is satisfiable. Let $s_{j,i}:\Sigma^{n}\to\Sigma$
be the Skolem function for $y_{j,i}$, where $1\leqslant j\leqslant 2$ and
$1\leqslant i\leqslant m$. Since $\bar{x}_{1}=\bar{x}_{2}\ \to\
\bar{y}_{1}=\bar{y}_{2}$, the functions $s_{1,i}$ and $s_{2,i}$ must be the
same, for every $1\leqslant i\leqslant m$. Define $g:\Sigma^{n}\to\Sigma^{m}$
where $g(\bar{a})=(s_{1}(\bar{a}),\ldots,s_{1,m}(\bar{a}))$ for every
$\bar{a}\in\Sigma^{n}$. Since
$C(\bar{a}_{1},g(\bar{a}_{1}),\bar{a}_{2},g(\bar{a}_{2}))$ is true for every
$\bar{a}_{1},\bar{a}_{2}$, the function $g$ agrees with $C$. That is, there is
a function that agrees with $C$. Hence, $w\in L$. This completes the second
proof.