# Approximating Minimum Dominating Set on String Graphs

Dibyayan Chakraborty Indian Statistical Institute, Kolkata, India. E-mail:
<EMAIL_ADDRESS>Sandip Das Indian Statistical Institute, Kolkata, India.
E-mail<EMAIL_ADDRESS>Joydeep Mukherjee Indian Statistical
Institute, Kolkata, India. E-mail<EMAIL_ADDRESS>Partially
supported by DST SERB NPDF fellowship (PDF/2016/001647).

###### Abstract

In this paper, we give approximation algorithms for the Minimum Dominating Set
(MDS) problem on _string_ graphs and its subclasses. A _path_ is a simple
curve made up of alternating horizontal and vertical line segments. A _$k$
-bend path_ is a path made up of at most $k+1$ line segments. An L-path is a
$1$-bend path having the shape ‘L’. A _vertically-stabbed- L graph_ is an
intersection graph of L-paths intersecting a common vertical line. We give a
polynomial time $8$-approximation algorithm for MDS problem on vertically-
stabbed-L graphs whose APX-hardness was shown by Bandyapadhyay et al. (MFCS,
2018). To prove the above result, we needed to study the _Stabbing segments
with rays_ (SSR) problem introduced by Katz et al. (Comput. Geom. 2005). In
the SSR problem, the input is a set of (disjoint) leftward-directed rays, and
a set of (disjoint) vertical segments. The objective is to select a minimum
number of rays that intersect all vertical segments. We give a
$O((n+m)\log(n+m))$-time $2$-approximation algorithm for the SSR problem where
$n$ and $m$ are the number of rays and segments in the input. A _unit $k$-bend
path_ is a $k$-bend path whose segments are of unit length. A graph is a _unit
$B_{k}$-VPG graph_ if it is an intersection graph of unit $k$-bend paths. Any
string graph is a unit-$B_{k}$-VPG graph for some finite $k$. Using our result
on SSR-problem, we give a polynomial time $O(k^{4})$-approximation algorithm
for MDS problem on unit $B_{k}$-VPG graphs for $k\geq 0$.

Keywords: Minimum Dominating Set, String graph, $B_{k}$-VPG graph,
Approximation algorithm

##  1 Introduction

A graph $G$ has vertex set $V(G)$ and edge set $E(G)$. A _dominating set_ of a
graph $G$ is a subset $D\subseteq V(G)$ of vertices such that each vertex in
$V(G)\setminus D$ is adjacent to some vertex in $D$. The Minimum Dominating
Set (MDS) problem is to find a minimum cardinality dominating set of a graph
$G$. A _string representation_ of a graph is a collection of simple curves on
the plane such that each curve in the collection represents a vertex of the
graph and two curves intersect if and only if the vertices they represent are
adjacent in the graph. The graphs that have a string representation are called
_string_ graphs.

Many important graph families like _planar_ graphs, _unit disk_ graphs and
_chordal graphs_ are subclasses of string graphs [1, 11]. Indeed, Pach and
Toth [17] proved that the number of string graphs on $n$ labelled vertices is
at least $2^{\frac{3}{4}{\binom{n}{2}}}$, indicating that many graphs are
string graphs. This motivates the search for efficient algorithms for solving
optimisation problems on string graphs. Fox and Pach [10] gave for every
$\epsilon>0$, a polynomial time algorithm for computing the Maximum
Independent set of $k$-string graphs (intersection graphs of curves on the
plane where two curves intersecting at most $k$ times) with approximation
ratio at most $n^{\epsilon}$. While Pawlik et al. [18] proved that triangle-
free _segment graphs_ (intersection graphs of line segments on the plane) can
have arbitrarily high Chromatic Number, Bonnet et al. [4] gave a
subexponential algorithm to color string graphs with three colors. In this
paper, we study the MDS problem on string graphs and its subclasses.

Since split graphs (graphs whose vertex set can be partitioned into a clique
and an independent set) are known to be string graphs, for every $\alpha>0$,
it is not possible to approximate the MDS problem on string graphs with $n$
vertices to within $(1-\alpha)\ln n$ unless $NP\subseteq DTIME(n^{O(\log\log
n)})$ [7]. Hence, researchers have focussed on developing approximation
algorithms for the MDS problem on special classes of string graphs. The
concepts of _bend number_ and _$B_{k}$ -VPG graphs_ (introduced by Asinowski
et al. [1]) become useful in gaining a better understanding of subclasses of
string graphs. A _path_ is a simple curve made up of alternating horizontal
and vertical line segments. A _$k$ -bend path_ is a path made up of at most
$k+1$ line segments. A _$B_{k}$ -VPG representation_ of a graph is a
collection of $k$-bend paths such that each path in the collection represents
a vertex of the graph, and two such paths intersect if and only if the
vertices they represent are adjacent in the graph. The graphs that have a
$B_{k}$-VPG representation are called _$B_{k}$ -VPG graphs_. A graph is said
to be a _VPG graph_ if it is a $B_{k}$-VPG graph for some $k$. Asinowski et
al. [1] showed that the family of VPG graphs are equivalent to the family of
string graphs.

Mehrabi [16] gave an $\epsilon$-net based $O(1)$-approximation algorithm for
the MDS problem on _one-string_ $B_{1}$-VPG graphs (graphs with $B_{1}$-VPG
representation where two curves intersect at most once). Bandyapadhyay et al.
[2] proved APX-hardness for the MDS problem on a special class of $B_{1}$-VPG
graphs, namely _vertically-stabbed- L graph_ (defined below) which was
originally introduced by McGuinness [15]. An L-path is a $1$-bend path having
the shape ‘L’. A _vertically-stabbed- L-representation_ of a graph is a
collection of L-paths and a vertical line such that each path in the
collection intersects the vertical line. Each path in the collection
represents a vertex of the graph and two paths intersect if and only if the
vertices they represent are adjacent in the graph. A graph is a _vertically-
stabbed- L graph_ if it has a vertically-stabbed-L-representation.
Bandyapadhyay et al. [2] proved APX-hardness for the MDS problem on
vertically-stabbed-L graphs by showing that all _circle_ graphs (intersection
graphs of chords of a circle) are vertically-stabbed-L graphs. Many
researchers have studied the MDS problem on circle graphs [5, 8, 9]. Since all
vertically-stabbed-L-graphs are also one-string $B_{1}$-VPG graphs, there is a
$O(1)$-approximation algorithm for the MDS problem on vertically-stabbed-L
graphs (due to Mehrabi [16]). In this paper, we prove the following theorems.

######  Theorem 1.

Given a vertically-stabbed-L-representation of a graph $G$ with $n$ vertices,
there is a polynomial time $8$-approximation algorithm to solve the MDS
problem on $G$.

The time complexity of our algorithm for the MDS problem on vertically-
stabbed-L graph is essentially the time required to solve a linear program
with $(0,1)$-coefficient matrix optimally. To prove the above theorem we
needed to study the _stabbing segment with rays ( SSR)_ problem introduced by
Katz et al. [13]. In the SSR problem, the inputs consist of a set of
(disjoint) leftward-directed rays and a set of (disjoint) vertical segments.
The objective is to select a minimum number of leftward-directed rays that
intersect all vertical segments. Katz et al. [13] gave a dynamic programming
based $O(n^{2}(n+m))$-time optimal algorithm to solve the SSR problem where
$n$ and $m$ are the number of rays and segments in the input instance
respectively. We prove the following theorem.

######  Theorem 2.

There is a $O((n+m)\log(n+m))$-time $2$-approximation algorithm for SSR
problem where $n$ and $m$ are the number of rays and segments in the input
instance respectively.

Using our approximation algorithm for the SSR problem, we give approximation
algorithms for other subclasses of string graphs as well. In this paper, we
introduce the class _Unit- $B_{k}$-graph_ as follows. A _unit $k$-bend path_
is a $k$-bend path whose segments are of unit length. A _unit $B_{k}$-VPG
representation_ of a graph $G$ is a $B_{k}$-VPG representation $\mathcal{R}$
of $G$ where all paths in $\mathcal{R}$ are unit $k$-bend paths. Graphs having
unit $B_{k}$-VPG representations are called _unit $B_{k}$-VPG graphs_. A graph
is said to be a _UVPG graph_ if it is a unit $B_{k}$-VPG graph for some $k$.
Notice that, every $B_{k}$-VPG graph has a unit $B_{k^{\prime}}$-VPG
representation for some finite $k^{\prime}\geq k$. The family of UVPG graphs
are equivalent to the family of VPG graphs and therefore equivalent to the
family of string graphs. Using our approximation algorithm for the SSR
problem, we prove the following theorem.

######  Theorem 3.

Given a unit $B_{k}$-VPG representation of a graph $G$ with $n$ vertices,
there is a polynomial time $O(k^{4})$-approximation algorithm to solve the MDS
problem on $G$.

On the negative side, we shall show that solving MDS problem on
Unit-$B_{1}$-VPG graph is NP-Hard. First, we give the approximation algorithm
for the SSR problem and prove Theorem 2 in Section 2. In Section 3, we prove
Theorem 1 and in Section 4, we give a proof sketch for Theorem 3. Finally we
draw conclusion in Section 5.

##  2 Approximation for SSR-problem

Throughout this section, we let $\mathcal{SSR}(R,V)$ denote an SSR instance
where $R$ is a given set of (disjoint) leftward-directed rays and $V$ is a
given set of (disjoint) vertical segments. The objective is to select a
minimum cardinality subset of $R$ that intersects all segments in $V$. In this
section, unless otherwise stated, whenever we say a “ray” we shall refer to a
leftward-directed ray and whenever we say a “segment” we shall refer to a
vertical segment. Without loss of generality, we can assume that all segments
lie in the first quadrant of the plane, each segment intersects at least one
ray and no two segments in $V$ has same $x$-coordinate.

The algorithm: Our algorithm consists of four main steps. (a) If some segments
in $V$ intersect precisely one ray $r\in R$, we put $r$ in our heuristic
solution $S$. (b) We delete all segments intersecting any ray in $S$ from $V$.
(c) We find a ray in $R\setminus S$ whose $x$-coordinate of the right endpoint
is the smallest among all rays in $R\setminus S$ and delete it from $R$ (when
there are multiple such rays, choose anyone arbitrarily). We repeat steps
(a)-(c) until all segments are deleted from the instance. We shall refer to
the above algorithm as _SSR -Algorithm_. Notice that, the SSR-Algorithm takes
$O((n+m)\log(n+m))$ time (using segment tree data structure [3]) where $n$ and
$m$ are the number of rays and segments in the input.

We shall show that the cardinality of the set returned by the SSR-algorithm is
at most twice the optimum cost of the relaxed linear programming of the input
instance. This would give us the desired approximation factor of the SSR-
algorithm. First, we introduce some definitions and some extra steps in the
above algorithm for analysis purpose. With each ray $r\in R$ we associate a
_token_ $T_{r}$, which is a subset of $R$ (possibly empty). We add an
_Initialisation Step_ to our algorithm where we assign $T_{r}=\\{r\\}$ for
each $r\in R$ and assign $R_{0}$ as $R$, $V_{0}$ as $V$, $S_{0}$ as
$\emptyset$. For $i\geq 1$ let $R_{i},V_{i},S_{i}$ be the set of rays, the set
of segments and the heuristic solution constructed by the SSR-Algorithm,
respectively at the end of $i^{th}$ iteration. A ray $r\in R_{i}$ is
_critical_ if there is a segment $v\in V_{i}$ such that $r$ is the only ray in
$R_{i}$ that intersects $v$. Notice that, in the $i^{th}$ iteration step (a)
of the SSR-Algorithm collects all the rays that became critical at the end of
$(i-1)^{th}$ iteration and adds them to the heuristic solution to create
$S_{i}$. Let $D$ be a subset of $R_{i}$. A ray $r\in D$ lies _in between_ two
rays $r^{\prime},r^{\prime\prime}\in D$ if the $y$-coordinate of $r$ lies in
between those of $r^{\prime},r^{\prime\prime}$. A ray $r\in D$ lies _just
above_ (resp. _just below_) a ray $r^{\prime}\in D$ if $y$-coordinate of $r$
is greater (resp. smaller) than that of $r^{\prime}$ and no other ray lies in
between $r,r^{\prime}$ in $D$. Two rays $r,r^{\prime}\in D$ are _neighbours_
of each other if $r$ lies just above or below $r^{\prime}$.

######  Definition 1.

For a ray $r\in R_{i-1}\setminus S_{i}$ and $i\geq 1$, the phrase “$r$ passes
the token to its neighbours” in the $i^{th}$ iteration shall refer to the
following operations in the prescribed order:

  1. (i)

Let $r^{\prime}$ lies just above $r$ and $r^{\prime\prime}$ lies just below
$r$ in $R_{i-1}\setminus S_{i}$. For all $x\in T_{r}$ ($x$ and $r$ not
necessarily distinct) do the following. If there is a segment in $V_{i}$ that
intersects $x,r^{\prime}$ and $r$ then assign
$T_{r^{\prime}}=T_{r^{\prime}}\cup\\{x\\}$ and if there is a segment in
$V_{i}$ that intersects $x,r^{\prime\prime}$ and $r$ then
$T_{r^{\prime\prime}}=T_{r^{\prime\prime}}\cup\\{x\\}$.

  2. (ii)

$T_{r}=\emptyset$.

Algorithm 1 MOD-SSR-Algorithm

Input: A set $R$ of leftward-directed rays and a set $V$ of vertical segments.
Output: A subset of $R$ that intersects all segments in $V$.

1:$T_{r}=\\{r\\}$ for each $r\in R$ and $i\leftarrow 1,V_{0}\leftarrow
V,R_{0}\leftarrow R,S\leftarrow\emptyset,S_{0}\leftarrow\emptyset$
$\triangleright$ Initialisation.

2:while $V_{i-1}\neq\emptyset$ do

3: $S\leftarrow S\cup\\{r\colon r\in R_{i-1},r~{}\text{ is critical
after}~{}(i-1)^{th}\text{ iteration}\\}$. $\triangleright$ Critical ray
collection (step (a) of SSR-Algoritm).

4: $S_{i}\leftarrow S$. $\triangleright$ $S_{i}$ is $S$ at the $i^{th}$
iteration.

5: $V_{i}\leftarrow$ the set obtained by deleting all segments from $V_{i-1}$
that intersect some rays in $S_{i}$. $\triangleright$ Step (b) of SSR-
Algorithm.

6: Find a $r\in R_{i-1}\setminus S_{i}$ whose $x$-coordinate of the right
endpoint is the smallest.

7: $r$ passes the token to its neighbours.

8: $R_{i}\leftarrow$ The set obtained by deleting $\\{r\\}\cup S_{i}$ from
$R_{i-1}$. $\triangleright$ Token-passing step (modified step (c) of SSR-
Algorithm).

9: $i\leftarrow i+1$;

10:end while

11:return $S$

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)

Figure 1: (a) An input SSR instance, (b) $1^{st}$ iteration, (c) $2^{nd}$
iteration and (d) $3^{rd}$ iteration of the MOD-SSR-Algorithm with (a) as
input. A dotted ray (or segment) indicates a deleted ray (or segment).

The modified algorithm is stated in Algorithm 1. For an illustration, consider
the input instance shown in Figure 1(a). At the first iteration,
$x$-coordinate of the right endpoint of $r_{3}$ is the smallest. So, $r_{3}$
passes the token to its neighbours ($r_{2},r_{4}$) and gets deleted. At the
end of $1^{st}$ iteration, notice that $r_{2}$ has become critical. At the
beginning of the $2^{nd}$ iteration Algorithm 1 put $r_{2}$ in the heuristic
solution. Then all segment intersecting $r_{2}$ is deleted and $r_{2}$ itself
is also deleted. Also in the second iteration, $r_{1}$ passes the token to its
neighbour ($r_{4}$) and gets deleted. Finally in the third iteration $r_{4}$
is put in the heuristic solution.

It is easy to see that, the rays returned by Algorithm 1 indeed intersect all
segments of the input SSR instance. Moreover for each $i$, the sets
$R_{i},S_{i},V_{i}$ constructed by Algorithm 1 is same as the sets constructed
by SSR-algorithm. From now on, whenever we refer to the sets
$R_{i},S_{i},V_{i}$ we shall refer to the sets constructed by Algorithm 1. We
shall now prove that the cardinality of the solution returned by Algorithm 1
is at most twice the optimum solution size of the input SSR instance. Below we
describe some observations.

######  Observation A.

For any ray $r\in R$ and some integer $k\geq 1$, if there is a segment $v\in
V_{k}$ that intersects $r$ in the input instance, then $v$ also intersects
some ray $r^{\prime}\in R_{k}$ such that $r\in T_{r^{\prime}}$.

###### Proof.

Fix an arbitrary segment $v\in V_{k}$ that intersects $r$ in the input
instance. Let $Y$ be the set of all rays that intersects $v$ in the input
instance and $X\subseteq Y$ be the set of rays that passed the token to its
neighbours at some $i^{th}$ iteration with $i<k$. Formally $X=\\{r^{\prime}\in
Y\colon T_{r^{\prime}}=\emptyset\\}$. If $r\notin X$, then $r\in R_{k}$ and we
are done. Otherwise, $r\in X$. Let $<r_{1},r_{2},...,r_{t}>$ be a sorted order
of the rays in $X$ such that for $i<j$, $r_{i}$ passed the token to the
neighbours before $r_{j}$. Due to step $6$ of MOD-SSR-algorithm, for $i<j$,
the $x$-coordinate of the ray $r_{i}$ is less than that of $r_{j}$. Hence
$<r_{1},r_{2},...,r_{t}>$ is an increasing sequence based on the
$x$-coordinate of their right endpoint. This implies that whenever a ray
$r_{i}\in Y$ was deleted it was _shortest_ among the rays that intersect $v$
and belonged to the set $R_{i-1}$. Therefore, whenever a ray $r_{i}\in X$
passed the token to its neighbours, it had a neighbor $r^{\prime}_{i}\in
R_{i}$ which intersects $v$. This fact combined with the token passing rule in
Definition $1$ says that $v$ intersects a ray $r^{\prime}\in R_{i}$ such that
$r\in T_{r^{\prime}_{i}}$. Applying the above arguments for all rays in $X$,
we have the proof. ∎

For any integer $k\geq 0$ and a ray $r\in R$, let $A_{k}(r)$ denote the
segments in $V_{k}$ that intersect $r$ and let $B_{k}(r)$ be the rays in
$R_{k}$ that intersect at least one segment in $A_{k}(r)$.

######  Observation B.

For any ray $r\in R$ and some integer $k\geq 1$, let $c$ be the bottom-most
(resp. top-most) ray in $B_{k-1}(r)$. If (i) $c$ is the only ray in
$B_{k-1}(r)\setminus S_{k}$ whose token contains $r$ and (ii) $c$ passes the
token to its neighbours in the $k^{th}$ iteration, then (a) there is exactly
one ray $c^{\prime}\in R_{k}$ whose token contains $r$; and $c^{\prime}$ is
the bottom-most (resp. top-most) ray in $B_{k}(r)$.

###### Proof.

Since $c$ is the bottom-most (resp. top-most) ray in $B_{k-1}(r)$ and $c\in
B_{k-1}(r)\setminus S_{k}$, then $c$ must be bottom-most (resp. top-most) ray
in $B_{k-1}(r)\setminus S_{k}$. There is exactly one neighbour $c^{\prime}$ of
$c$ in $R_{k-1}\setminus S_{k}$ such that there is a segment in $V_{k}$ that
intersects $r,c,c^{\prime}$. Therefore, when $c$ passes the token to its
neighbours, $c^{\prime}$ is the only ray whose token shall contain $r$. Since
$c$ does not belong to $R_{k}$, $c$ does not belong to $B_{k}(r)$. Hence,
$c^{\prime}$ must be the bottom-most (resp. top-most) ray in $B_{k}(r)$. This
completes the proof of the claim. ∎

######  Lemma 1.

Let $r$ be a ray. After the termination of Algorithm 1, there are at most two
tokens containing $r$.

###### Proof.

If $r$ never passed the token to its neighbours, then the only token that
contains $r$ is $T_{r}$ and therefore the statement is true. Now let us assume
that, at iteration $i$, $r$ passed the token to its neighbours and was deleted
from $R_{i-1}$. Let $j$ be the minimum integer with $i<j$ such that at the end
of $(j-1)^{th}$ iteration, there is a ray $p\in R_{j-1}$ which is critical and
$r\in T_{p}$. If $j$ does not exist then we simply assume $j$ to be the number
of iterations performed by MOD-SSR-Algorithm. We shall prove the following
claims.

Claim 1. For each $k<i$, the only ray in $R_{k}$ whose token contains $r$ is
$r$ itself.

The proof of the above claim follows directly from the initialisation step and
Token-passing step of the Algorithm 1.

Claim 2. For each $k$ with $i\leq k<j$, (a) there at most two rays
$r^{\prime},r^{\prime\prime}\in R_{k}$ such that $r\in T_{r^{\prime}}\cap
T_{r^{\prime\prime}}$; (b) if both $r^{\prime},r^{\prime\prime}$ exists then
they are neighbours and $r$ lies in between $r^{\prime},r^{\prime\prime}$ in
$R_{0}$; (c) if there is exactly one ray $r^{\prime\prime\prime}\in R_{k}$
such that $r\in T_{r^{\prime\prime\prime}}$ then $r^{\prime\prime\prime}$ must
be the top-most or bottom-most ray in $B_{k}(r)$.

We prove the claim by induction on the number of iterations. Consider the
$i^{th}$ iteration, where $r$ passed the token to its neighbours and got
deleted from $R_{i-1}$ to create $R_{i}$. Clearly, if $r$ was not the top-most
or bottom-most ray of $B_{i-1}(r)$, then at the end of $i^{th}$ iteration
there are at most two rays $r_{1},r_{2}\in R_{i}$ such that $r_{1},r_{2}$ are
neighbours, $r\in T_{r_{1}}\cap T_{r_{2}}$ and $r$ lies in between
$r_{1},r_{2}$ in $R_{0}$. Hence, the claim remains true in this case. Suppose
$r$ was the top-most (resp. bottom-most) ray of $B_{i-1}(r)$. Since $r\notin
S_{i}$, $r$ is the top-most (resp. bottom-most) ray of $B_{i-1}(r)\setminus
S_{i}$. By Observation B, at the end of $i^{th}$ iteration there is exactly
one ray $r_{3}\in R_{i}$ such that $r\in T_{r_{3}}$ and $r_{3}$ must be the
top-most (resp. bottom-most) ray in $B_{i}(r)$. Hence, the claim remains true
in this case. We assume the claim to be true for all $i,i+1,\ldots,(k-1)^{th}$
iterations. Let $x$ passed the token to its neighbours in the $k^{th}$
iteration. If $r\notin T_{x}$ then the claim remains true. When $r\in T_{x}$,
we have the following cases.

  1. (i)

Let $x$ be the only ray in $R_{k-1}$ such that $r\in T_{x}$. Then by induction
hypotheis, $x$ was the top-most (or bottom-most) ray in $B_{k-1}(r)$ and hence
in $B_{k-1}(r)\setminus S_{k}$. By Observation B, at the end of $k^{th}$
iteration there is exactly one ray $x^{\prime}\in R_{k}$ such that $r\in
T_{x^{\prime}}$ and $x^{\prime}$ must be the top-most (resp. bottom-most) ray
in $B_{k}(r)$.

  2. (ii)

Let $x_{1},x_{2}\in R_{k-1}$ be two rays such that $r\in T_{x_{1}}\cap
T_{x_{2}}$. Without loss of generality, we further assume that $x=x_{1}$,
$x_{1}$ lies just above $x_{2}$. If there exists a neighbour of $x_{1}$ (say
$x_{3}$) which is different from $x_{2}$, then due to the Token-passing step
of $k^{th}$ iteration, $x_{1}$ passes the token to its neighbours (i.e $x_{2}$
and $x_{3}$) and gets deleted from $R_{k-1}$ to create $R_{k}$. Letting
$r^{\prime}=x_{2}$ and $r^{\prime\prime}=x_{3}$, we have the proof of the
claim. If $x_{3}$ does not exist, then $x_{1}$ shall pass the token only to
$x_{2}$ and $x_{2}$ becomes the top-most ray in $R_{k}$ (and therefore in
$B_{k}(r)$).

This completes the proof of the claim.

Claim 3. For each $k\geq j$, there is at most one ray $r^{\prime}\in R_{k}$
such that $r\in T_{r^{\prime}}$ and if $r^{\prime}$ exists then $r^{\prime}$
must be the top-most or bottom-most ray in $B_{k}(r)$.

We shall prove the claim by induction on the number of iteration. First
consider the $j^{th}$ iteration. Due to Claim 2, we know that there was at
most two rays $r^{\prime},r^{\prime\prime}\in R_{j-1}$ such that $r\in
T_{r^{\prime}}\cap T_{r^{\prime\prime}}$. Recall from the definition of $j$
that, there was a ray $p\in R_{j-1}$ which was critical and $r\in T_{p}$. We
have the following cases.

  1. (i)

If there were only one ray $r^{\prime\prime\prime}\in R_{j-1}$ whose token
contained $r$, then $p$ and $r^{\prime\prime\prime}$ must be same. Since $p$
is put in heuristic solution, $p$ will never pass the token to its neighbours
at any subsequent iteration. Therefore only $T_{p}$ will contain $r$ after the
termination of Algorithm 1.

  2. (ii)

Let both $r^{\prime},r^{\prime\prime}\in R_{j-1}$ exists. By Claim 2 they must
be neighbours and $r$ lies in between $r^{\prime},r^{\prime\prime}$ in
$R_{0}$. Without loss of generality, assume that $r^{\prime}$ lies just above
$r^{\prime\prime}$ and $p=r^{\prime\prime}$. If both
$r^{\prime},r^{\prime\prime}\in S_{j}$, then there is nothing to prove.
Otherwise, $r^{\prime}$ is the only ray in $R_{j-1}\setminus S_{j}$ whose
token contains $r$. By Observation A, any segment of $V_{j}$ that intersects
$r$ in the input instance, intersects $r^{\prime}$. Now consider the set
$A_{j}(r)$ and the set $B_{j-1}(r)\setminus S_{j}$ and notice that
$r^{\prime}$ must be the bottom-most ray in $B_{j-1}(r)\setminus S_{j}$. If
$r^{\prime}$ did not pass the token to its neighbours in the $j^{th}$
iteration, then $r^{\prime}$ becomes the bottom-most ray in $B_{j}(r)$ and the
statement of the claim remains true. If $r^{\prime}$ passed the token to its
neighbours in the $j^{th}$ iteration, then we are done by Observation B.

Now assume that the statement of the claim remains true for
$j,j+1,\ldots,(k-1)^{th}$ iteration. If there is no ray in $R_{k-1}\setminus
S_{k}$ whose token contained $r$ then we directly have the proof of the claim.
Otherwise by induction hypothesis, there is a unique ray $r^{\prime}\in
R_{k-1}$ whose token contains $r$ and if $r^{\prime}$ exists then $r^{\prime}$
is the bottom-most or top-most ray in $B_{k-1}(r)$. Again if $r^{\prime}$ did
not pass the token to its neighbours in the $k^{th}$ iteration, then the
statement of the claim remains true. If $r^{\prime}$ passed the token to its
neighbours in the $k^{th}$ iteration, then $r^{\prime}$ must be the bottom-
most or top-most ray in $B_{k-1}(r)\setminus S_{k}$ and by Observation B we
have the proof of the claim.

Now combining Claim 1, Claim 2 and Claim 3, we have the proof of the lemma. ∎

For a segment $v\in V$, we let $N(v)$ denote the set of rays in $R$ that
intersect $v$. Let $r\in S$ be a ray, $i$ be the minimum integer such that
$r\in S_{i}$. In other words, $r$ was put in the heuristic solution in the
$i^{th}$ iteration. This means there must exist a segment $\nu_{r}\in V_{i-1}$
such that $r$ is the only ray in $R_{i-1}$ that intersects $\nu_{r}$.
Moreover, no ray in $S\setminus\\{r\\}$ intersects $\nu_{r}$ (otherwise
$\nu_{r}$ would not have been present in $V_{i-1}$ by step-5 of MOD-SSR-
Algorithm). Hence, all rays in $N(\nu_{r})\setminus\\{r\\}$ must have passed
the token to its neighbours. Therefore, for all $x\in
N(\nu_{r})\setminus\\{r\\}$ we have $T_{x}=\emptyset$. So, for each ray $r\in
S$, there always exists a segment $\nu_{r}$ such that for all $x\in
N(\nu_{r})\setminus\\{r\\}$ we have $T_{x}=\emptyset$. We shall denote such a
segment as a _critical segment with respect to $r$_ and denote it as $\nu_{r}$
(in case of multiplicity choose any one as $\nu_{r}$). Now we have the
following lemma.

######  Observation C.

For a ray $r\in S$ let $\nu_{r}$ be a critical segment with respect to $r$.
Then $N(\nu_{r})\subseteq T_{r}$.

###### Proof.

Consider any arbitrary but fixed deleted ray $y\in N(\nu_{r})\setminus\\{r\\}$
which was deleted at some $j^{th}$ iteration. By Observation A, there exists a
ray $y^{\prime}\in R_{j}$ such that $y^{\prime}$ intersects $v$ and $y\in
T_{y^{\prime}}$. Now applying the above argument for all rays in
$N(\nu_{r})\setminus\\{r\\}$, we have the proof. ∎

######  Lemma 2.

Let $S$ be the set returned by Algorithm 1 with $\mathcal{SSR}(R,V)$ as input
and $OPT$ be an optimum solution of $\mathcal{SSR}(R,V)$. Then $|S|\leq
2|OPT|$.

###### Proof.

Let $R$ be the set of rays and $V$ be the set of segments with $|R|=n,|V|=m$.
To prove the lemma we consider the following integer linear programming (ILP)
formulation $Q$ of $\mathcal{SSR}(R,V)$ and the corresponding relaxed linear
programming (LP) formulation $Q_{l}$ where for each ray $r\in R$, let
$x_{r}\in\\{0,1\\}$ denote the variable corresponding to $r$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{r\in
R}x_{r}&\\\ \text{subject to}&\displaystyle\sum\limits_{r\in N(v)}x_{r}\geq
1,&\forall v\in V\\\ x_{r}\in\\{0,1\\},&\forall r\in R\end{array}$ (1)
---
$Q$

We shall show that the set $S$ returned by Algorithm 1 gives an integral
solution for $Q$ whose cost (i.e. cardinality of $S$) is at most twice the
optimum cost of $Q$. This will immediately imply the statement of the lemma.
Let $\textbf{Q}_{l}=\\{x_{r}\\}_{r\in R}$ be an optimal solution of $Q_{l}$.
Also define $y_{r}=1$ if $r\in S$, $y_{r}=0$ if $r\notin S$ and
$\textbf{Q}^{\prime}=\\{y_{r}\\}_{r\in R}$. Now we claim that
$\textbf{Q}^{\prime}$ is a feasible solution of $Q$. This is true because
Algorithm 1 terminates only when no segments are left in $V_{i}$. Hence, for
each $v$ there is a ray $r\in S$ that intersects $v$ and therefore each
constraint of $Q$ contains a variable $y_{r}$ such that $y_{r}=1$ in
$\textbf{Q}^{\prime}$. Hence $\textbf{Q}^{\prime}$ is feasible. Now we fix any
arbitrary $r\in S$ and $\nu_{r}$ be a critical segment with respect to $r$.
Then due to Observation C, we know that for all $z\in
N(\nu_{r})\setminus\\{r\\}$ we have $T_{z}=\emptyset$ and $N(\nu_{r})\subseteq
T_{r}$. Therefore, for the constraint corresponding to $\nu_{r}$ in $Q_{l}$,
we have that

$\sum_{z\in N(\nu_{r})}y_{z}=1\leq\sum_{z\in N(\nu_{r})}x_{z}\leq\sum_{z\in
T_{r}}x_{z}\hskip 20.0pt\left[\text{since }N(\nu_{r})\subseteq T_{r}\text{ by
Observation~{}\ref{obs:constraint-critical}}\right]$

Due to Lemma 1, we know that for each ray $r\in R$ there are at most two rays
$r_{1},r_{2}$ such that $r\in T_{r_{1}}\cap T_{r_{2}}$. Therefore,

$|S|=\sum_{r\in S}y_{r}=\sum_{r\in S}\sum_{z\in N(\nu_{r})}y_{z}\leq\sum_{r\in
S}\sum_{z\in T_{r}}x_{z}\leq 2\sum_{z\in R}x_{z}\leq 2|OPT|$

This completes the proof of the lemma. ∎

Proof of Theorem 2 follows from Lemma 2 which essentially implies that SSR-
algorithm is a 2-approximation algorithm for SSR problem. We shall use the
following corollary in the proof of Theorem 1 and 3 which follows from Lemma
2.

######  Corollary 1.

Let $R$ be a set of leftward-directed rays and $V$ be a set of vertical
segments. The cost of an optimal solution for the ILP of $\mathcal{SSR}(R,V)$
is at most $2$ times the cost of an optimal solution for the relaxed LP of
$\mathcal{SSR}(R,V)$.

##  3 Approxmation algorithm for MDS on vertically-stabbed-L graphs

In this section, we shall give a polynomial time $8$-approximation algorithm
to solve the MDS problem on vertically-stabbed-L graphs. In the rest of the
paper, $OPT(Q)$ (resp. $OPT(Q_{l})$) denotes the cost of the optimum solution
of an ILP $Q$ (resp. LP $Q_{l}$).

Overview of the algorithm: First, we solve the relaxed LP formulation of the
ILP of the MDS problem on the input vertically-stabbed-L graph $G$ and create
two subproblems. We shall show that one of those two subproblems is equivalent
to the SSR problem and the other is equivalent to a Stabbing Rays with
Segments problem (defined below) which was introduced by Katz et al. [13]. We
solve these two subproblems individually and show that the union of the
solutions gives a solution for the MDS problem on $G$ which is at most $8$
times the optimal solution.

In the _Stabbing Rays with Segments_ (SRS) problem, the input is a set $R$ of
(disjoint) leftward-directed rays and a set $V$ of (disjoint) vertical
segments. The objective is to select a minimum cardinality subset of $V$ that
intersects all rays in $R$.

######  Result 1 ([13]).

There is a $2$-approximation algorithm for the SRS problem for $n$ rays and
$m$ segments that runs in time $O((m+n)\log(m+n))$, using $O(n+m\log m)$
space.

We shall show that the cost of the optimum solution of the ILP of SRS is at
most twice the cost of the optimum solution of the corresponding relaxed LP.
Below we restate the algorithm of Katz et al. [13] in a way that would assist
our analysis.

2-approximation algorithm for SRS problem: With each segment $v\in V$, we
associate a token $T_{v}$ which is a subset of $V$. Initialise
$T_{v}=\emptyset$ for each $v\in V$. Let $r_{i}$ be the ray whose right-
endpoint, $(x_{i},y_{i})$, has the smallest $x$-coordinate. (We can assume
without loss of generality that $x$\- and $y$-coordinates of the endpoints of
the rays are all distinct.) Assuming that there is a feasible solution to the
SRS instance, there must exist a segment of $V$ that intersects $r_{i}$. Let
$N(r_{i})\subseteq V$ be the set of segments that intersect $r_{i}$. Let
$v_{top}$ (resp. $v_{bot}$) be a segment in $N(r_{i})$ whose top endpoint is
top-most (resp., bottom endpoint is bottom-most); it may be that
$v_{top}=v_{bot}$. We add both $v_{top}$ and $v_{bot}$ to our heuristic
solution set $S$. Also we set $T_{v_{top}}=T_{v_{bot}}=N(r_{i})$. Then we
remove from $R$ all of the rays that intersect $v_{top}$ or $v_{bot}$, delete
all segments in $N(r_{i})$ and then repeat the above steps untill
$R=\emptyset$. We shall refer the algorithm stated above as KMN-algorithm.

First, we state the following observations required to prove Lemma 3.

######  Observation D.

For each ray $r$, there is a segment $v\in S$ that intersects $r$.

######  Observation E.

For each segment $v\in V$, there are at most two tokens such that both of them
contains $v$.

######  Lemma 3.

Let $R$ (resp. $V$) be a set of (disjoint) leftward-directed rays (resp.
vertical segments), $Q$ be the ILP of the SRS instance with $R,V$ as input and
$Q_{l}$ be the corresponding relaxed LP. Then $OPT(Q)\leq 2\cdot OPT(Q_{l})$.

###### Proof.

Consider the following ILP of the SRS instance with $R,V$ as input. For a ray
$u\in R$, let $N(u)$ denote the set of segments in $V$ that intersect $u$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{w\in
V}x_{w}&\\\ \text{subject to}&\displaystyle\sum\limits_{w\in N(u)}x_{w}\geq
1,&\forall u\in R\\\ x_{w}\in\\{0,1\\},&\forall w\in V\end{array}$ (2)
---
$Q$

Let $\textbf{X}=\\{x_{v}\\}_{v\in V}$ be an optimal solution of $Q_{l}$
(relaxed LP of $Q$) where $x_{v}$ denotes the value of the variable in $Q_{l}$
corresponding to $v\in V$. Let $S$ be the solution returned by the KMN
algorithm with $R,V$ as input. Now define for each $v\in V$,
$x^{\prime}_{v}=1$ if $v\in S$, $x^{\prime}_{v}=0$ if $v\notin S$ and let
$\textbf{X}^{\prime}=\\{x^{\prime}_{v}\\}_{v\in V}$. By Observation D,
$\textbf{X}^{\prime}$ is a feasible solution of $Q$. For each $z\in S$, there
is a ray $r_{i}$ such that $T_{z}=N(r_{i})$. Therefore, for the constraint
corresponding to $r_{i}$ in $Q_{l}$, we have the following

$x^{\prime}_{z}=1\leq\displaystyle\sum\limits_{v\in
N(r_{i})}x_{v}=\displaystyle\sum\limits_{v\in T_{z}}x_{v}$ (3)
---

Hence,

$\begin{split}|S|&=\displaystyle\sum\limits_{v\in S}x^{\prime}_{v}\\\
&\leq\displaystyle\sum\limits_{v\in S}\displaystyle\sum\limits_{v^{\prime}\in
T_{v}}x_{v^{\prime}}\hskip 20.0pt\text{Using Inequality~{}\ref{ineq:1}}\\\
&\leq 2\displaystyle\sum\limits_{v^{\prime}\in V}x_{v^{\prime}}\hskip
32.0pt\text{Using Observation~{}\ref{obs:stab-L-trivial-2}}\\\ &=2\cdot
OPT(Q_{l})\end{split}$ (4)

This completes the proof. ∎

Now we are ready to describe our approximation algorithm for MDS problem on
vertically-stabbed-L graphs. Let $\mathcal{R}$ be a vertically-stabbed-L-
representation of a graph $G$. Without loss of generality, we assume that

  1. (i)

the vertical line $x=0$ intersects all the L-paths in $\mathcal{R}$,

  2. (ii)

the $x$-coordinate of the corner point of each L-path in $\mathcal{R}$ is
strictly less than $0$, and

  3. (iii)

whenever two distinct L-paths intersect in $\mathcal{R}$, they intersect at
exactly one point.

|  |  |  |  |  |
---|---|---|---|---|---|---
(a) |  | (b) |  | (c) |  | (d)

Figure 2: A vertically-stabbed-L graph. (a) The sets $H_{u}$ and $V_{u}$
corresponding to a vertex $u$. (b) The gray L-paths belongs to $A_{1}$ and the
black L-paths belongs to $A_{2}$, (c) The subproblem equivalent to SRS-
problem. (d) The subproblem equivalent to SSR-problem.

For a vertex $u\in V(G)$, let $N[u]$ denote the closed neghbourhood of $u$ in
$G$. For each vertex $u\in V(G)$, let $H_{u}=\\{c\in
N[u]\colon\textsc{L}_{c}~{}\text{intersects the horizontal segment
of}~{}\textsc{L}_{u}\\}$ and let $V_{u}$ denote the set $N(u)\setminus H_{u}$
(See Figure 2(a)). Based on these we have the following ILP (say $Q$) of the
problem of finding a minimum dominating set of $G$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in
V(G)}x_{v}&\\\ \text{subject to}&\displaystyle\sum\limits_{v\in
H_{u}}x_{v}+\displaystyle\sum\limits_{v\in V_{u}}x_{v}\geq 1,&\forall u\in
V(G)\\\ x_{v}\in\\{0,1\\},&\forall v\in V(G)\end{array}$ (5)
---
$Q$

The first step of our algorithm is to solve the relaxed LP formulation, say
$Q_{l}$ of $Q$. Let $\textbf{Q}_{l}=\\{x_{v}\colon v\in V(G)\\}$ be an optimal
solution of $Q_{l}$. Now we define the following sets.

$A_{1}=\left\\{u\in V(G)\colon\displaystyle\sum\limits_{v\in
H_{u}}x_{v}\geq\frac{1}{2}\right\\},A_{2}=\left\\{u\in
V(G)\colon\displaystyle\sum\limits_{v\in V_{u}}x_{v}\geq\frac{1}{2}\right\\}$
$H=\bigcup\limits_{u\in A_{1}}H_{u},V=\bigcup\limits_{u\in A_{2}}V_{u}$

Based on these, we consider the following two integer programs $Q^{\prime}$
and $Q^{\prime\prime}$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in H}x^{\prime}_{v}\\\ \text{subject to}&\displaystyle\sum\limits_{v\in H_{u}}x^{\prime}_{v}\geq 1,&\forall u\in A_{1}\\\ x^{\prime}_{v}\in\\{0,1\\},&v\in H\end{array}$ (6) |  $\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in V}x^{\prime\prime}_{v}&\\\ \text{subject to}&\displaystyle\sum\limits_{v\in V_{u}}x^{\prime\prime}_{v}\geq 1,&\forall u\in A_{2}\\\ x^{\prime\prime}_{v}\in\\{0,1\\},&v\in V\end{array}$ (7)
---|---
$Q^{\prime}$ | $Q^{\prime\prime}$

Let $Q^{\prime}_{l}$ and $Q^{\prime\prime}_{l}$ be the relaxed LP of
$Q^{\prime}$ and $Q^{\prime\prime}$ respectively. Clearly, the solutions of
$Q^{\prime}$ and $Q^{\prime\prime}$ gives a solution for $Q$. Hence
$OPT(Q)\leq OPT(Q^{\prime})+OPT(Q^{\prime\prime})$. For each
$x_{v}\in\textbf{Q}_{l}$, define $y_{v}=\min\\{1,2x_{v}\\}$ and define
$\textbf{Y}_{l}=\\{y_{v}\\}_{x_{v}\in\textbf{Q}_{l}}$. Notice that
$\textbf{Y}_{l}$ gives a solution to $Q^{\prime}_{l}$ (and
$Q^{\prime\prime}_{l}$). Therefore,
$OPT(Q^{\prime}_{l})+OPT(Q^{\prime\prime}_{l})\leq 4\cdot OPT(Q_{l})$. We have
the following lemma.

######  Lemma 4.

$OPT(Q^{\prime})\leq 2\cdot OPT(Q^{\prime}_{l})$ and
$OPT(Q^{\prime\prime})\leq 2\cdot OPT(Q^{\prime\prime}_{l})$.

###### Proof.

Solving $Q^{\prime}$ is equivalent to finding a minimum cardinality
$D\subseteq H$ such that each vertex $u\in A_{1}$ is adjacent to some vertex
in $D\cap H_{u}$. Recall that for each vertex $u\in A_{1}$ and $v\in H_{u}$,
$L_{v}$ intersects the horizontal segment of $L_{u}$. Now consider the
following sets. Let $R$ be the set of horizontal segments of the L-paths
representing the vertices in $A_{1}$ and $S$ be the set of vertical segments
of the L-paths representing the vertices in $H$ (See Figures 2(b) and 2(c) for
an example). Since all horizontal segments in $R$ intersect the $x=0$ vertical
line and the $x$-coordinates of the vertical segments in $S$ is strictly less
than $0$, we can consider the horizontal segments in $R$ as rightward directed
rays. Hence, solving $Q^{\prime}$ is equivalent to solving the ILP (say
$\mathcal{E}$) of the problem of finding a minimum cardinality subset of $S$
(a set of vertical segments) that intersects all rays in $R$ (a set of
rightward-directed rays). Hence solving $\mathcal{E}$ is equivalent to solving
an SRS instance with $R$ and $S$ as input. By Lemma 3, we have that

$OPT(Q^{\prime})=OPT(\mathcal{E})\leq 2\cdot OPT(\mathcal{E}_{l})\leq 2\cdot
OPT(Q^{\prime}_{l})$

where $\mathcal{E}_{l}$ is the relaxed LP of $\mathcal{E}$. This proves the
first part.

For the second part, solving $Q^{\prime\prime}$ is equivalent to finding a
minimum cardinality subset $D$ of $V$ such that each vertex $u\in A_{2}$ is
adjacent to some vertex in $D\cap V_{u}$. Recall that, for each vertex $u\in
A_{2}$ and $v\in V_{u}$, $L_{v}$ intersects the vertical segment of $L_{u}$.
Now consider the following sets. Let $R$ be the set of horizontal segments of
the L-paths representing the vertices in $V$ and $S$ be the set of vertical
segments of the L-paths representing the vertices in $A_{2}$ (See Figures 2(b)
and 2(d) for an example). Since all horizontal segments in $R$ intersect the
$x=0$ vertical line and the $x$-coordinates of the vertical segments in $S$ is
strictly less than $0$, we can consider the segments in $R$ as rightward-
directed rays. Hence, solving $Q^{\prime\prime}$ is equivalent to solving the
ILP (say $\mathcal{F}$) of the problem of finding a minimum cardinality subset
of $R$ (a set of rightward-directed rays) that intersects all segments in $S$
(a set of vertical segments). Hence, solving $\mathcal{F}$ is equivalent to
solving an SSR instance with $R$ and $S$ as inputs. By Corollary 1, we have
that

$OPT(Q^{\prime\prime})=OPT(\mathcal{F})\leq 2\cdot OPT(\mathcal{F}_{l})=2\cdot
OPT(Q^{\prime\prime}_{l})$

where $\mathcal{F}_{l}$ is the relaxed LP of $\mathcal{F}$. This proves the
second part. ∎

To complete the proof of Theorem 1, notice that Lemma 4 implies that solving
$Q^{\prime}$ (resp. $Q^{\prime\prime}$) is equivalent to solving SRS (resp.
SSR) problem instance. Let $A$ be the union of the solutions returned by KMN-
algorithm and SSR-algorithm, used to solve $Q^{\prime}$ and $Q^{\prime\prime}$
respectively. Hence,

$|A|\leq 2(OPT(Q^{\prime}_{l})+OPT(Q^{\prime\prime}_{l}))\leq 8\cdot
OPT(Q_{l})\leq 8\cdot OPT(Q)$

Since the LP $Q_{l}$ consists of $n$ variables where $n=|V(G)|$, solving
$Q_{l}$ takes $O(n^{3}\cdot T)$ time [12] where $T$ is the total number of
bits required to encode the $(0,1)$-constraint matrix of $Q_{l}$. Solving both
the SSR and SRS instances takes a total of $O(n\log n)$ time (Theorem 2 and
Result 1) and therefore the total running time of the algorithm is
$O(n^{3}\cdot T)$.

##  4 Hardness and Approximation for MDS on Unit-$B_{k}$ VPG-graphs

|
---|---
(a) | (b)

Figure 3:  A unit L-representation (b) of (3,3)-grid (a).

First we prove the NP-hardness for MDS problem on unit-$B_{1}$-VPG graphs. The
_$(h,w)$ -grid_ is the undirected graph $G$ with $V(G)=\\{(x,y)\colon
x,y\in\mathbb{Z},1\leq x\leq h,1\leq y\leq w\\}$ and
$E(G)=\\{(u,v)(x,y)\colon|u-x|+|v-y|=1\\}$. A graph $G$ is a _grid_ graph if
$G$ is an induced subgraph of $(h^{\prime},w^{\prime})$-grid for some positive
integers $h^{\prime},w^{\prime}$. Given a grid graph $G$, the Grid-Dominating-
Set problem is to find a minimum cardinality dominating set of $G$. We shall
reduce the Grid-Dominating-Set problem to the MDS problem on unit-$B_{1}$-VPG
graphs. We will be done by showing that for any positive integers $h,w$ the
$(h,w)$-grid has a unit-$B_{1}$-VPG representation. Let $G$ be a $(h,w)$-grid
and $\epsilon=\frac{1}{hw}$. For each $(x,y)\in V(G)$ consider the L-path
$\textsc{L}_{(x,y)}$ such that top endpoint of vertical segment of
$\textsc{L}_{(x,y)}$ is $(x,y-\epsilon(x-1))$ (See Figure 3). It is easy to
verify that the set of L-paths
$\mathcal{R}=\\{\textsc{L}_{(x,y)}\colon(x,y)\in V(G)\\}$ is a
unit-$B_{1}$-VPG representation of $G$. Hence, we have the following theorem.

######  Theorem 4.

It is NP-Hard to solve the MDS problem on unit-$B_{1}$-VPG graphs.

In this section, we describe our approximation algorithm for MDS on
Unit-$B_{k}$ VPG-graphs and prove Theorem 3. First we give an overview of the
algorithm below.

Overview of the algorithm for MDS on Unit-$B_{k}$-VPG graphs: First, we solve
the relaxed LP formulation of the ILP of MDS problem on the input
Unit-$B_{k}$-VPG graph $G$ and create $(k+1)^{2}$ many subproblems each of
which are equivalent to a Proper-Seg-Dom problem (defined below). We shall
show that it is possible to get constant factor approximate solutions for each
of these subproblems in polynomial time and take the union of all the
solutions to get a set $S$. We shall conclude by showing that $S$ is a
$O(k^{4})$-approximate solution for MDS problem on $G$ and $S$ can be computed
in polynomial time.

In the Proper-Seg-Dom (_Proper Orthogonal Segment Domination_) problem the
input is a set $V$ of vertical segments, a set $H$ of horizontal segments such
that the sets of intervals obtained by projecting the segments in $H$ (resp.
$V$) onto the $x$-axis (resp. $y$-axis) are proper (a set of intervals is
_proper_ if no two intervals in the set contain each other). The objective is
to select a minimum cardinality subset of $H\cup V$ that intersects all
segments in $H\cup V$.

In Section 4.1 we shall give a constant factor approximation for the Proper-
Seg-Dom problem and in Section 4.2 we shall describe the approximation
algorithm for MDS on Unit-$B_{k}$ VPG-graphs and use our result on Proper-Seg-
Dom to prove Theorem 3.

###  4.1 Approximation for PROPER-SEG-DOM problem

Let $V$ (resp. $H$) be a set of vertical (resp. horizontal) segments,
$\mathcal{I}_{V}$ (resp. $\mathcal{I}_{H}$) be the projections of the segments
in $V$ (resp. $H$) onto the $y$-axis (resp. $x$-axis) and both
$\mathcal{I}_{V}$ and $\mathcal{I}_{H}$ are proper sets of intervals. The
Proper-Seg-Dom problem is to find a minimum cardinality subset of $H\cup V$
that intersects all segments in $H\cup V$. In this section, we shall give a
polynomial time $18$-approximation algorithm to solve the Proper-Seg-Dom
problem where $n=|H|+|V|$. Throughout this section, we let
$\mathcal{PSD}(H,V)$ denote the Proper-Seg-Dom problem instance with $H$ and
$V$ as input. In order to solve Proper-Seg-Dom, we consider the following
problems.

Overview of the algorithm: First, we solve the relaxed LP formulation of the
ILP of the input Proper-Seg-Dom problem and create two subproblems. We shall
show that one of the subproblem is equivalent to a _Subset Proper Interval
Domination_ problem (defined below) and the other is equivalent to a _Proper
Orthogonal Segment Stabbing_ problem (defined below). We give constant factor
approximate solution for each these two problems and show that the union of
the solutions of these subproblems gives a solution for the input Proper-Seg-
Dom problem instance which is at most $18$ times the optimal solution.

In the _Subset Proper Interval Domination_ problem (SPID) the inputs are a
proper set of intervals $S$ and a set $T\subseteq S$. The SPID problem is to
select a minimum cardinality subset of $S$ that intersects all intervals in
$T$. In the _Proper Orthogonal Segment Stabbing_ problem (POSS) inputs are a
set $S$ of horizontal segments a set $T$ of vertical segments such that the
set of intervals obtained by projecting the segments in $S$ onto the $x$-axis
is a proper set of intervals. The POSS problem is to select a minimum
cardinality subset of $S$ that intersects all vertical segments in $T$. For a
set of horizontal segments $S$ and a set of vertical segments $T$,
$\mathcal{P}(T,S)$ shall denote the POSS instance. Let $S$ be a proper set of
intervals and $T$ be a subset of $S$. Then $\mathcal{SP}(T,S)$ shall denote
the SPID instance.

In Section 4.1.1, we give approximation algorithms to solve SPID-problems and
POSS-problems. In Section 4.1.2, we give the approximation algorithm for the
$\mathcal{PSD}(H,V)$ problem.

####  4.1.1 Approximation algorithms for SPID and POSS problem

Lemma 5 and Lemma 6 shall compare the integral cost with the fractional cost
of the SPID-problem and POSS-problem respectively. We shall use Corollary 2
and Corollary 3 in Section 4.1.2.

######  Lemma 5.

Let $S$ be a proper set of intervals and $T\subseteq S$. The cost of an
optimal solution for the relaxed LP of $\mathcal{SP}(T,S)$ equals to the cost
of an optimal solution for the ILP of $\mathcal{SP}(T,S)$.

###### Proof.

For an interval $v\in S$, let $l(v)$ and $r(v)$ denote the left and right
endpoints. Let $s_{1},s_{2},\ldots,s_{k}$ be the intervals in $S$ sorted in
the ascending order of the right endpoints. Hence,
$r(s_{1})<r(s_{2})<\ldots<r(s_{k})$ and as no two intervals in $S$ contain
each other, we have $l(s_{1})<l(s_{2})<\ldots l(s_{k})$. For an interval $x\in
T$, let $N(x)$ denote the set of intervals in $S$ that intersect $x$. Now
consider the following ILP (say $Q$) of $\mathcal{SP}(T,S)$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in
S}x_{v}&\\\ \text{subject to}&\displaystyle\sum\limits_{v\in N(u)}x_{v}\geq
1,&\forall u\in T\\\ x_{v}\in\\{0,1\\},&\forall v\in S\end{array}$ (8)
---
$Q$

Let $\mathcal{M}$ be a coefficient matrix of $Q$ such that the $i^{th}$ column
of $\mathcal{M}$ corresponds to the variable corresponding to $s_{i}\in S$.
Each row of $\mathcal{M}$ have the interval property (i.e the set of 1’s are
consecutively in each row). To see this consider any three intervals
$\\{s_{i},s_{j},s_{j^{\prime}}\\}\subseteq S$ such that $i<j<j^{\prime}$ and
any interval $t\in T$ such that $t$ intersects both $s_{i}$ and
$s_{j^{\prime}}$. Since $r(s_{i})<r(s_{j})<r(s_{j^{\prime}})$ and
$l(s_{i})<l(s_{j})<l(s_{j^{\prime}})$, $t$ must intersect $s_{j}$. Therefore,
$\mathcal{M}$ is a totally unimodular matrix [19]. Thus any optimal solution
of the relaxed LP of $\mathcal{SP}(T,S)$ is integral and therefore an optimal
solution for the ILP of $\mathcal{SP}(T,S)$. This completes the proof. ∎

For a proper set of intervals $S$ and $T\subseteq S$, an optimal solution of
$\mathcal{SP}(T,S)$ can be computed in $O(n\log n)$ time [6]. We shall use the
following corollary whose proof follows from Lemma 5.

######  Corollary 2.

Let $X$ (resp. $Y$) be a set of horizontal (resp. vertical) segments,
$\mathcal{I}_{X}$ (resp. $\mathcal{I}_{Y}$) be the projections of the segments
in $X$ (resp. $Y$) onto the $x$-axis (resp. $y$-axis) and both
$\mathcal{I}_{X}$ and $\mathcal{I}_{Y}$ are proper sets of intervals. For
$X^{\prime}\subseteq X$ and $Y^{\prime}\subseteq Y$, let $\mathcal{A}$ be the
ILP of finding a minimum cardinality subset $D$ of $X\cup Y$ such that every
horizontal (resp. vertical) segment in $X^{\prime}$ (resp. $Y^{\prime}$)
intersects at least one horizontal (resp. vertical) segment in $D\cap X$
(resp. $D\cap Y$). Then $OPT(\mathcal{A})=OPT(\mathcal{A}_{l})$ where
$\mathcal{A}_{l}$ is the relaxed LP of $\mathcal{A}$. Moreover,
$OPT(\mathcal{A})$ can be computed in $O(n\log n)$ time where $n=|X|+|Y|$.

######  Lemma 6.

Let $S$ be a set of horizontal segments, $T$ be a set of vertical segments and
$\mathcal{I}_{S}$ be the projections of the horizontal segments in $S$ onto
the $x$-axis. Let $\mathcal{I}_{S}$ be a proper set of intervals. Then the
cost of an optimal solution for the ILP of $\mathcal{P}(T,S)$ is at most $8$
times the cost of an optimal solution for the relaxed LP of
$\mathcal{P}(T,S)$.

###### Proof.

Without loss of generality, we assume that the segments in $S$ and $T$ are in
“general position” i.e. $x$-coordinate of any vertical segment in $T$ is
distinct from the $x$-coordinates of the left and right endpoints of any
interval in $\mathcal{I}_{S}$. Since no two interval in $\mathcal{I}_{S}$
contain each other, we have a set $P$ of real numbers such that each interval
in $\mathcal{I}_{S}$ contains exactly one real number from $P$. (To see this,
consider the $x$-coordinates of the right endpoints of the intervals in the
maximum cardinality subset of $\mathcal{I}_{S}$ with pairwise non-intersecting
intervals which is obtained using the greedy algorithm [14]). Add in $P$ two
more dummy values $q,q^{\prime}$ which are not contained in any interval in
$\mathcal{I}_{S}$ and $q$ (resp. $q^{\prime}$) is less than (resp. greater
than) that of all values in $P$. Let $p_{1},p_{2},\ldots,p_{t}$ be the values
in $P$ sorted in the ascending order (notice that $p_{1}=q$ and
$p_{t}=q^{\prime}$). For each $i\in\\{1,2,\ldots,t-1\\}$, let $T_{i}$ denote
the vertical segments of $T$ that lies inside the strip bounded by the lines
$y=p_{i}$ and $y=p_{i+1}$. Due to our general position assumption for any
$i\neq j$, $T_{i}$ and $T_{j}$ are disjoint. For each
$i\in\\{1,2,\ldots,t-1\\}$, and each vertical segment $v\in T_{i}$, let
$S_{v}^{left}$ (resp. $S_{v}^{right}$) be the subset of $S$ that intersects
$v$ and the line $y=p_{i}$ (resp. $y=p_{i+1}$). Since any interval in
$\mathcal{I}_{S}$ contains exactly one value from $P$ and therefore from
$\\{p_{i},p_{i+1}\\}$, $S_{v}^{left}\cap S_{v}^{right}=\emptyset$, for each
vertical segment $v\in T$. Based on these we have the following ILP (say $W$)
of $\mathcal{P}(T,S)$ problem.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in
S}x_{v}&\\\ \text{subject to}&\displaystyle\sum\limits_{v\in
S^{left}_{u}}x_{v}+\displaystyle\sum\limits_{v\in S^{right}_{u}}x_{v}\geq
1,&\forall u\in T\\\ x_{v}\in\\{0,1\\},&\forall v\in S\end{array}$ (9)
---
$W$

First step of our algorithm is to solve the relaxed LP formulation (say
$W_{l}$) of $W$. Let $\textbf{W}_{l}=\\{x_{v}\colon v\in S\\}$ be an optimal
solution of $W_{l}$. Consider the following sets.

$A_{1}=\left\\{u\in T\colon\displaystyle\sum\limits_{v\in
S^{left}_{u}}x_{v}\geq\frac{1}{2}\right\\},A_{2}=\left\\{u\in
T\colon\displaystyle\sum\limits_{v\in
S^{right}_{u}}x_{v}\geq\frac{1}{2}\right\\}$ $L=\bigcup\limits_{v\in
A_{1}}S^{left}_{v},R=\bigcup\limits_{v\in A_{2}}S^{right}_{v}$

Based on these, we consider the following two integer programs $W^{\prime}$
and $W^{\prime\prime}$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in L}x^{\prime}_{v}\\\ \text{subject to}&\displaystyle\sum\limits_{v\in S^{left}_{u}}x^{\prime}_{v}\geq 1,&\forall u\in A_{1}\\\ x^{\prime}_{v}\in\\{0,1\\},&v\in L\end{array}$ (10) |  $\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in R}x^{\prime\prime}_{v}\\\ \text{subject to}&\displaystyle\sum\limits_{v\in S^{right}_{u}}x^{\prime\prime}_{v}\geq 1,&\forall u\in A_{2}\\\ x^{\prime\prime}_{v}\in\\{0,1\\},&v\in R\end{array}$ (11)
---|---
$W^{\prime}$ | $W^{\prime\prime}$

Let $W^{\prime}_{l}$ and $W^{\prime\prime}_{l}$ be the corresponding relaxed
LPs of $W^{\prime}$ and $W^{\prime\prime}$ respectively. The union of the
solutions of $W^{\prime}$ and $W^{\prime\prime}$ gives a solution for $W$
implying $OPT(W)\leq OPT(W^{\prime})+OPT(W^{\prime\prime})$. For each
$x_{v}\in\textbf{W}_{l}$, define $y_{v}=\min\\{1,2x_{v}\\}$ and define
$\textbf{Y}_{l}=\\{y_{v}\\}_{x_{v}\in\textbf{W}_{l}}$. Notice that
$\textbf{Y}_{l}$ gives a solution to $W^{\prime}_{l}$ (and
$W^{\prime\prime}_{l}$). Hence, $OPT(W^{\prime}_{l})\leq 2\cdot OPT(W_{l})$
and $OPT(W^{\prime\prime}_{l})\leq 2\cdot OPT(W_{l})$. Therefore,
$OPT(W^{\prime}_{l})+OPT(W^{\prime\prime}_{l})\leq 4\cdot OPT(W_{l})$. Notice
that, solving $W^{\prime}$ (resp. $W^{\prime\prime}$) is equivalent to the
problem of finding a minimum cardinality subset of the horizontal segments in
$L$ (resp. $R$) to intersect all vertical segments in $A_{1}$ (resp. $A_{2}$).
Now we have the following claim.

Claim 4. $OPT(W^{\prime})\leq 2\cdot OPT(W^{\prime}_{l})$ and
$OPT(W^{\prime\prime})\leq 2\cdot OPT(W^{\prime\prime}_{l})$.

We shall prove the above claim only for $W^{\prime}$ as proof for the other
case is similar. Recall that solving $W^{\prime}$ is equivalent to the problem
of finding a minimum cardinality subset of the horizontal segments in the set
$L$ (defined earlier) to intersect all vertical segments in $A_{1}$. For each
$i\in\\{1,2,\ldots,(t-1)\\}$ let $T_{1,i}=A_{1}\cap T_{i}$ and $L_{i}$ be the
set of horizontal segments in $L$ that intersect some vertical segment in
$T_{1,i}$. Formally, $L_{i}=\bigcup\limits_{v\in T_{1,i}}S^{left}_{v}$. For
any $i\neq j$, $T_{1,i}\cap T_{1,j}=\emptyset$ and $L_{i}\cap L_{j}=\emptyset$
(this follows from the fact no horizontal segment in $S$ intersects both
$y=p_{i}$ and $y=p_{j}$). For each $i\in\\{1,2,\ldots,(t-1)\\}$, let
$\mathcal{D}_{i}$ (resp, $\mathcal{D}_{i,l}$) denote the ILP (resp. relaxed
LP) of the problem of selecting minimum subset $D_{i}$ horizontal segments in
$L_{i}$ such that all vertical segments in $T_{1,i}$ intersect at least one
horizontal segment in $D_{i}$. Clearly,
$OPT(W^{\prime})=\sum_{i=1}^{t-1}OPT(\mathcal{D}_{i})$ and
$OPT(W^{\prime}_{l})=\sum_{i=1}^{t-1}OPT(\mathcal{D}_{i,l})$. For each
$i\in\\{1,2,\ldots,(t-1)\\}$ notice that, all horizontal segments intersect
the vertical line $y=p_{i}$ and all vertical segments in $T_{1,i}$ lies to the
left of the vertical line $y=p_{i}$. For each $i\in\\{1,2,\ldots,(t-1)\\}$ if
we consider the segments in $L_{i}$ to be leftward-directed rays then solving
$\mathcal{D}_{i}$ is equivalent to solving an SSR instance with $T_{1,i}$ and
$L_{i}$ as input. Due to Corollary 1, for each $i\in\\{1,2,\ldots,(t-1)\\}$,
$OPT(\mathcal{D}_{i})\leq 2\cdot OPT(\mathcal{D}_{i,l})$. Hence,

$OPT(W^{\prime})=\displaystyle\sum\limits_{i=1}^{t-1}OPT(\mathcal{D}_{i})\leq
2\cdot\displaystyle\sum\limits_{i=1}^{t-1}OPT(\mathcal{D}_{i,l})=2\cdot
OPT(W^{\prime}_{l})$

This completes the proof of the claim.

Using the above claim and previous observations, we can infer that

$OPT(W)\leq OPT(W^{\prime})+OPT(W^{\prime\prime})\leq
2(OPT(W^{\prime}_{l})+OPT(W^{\prime\prime}_{l}))\leq 8\cdot
OPT(W^{\prime}_{l})$

This completes the proof of the lemma. ∎

Therefore, we have a polynomial time $8$-approximation algorithm to solve the
$\mathcal{P}(T,S)$ problem where $n=|S|+|T|$. We shall use the following
corollary which follows from Lemma 6.

######  Corollary 3.

Let $X_{1},X_{2}$ (resp. $Y_{1},Y_{2}$) be sets of horizontal (resp. vertical)
segments, $\mathcal{I}_{X}$ (resp. $\mathcal{I}_{Y}$) be the projections of
the segments of $X_{1}\cup X_{2}$ (resp. $Y_{1}\cup Y_{2}$) onto the $x$-axis
(resp. $y$-axis) and both $\mathcal{I}_{X}$ and $\mathcal{I}_{Y}$ are proper
sets of intervals. Let $\mathcal{B}$ be the ILP of finding minimum cardinality
subset $D$ of $X_{2}\cup Y_{2}$ such that every horizontal (resp. vertical)
segment in $X_{1}$ (resp. $Y_{1}$) intersect at least one vertical (resp.
horizontal) segment in $D\cap Y_{2}$ (resp. $D\cap X_{2}$). Then there is a
polynomial time algorithm to compute a set $D^{\prime}$ which gives a solution
of $\mathcal{B}$ and $|D^{\prime}|\leq 8\cdot OPT(\mathcal{B}_{l})$ where
$n=|X_{1}\cup X_{2}\cup Y_{1}\cup Y_{2}|$ and $\mathcal{B}_{l}$ is the relaxed
LP of $\mathcal{B}$.

####  4.1.2 Approximation algorithms for $\mathcal{PSD}(H,V)$

Now we are ready to describe our approximation algorithm to solve the
$\mathcal{PSD}(H,V)$ problem. Recall that $V$ (resp. $H$) is a set of vertical
(resp. horizontal) segments, $\mathcal{I}_{V}$ (resp. $\mathcal{I}_{H}$) is
the projections of the segments in $V$ (resp. $H$) onto the $y$-axis (resp.
$x$-axis) and both $\mathcal{I}_{V}$ and $\mathcal{I}_{H}$ are proper sets of
intervals. The $\mathcal{PSD}(H,V)$ problem is to find a minimum cardinality
subset of $H\cup V$ that intersects all vertical segments in $H\cup V$. For a
segment $v\in H\cup V$, let $N(v)\subseteq H\cup V$ denote the set of segments
that intersects $v$. For a segment $w\in H$, let $N_{o}(w)=N(w)\cap H$ and for
a segment $w^{\prime}\in V$ let $N_{o}(w^{\prime})=N(w^{\prime})\cap V$. Based
on these we have the following ILP (say $Z$) for the $\mathcal{PSD}(H,V)$
problem.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{w\in H\cup
V}x_{w}&\\\ \text{subject to}&\displaystyle\sum\limits_{w\in
N_{o}(u)}x_{w}+\displaystyle\sum\limits_{w\in N(u)\setminus N_{o}(u)}x_{w}\geq
1,&\forall u\in H\cup V\\\ x_{w}\in\\{0,1\\},&\forall w\in H\cup V\end{array}$
(12)
---
$Z$

The first step of our algorithm is to solve the relaxed LP formulation (say
$Z_{l}$) of $Z$. Let $\textbf{Z}_{l}=\\{x_{w}\colon w\in H\cup V\\}$ be an
optimal solution of $Z_{l}$. Let

$A_{1}=\left\\{u\in H\cup V\colon\displaystyle\sum\limits_{w\in
N_{o}(u)}x_{w}\geq\frac{1}{2}\right\\},A_{2}=\left\\{u\in H\cup
V\colon\displaystyle\sum\limits_{w\in N(u)\setminus
N_{o}(u)}x_{w}\geq\frac{1}{2}\right\\}$

,

$B_{1}=\bigcup\limits_{u\in A_{1}}N_{o}(u),\hskip
5.0ptB_{2}=\bigcup\limits_{u\in A_{2}}N(u)\setminus N_{o}(u)$

Based on these, we consider the following two integer programs $Z^{\prime}$
and $Z^{\prime\prime}$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{w\in B_{1}}x^{\prime}_{w}\\\ \text{subject to}&\displaystyle\sum\limits_{w\in N_{o}(v)}x^{\prime}_{w}\geq 1,&\forall v\in A_{1}\\\ x^{\prime}_{w}\in\\{0,1\\},&w\in B_{1}\end{array}$ (13) |  $\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{w\in B_{2}}x^{\prime\prime}_{w}\\\ \text{subject to}&\displaystyle\sum\limits_{w\in N(v)\setminus N_{o}(v)}x^{\prime\prime}_{w}\geq 1,&\forall v\in A_{2}\\\ x^{\prime\prime}_{w}\in\\{0,1\\},&w\in B_{2}\end{array}$ (14)
---|---
$Z^{\prime}$ | $Z^{\prime\prime}$

Let $Z^{\prime}_{l}$ and $Z^{\prime\prime}_{l}$ be the corresponding relaxed
LPs of $Z^{\prime}$ and $Z^{\prime\prime}$ respectively. Clearly, the union of
the solutions of $Z^{\prime}$ and $Z^{\prime\prime}$ gives a solution for $Z$.
Hence, $OPT(Z)\leq OPT(Z^{\prime})+OPT(Z^{\prime\prime})$. For each
$x_{v}\in\textbf{Z}_{l}$, define $y_{v}=\min\\{1,2x_{v}\\}$ and define
$\textbf{Y}_{l}=\\{y_{v}\\}_{x_{v}\in\textbf{Z}_{l}}$. Notice that
$\textbf{Y}_{l}$ gives a solution for $Z^{\prime}_{l}$ and
$Z^{\prime\prime}_{l}$. Hence, $OPT(Z^{\prime}_{l})\leq 2\cdot OPT(Z_{l})$ and
$OPT(Z^{\prime\prime}_{l})\leq 2\cdot OPT(Z_{l})$. Now we prove the following
lemma.

######  Lemma 7.

$OPT(Z^{\prime})=OPT(Z^{\prime}_{l})$ and $OPT(Z^{\prime\prime})\leq 8\cdot
OPT(Z^{\prime\prime}_{l})$.

###### Proof.

To prove the first part, let $X$ (resp. $Y$) be the set of horizontal (resp.
vertical) segments in $B_{1}$ and $X^{\prime}$ (resp. $Y^{\prime}$) be the set
of horizontal (resp. vertical) segments in $A_{1}$. Notice that
$X^{\prime}\subseteq X$ and $Y^{\prime}\subseteq Y$. Hence, $Z^{\prime}$ is
the ILP of finding minimum cardinality subset $D$ of $X\cup Y$ such that every
horizontal (resp. vertical) segment in $X^{\prime}$ (resp. $Y^{\prime}$)
intersects at least one horizontal (resp. vertical) segment in $D\cap X$
(resp. $D\cap Y$). By Corollary 2, we have that
$OPT(Z^{\prime})=OPT(Z^{\prime}_{l})$.

To prove the second part, let $X_{1}$ and $X_{2}$ (resp. $Y_{1}$ and $Y_{2}$)
be the sets of horizontal (resp. vertical) segments in $A_{2}$ and $B_{2}$,
respectively. Notice that $Z^{\prime\prime}$ is the ILP of finding minimum
cardinality subset $D$ of $X_{2}\cup Y_{2}$ such that every horizontal (resp.
vertical) segment in $X_{1}$ (resp. $Y_{1}$) intersects at least one vertical
(resp. horizontal) segment in $D\cap Y_{2}$ (resp. $D\cap X_{2}$). By
Corollary 3, we have that $OPT(Z^{\prime\prime})\leq 8\cdot
OPT(Z^{\prime\prime}_{l})$. ∎

Using Lemma 7, we can conclude that

$OPT(Z)\leq OPT(Z^{\prime})+OPT(Z^{\prime\prime})\leq
OPT(Z^{\prime}_{l})+8\cdot OPT(Z^{\prime\prime}_{l})\leq 18\cdot
OPT(Z^{\prime}_{l})$

Due to Lemma 7, Corollary 2 and 3 we have the following theorem.

######  Theorem 5.

There is a polynomial time $18$-approximation algorithm to solve the Proper-
Seg-Dom problem where $n$ is the total number of segments in the input
instance.

We shall use the following corollary in Section 4.2, whose proof follows from
that of Theorem 5.

######  Corollary 4.

Let $V_{1},V_{2}$ (resp. $H_{1},H_{2}$) be a set of vertical (resp.
horizontal) segments, $\mathcal{I}_{V}$ (resp. $\mathcal{I}_{H}$) be the
projections of the segments of $V_{1}\cup V_{2}$ (resp. $H_{1}\cup H_{2}$)
onto the $y$-axis (resp. $x$-axis) and both $\mathcal{I}_{V}$ and
$\mathcal{I}_{H}$ are proper sets of intervals. Let $\mathcal{C}$ be the ILP
of the problem of finding a minimum cardinality subset $D$ of $V_{2}\cup
H_{2}$ such that every segment in $V_{1}\cup H_{1}$ intersects some segment in
$D$. Then there is a polynomial time algorithm to compute a set $D^{\prime}$
which gives a solution of $\mathcal{C}$ and $|D^{\prime}|\leq 18\cdot
OPT(\mathcal{C}_{l})$ where $n=|V_{1}\cup V_{2}\cup H_{1}\cup H_{2}|$ and
$\mathcal{C}_{l}$ is the relaxed LP of $\mathcal{C}$.

###  4.2 Completion of Proof for Theorem 3

Let $\mathcal{R}$ be a unit $B_{k}$-VPG representation of a unit $B_{k}$-VPG
graph $G$. We shall assume that every vertex of $G$ has a self loop (this does
not contradict the intersection model as every rectilinear path intersects
itself). For a vertex $v\in V(G)$, let $P(v)$ denote the path in $\mathcal{R}$
that corresponds to $v$. For a vertex $v\in V(G)$, $N(v)$ and $N[v]$ denote
the _open neighbourhood_ and _closed neighbourhood_ of $v$, respectively.
Throughout this section, we shall assume that the segments of each path
$P\in\mathcal{R}$ are numbered consecutively starting from the leftmost
segment by $1,2,\ldots,t$ where $t(\leq k+1)$ is the number of segments in
$P$.

######  Definition 2.

Let $\phi\colon E(G)\rightarrow\mathbb{N}\times\mathbb{N}$ be a mapping such
that for an edge $uv$, $\phi(uv)=(i,j)$ if and only if

  1. 1.

the $i^{th}$ segment of $P(u)$ intersects the $j^{th}$ segment of $P(v)$, and

  2. 2.

for all $1\leq a<i$ and $1\leq b<j$, the $a^{th}$ segment of $P(u)$ and
$b^{th}$ segment of $P(v)$ does not intersect each other.

Notice that for each vertex $u\in V(G)$, $\phi(u,u)=(1,1)$. Based on the
definition we can partition the closed neighbourhood of a vertex as follows.
For a vertex $u\in V(G)$, let $X_{u}(i,j)=\\{v\in
N(u)\colon\phi(uv)=(i,j)\\}$. For distinct pairs $(i,j)$ and
$(i^{\prime},j^{\prime})$ the sets $X_{u}(i,j)$ and
$X_{u}(i^{\prime},j^{\prime})$ are disjoint. By $\mathcal{K}$ we shall denote
the set $\\{1,2,\ldots,k+1\\}\times\\{1,2,\ldots,k+1\\}$. Based on these we
have the following ILP of the Unit-$B_{k}$-VPG-Dom problem on $G$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in
V(G)}x_{v}&\\\ &\\\ \text{subject
to}&\displaystyle\sum\limits_{(i,j)\in\mathcal{K}}\hskip
5.0pt\sum\limits_{v\in X_{u}(i,j)}x_{v}\geq 1,&\hskip 5.0pt\forall u\in
V(G)\\\ &\\\ x_{v}\in\\{0,1\\},&\forall v\in V(G)\end{array}$ (15)
---
$Q$

First step of our algorithm is to solve the relaxed LP formulation (say
$Q_{l}$) of $Q$. Let $\mathbf{Q}_{l}=\\{x_{v}\colon v\in V(G)\\}$ be an
optimal solution of $Q_{l}$. For each vertex $u\in V(G)$, there is a pair
$(i,j)\in\mathcal{K}$ such that $\sum\limits_{v\in
X_{u}(i,j)}x_{v}\geq\frac{1}{(k+1)^{2}}$. For each pair $(i,j)\in\mathcal{K}$,
define

$A(i,j)=\left\\{u\in V(G)\colon\sum\limits_{v\in
X_{u}(i,j)}x_{v}\geq\frac{1}{(k+1)^{2}}\right\\}$

$B(i,j)=\displaystyle\bigcup\limits_{u\in A(i,j)}X_{u}(i,j)$

Based on these we have the following ILP for each pair $(i,j)\in\mathcal{K}$.

$\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle\sum\limits_{v\in
B(i,j)}x^{\prime}_{v}&\\\ &\\\ \text{subject
to}&\displaystyle\sum\limits_{v\in X_{u}(i,j)}x^{\prime}_{v}\geq 1,&\hskip
5.0pt\forall u\in A(i,j)\\\ &\\\ x^{\prime}_{v}\in\\{0,1\\},&\forall v\in
B(i,j)\end{array}$ (16)
---
$Q(i,j)$

For each pair pair $(i,j)\in\mathcal{K}$, let $Q_{l}(i,j)$ be the relaxed LP
of $Q(i,j)$. We have the following

$OPT(Q)\leq\displaystyle\sum\limits_{(i,j)\in\mathcal{K}}OPT(Q(i,j))$

For each $x_{v}\in\textbf{Q}_{l}$, define $y_{v}=\min\\{1,2x_{v}\\}$ and
define $\textbf{Y}_{l}=\\{y_{v}\\}_{x_{v}\in\textbf{Q}_{l}}$. Clearly,
$\textbf{Y}_{l}$ gives a solution to $Q_{l}(i,j)$ for each
$(i,j)\in\mathcal{K}$. Hence, we have the following inequality.

$\displaystyle\sum\limits_{(i,j)\in\mathcal{K}}OPT(Q_{l}(i,j))\leq(k+1)^{4}\cdot
OPT(Q_{l})$

Now we have the following lemma.

######  Lemma 8.

For each pair $(i,j)\in\mathcal{K}$, there is a solution $D(i,j)$ for $Q(i,j)$
such that $|D(i,j)|\leq 18\cdot OPT(Q_{l}(i,j))$.

###### Proof.

Fix an arbitrary but fixed pair $(i,j)\in\mathcal{K}$. Solving $Q(i,j)$ is
equivalent to finding a minimum cardinality subset $D$ of $B(i,j)$ such that
each vertex $u\in A(i,j)$ has a neighbour in $D\cap X_{u}(i,j)$. Since for
each vertex $u\in A(i,j)$ and each $v\in X_{u}(i,j)$, the $i^{th}$ segment of
$P(u)$ intersects the $j^{th}$ segment of $P(v)$. Now we define some sets as
follows.

$S=\\{i^{th}\text{ segment of }P(u)\colon u\in A(i,j)\\},\hskip
5.0ptT=\\{j^{th}\text{ segment of }P(v)\colon v\in B(i,j)\\}$ $V_{1}=\text{set
of vertical segments in }S,\hskip 5.0ptV_{2}=\text{set of vertical segments in
}T$ $H_{1}=\text{set of horizontal segments in }S,\hskip 5.0ptH_{2}=\text{set
of horizontal segments in }T$

Notice that, solving $Q(i,j)$ is equivalent to the problem finding a minimum
cardinality subset $D$ of $V_{2}\cup H_{2}$ such that every segment in
$V_{1}\cup H_{1}$ intersect at least one segment in $D$. Since every segment
in $V_{1}\cup V_{2}\cup H_{1}\cup H_{2}$ have unit length, we can modify the
vertical (resp. horizontal) segments in $V_{1},V_{2}$ (resp. $H_{1},H_{2}$)
and get $V^{\prime}_{1},V^{\prime}_{2}$ (resp. $H^{\prime}_{1}\cup
H^{\prime}_{2}$) respectively such that

  1. 1.

the set of intervals obtained by projecting the segments in
$V^{\prime}_{1}\cup V^{\prime}_{2}$ (resp. $H^{\prime}_{1}\cup
H^{\prime}_{2}$) onto the $y$-axis (resp. $x$-axis) is a proper set of
intervals, and

  2. 2.

two segments $u^{\prime},v^{\prime}\in V^{\prime}_{1}\cup V^{\prime}_{2}\cup
H^{\prime}_{1}\cup H^{\prime}_{2}$ intersect if and only if the corresponding
segments $u,v\in V_{1}\cup V_{2}\cup H_{1}\cup H_{2}$ intersect.

Hence, solving $Q(i,j)$ is equivalent to the problem of finding a minimum
cardinality subset $D$ of $V^{\prime}_{2}\cup H^{\prime}_{2}$ such that every
segment in $V^{\prime}_{1}\cup H^{\prime}_{1}$ intersect at least one segment
in $D$. Moreover, the sets of intervals obtained by projecting the segments in
$V^{\prime}_{1}\cup V^{\prime}_{2}$ and $H^{\prime}_{1}\cup H^{\prime}_{2}$
onto the $y$-axis and $x$-axis, respectively are proper sets of intervals.
Hence by Corollary 4, we can find a solution (say $D(i,j)$) for $Q(i,j)$ such
that $|D(i,j)|\leq 18\cdot OPT(Q_{l}(i,j))$. This completes the proof. ∎

For each pair $(i,j)\in\mathcal{K}$, due to Lemma 8, we can get a solution
$D(i,j)$ of $Q(i,j)$ such that $|D(i,j)|\leq 18\cdot OPT(Q(i,j))$ in
polynomial time. Let $D$ be the union of $D(i,j)$’s for all
$(i,j)\in\mathcal{K}$. We have that

$|D|=\displaystyle\sum\limits_{(i,j)\in\mathcal{K}}|D(i,j)|\leq\displaystyle\sum\limits_{(i,j)\in\mathcal{K}}18\cdot
OPT(Q_{l}(i,j))\leq 18\cdot(k+1)^{4}\cdot OPT(Q_{l})\leq 18\cdot(k+1)^{4}\cdot
OPT(Q)$

This completes the Proof of Theorem 3.

##  5 Conclusion

In this paper, we gave approximation algorithms for MDS problems on
vertically-stabbed-L graphs and unit-$B_{k}$-VPG graphs. We gave a polynomial
time $O(k^{4})$-approximation algorithm to solve the MDS problem on
unit-$B_{k}$-VPG graphs. However, the status of MDS problems on $B_{k}$-VPG
graphs remains unknown for a fixed $k$. Approximation algorithms with better
running time or better approximation factor for MDS problems on vertically-
stabbed-L graphs and unit-$B_{k}$-VPG graphs would be interesting.

## References

  * [1] A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, and M. Stern.  Vertex intersection graphs of paths on a grid.  Journal of Graph Algorithms and Applications, 16(2):129–150, 2012\.
  * [2] S. Bandyapadhyay, A. Maheshwari, S. Mehrabi, and S. Suri.  Approximating dominating set on intersection graphs of rectangles and L-frames.  In MFCS, pages 37:1–37:15, 2018.
  * [3] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.  Computational geometry: algorithms and applications.  Springer-Verlag TELOS, 2008.
  * [4] E. Bonnet and P. Rzazewski.  Optimality program in segment and string graphs.  In WG, pages 79–90, 2018.
  * [5] N. Bousquet, D. Gonçalves, G.B. Mertzios, C. Paul, I. Sau, and S. Thomassé.  Parameterized domination in circle graphs.  In WG, pages 308–319. Springer, 2012.
  * [6] MS. Chang.  Efficient algorithms for the domination problems on interval and circular-arc graphs.  SIAM Journal on computing, 27(6):1671–1694, 1998.
  * [7] Miroslav Chlebík and Janka Chlebíková.  Approximation hardness of dominating set problems in bounded degree graphs.  Information and Computation, 206(11):1264–1275, 2008.
  * [8] M. Damian and S.V. Pemmaraju.  APX-hardness of domination problems in circle graphs.  Information processing letters, 97(6):231–237, 2006.
  * [9] M. Damian-Iordache and S.V. Pemmaraju.  A (2+ $\varepsilon$)-approximation scheme for minimum domination on circle graphs.  Journal of Algorithms, 42(2):255–276, 2002.
  * [10] J. Fox and J. Pach.  Computing the independence number of intersection graphs.  In SODA, pages 1161–1165, 2011.
  * [11] D. Gonçalves, L. Isenmann, and C. Pennarun.  Planar graphs as L-intersection or L-contact graphs.  In SODA, pages 172–184, 2018.
  * [12] Clóvis C Gonzaga.  An algorithm for solving linear programming problems in o (n 3 l) operations.  In Progress in mathematical programming, pages 1–28. Springer, 1989\.
  * [13] M. J Katz, J. SB Mitchell, and Y. Nir.  Orthogonal segment stabbing.  Computational Geometry: Theory and Applications, 30(2):197–205, 2005.
  * [14] J. Kleinberg and E. Tardos.  Algorithm design.  Pearson Education India, 2006.
  * [15] S. McGuinness.  On bounding the chromatic number of L-graphs.  Discrete Mathematics, 154(1-3):179–187, 1996.
  * [16] S. Mehrabi.  Approximating domination on intersection graphs of paths on a grid.  In WAOA, pages 76–89. Springer, 2017.
  * [17] J. Pach and G. Tóth.  How many ways can one draw a graph?  In GD, pages 47–58. Springer, 2003.
  * [18] A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W.T Trotter, and B. Walczak.  Triangle-free intersection graphs of line segments with large chromatic number.  Journal of Combinatorial Theory, Series B, 105:6–10, 2014.
  * [19] Alexander Schrijver.  Theory of linear and integer programming.  John Wiley & Sons, 1998.