---
abstract: |
    A graph $G$ is called *B$_k$-VPG* (resp., *B$_k$-EPG*), for some constant $k\geq 0$, if it has a string representation on a grid such that each vertex is an orthogonal path with at most $k$ bends and two vertices are adjacent in $G$ if and only if the corresponding strings intersect (resp., the corresponding strings share at least one grid edge). If two adjacent strings of a B$_k$-VPG graph intersect exactly once, then the graph is called a *one-string* B$_k$-VPG graph.

    In this paper, we study the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problems on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We first give a simple $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, improving the previous $O((\log n)^2)$-approximation algorithm of Lahiri et al. [@LahiriMS15]. Then, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem. We give an $O(1)$-approximation algorithm for this problem on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem is [<span style="font-variant:small-caps;">APX</span>-hard ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, ruling out the possibility of a PTAS unless <span style="font-variant:small-caps;">P=NP</span>. Finally, we give constant-factor approximation algorithms for this problem on two non-trivial subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. To our knowledge, these are the first results for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, partially answering a question posed by Epstein et al. [@EpsteinGM13].
author:
- Saeed Mehrabi
bibliography:
- 'ref.bib'
title: 'Approximation Algorithms for Independence and Domination on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}Graphs'
---

Introduction {#sec:introduction}
============

In this paper, we study [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. These are two special subclasses of *string graphs*, which are of interest in several applications such as circuit layout design and bioinformatics. In a string representation of a graph, the vertices are drawn as a set of curves in the plane and two vertices are adjacent if their corresponding curves intersect; graphs that can be represented in this way are called string graphs. Studying string graphs dates back to 1970s when Ehrlich et al. [@EhrlichET76] showed that every planar graph has a string representation. Also, Scheinerman’s conjecture [@thesisEdwardScheinerman], stating that all planar graphs can be represented as intersection graphs of line segments, was a long-standing open problem until 2009 when it was proved affirmatively by Chalopin and Goncalves [@ChalopinG09].

EPG graphs (stands for Edge intersection of Paths in a Grid) were introduced by Golumbic et al. [@GolumbicLS09] as the class of graphs whose vertices can be represented as simple orthogonal paths on a rectangular grid in such a way that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. Golumbic et al. [@GolumbicLS09] showed that every graph is an EPG graph, and the size of the underlying grid is polynomial in the size of $G$. Since then much of the work has focused on studying subclasses of EPG graphs; in particular, restricting the type of paths allowed. A turn of a path at a grid node is called a *bend* and a graph is called a *B$_k$-EPG graph* if it has an EPG representation in which each path has at most $k$ bends. In this paper, we are interested in B$_k$-EPG graphs for $k=1$.

\[def:B1EPG\] A graph $G=(V,E)$ is called a *[<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph*, if every vertex $u$ of $G$ can be represented as a *path* $P_u$ on a grid $\mathcal{G}$ such that

$P_u$ is orthogonal and has at most one bend, and

paths $P_u, P_v\in P$ share a grid edge of $\mathcal{G}$ if and only if $(u, v)\in E$.

Instead of considering the edge intersection of graphs on a grid, we can think of the vertex intersection of graphs on a grid. More formally, a graph is said to have a VPG representation (stands for Vertex representation of Paths in a Grid), if its vertices can be represented as simple orthogonal paths on a rectangular grid such that two vertices are adjacent if and only if the corresponding paths share at least one grid node. Although these graphs were considered a while ago when studying string graphs [@MiddendorfP92], they were formally investigated by Asinowski et al. [@AsinowskiCGLLS12]. Similar to B$_k$-EPG graphs, a *B$_k$-VPG graph* is a VPG graph in which each path has at most $k$ bends. In this paper, we are interested in B$_k$-VPG graphs for $k=1$.

\[def:B1VPG\] A graph $G=(V, E)$ is called a *[<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph*, if every vertex $u$ of $G$ can be represented as a *path* $P_u$ on a grid $\mathcal{G}$ such that

$P_u$ is orthogonal and has at most one bend, and

two paths $P_u$ and $P_v$ intersect each other at a grid node if and only if $(u, v)\in E$.

We remark that by *intersecting* each other, we exclude the case where two paths only *touch* each other. Figure \[fig:sampleGraphs\] shows a graph with its [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}representations. A natural restriction on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs can be the number of intersections allowed between every pair of paths. A string graph is called *one-string* if it has a string representation in which curves intersect at most once [@ChalopinGO10; @BiedlD15]. By combining one-string and [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}representations, a *one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph* is defined as a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph in which two paths intersect each other exactly once whenever the corresponding vertices are adjacent.

![A graph on six vertices (left) with its [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}(middle) and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}(right) representations. Notice that the vertices $e$ and $f$ are not adjacent in the [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}representation as they only share a grid node (but not a grid edge).[]{data-label="fig:sampleGraphs"}](finalSampleGraphs){width="90.00000%"}

In this paper, we study two classical graph problems; namely, the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problems, on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. Let $G=(V, E)$ be an unweighted, undirected graph. A set $S\subseteq V$ is an independent set if no two vertices in $S$ are adjacent, while $S$ is a dominating set if every vertex in $V\setminus S$ is adjacent to some vertex in $S$. The objective of the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem is to compute a maximum-cardinality independent set of $G$, whereas the goal in [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is to minimize the size of the dominating set $S$. [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}are two fundamental optimization problems in graph theory, which arise in many applications such as wireless sensor networks, scheduling and resource allocation; both problems are well known to be <span style="font-variant:small-caps;">NP</span>-hard.

It is known that every graph has an EPG representation [@GolumbicLS09]. Heldt et al. [@HeldtKU14] showed that every graph of maximum degree $\Delta$ has a B$_\Delta$-EPG representation. Moreover, Heldt et al. [@HeldtKU14a] proved that the class of B$_4$-EPG graphs contains all planar graphs; it is however still open whether $k=4$ is best possible. They also proved a conjecture of Biedl and Stern [@BiedlS10] affirmatively stating that all outerplanar graphs are B$_2$-EPG graphs. For the case of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, Golumbic et al. [@GolumbicLS09] showed that every tree is a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph, and a characterization of the subfamily of co-graphs that are [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}is also known by a complete family of minimal forbidden induced sub-graphs [@CohenGR14]. We observe by the construction of Ehrlich et al. [@EhrlichET76] that every planar graph has a VPG representation. Moreover, Chaplick and Ueckerdt [@ChaplickU13] proved that every planar graph has a B$_2$-VPG representation, although the representation may not be one-string. On the other hand, Chalopin et al. [@ChalopinGO10] showed that every planar graph has a one-string representation. Biedl and Derka [@BiedlD15] re-proved these results simultaneously by showing that every planar graph has a one-string B$_2$-VPG representation. It is however not known if every planar graph has also a one-string B$_1$-VPG representation. Felsner et al. [@FelsnerKMU16] proved that every planar 3-tree is [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and the line graph of every planar graph is a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph.

In terms of recognition problems, it is known that recognizing [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs is <span style="font-variant:small-caps;">NP</span>-hard [@HeldtKU14], and the hardness of recognizing B$_2$-EPG graphs is shown by Pergel and Rz[ż]{}ewski [@PergelR16]. Moreover, recognizing VPG graphs is <span style="font-variant:small-caps;">NP</span>-complete [@ChaplickJKV12]. They also showed that recognizing if a given B$_{k+1}$-VPG graph is a B$_k$-VPG graph is <span style="font-variant:small-caps;">NP</span>-complete even if we are given a B$_{k+1}$-VPG representation as part of the input. Furthermore, Chaplick et al. [@ChaplickCS11] considered the recognition problem for some restricted classes of B$_0$-VPG graphs.

#### Related work and our results.

The decision version of the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs was shown to be <span style="font-variant:small-caps;">NP</span>-complete by Lahiri et al. [@LahiriMS15] who also gave an $O((\log n)^2)$-approximation algorithm for this problem. Notice that the best known algorithm for [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on arbitrary string graphs has an approximation factor $n^{\epsilon}$, for some $\epsilon>0$ [@FoxP11].

-   We give a polynomial-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, improving the $O((\log n)^2)$-approximation algorithm of Lahiri et al. [@LahiriMS15].

Our algorithm is actually based on that of Lahiri et al. [@LahiriMS15], which is a divide-and-conquer approach [@clrsBook; @deBergBook]. However, instead of solving a special subproblem using a secondary divide-and-conquer, we show how to solve that subproblem directly and improve the approximation factor. For [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, Asinowski et al. [@AsinowskiCGLLS12] proved that every circle graph is a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph. A circle graph is the intersection graph of a set of chords of a circle; that is, each vertex corresponds to a chord of the circle and two vertices are adjacent if and only if their corresponding chords intersect. The proof of Asinowski et al. [@AsinowskiCGLLS12] shows that every circle graph is in fact a one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph (although not every one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph is a circle graph [@Bouchet94]). Since [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is [<span style="font-variant:small-caps;">APX</span>-hard ]{}on circle graphs [@DamianP06], the problem becomes [<span style="font-variant:small-caps;">APX</span>-hard ]{}also on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs.[^1] However, to our knowledge, there is no approximation algorithm known for the problem. We note that there are $O(1)$-approximation algorithms for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on circle graphs [@Damian-IordacheP99a; @Damian-IordacheP02], but these algorithms do not work for [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs as they heavily rely on the fact that the vertices of the input graph are modelled as chords of a circle.

-   We give a polynomial-time $O(1)$-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on *one-string* [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. To our knowledge, this is the first constant-factor approximation algorithm for this problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs.

Our algorithm is based on formulating the problem as a hitting set problem among orthogonal line segments and then proving that the corresponding hitting set has a small $\varepsilon$-net. However, proving the existence of such an $\varepsilon$-net is not straightforward and requires a decomposition of the problem into two “one-dimensional” instances, each of which will then admit such an $\varepsilon$-net. Informally speaking, the idea is that although the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem is not “decomposable” into horizontal and vertical instances, the $\varepsilon$-net corresponding to this problem is. Combining these nets along with the technique of Brönnimann and Goodrich [@BronnimannG95] gives us the desired result.

For [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem is known to be <span style="font-variant:small-caps;">APX</span>-hard [@BougeretBGP15], and there exists a polynomial-time 4-approximation algorithm for this problem [@EpsteinGM13]. Moreover, there exists a 4-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs [@ButmanHLR10], as it is known that such graphs are a subset of 2-interval graphs [@HeldtKU14]. However, we were unable to find a reference on the complexity of the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We note here that every tree is a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph [@GolumbicLS09], and even permutation graphs or co-graphs are known to be [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}[@CohenGR14], but [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is polynomial-time solvable on these graphs [@graphTheoryBook].

-   We prove that the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem is [<span style="font-variant:small-caps;">APX</span>-hard ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, even if only two types of paths are allowed in the input graph. Thus, there exists no PTAS for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs unless <span style="font-variant:small-caps;">P=NP</span>.

Let us also mention that Asinowski and Ries [@AsinowskiR12] showed that the class of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs contains a number of subclasses of chordal graphs; namely, chordal bull-free, chordal claw-free and chordal diamond-free graphs; however, we were unable to find any reference on the status of the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on these subclasses of chordal graphs. To show the <span style="font-variant:small-caps;">APX</span>-hardness, we give an <span style="font-variant:small-caps;">L</span>-reduction from the [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}problem on graphs with maximum-degree three (which is known to be [<span style="font-variant:small-caps;">APX</span>-hard ]{} [@AlimontiK00]) to the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. As noted above, there is a 4-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs [@ButmanHLR10]. Here, we give $c$-approximation algorithms for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on two non-trivial subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, for $c\in\{2, 3\}$. Let us defer the definition of these subclasses to Section \[subsec:MDSonBEPG\].

-   We give polynomial-time constant-factor approximation algorithms for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on two subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

#### Organization.

This paper is organized based on the problems as follows. We first give some notations and definitions in Section \[sec:prelimins\]. Then, we give our $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs in Section \[sec:independentSet\]. Next, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[sec:dominatingSet\]. We first give the $O(1)$-approximation algorithm for this problem on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs in Section \[subsec:MDSonBVPG\], and then present our results for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[subsec:MDSonBEPG\]. We conclude the paper with a discussion on open problems in Section \[sec:conclusion\].

Notation and Definitions {#sec:prelimins}
========================

For a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}(resp., [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}) graph $G$, we use $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ (resp., $\langle$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$,\mathcal{G}\rangle$) to denote a particular [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}(resp., [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}) representation of $G$, where [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}(resp., [$\mathcal{P}_{{\texttt{edg}}}$ ]{}) is the collection of paths correspond to the vertices of $G$ and $\mathcal{G}$ is the underlying grid. Since the recognition problem is <span style="font-variant:small-caps;">NP</span>-hard on such graphs, we assume throughout this paper, that we are always given a string representation of a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}or [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph as input (in addition to $G$). We sometimes violate the wording and say *path(s) in $G$* to actually refer to the vertices in $G$ corresponding to the paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}or [$\mathcal{P}_{{\texttt{edg}}}$ ]{}. We denote the $x$- and $y$-coordinates of a point $p$ in the plane by $x(p)$ and $y(p)$, respectively.

Let $G=(V, E)$ be a graph with its representations $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ and $\langle$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$,\mathcal{G}\rangle$, and let $P\in\{$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$\cup$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$\}$ be an arbitrary path. Since $P$ has at most one bend, it is in one of the types {[$\ulcorner$]{}, [$\llcorner$]{}, [$\urcorner$]{}, [$\lrcorner$]{}, $|$, $-$}. We call a path $P$ of type $\texttt{x}\in${[$\ulcorner$]{}, [$\llcorner$]{}, [$\urcorner$]{}, [$\lrcorner$]{}}, a *$\texttt{x}$-type path*; we complete the definition by referring to no-bend paths as [$\llcorner$]{}-type paths.

We denote the horizontal and vertical segments of $P$ by ${\texttt{hPart}}(P)$ and ${\texttt{vPart}}(P)$, respectively. We call the common endpoint of ${\texttt{hPart}}(P)$ and ${\texttt{vPart}}(P)$ the *corner* of $P$ and denote it by ${\texttt{corner}}(P)$. Moreover, let ${\texttt{hTip}}(P)$ (resp., ${\texttt{vTip}}(P)$) denote the endpoint of ${\texttt{hPart}}(P)$ (resp., ${\texttt{vPart}}(P)$) that is not shared with ${\texttt{vPart}}(P)$ (resp., not shared with ${\texttt{hPart}}(P)$). Let $N[P]$ denote the set of paths adjacent to $P$; we assume that $P\in N[P]$. Moreover, for a set $S$ of paths, define $N[S]:=\cup_{P\in S}N[P]$. We denote the set of neighbours of $P$ that share at least one grid edge with ${\texttt{hPart}}(P)$ (resp., with ${\texttt{vPart}}(P)$) by ${\texttt{hNeighbor}}(P)$ (resp., by ${\texttt{vNeighbor}}(P)$). Throughout this paper, we assume a weak general-position assumption on the corners of paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}only: for every two distinct paths $P, P'\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}, either $x({\texttt{corner}}(P))\ne x({\texttt{corner}}(P'))$ or $y({\texttt{corner}}(P))\ne y({\texttt{corner}}(P'))$; that is, the corners of no two paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}coincide. Notice that by our weak general-position assumption, $\{{\texttt{hNeighbor}}(P), {\texttt{vNeighbor}}(P)\}$ is a partition of $N[P]$ for any $P\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}.

Independent Set {#sec:independentSet}
===============

In this section, we consider the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, and give an $O(n^3)$-time $O(\log n)$-approximation algorithm for this problem. This improves the previous $O((\log n)^2)$-approximation algorithm of Lahiri et al. [@LahiriMS15]. Our algorithm is actually based on that of Lahiri et al. [@LahiriMS15] and uses a divide-and-conquer approach. We first describe their algorithm and then show how a simple modification can improve the approximation factor, although the running time would slightly increase. For the rest of this section, let $G$ be a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with $n$ vertices, and let $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ denote a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}representation of it.

#### Approximating a subproblem.

To solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, Lahiri et al. [@LahiriMS15] first considered a subproblem in which all paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}are assumed to be of [$\llcorner$]{}-type. So, suppose for now that $G$ is a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph such that all paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}are of [$\llcorner$]{}-type. The algorithm sorts the paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}by the $x({\texttt{corner}}(P))$ of all paths $P$ and considers the vertical line $\ell: x=x_{med}$, where $x_{med}$ is the middle point between $x({\texttt{corner}}(P_{\lfloor n/2\rfloor}))$ and $x({\texttt{corner}}(P_{\lfloor n/2\rfloor+1}))$ in the ordering. Then, the paths are partitioned into three groups: the set $I_L$ of paths that lie to the left of $\ell$, the set $I_R$ of paths that lie to the right of $\ell$ and the set $I_M$ of paths that intersect $\ell$. The algorithm solves [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $I_L$ and $I_R$ recursively and returns the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$ as the solution, where $S(A)$ is a maximum independent set on the set of paths in $A$.

To compute $S(I_M)$, the algorithm performs the above divide-and-conquer approach on the sorted $y({\texttt{corner}}(P))$ of only paths $P\in I_M$; hence, partitioning the paths in $I_M$ into three analogous groups $I'_L$, $I'_R$ and $I'_M$. Notice that the paths in $I'_M$ are intersecting a vertical and a horizontal line. Lahiri et al. [@LahiriMS15] showed that the [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph induced by the paths in $I_M\cap I'_M$ is a co-comparability graph for which [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}can be solved optimally in polynomial time [@KohlerM16; @Golumbic04]. They analyzed this algorithm and showed that it has an $O((\log n)^2)$-approximation factor.

To improve the approximation factor to $O(\log n)$, we avoid running the divide-and-conquer algorithm on the $y({\texttt{corner}}(P))$ of paths $P\in I_M$. Instead, we directly solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on paths in $I_M$ and then return the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$ as the solution. To solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $I_M$, we show that the [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph $G_{I_M}$ induced by the paths in $I_M$ is an *outerstring graph* for which we can solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}optimally using the recent algorithm of Keil et al. [@KeilMPV15]. See Algorithm \[alg:approxMISonVPG\] in which <span style="font-variant:small-caps;">MIS</span>$(H)$ denotes the algorithm of Keil et al. [@KeilMPV15] for computing a maximum independent set on an outerstring graph $H$.

It remains to show that $G_{I_M}$ is an outerstring graph. Outerstring graphs were first introduced by Kratochvíl [@Kratochvil91; @Kratochvil91a] as the intersection graphs of a set of curves in the plane that lie inside a disk such that each curve intersects the boundary of the disk in one of its endpoints. Keil et al. [@KeilMPV15] gave an $O(N^3)$-time algorithm for [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on outerstring graphs, where they model the disk as a polygon and each curve as a polygonal line (i.e., a chain of line segments) completely inside the polygon such that one of its endpoints coincides with a vertex of the polygon. Here, $N$ denotes the total number of segments used in the geometric representation of the polygonal lines and the polygon. The main part of the proof of Lemma \[lem:misOnIM\] is to show that $G_{I_M}$ is an outerstring graph.

\[lem:misOnIM\] [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}can be solved on $G_{I_M}$ in $O(N^3)$ time, where $N$ is the number of paths in $I_M$.

We prove that $G_{I_M}$ is an outerstring graph with an $O(N)$ geometric representation. The lemma then follows by the algorithm of Keil et al. [@KeilMPV15] for solving [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on outerstring graphs.

Enclose the paths in $I_M$ within a large-enough vertical rectangle $R$ such that the vertical line $\ell$ contains the right side of $R$; ignore the portion of every path of $I_M$ that lies to the right of $\ell$ (and hence outside of $R$). Next, convert $R$ into a polygon $P$ by slightly modifying $R$ at the intersection point of each path in $I_M$ with the right side of $R$ such that the path ends at a vertex of the polygon $P$; see Figure \[fig:ourOuterstring\] for an illustration. First, notice that by definition of $\ell$, every path in $I_M\cap R$ intersects the right side of $R$ in exactly one point. Moreover, since all paths in $I_M$ are [$\llcorner$]{}-type paths, no two paths in $I_M$ would intersect each other on the right of $\ell$ without first intersecting each other inside $R$; hence, $R$ captures all the adjacencies between the paths in $I_M$. The resulting representation models our outerstring graph.

Clearly, $P$ is a simple polygon with $O(N)$ vertices (and, hence $O(N)$ edges). Moreover, each path inside $P$ consists of two segments and so the total number of segments to represent all the paths in $I_M$ is $O(N)$. Therefore, $G_{I_M}$ is outerstring and the above construction is an $O(N)$ geometric representation of $G_{I_M}$.

![A illustration in support of the proof of Lemma \[lem:misOnIM\].[]{data-label="fig:ourOuterstring"}](IM){width="80.00000%"}

compute a maximum independent set $S$ of $G$ in $O(1)$ time; compute $x_{med}$ and the partition $\{I_L, I_R, I_M\}$; $S(I_L)\gets$ ApproximateMISonVPG($I_L$); $S(I_R)\gets$ ApproximateMISonVPG($I_R$); $S(I_M)\gets$<span style="font-variant:small-caps;">MIS</span>$(I_M)$; $S\gets$ the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$; $S$;

\[lem:approxMISonVPGfactor\] Algorithm \[alg:approxMISonVPG\] is an $O(n^3)$-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on $G$.

Clearly, the paths in $I_L$ are disjoint from those in $I_R$; so, $S(I_L)\cup S(I_R)$ is an independent set. Therefore, the solution returned by the algorithm is a feasible solution for [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $G$. Let $T(n)$ denote the running time of the algorithm on any [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph $G$ with $n$ vertices. If $n\leq 2$, then clearly $T(n)=O(1)$. Otherwise, we first compute $x_{med}$ in $O(n\log n)$ time by sorting all the paths $P$ by $x({\texttt{corner}}(P))$. Then, by the choice of $x_{med}$, we solve two instances of the problem recursively each of which having size $O(n/2)$. Since the algorithm of Keil et al. [@KeilMPV15] takes $O(n^3)$ time, we have $T(n)=2T(n/2)+O(n^3)$, which is solved to $T(n)=O(n^3)$.

Now, let $O^*$ be a maximum independent set in $G$. Moreover, let $O^*_L$, $O^*_R$ and $O^*_M$ denote a maximum independent set for the paths in $I_L$, $I_R$ and $I_{M}$, respectively. We prove by induction on $n$ that $\lvert S\rvert\geq\lvert O^*\rvert/\log n$, hence completing the proof of the lemma. If $n\leq 2$, then the lemma is clearly true. Suppose that the lemma is true for all $m<n$. Notice that since the algorithm directly computes a maximum independent set of $I_M$, we have $\lvert S(I_M)\rvert=\lvert O^*_M\rvert\geq\lvert O^*\cap I_M\rvert$. By induction hypothesis, we know that $$\lvert S(I_L)\rvert\geq\frac{\lvert O^*_L\rvert}{\log(n/2)}\geq\frac{\lvert O^*\cap I_L\rvert}{\log n - 1} \mbox{ and } \lvert S(I_R)\rvert\geq\frac{\lvert O^*_R\rvert}{\log(n/2)}\geq\frac{\lvert O^*\cap I_R\rvert}{\log n - 1}.$$ Since $S(I_L)\cap S(I_R)=\emptyset$, we have $$\begin{aligned}
\lvert S\rvert=\max\{\lvert S(I_L)\cup S(I_R)\rvert, \lvert S(I_M)\rvert\} & \geq\max\{\frac{\lvert O^*\cap I_L\rvert + \lvert O^*\cap I_R\rvert}{\log n-1}, \lvert O^*\cap I_M\rvert\}\\
& \geq\max\{\frac{\lvert O^*\rvert - \lvert O^*\cap I_M\rvert}{\log n-1}, \lvert O^*\cap I_M\rvert\}.\end{aligned}$$ If $\lvert O^*\cap I_M\rvert\geq\lvert O^*\rvert/\log n$, then we are done. Otherwise, $$\begin{aligned}
\frac{\lvert O^*\rvert - \lvert O^*\cap I_M\rvert}{\log n-1}\geq\frac{\lvert O^*\rvert - \lvert O^*\rvert/\log n}{\log n-1}=\frac{\lvert O^*\rvert}{\log n},\end{aligned}$$ which proves the induction step.

#### Original problem.

To approximate the original problem in which [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}consists of all types of paths (i.e., {[$\ulcorner$]{}, [$\llcorner$]{}, [$\urcorner$]{}, [$\lrcorner$]{}, $|$, $-$}), we run the above algorithm four times once for each of the four types of paths (recall that we defined no-bend paths as [$\llcorner$]{}-type paths), and then return the largest solution as the final answer. By Lemma \[lem:approxMISonVPGfactor\], our final answer is at least $\frac{1}{4}(\log n)$ times an optimal solution for the original problem, where $\lvert$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$\rvert=n$. This gives us the main result of this section.

\[thm:approxMISonVPG\] There exists an $O(n^3)$-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on any [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with $n$ vertices.

Dominating Set {#sec:dominatingSet}
==============

In this section, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on *one-string* [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We first give our $O(1)$-approximation algorithm for this problem on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs in Section \[subsec:MDSonBVPG\], and then will present our results for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[subsec:MDSonBEPG\].

One-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}Graphs {#subsec:MDSonBVPG}
-----------------------------------------------------------------------------

Recall that Asinowski et al. [@AsinowskiCGLLS12] proved that every circle graph is a one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph. Since [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is known to be [<span style="font-variant:small-caps;">APX</span>-hard ]{}on circle graphs [@DamianP06], the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem becomes [<span style="font-variant:small-caps;">APX</span>-hard ]{}also on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. In the following, we give an $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. To our knowledge, this is the first $O(1)$-approximation algorithm for this problem on such graphs. For the rest of this section, let $G$ be a one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with $n$ vertices, and let $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ denote its string representation.

Our algorithm is based on first formulating the problem on $G$ as a hitting set problem and then computing a small $\varepsilon$-net for the corresponding instance of the hitting set problem. Having such an $\varepsilon$-net along with the technique of Brönnimann and Goodrich [@BronnimannG95] gives us an $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$. We first formulate [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ as a hitting set problem and then describe our $\varepsilon$-net for it.

[r]{}[0.35]{} ![image](newCross-5) \[fig:aCross\]

#### Hitting set.

A *set system* is a pair $\mathcal{R}=(\mathcal{U}, \mathcal{S})$, where $\mathcal{U}$ is a ground set of elements and $\mathcal{S}$ is a collection of subsets of $\mathcal{U}$. A *hitting set* for the set system $(\mathcal{U}, \mathcal{S})$ is a subset $M$ of $\mathcal{U}$ such that $M\cap S\neq \emptyset$ for all $S\in\mathcal{S}$; we call each element of $\mathcal{U}$ a *hitting element*. For the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on $G$, we construct the set system $(\mathcal{U}, \mathcal{S})$ as follows. Let $P$ be any path in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}and assume w.l.o.g. that it is a [$\llcorner$]{}-type path. We associate a *cross* $c:=(\ell_H, \ell_V)$ to $P$ in which $\ell_H$ and $\ell_V$ denote its horizontal and vertical segments, respectively; we call $\ell_H$ and $\ell_V$ the *supporting segments* of $c$. The left endpoint of $\ell_H$ is $x:=(x({\texttt{corner}}(P))-\delta, y({\texttt{corner}}(P)))$ and its right endpoint is $x':=((x({\texttt{hTip}}(P))-3\delta, y({\texttt{corner}}(P)))$ in which $\delta:=s/4$, where $s$ is the length of a grid edge. See the figure on right for an illustration. Similarly, the bottom endpoint of $\ell_V$ is $y:=(x({\texttt{corner}}(P), y({\texttt{corner}}(P))-\delta)$ and its top endpoint is $y':=((x({\texttt{corner}}(P)), y({\texttt{vTip}}(P))-3\delta)$. We denote the cross of $P$ by ${\texttt{cross}}(P)$. The following observation is immediate by the construction of a cross.

\[obs:crossAndPath\] Let $P_u, P_v$ be two paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}. Then, $P_u$ and $P_v$ intersect each other at a grid node if and only if ${\texttt{cross}}(P_u)$ and ${\texttt{cross}}(P_v)$ intersect each other.

To see the hitting elements of the set system, for each path $P\in$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}, we add into $\mathcal{U}$ both of the supporting segments of ${\texttt{cross}}(P)$. We say that a hitting element $e\in \mathcal{U}$ *hits* a cross $c$ if $e$ intersects one of the supporting segments of $c$; we assume that the hitting elements corresponding to supporting segments of $c$ also hit $c$. To compute $\mathcal{S}$, consider the set of elements of $\mathcal{U}$ hitting a cross $c$ and let $\mathcal{S}$ be the collection of these sets; notice that there is a set in $\mathcal{S}$ for each cross $c$. This forms the set system $(\mathcal{U}, \mathcal{S})$ corresponding to [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$. For a set $S\in\mathcal{S}$, we say that an element $e\in\mathcal{U}$ *intersects* $S$ if $e\in S$.

\[lem:ifMDSthenMHS\] If there is a dominating set of size $k$ on the one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph $G$, then there is a hitting set of size at most $2k$ on the set system $(\mathcal{U}, \mathcal{S})$.

\[prf:lem:ifMDSthenMHS\] Let $M$ be a dominating set of size $k$ for $G$. For each path $P\in M$, add the supporting segments of ${\texttt{cross}}(P)$ into $M'$. Clearly, $\lvert M'\rvert=2k$. Now, consider a set $S\in\mathcal{S}$ and let $P$ and $c$ denote its corresponding path and cross, respectively. Since $M$ is a dominating set, either $P\in M$ or $P'\in M$ for some path $P'$ intersecting $P$. If $P\in M$, then clearly $S$ is intersected by some segment in $M'$. If $P'\in M$, then $c$ intersects ${\texttt{cross}}(P')$ by Observation \[obs:crossAndPath\] and so at least one of the supporting segments of ${\texttt{cross}}(P')$ (that is in $M'$) intersects $S$.

\[lem:ifMHSthenMDS\] If there is a hitting set of size $k$ on the set system $(\mathcal{U}, \mathcal{S})$, then there is a dominating set of size at most $k$ on $G$.

\[prf:lem:ifMHSthenMDS\] Suppose that $M'$ is a hitting set of size $k$ for the set system $(\mathcal{U}, \mathcal{S})$. For each hitting element $e\in M'$: add $P$ to $M$, where $P$ is the path for which $e$ is a supporting segment of ${\texttt{cross}}(P)$. Clearly, $\lvert M\rvert\leq k$. To see why $M$ is a dominating set for $G$, consider any path $P$ and let $S\in\mathcal{S}$ denote its corresponding set. Since $M'$ is a hitting set, there must be a hitting element $e'\in M'$ that intersects $S$. Let $P'$ be the path for which $e'$ is a supporting segment of ${\texttt{corner}}(P')$; notice that $P'\in M$. If $P'=P$, then we are done. Otherwise, $e'$ must hit the cross $c$ corresponding to $P$ since $c\in S$. This means that the cross corresponding to $P'$ intersects $c$ and so $P$ is intersected by $P$ by Observation \[obs:crossAndPath\].

#### Approximation using $\varepsilon$-nets.

An [*$\varepsilon$-net*]{} for a set system $\mathcal{R}=(\mathcal{U}, \mathcal{S})$ is a subset $N$ of $\mathcal{U}$ such that every set $S$ in $\mathcal{S}$ with size at least $\varepsilon\cdot\lvert\mathcal{U}\rvert$ has a non-empty intersection with $N$. Brönnimann and Goodrich [@BronnimannG95] introduced the following iterative-doubling approach for turning algorithms for finding $\varepsilon$-nets into approximation algorithms for hitting sets of minimum size. For a given set system $\mathcal{R}=(\mathcal{U},\mathcal{S})$ and any $r>0$, a *net finder* is a polynomial-time algorithm that computes an $(1/r)$-net of $\mathcal{R}$ whose size is at most $s(r)$ for some computable function $s$. Moreover, given a subset $H\subset \mathcal{U}$, a [*verifier*]{} is a polynomial-time algorithm that outputs whether the set $H$ is a hitting set; if it is not, then the verifier returns a non-empty set $S\in \mathcal{S}$ for which $H$ does not hit $S$.

[@BronnimannG95] \[thm:epsNet\] Let $\mathcal{R}$ be a set system that admits both a polynomial-time net finder and a polynomial-time verifier. Then, there exists a polynomial-time algorithm that computes a hitting set of size at most $s(4 \cdot \textsc{OPT})$, where <span style="font-variant:small-caps;">OPT</span> is the size of a minimum hitting set, and $s(r)$ is the size of the $(1/r)$-net.

Clearly, the hitting set problem corresponding to [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ has a polynomial-time verifier. In the following, we compute an $\varepsilon$-net finder of size $O(1/\varepsilon)$ for the set system $(\mathcal{U}, \mathcal{S})$. Then, we prove that this result combined by Lemmas \[lem:ifMDSthenMHS\]—\[lem:ifMHSthenMDS\] and Theorem \[thm:epsNet\], gives an $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$.

Unfortunately, we were unable to compute an $\varepsilon$-net of size $O(1/\varepsilon)$ directly for $(\mathcal{U},\mathcal{S})$. Instead, we first compute such an $\varepsilon$-net for a “one-dimensional” variant of our hitting set problem and then show that re-using such an $\varepsilon$-net twice would result in the desired $\varepsilon$-net. Informally speaking, the idea is that although the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on $G$ is not “decomposable” into horizontal and vertical instances, the $\varepsilon$-net corresponding to our set system $(\mathcal{U},\mathcal{S})$ for this problem is. In the following, we first formulate a one-dimensional variant of our hitting set problem and then show that it admits a small-size $\varepsilon$-net.

Recall the set system $(\mathcal{U}, \mathcal{S})$ corresponding to [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ that we constructed just before Lemma \[lem:ifMDSthenMHS\]. Let $\mathcal{U}_H$ denote the set of only-horizontal hitting elements of $\mathcal{U}$, and consider the set system $(\mathcal{U}_H, \mathcal{S})$. Representing each cross by its vertical supporting segment only, the minimum hitting set problem on $(\mathcal{U}_H, \mathcal{S})$ reduces to the following problem: given a set of horizontal line segments $\mathcal{H}$ and a set of vertical line segments $\mathcal{V}$, find a minimum-cardinality set $S\subseteq\mathcal{H}$ such that every line segment in $\mathcal{V}$ is intersected by $S$. This problem is known as the *orthogonal segment covering* problem and is known to be <span style="font-variant:small-caps;">NP</span>-complete [@KatzMN05].

\[lem:oneDmdsVhitting\] The minimum hitting set problem on $(\mathcal{U}_H, \mathcal{S})$ reduces to the orthogonal segment covering problem.

\[prf:lem:oneDmdsVhitting\] ($\Rightarrow$) Let $M$ be a feasible solution for the minimum hitting set problem on $(\mathcal{U}_H, \mathcal{S})$. If a hitting element $e$ hits a cross $c$, then it intersects one of its supporting segments $s$. Let $P$ denote the path in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}corresponding to cross $c$. Since $e$ is horizontal, $s$ cannot be horizontal because if $e$ intersects the horizontal supporting segment of $P$ (i.e., $s$), then ${\texttt{vPart}}(P)$ and ${\texttt{hPart}}(P')$ must intersect each other in more than one point, where $P'$ is the path in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}for which $e$ is a supporting segment. This contradicts the fact that $G$ is a one-string [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph. Therefore, $s$ is vertical and so for any feasible solution $M$, we have a feasible solution for the orthogonal segment covering problem with the same size.

($\Leftarrow$) Clearly, a feasible solution to the minimum segment covering problem is also a feasible solution to the minimum hitting set problem with the same size.

For the orthogonal segment covering problem, Biedl et al. [@BiedlCLMMV16] showed (using the linear union-complexity ideas of Clarkson and Varadarajan [@ClarksonV07]) that there exists an $\varepsilon$-net finder of size $s(1/\varepsilon)\in O(1/\varepsilon)$. Therefore, by Lemma \[lem:oneDmdsVhitting\], we have the following result.

\[lem:epsilonUH\] There exists an $\varepsilon$-net of size $O(1/\varepsilon)$ for the minimum hitting set problem on $(\mathcal{U}_H, \mathcal{S})$.

\[lem:approxMHSonU\] There exists a polynomial-time $O(1)$-approximation algorithm for the minimum hitting set problem on $(\mathcal{U},\mathcal{S})$.

\[prf:lem:approxMHSonU\] To prove the lemma, it suffices by Theorem \[thm:epsNet\] to compute an $\varepsilon$-net of size $O(1/\varepsilon)$ for $(\mathcal{U},\mathcal{S})$. Define the set system $(\mathcal{U}_V, \mathcal{S})$ similar to $(\mathcal{U}_H, \mathcal{S})$; that is, $\mathcal{U}_V$ is the set of only-vertical hitting elements of $\mathcal{U}$. By Lemma \[lem:epsilonUH\], let $N_H$ (resp., $N_V$) be an $(\varepsilon/2)$-net of size $O(1/\varepsilon)$ for the corresponding one-dimensional variant of the hitting set problem on $(\mathcal{U}_H, \mathcal{S})$ (resp., $(\mathcal{U}_V, \mathcal{S})$). Let $N:=N_H\cup N_V$. Clearly, $N$ has size $O(1/\varepsilon)$. We now prove that $N$ is an $\varepsilon$-net.

Let $S\in\mathcal{S}$ such that $\lvert S\rvert\geq\varepsilon\cdot\lvert\mathcal{U}\rvert$. We need to show that $N\cap S\neq\emptyset$. Notice that having $\lvert S\rvert\geq\varepsilon\cdot\lvert\mathcal{U}\rvert$ means that there exists a cross $c$ that is hit by $\varepsilon\cdot\lvert\mathcal{U}\rvert$ hitting elements. Assume w.l.o.g. that at least half of these hitting elements are horizontal. Then, the vertical supporting segment $s$ of $c$ intersects at least $\varepsilon\cdot\lvert\mathcal{U}/2\rvert$ horizontal hitting elements of $\mathcal{U}$. By definition of an $(\varepsilon/2)$-net, there is a hitting element $e\in N_H$ that intersects $s$. Therefore, $e$ hits cross $c$ and so $e\in N\cap S$.

Putting everything together, we can prove the main result of this section.

\[thm:approxMDSonVPG\] There exists a polynomial-time $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on any one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph.

Let $G$ be any one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with its string representation $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$. We show how to obtain a constant-factor approximation solution for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ in polynomial time and so proving the theorem.

First, compute the set system $(\mathcal{U},\mathcal{S})$ corresponding to [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}as described above. Let ${\textsc{OPT$_{DS}$}}$ (resp., ${\textsc{OPT$_{HS}$}}$) denote an optimal solution for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ (resp., for the minimum hitting set problem on $(\mathcal{U},\mathcal{S})$). By Lemma \[lem:ifMDSthenMHS\], we know that $\lvert{\textsc{OPT$_{HS}$}}\rvert\leq 2\lvert{\textsc{OPT$_{DS}$}}\rvert$. By Lemma \[lem:approxMHSonU\], let $S_{HS}$ be a constant-factor approximation to the minimum hitting set problem on $(\mathcal{U},\mathcal{S})$; that is, $\lvert S_{HS}\rvert\leq c\cdot\lvert {\textsc{OPT$_{HS}$}}\rvert$ for some constant $c>0$. Apply Lemma \[lem:ifMHSthenMDS\] to $S_{HS}$ and let $S_{DS}$ be a feasible solution for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$; notice that $\lvert S_{DS}\rvert\leq\lvert S_{HS}\rvert$. The set system $(\mathcal{U},\mathcal{S})$, $S_{HS}$ and $S_{DS}$ can each be computed in polynomial time. Therefore, $$\frac{\lvert S_{DS}\rvert}{\lvert{\textsc{OPT$_{DS}$}}\rvert}\leq\frac{\lvert S_{HS}\rvert}{\lvert{\textsc{OPT$_{DS}$}}\rvert}\leq \frac{2\lvert S_{HS}\rvert}{\lvert{\textsc{OPT$_{HS}$}}\rvert}\leq 2c.$$

That is, $S_{DS}$ is an $O(1)$-approximation solution for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$, which can be computed in polynomial time.

[<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}Graphs {#subsec:MDSonBEPG}
------------------------------------------------------------------

In this section, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We first show that the problem is [<span style="font-variant:small-caps;">APX</span>-hard ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, even if only two types of paths are allowed in the graph; hence, ruling out the possibility of a PTAS for this problem unless <span style="font-variant:small-caps;">P=NP</span>. Then, we give $c$-approximation algorithms for this problem on two subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, for $c\in\{2, 3\}$.

#### <span style="font-variant:small-caps;">APX</span>-hardness.

To show the <span style="font-variant:small-caps;">APX</span>-hardness, we give an <span style="font-variant:small-caps;">L</span>-reduction from the [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}problem on graphs with maximum-degree three to the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs; [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}is known to be [<span style="font-variant:small-caps;">APX</span>-hard ]{}on graphs with maximum-degree three [@AlimontiK00]. Before describing the reduction, let us give a formal definition of <span style="font-variant:small-caps;">L</span>-reduction [@PapadimitriouY91] as a reminder. Let $\Pi$ and $\Pi'$ be two optimization problems with the cost functions $c_\Pi(.)$ and $c_{\Pi'}(.)$, respectively. We say that *$\Pi$ $L$-reduces to $\Pi'$* if there are two polynomial-time computable functions $f$ and $g$ such that the followings hold.

For any instance $x$ of $\Pi$, $f(x)$ is an instance of $\Pi'$.

If $y$ is a solution to $f(x)$, then $g(y)$ is a solution for $x$.

There exists a constant $\alpha>0$ such that $OPT_{\Pi'}(f(x))\leq\alpha OPT_\Pi(x)$, where $OPT_Y(x)$ denotes the cost of an optimal solution for problem $Y$ on its instance $x$.

There exists a constant $\beta>0$ such that for every solution $y$ for $f(x)$, $$|OPT_\Pi(x)-c_\Pi(g(y))|\leq \beta |OPT_{\Pi'}(f(x))-c_{\Pi}(y)|,$$ where $|x|$ denotes the absolute value of $x$.

\[lem:mdsApx\] [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}on graphs with maximum-degree three is <span style="font-variant:small-caps;">L</span>-reducible to [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

\[prf:lem:mdsApx\] Consider an arbitrary instance $I$ of [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}on graphs of maximum-degree three; let $G=(V, E)$ be the graph corresponding to $I$ and let $k$ be size of the smallest vertex cover in $G$. First, let $u_1, \dots, u_n$ be an arbitrary ordering of the vertices of $G$, where $n=\lvert V\rvert$. In the following, we give a computable function $f$ that takes $I$ as input and outputs an instance $f(I)$ of [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}in polynomial time, where $f(I)$ consists of a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph such that its paths are of either [$\ulcorner$]{}-type or [$\lrcorner$]{}-type only.

We first describe the vertex gadgets. For each vertex $u_i$, $1\leq i\leq n$, construct a horizontal [$\ulcorner$]{}-type $\Gamma^h_i$ and a vertical [$\ulcorner$]{}-type $\Gamma^v_i$, and connect them as shown in Figure \[fig:mdsApx\]. We call the big [$\ulcorner$]{}-type path used in the connection of $\Gamma^h_i$ and $\Gamma^v_i$ the *big connector* $C_i$ of $i$, and the two small (blue, dashed) [$\ulcorner$]{}-type paths the *small connectors* of $i$. For each edge $(u_i, u_j)\in E$, where $i<j$, we add two small paths, one of [$\ulcorner$]{}-type and one of [$\lrcorner$]{}-type, at the intersection point of $\Gamma^v_i$ and $\Gamma^h_j$ such that each of them becomes adjacent to both $\Gamma^v_i$ and $\Gamma^h_j$; see the two (red, dash-dotted) [$\ulcorner$]{}-type and [$\lrcorner$]{}-type paths at the intersection of $\Gamma^v_1$ and $\Gamma^h_2$ in Figure \[fig:mdsApx\]. We denote this pair of paths by $E_{i,j}$; notice that the paths of $E_{i,j}$ are not adjacent to each other (they only share a grid node). This gives the instance $f(I)$ of [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs; let $G'$ be the corresponding [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph. Notice that $f$ is a polynomial-time computable function. In the following, we denote an optimal solution for the instance $X$ of a problem by $s^*(X)$. We now prove that all the four conditions of $L$-reduction hold.

First, let $M$ be a vertex cover of $G$ of size $k$. Denote by $\Gamma^h[M] := \{\Gamma^h_i | u_i\in M\}$ the set of horizontal paths induced by $M$ and define $\Gamma^v[M]$ analogously. Moreover, let $C[M] := \{C_i | u_i \notin M\}$ be the set of big connectors whose corresponding vertex is not in $M$. We show that $D := \Gamma^h[M]\cup \Gamma^v[M]\cup C[M]$ is a dominating set of $G'$. Let $\gamma$ be a path. If $\gamma$ is any of the paths in $E_{i,j}$ for some $i,j$, then $u_i\in M$ or $u_j\in M$ because $M$ is a vertex cover; assume w.l.o.g. that $u_i\in M$. Then, $\Gamma^h_i, \Gamma^v_i\in D$ and so $\gamma$ must be dominated. If $\gamma$ is a connector of $i$ for some $i$ (either big or small), then there are two cases: if $u_i\in M$, then $\Gamma^h_i, \Gamma^v_i\in D$ and so the connector is dominated. If $u_i\notin M$, then $C_i\in C[M]$ and $C[M]\subseteq D$; hence, the connector is again dominated. Finally, suppose that $\gamma$ is $\Gamma^h_i$ (resp., $\Gamma^v_i$) for some $i$. If $u_i\in M$, then $\Gamma^h_i, \Gamma^v_i\in D$ and so $\Gamma^h_i$ (resp., $\Gamma^v_i$) is dominated. If $u_i\notin M$, then $C_i\in C[M]$ and $C[M]\subseteq D$; hence, $\Gamma^h_i$ (resp., $\Gamma^v_i$) is again dominated. This shows that $D$ is a dominating set for $G'$.

![An illustration in support of the construction in the proof of Lemma \[lem:mdsApx\].[]{data-label="fig:mdsApx"}](newColorApxGadget){width="50.00000%"}

Second, let $D$ be an arbitrary dominating set on $G'$. First, notice that we can construct a dominating set $D'$ for $G'$ such that $\lvert D'\rvert\leq\lvert D\rvert$ and $D'$ consists of only $\Gamma^h_i$ and $\Gamma^v_i$ for some $i$ or a big connector. This is because

any path dominated by a small connector is also dominated by some big connector, and

\[inl:domiantingEij\] any path dominated by a path from $E_{i,j}$ is also dominated by $\Gamma^v_i$ or $\Gamma^h_j$.

For , in particular, if exactly one of the paths in $E_{i,j}$ is in $D$, then we can replace it with one of $\Gamma^v_i$ or $\Gamma^h_j$ arbitrarily. Moreover, if both paths in $E_{i,j}$ are in $D$, then we can replace both of them with $\Gamma^v_i$ and $\Gamma^h_j$. As such, $\lvert D'\rvert\leq\lvert D\rvert$ and $D'$ is a feasible dominating set for $G'$. Now, define $\Gamma_{{\texttt{both}}}[D'] = \{\Gamma^h_i,\Gamma^v_i | \Gamma^h_i,\Gamma^v_i \in D'\}$; i.e., the paths of a vertex $u_i$, where *both* its horizontal and its vertical copies appear in $D'$. Also, define $\Gamma_{{\texttt{one}}}[D']$ to be the remaining paths of type $\Gamma^h_i$ and $\Gamma^v_i$; i.e., those of $u_i$, where *only* one of its copies appears in $D'$. Finally, let $C[D']$ be the set of big connectors in $D'$. We denote $\Gamma_{{\texttt{both}}}[D']\cup\Gamma_{{\texttt{one}}}[D']$ by $\Gamma[D']$. Now, let $M := \{u_i | \Gamma^h_i\in D' \mbox{ or } \Gamma^v_i\in D'\}$. Since all $E_{i,j}$ are dominated by $\Gamma[D']$, $M$ is a vertex cover.

Third, observe that $\lvert\Gamma^h[M]\rvert=\lvert\Gamma^v[M]\rvert=\lvert M\rvert=k$ and also $\lvert C[M]\rvert=n-k$. Given that $G$ has degree three, $k\geq n/4$ and so $\lvert s^*(f(I))\rvert\leq n-k+k+k\leq 5k\leq 5\lvert s^*(I)\rvert$.

Finally, to dominate all connectors of $i$, we must have $C_i\in D'$ or $\Gamma^h_i, \Gamma^v_i\in D'$; this indeed holds for all $i$. Thus, $\lvert C[D']\rvert+\lvert \Gamma_{{\texttt{both}}}[D']\rvert/2\geq n$. Moreover, $\lvert\Gamma_{{\texttt{one}}}[D']\rvert+\lvert\Gamma_{{\texttt{both}}}[D']\rvert/2\geq k$ since $M$ is a vertex cover of $G$. Therefore, $\lvert D'\rvert\geq\lvert\Gamma_{{\texttt{both}}}[D']\rvert+\lvert\Gamma_{{\texttt{one}}}[D']\rvert+\lvert C[D']\rvert\geq\lvert\Gamma_{{\texttt{one}}}[D']\rvert+\lvert\Gamma_{{\texttt{both}}}[D']\rvert/2+n\geq k+n$. By this and our earlier inequality $\lvert s^*(f(I))\rvert\leq n-k+k+k$, we have $\lvert s^*(f(I))\rvert=n+k$. Now, suppose that $\lvert D\rvert=\lvert s^*(f(I))\rvert+c$ for some $c\geq 0$. Then, $$\begin{aligned}
& \lvert D\rvert-\lvert s^*(f(I))\rvert=c\\
& \Rightarrow \lvert D\rvert-(n+k)=c\\
& \Rightarrow \lvert D'\rvert-(n+k)\leq c\\
& \Rightarrow \lvert\Gamma_{{\texttt{one}}}[D']\rvert+\lvert\Gamma_{{\texttt{both}}}[D']\rvert/2+n-(n+k)\leq c\\
& \Rightarrow \lvert\Gamma_{{\texttt{one}}}[D']\rvert+\lvert\Gamma_{{\texttt{both}}}[D']\rvert/2-k\leq c\\
& \Rightarrow \lvert M\rvert-\lvert s^*(I)\rvert\leq c.\end{aligned}$$ That is, $\lvert M\rvert-\lvert s^*(I)\rvert\leq\lvert D\rvert-\lvert s^*(f(I))\rvert$. This concludes our <span style="font-variant:small-caps;">L</span>-reduction from [<span style="font-variant:small-caps;">Minimum Vertex Cover</span> ]{}on graphs of maximum-degree three to [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs with $\alpha=5$ and $\beta=1$.

Our reduction reveals that every path in the constructed [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph $G'$ is a [$\ulcorner$]{}-type or a [$\lrcorner$]{}-type path. Therefore, by Lemma \[lem:mdsApx\], we have the following theorem.

\[thm:mdsApx\] The [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem is [<span style="font-variant:small-caps;">APX</span>-hard ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, even if all the paths in the graph are `x`-type paths, for some $\texttt{x}\in\{$[$\ulcorner$]{}, [$\lrcorner$]{}$\}$. Thus, there exists no PTAS for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs unless <span style="font-variant:small-caps;">P=NP</span>.

#### Approximation algorithms.

In this section, we give constant-factor approximation algorithms for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on two subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. Let us first define these subclasses.

First, we consider a subclass of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in which every path of each [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph intersects two axis-parallel lines that are normal to each other. Recall that this is the variant for which Lahiri et al. [@LahiriMS15] gave an exact solution for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem when the input graph is a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph: they showed that the induced graph is a co-comparability graph and so solved the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem exactly. However, the graph induced by this variant when considering [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs is not necessarily a co-comparability graph; this is mainly because two paths intersecting in only one point in a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph are not adjacent. Here, we give a 2-approximation algorithm for this problem on such [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We call this subclass, the class of <span style="font-variant:small-caps;">Double-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. Next, we consider a less-restricted subclass of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in which every path of each [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph intersects only a vertical line. We show that the same algorithm is a 3-approximation algorithm for the problem on this subclass of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, albeit considering a “non-containment” assumption. We call this subclass, the class of <span style="font-variant:small-caps;">Vertical-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

Before describing the algorithms, let us define an ordering $\prec$ on the paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}as follows. The paths appear in the ordering by the $y$-coordinate of their corners from bottom to top and then from left to right whenever they have the same $y$-coordinate; that is, $P\prec P'$ for two paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}, if and only if $y({\texttt{corner}}(P))<y({\texttt{corner}}(P'))$ or $y({\texttt{corner}}(P))=y({\texttt{corner}}(P'))$ but $x({\texttt{corner}}(P))<x({\texttt{corner}}(P'))$. Notice that this ordering is well defined by out weak general-position assumption. For the rest of this section, we assume that every path in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}is a [$\llcorner$]{}-type path.

[r]{}[0.35]{} ![image](dcMDS-2) \[fig:dcMDS\]

#### Double-crossing [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

Recall that in a <span style="font-variant:small-caps;">Double-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph, we are given a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph $G$, a horizontal line $L$ and a vertical line $\ell$ both on the grid $\mathcal{G}$ such that $L$ and $\ell$ intersect each other and $P$ intersects both $L$ and $\ell$ for all $P\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}(hence, ${\texttt{corner}}(P)$ lies in the lower-left quadrant defined by $L$ and $\ell$). Our 2-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem is as follows; let $S$ be an initially-empty set. For each path $P$ in the increasing order $\prec$: add $P$ into $S$ and set [$\mathcal{P}_{{\texttt{edg}}}$ ]{}$:=$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$\setminus N[P]$. See Algorithm \[alg:approxLineMDS\]. Clearly, the algorithm terminates in time polynomial in $\lvert$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$\rvert$, and $S$ is a feasible solution for the problem. To see the approximation factor, let $OPT$ be an optimal solution for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on $G$; notice that by deleting the paths in $S\cap OPT$ we can assume that $S\cap OPT=\emptyset$. This means that every path in $S$ must be adjacent to at least one path in $OPT$.

\[lem:2crossingMDS\] Any path in $OPT$ is adjacent to at most two distinct paths in $S$.

Suppose for a contradiction that there exists a path $P\in OPT$ that is adjacent to three distinct paths $P_1, P_2$ and $P_3$ of $S$. W.l.o.g., assume that $P_i, P_j\in {\texttt{vNeighbor}}(P)$ for some $i<j\in\{1,2,3\}$. This means that $x({\texttt{corner}}(P))=x({\texttt{corner}}(P_i))=x({\texttt{corner}}(P_j))$. Since $i<j$, we have $y({\texttt{corner}}(P_i))<y({\texttt{corner}}(P_j))$. Moreover, since all the paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}intersect the horizontal line $L$, the three paths $P, P_i$ and $P_j$ must all intersect $L$ at the same point and so they share the topmost vertical grid edge below $L$ on which ${\texttt{vPart}}(P)$ lies; see the figure on right. Thus, $P_i$ and $P_j$ are adjacent in $G$. Since $y({\texttt{corner}}(P_i))<y({\texttt{corner}}(P_j))$, we have $P_i\prec P_j$ and so $P_j$ is removed from [$\mathcal{P}_{{\texttt{edg}}}$ ]{}when the algorithm adds $P_i$ to $S$. So, $P_j\notin S$ — a contradiction.

Since every path in $S$ must be adjacent to at least one path in $OPT$ and any path in $OPT$ can be adjacent to at most two distinct paths in $S$ by Lemma \[lem:2crossingMDS\], we have $\lvert S\rvert\leq 2\lvert OPT\rvert$. Therefore, we have the following theorem.

\[thm:2crossingMDS\] There exists a polynomial-time 2-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on <span style="font-variant:small-caps;">Double-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

$S\gets \emptyset$; $S\gets S\cup P$; [$\mathcal{P}_{{\texttt{edg}}}$ ]{}$\gets$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$\setminus N[P]$; $S$;

#### Vertical-crossing [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

Here, we are given a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph $G$ and a vertical line $\ell$ on the grid $\mathcal{G}$ such that ${\texttt{hPart}}(P)$ intersects $\ell$ for all $P\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}. Moreover, we make a *non-containment assumption* in the sense that the vertical segment of no path is entirely contained in that of any other path in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}; that is, for every two paths $P, P'\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}such that $P\in{\texttt{vNeighbor}}(P')$, neither ${\texttt{vPart}}(P)\subseteq{\texttt{vPart}}(P')$ nor ${\texttt{vPart}}(P')\subseteq{\texttt{vPart}}(P)$. We prove that Algorithm \[alg:approxLineMDS\] is a 3-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on <span style="font-variant:small-caps;">Vertical-crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

\[thm:approxGPrim\] Algorithm \[alg:approxLineMDS\] is a 3-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on <span style="font-variant:small-caps;">Vertical-crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

\[prf:thm:approxGPrim\] Let $G$ be any <span style="font-variant:small-caps;">Vertical-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph. Moreover, let $OPT$ be an optimal solution for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on $G$ and let $S$ be the solution returned by Algorithm \[alg:approxLineMDS\]. Again, we can assume that $S\cap OPT=\emptyset$. Thus, every path in $S$ must be dominated by at least one path in $OPT$. In the following, we show that any path in $OPT$ can dominate at most three distinct paths in $S$ and so prove that $\lvert S\rvert\leq 3\lvert OPT\rvert$. Let $P$ be any path in $OPT$. We show that $\lvert S\cap {\texttt{hNeighbor}}(P)\rvert\leq 1$ and $\lvert S\cap {\texttt{vNeighbor}}(P)\rvert\leq 2$.

First, suppose for a contradiction that there are two paths $P_1,P_2\in S\cap{\texttt{hNeighbor}}(P)$; assume w.l.o.g. that $P_1\prec P_2$. Notice that $y({\texttt{corner}}(P))=y({\texttt{corner}}(P_1))=y({\texttt{corner}}(P_2))$. Thus, since all the three paths $P, P_1$ and $P_2$ intersect the vertical line $\ell$, we conclude that they all intersect $\ell$ at the same point. Therefore, they share the rightmost horizontal grid edge to the left of $\ell$ on which ${\texttt{hPart}}(P)$ lies. This means that $P_1$ and $P_2$ are adjacent in $G$. Since $P_1\prec P_2$, Algorithm \[alg:approxLineMDS\] removes $P_2$ from [$\mathcal{P}_{{\texttt{edg}}}$ ]{}when adding $P_1$ into $S$; that is, $P_2\notin S$ — a contradiction. So, $\lvert S\cap {\texttt{hNeighbor}}(P)\rvert\leq 1$.

Now, suppose for a contradiction that there are three paths $P_1, P_2, P_3\in S\cap{\texttt{vNeighbor}}(P)$; assume w.l.o.g. that $P_1\prec P_2\prec P_3$. Notice that $x({\texttt{corner}}(P))=x({\texttt{corner}}(P_i))$ for all $1\leq i\leq 3$. Consider $y({\texttt{corner}}(P))$. Then, for at least two paths $P_i, P_j$, where $i<j\in\{1,2,3\}$, we have either $y({\texttt{corner}}(P_i)), y({\texttt{corner}}(P_j))>y({\texttt{corner}}(P))$ or $y({\texttt{corner}}(P_i)), y({\texttt{corner}}(P))<y({\texttt{corner}}(P))$ (equality does not happen due to our weak general-position assumption).

-   If $y({\texttt{corner}}(P_i)), y({\texttt{corner}}(P_j))<y({\texttt{corner}}(P))$, then ${\texttt{vPart}}(P_i)$ and ${\texttt{vPart}}(P_j)$ both share with $P$ the bottommost vertical grid edge on which ${\texttt{vPart}}(P)$ lies, implying that $P_i$ and $P_j$ are adjacent in $G$. Since $i<j$, we have $P_i\prec P_j$ and so Algorithm \[alg:approxLineMDS\] removes $P_j$ from $G$ when adding $P_i$ to $S$. So, $P_j\notin S$ — a contradiction.

-   If $y({\texttt{corner}}(P_i)), y({\texttt{corner}}(P_j))>y({\texttt{corner}}(P))$, then $x({\texttt{vTip}}(P_i))>x({\texttt{vTip}}(P))$ and $x({\texttt{vTip}}(P_j))>x({\texttt{vTip}}(P))$ because otherwise ${\texttt{vPart}}(P_i)\subseteq {\texttt{vPart}}(P)$ or ${\texttt{vPart}}(P_j)\subseteq {\texttt{vPart}}(P)$, which is a contradiction to the non-containment assumption of paths in $G$. Since $i<j$, we have $P_i\prec P_j$. Therefore, $P_i$ and $P_j$ share the topmost vertical grid edge on which ${\texttt{vPart}}(P)$ lies, meaning that $P_i$ and $P_j$ are adjacent in $G$. So, Algorithm \[alg:approxLineMDS\] removes $P_j$ when adding $P_i$ into $S$ — a contradiction to $P_j\in S$.

Therefore, $\lvert S\cap {\texttt{hNeighbor}}(P)\rvert\leq 1$ and $\lvert S\cap {\texttt{vNeighbor}}(P)\rvert\leq 2$. This completes the proof of the theorem.

Conclusion {#sec:conclusion}
==========

In this paper, we considered the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problems on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. For [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, we gave an $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem, and an $O(1)$-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem when the input graph is one-string. For [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, we proved that [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is <span style="font-variant:small-caps;">APX</span>-hard (even if the graph has only two types of paths), ruling out the existence of a PTAS unless <span style="font-variant:small-caps;">P=NP</span>. We also gave $c$-approximation algorithms for this problem on two subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, for $c\in\{2, 3\}$. We conclude the paper by the following open problems:

-   Is there an $O(1)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs? Also, does the problem admit a PTAS or it is <span style="font-variant:small-caps;">APX</span>-hard?

-   Our $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs relies on the fact that the input graph is one-string (in the proof of Lemma \[lem:oneDmdsVhitting\], in particular); is there an $O(1)$-approximation algorithm for this problem on any [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph?

-   Although graph $G'$ in our <span style="font-variant:small-caps;">APX</span>-hardness consists of two types of paths, we believe that the problem remains [<span style="font-variant:small-caps;">APX</span>-hard ]{}even if only one type of paths are allowed. Is the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem [<span style="font-variant:small-caps;">APX</span>-hard ]{}on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, if the graph consists of only one type of paths?

-   Is there an $O(1)$-approximation algorithm for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs?

-   Is the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem <span style="font-variant:small-caps;">NP</span>-hard on <span style="font-variant:small-caps;">Vertical-Crossing</span> [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs?

[^1]: We note here that, unlike the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem, [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}is polynomial-time solvable on circle graphs [@NashG10].
