# Minimum Shared-Power Edge Cut 111This work was partially supported by NSERC
and by the Slovenian Research Agency (P1-0297).

Sergio Cabello University of Ljubljana and IMFM<EMAIL_ADDRESS>Kshitij Jain University of Waterloo<EMAIL_ADDRESS>Anna Lubiw
University of Waterloo<EMAIL_ADDRESS>Debajyoti Mondal University of
Saskatchewan<EMAIL_ADDRESS>
###### Abstract

We introduce a problem called the Minimum Shared-Power Edge Cut (_MSPEC_). The
input to the problem is an undirected edge-weighted graph with distinguished
vertices $s$ and $t$, and the goal is to find an $s$-$t$ cut by assigning
“powers” at the vertices and removing an edge if the sum of the powers at its
endpoints is at least its weight. The objective is to minimize the sum of the
assigned powers.

_MSPEC_ is a graph generalization of a barrier coverage problem in a wireless
sensor network: given a set of unit disks with centers in a rectangle, what is
the minimum total amount by which we must shrink the disks to permit an
intruder to cross the rectangle undetected, i.e. without entering any disc.
This is a more sophisticated measure of barrier coverage than the minimum
number of disks whose removal breaks the barrier.

We develop a fully polynomial time approximation scheme (FPTAS) for _MSPEC_.
We give polynomial time algorithms for the special cases where the edge
weights are uniform, or the power values are restricted to a bounded set.
Although _MSPEC_ is related to network flow and matching problems, its
computational complexity (in P or NP-hard) remains open.

##  1 Introduction

Minimum weight edge cuts in graphs are very well-studied. In this paper we
look at a variation that arises from unit disk graphs and other situations
where the edges of the graph are determined by geometric properties of the
vertices. In this variation, we assign a _power_ $p_{v}$ to each vertex $v$
and an edge $e=(u,v)$ is removed if $p_{u}+p_{v}$ is at least the weight of
edge $e$. The goal is to remove the edges of an $s$-$t$ cut while minimizing
the power sum. More formally, the Minimum Shared-Power Edge Cut Problem
(_MSPEC_) is defined as follows:

Input: Graph $G=(V\cup\\{s,t\\},E)$ with $n$ vertices, $m$ edges, and a non-
negative weight $w_{u,v}$ on each edge $(u,v)\in E$.

Problem: Assign a non-negative power $p_{v}$ to each $v\in V$ and assign
$p_{s}=p_{t}=0$ so that removing the edge set $\\{(u,v)\in E:p_{u}+p_{v}\geq
w_{u,v}\\}$ disconnects $s$ and $t$ and $\sum_{v\in V}p_{v}$ is minimized.

Our main result is a fully polynomial time approximation scheme (FPTAS) for
the Minimum Shared-Power Edge Cut Problem.

A special case of _MSPEC_ —and our original motivation for studying it—is the
problem of measuring barrier coverage of a sensor network. A sensor network is
typically modelled as a collection of unit disks in the plane, where each disk
represents the sensing region of its corresponding sensor [25]. The network
provides a _barrier_ between regions $R_{1}$ and $R_{2}$ if every path from
$R_{1}$ to $R_{2}$ intersects the union of the disks. One simple measure of
barrier coverage is the minimum number of disks whose removal permits a path
from $R_{1}$ to $R_{2}$ in the free space outside the disks. This can be
computed in polynomial time [13] for the special case of a _rectangular
barrier_ , where the sensors lie in a rectangle and must block paths from the
bottom to the top of the rectangle. We suggest, as a more sophisticated
measure, the minimum total amount by which we must shrink the disks to permit
such a path. This measure reflects the reality that sensor strength typically
deteriorates (“attenuates”) with distance from the sensor [25]. For a
rectangular barrier, our Minimum Shrinkage problem (as in Figure 1) can be
modelled as _MSPEC_ , where we have a vertex for each disk, and the power
assigned to a vertex tells us how much to shrink the corresponding disk. Thus
our main result provides an approximation scheme to compute Minimum Shrinkage
for rectangular barrier coverage.

(a)

(b)

Figure 1: Minimum shrinkage for the rectangular barrier coverage problem:
(1(a)) shows the rectangular barrier and the disks representing sensors;
(1(b)) shows a path from bottom to top in the free space after shrinking three
of the disks.

###  1.1 Related Models and Work

Motivated by problems in design of wireless networks, there is substantial
previous work on graph optimization problems in which edges are selected
depending on “power” values $p_{v}$ that are assigned to each vertex $v$. The
objective is to minimize the sum of the powers, while satisfying connectivity
properties for the selected edges that are of interest in the design of ad-hoc
wireless networks. For example, the selected edges form a spanning tree, or a
$k$-connected subgraph. The models that have been considered for selecting, or
“activating”, an edge $(u,v)$ of weight $w_{u,v}$ are:

  1. 1.

$\min\\{p_{u},p_{v}\\}\geq w_{u,v}$ (“Power Optimization”, e.g. [9])

  2. 2.

$\max\\{p_{u},p_{v}\\}\geq w_{u,v}$ ([4])

  3. 3.

$p_{u}+p_{v}\geq w_{u,v}$ (“Installation Cost” [20])

  4. 4.

a more general function of $p_{u}$ and $p_{v}$ (“Activation Networks” [20])

The only previous work in Activation Networks on our model (3) is an $O(\log
n)$ approximation algorithm for minimum spanning tree, see [20]. The only
Activation result for the $s$-$t$ cut problem in any of these models is due to
Angel et al. [4] who use model (2) and reduce the problem to a conventional
min cost $s$-$t$ cut problem, which can then be solved in polynomial time.
They heavily use the fact that in model (2) the power assigned to a vertex
will be equal to the weight of an incident edge. This property does not hold
for our model, nor do we assume (as is done in model (4)) a discrete set of
power values. In Section 6.2 we show that with that assumption, our problem
can be solved in polynomial time.

In the most well-studied model, called “Power Optimization,” an edge $(u,v)$
with weight $w_{u,v}$ is selected, or “activated”, if $p_{u}$ and $p_{v}$ are
both at least $w_{u,v}$, i.e., $\min\\{p_{u},p_{v}\\}\geq w_{u,v}$. This makes
the problems easier because the power at a vertex will be equal to the weight
of one of its incident edges, so the possible powers form a discrete set. The
literature on Power Optimization includes approximation algorithms for minimum
spanning tree, Steiner forest, $k$-vertex or $k$-edge connected subgraph (all-
pairs, single source, or $s$-$t$), and various degree-constrained and edge-
cover problems [3, 9, 14, 7].

In a less well-studied scenario, Angel et al. [4] defined an edge $(u,v)$ to
be activated if $\max\\{p_{u},p_{v}\\}$ $\geq w_{u,v}$. Again, the power at a
vertex will be equal to the weight of one of its incident edges, so there are
only a discrete set of possible powers that may be assigned to a node. Using
this property, Angel et al. reduced the problem of finding an optimum $s$-$t$
cut in this model to the conventional minimum cut problem. For their model,
they also gave a polynomial time algorithm for optimum $s$-$t$ path, a
2-approximation for vertex cover, and a proof that spanning tree is hard to
approximate.

Our model, where an edge $(u,v)$ with weight $w_{u,v}$ is selected if
$p_{u}+p_{v}\geq w_{u,v}$, was called the “installation cost” model by
Panigrahi [20] who reported an $O(\log n)$ approximation algorithm for minimum
spanning tree [21]. He proved that this approximation factor is best possible
assuming P $\neq$ NP [20]. We are unaware of any other work specifically on
this model.

Panigrahi [20] formulated a generalization of all these power requirements
called “Activation Networks,” where there is a general 0-1 function $f$ on
pairs of vertex powers and an edge $(u,v)$ is activated if $f(p_{u},p_{v})=1$.
In fact, his model is more general in that it allows for different functions
$f$ for different pairs of vertices. However, the model has a significant
restriction in that the power values are constrained to a discrete set $D$
whose size is assumed to to be polynomially bounded in $n$. Panigrahi gave
$O(\log n)$ approximation algorithms for various network survivability
problems in this setting, such as minimum spanning tree, minimum Steiner
forest, and $2$-edge/vertex connectivity. These algorithms were improved in
several follow-up papers [19, 2].

Organization. The remainder of our paper is organized as follows. Section 2
contains some alternative formulations of _MSPEC_. The barrier coverage
application is treated in Section 3. Our approximation scheme for _MSPEC_ is
in Section 5. This is preceded by Section 4 on a bottleneck version of the
problem, and followed by Section 7 on speeding up the approximation algorithm.
Some more general and some restricted versions of _MSPEC_ are considered in
Section 6, and Section 8 concludes the paper.

##  2 Alternative Formulations of _MSPEC_

In this section we give two alternative formulations of the _MSPEC_ problem.

In _MSPEC_ we are searching for an edge cut. The set of edges in an $s$-$t$
cut form a bipartite graph. Given an edge cut, the power assignment that will
remove those edges corresponds to a minimum “$w$-vertex cover” [23, chapter
17], that is, an assignment of weights $y_{v}$ to the vertices so that
$y_{u}+y_{v}\geq w_{u,v}$ for all edges $(u,v)$ in the cut. In a bipartite
graph the minimum $w$-vertex cover is dual to the maximum weight matching.
Therefore, _MSPEC_ can be alternatively stated as: given an edge-weighted
graph, partition the vertices into two sets with $s$ in one set and $t$ in the
other, and minimize the weight of a maximum matching of the edges crossing
between the two sets, e.g, see Figure 2(a).

We can also formulate _MSPEC_ as an integer program (ILP). Although we do not
use it in our algorithms, it may lead to future developments. Let $\Pi_{st}$
be the set of all paths in $G$ from $s$ to $t$. We will have a non-negative
variable $p_{u}$ for each $u\in V$ and a $0$-$1$ variable $x_{u,v}$ for each
edge $(u,v)\in E$ with the intended interpretation that the cut edges have
$x_{u,v}=1$.

$\begin{array}[]{ll@{\hspace{2mm}}ll}&\min\displaystyle\sum_{u\in
V}p_{u}\hfil\hskip 5.69054pt&\\\
&\textit{s.t.}\displaystyle\sum_{(u,v)\in\pi}x_{u,v}\geq 1\hfil\hskip
5.69054pt&\forall\pi\in\Pi_{st}\\\ &p_{u}+p_{v}\geq w_{u,v}x_{u,v}\hfil\hskip
5.69054pt&\forall(u,v)\in E\\\ &x_{u,v}\in\\{0,1\\}\hfil\hskip
5.69054pt&\forall(u,v)\in E\\\ &p_{u}\geq 0\hfil\hskip 5.69054pt&\forall u\in
V\\\ &p_{s}=p_{t}=0\hfil\hskip 5.69054pt\end{array}$ (1)

Figure 2: (a) Illustration for _MSPEC_. The powers on the vertices are shown
in red. The cut edges are in gray and the edges of the maximum matching are
shown in bold gray. (b) The integrality gap of ILP (1) is 2 for this graph.

This integer programming formulation has an integrality gap of at least $2$.
Consider the graph shown in Figure 2(b). It is easy to verify that the optimum
integral solution has cost $1$. On the other hand, if we assign $p_{c}=0.5$
and $x_{b,c}=0.5,x_{c,d}=0.5$ and $x_{c,t}=0.5$, this is a feasible solution
for the LP relaxation of the above ILP. The integrality gap of this ILP is
thus $\geq\frac{1}{0.5}=2$.

##  3 Barrier Coverage in a Sensor Network

Our motivation for studying the Minimum Shared-Power Edge Cut problem comes
from a problem of measuring barrier coverage in a sensor network. A sensor
network consists of a set of sensors, where each sensor is modelled as a unit
disk (a disk of radius 1) in the plane. The location of a sensor is the center
point of its unit disk, and the sensor detects points within its unit disk.

A sensor network provides a barrier between one region of the plane, $R_{1}$,
and another region, $R_{2}$, if any point that travels from $R_{1}$ to $R_{2}$
will be detected by the sensors, i.e., there is no path between the two
regions that remains outside all the disks.

In a _rectangular barrier_ the sensors are located at points in a rectangle
and the sensor network must detect any path that crosses the rectangle from
below to above. Kumar et al. [13] introduced this concept and suggested
measuring “barrier coverage” as the minimum value $k$ such that every path
that crosses the barrier intersects at least $k$ sensor disks. Equivalently,
the barrier coverage is the minimum number of sensors that must be removed to
allow a path in the free space between disks. For a rectangular barrier, Kumar
et al. showed that barrier coverage can be computed in polynomial time by
applying Menger’s theorem to the intersection graph of the disks—barrier
coverage becomes the minimum size of a vertex cut, which is equal to the
maximum number of vertex disjoint paths that go from the left of the rectangle
to the right of the rectangle.

A number of alternative measures of barrier coverage have been proposed in the
literature with the (conflicting) goals of having a measure that models
reality and that can be computed efficiently. We propose a new measure called
Minimum Shrinkage. Like some of the previous measures (see the following
section for more background) it models the fact that a sensor’s ability to
detect points decreases with distance from the sensor. Our approximation
algorithm for Maximum Shared-Power Edge Cut can be applied to compute Minimum
Shrinkage for rectangular barrier coverage.

Our new measure is defined in Section 3.2, and the reduction to _MSPEC_ is
given in Section 3.3. We begin with further background on barrier coverage in
Section 3.1.

###  3.1 Background on Barrier Coverage

As mentioned above, Kumar et al. [13] introduced the idea of measuring barrier
coverage by the minimum number of sensors whose removal permits a path from
region $R_{1}$ to region $R_{2}$ in the free space outside the sensor disks.

Bereg and Kirkpatrick [5] applied this measure more broadly and called it
“resilience”. They introduced a new measure of barrier coverage called
_thickness_ which is defined to be the minimum, over all paths from $R_{1}$ to
$R_{2}$, of the number of times the path enters a disk, counting repeats.
Whereas resilience seems to be hard to compute except for the case of a
rectangular barrier, thickness can easily be computed in polynomial time using
weighted shortest path algorithms. Bereg and Kirkpatrick showed that thickness
provides a constant-factor approximation to resilience. Korman et al. [12]
provided fixed-parameter tractable algorithms (parameterized by the
resilience) and a PTAS when each point of the plane is covered by a few disks.

The above measures implicitly assume that a sensor can detect points uniformly
across its unit disk. In reality, the power of a sensor decreases with
distance, and a sensor can detect closer points more easily than farther
points. In order to take distance from the sensors into account, we can think
of diminishing the power of the sensors, or shrinking their unit disks.
Meguerdichian et al. [16] formulated this as a “maximum breach path”—to find
the maximum value $d$ such that there is a path from region $R_{1}$ to $R_{2}$
where every point of the path is at least distance $d$ from every sensor
point. They showed that a maximum breach path should travel on the Voronoi
diagram of the sensor points, and thus can be computed in time $O(n\log n)$.
The maximum breach measure is equivalent to asking for the maximum value $d$
such that shrinking all the sensor disks to radius $d$ permits a path in the
free space between the shrunken disks.

In a related paper Megerian et al. [15] introduced the notion of “exposure”.
This measure takes into account, not only how close the path goes to the
sensor points, but also the amount of time that is spent close to sensor
points. More formally, the “[all] sensor field intensity” at a point is the
sum of all the sensor’s powers at that point, and “exposure” along a path is
the integral of the sensor field intensity along the path. Computing a path of
minimum exposure is a very difficult continuous problem. Djidjev [8] gave an
approximation algorithm, using the idea of discretizing the domain. For the
special case of a rectangular barrier, there is a min-max formula that relates
the minimum exposure of a path from bottom to top of the rectangle and a
maximum flow from left to right of the rectangle—see Strang [24] and Mitchell
[17].

For further background refer to Wang’s survey on coverage problems in sensor
networks [25] (in particular, Section 6).

###  3.2 Minimum Shrinkage

We propose a new measure of barrier coverage, called _minimum shrinkage_. This
new measure models the reality that a sensor’s detection ability drops off
with distance.

To _shrink_ a unit disk by amount $s_{i}$ for $0\leq s_{i}\leq 1$ means to
decrease its radius by $s_{i}$, i.e., to replace the unit disk by a disk of
radius $(1-s_{i})$. Let $c_{i}$, $i=1,\ldots,n$ be the locations of unit disk
sensors in a sensor network that is supposed to act as a barrier between
region $R_{1}$ and region $R_{2}$ in the plane. The _minimum shrinkage_ of the
sensor network is the minimum $\sum s_{i}$ such that if we shrink the $i^{\rm
th}$ sensor disk by $s_{i}$, $1\leq i\leq n$, then the network no longer
provides a barrier between regions $R_{1}$ and $R_{2}$, i.e., there is a path
from $R_{1}$ to $R_{2}$ in the free space between the shrunken disks. See
Figure 1.

###  3.3 Reduction from Minimum Shrinkage to _MSPEC_

We will show that the Minimum Shrinkage problem for rectangular barrier
coverage can be formulated as an _MSPEC_ problem.

Given a set of $n$ points $P$ in $\mathbb{R}^{2}$, the _unit disk graph_
induced by $P$, denoted _UDG_($P$), is an embedded graph with vertex set $P$
and an edge $(u,v)$ when the unit disks centered at $u$ and $v$ intersect,
i.e., the edge set is $\\{(u,v):u,v\in P$ and dist$(u,v)\leq 2\\}$.

An instance of the Minimum Shrinkage problem for rectangular barrier coverage
consists of a set of points $P$ inside a rectangle $R$. To reduce to _MSPEC_
we start with the graph _UDG_($P$). Define the weight of edge $(u,v)$ to be
$(2-\text{dist}(u,v))$. This is the amount of shrinkage at $u$ and $v$ that is
needed to make the disks at $u$ and $v$ non-intersecting. We add two special
vertices $s$ and $t$. Vertex $s$ is connected to every vertex whose unit disk
intersects the left boundary of $R$, and vertex $t$ is connected to every
vertex whose unit disk intersects the right boundary of $R$. To define the
weight of these edges, let $R_{l}$ and $R_{r}$ be the lines through the left
and right boundaries of $R$, respectively, and, for line $L$, let
$\text{dist}(u,L)$ be the distance from point $u$ to line $L$. Define the
weight of an edge $(s,u)$ to be $(1-\text{dist}(u,R_{l}))$. This is the amount
of shrinkage needed to make the disk at $u$ not intersect the left boundary of
$R$. Similarly, define the weight of an edge $(t,u)$ to be
$(1-\text{dist}(u,R_{r}))$. It is straight-forward to show that _MSPEC_ on the
resulting graph solves the _MSS_ problem where we interpret $p_{v}$ as the
amount to shrink the disk centered at $v$.

Observe that this reduction still works (with obvious modifications) for the
more general problem where each sensor disk has a specified radius, i.e. the
radii are not uniform.

##  4 Minimum Bottleneck Shared-Power Edge Cut

To approximately solve the minimum shared-power edge cut problem, we will need
a solution to another closely related problem which we refer to as the
“Minimum Bottleneck Shared-Power Edge Cut Problem”. This problem is very
similar to _MSPEC_ in that we want to assign powers to the vertices such that
$s$ and $t$ become disconnected if we remove any edge where the sum of the
powers on its endpoints is at least its weight. The key difference is that
instead of assigning different powers to every vertex we will assign the same
power to each vertex in $V$ and minimize this “bottleneck” power. More
precisely, we want the minimum value $p$ such that $s$ and $t$ become
disconnected if we remove the edges $(u,v),u,v\in V$ with $2p\geq w_{u,v}$ and
the edges $(u,v),u\in V,v\in\\{s,t\\}$ with $p\geq w_{u,v}$.

In the case of barrier coverage for a rectangular barrier, the minimum
bottleneck shared-power edge cut is equivalent to the “maximum breach path”
measure introduced by Meguerdichian et al. [16]. Namely, we want to shrink all
sensor disks by the same (minimum) amount to permit a path in the free space
between disks. Meguerdichian et al. computed the maximum breach path in
polynomial time using Voronoi diagrams. It is interesting that the problem can
be solved in a more general non-geometric setting.

In the following we show how to obtain an exact solution to the minimum
bottleneck shared-power edge cut in polynomial time. Let the set of removed
edges in the optimal solution be $M^{*}$ and the optimal power be $p^{*}$.

######  Claim 1.

There is an edge $e=(u,v)\in M^{*}$ which is _tight_ for $p^{*}$, i.e.,
$w_{u,v}=2p^{*}$ if $u,v\in V$ or $w_{u,v}=p^{*}$ if $u\in V$ and
$v\in\\{s,t\\}$.

###### Proof.

Suppose $w_{u,v}<2p^{*}$ for all edges in $M^{*}$ with both end points in $V$
and $w_{u,v}<p^{*}$ for all edges in $M^{*}$ with one end point in $V$ . Then
we can reduce $p^{*}$ to $(p^{*}-\varepsilon)$ and still ensure that
$w_{u,v}\leq 2(p^{*}-\varepsilon)$ for all edges in $M^{*}$ with both end
points in $V$ and $w_{u,v}\leq p^{*}-\varepsilon$ for edges in $M^{*}$ with
one end point in $V$, so $p^{*}$ was not the minimum bottleneck power. ∎

######  Theorem 1.

Minimum Bottleneck Shared-Power Edge Cut can be solved optimally in
$O((n+m)\log m)$ time.

###### Proof.

Define the _power requirement_ of edge $e=(u,v)$ to be $\frac{1}{2}w_{u,v}$ if
$u,v\in V$ or $w_{u,v}$ if $u\in V$ and $v\in\\{s,t\\}$. By Claim 1, $p^{*}$
is equal to the power requirement for some edge $e\in E$, and we can use
binary search on the power requirements to find the minimum $p$ such that $s$
and $t$ become disconnected if we remove the edges whose power requirement is
at most $p$. We sort all the power requirements in non-decreasing order and
perform binary search on this list. To test a value $p^{\prime}$ from this
list, we create a graph $G^{\prime}$ with vertices of $G$ and edges of $G$
whose power requirement is greater than $p^{\prime}$.

If $s$ and $t$ are disconnected in $G^{\prime}$ we recursively perform a
binary search on the power requirements between $0$ and $p^{\prime}$,
otherwise we recurse on all higher power requirements. The running time for
this approach is determined by the binary search, which takes time $O(\log
m)$, and by checking connectivity of $s$ and $t$ in $G^{\prime}$, which takes
time $O(n+m)$. Therefore, the total running time is $O((n+m)\log m)$. Here $n$
is the number of vertices and $m$ is the number of edges. ∎

##  5 Approximation Scheme for _MSPEC_

The idea of our approximation algorithm is to convert the _MSPEC_ problem to a
minimum vertex cut problem. Observe that if we can only assign power 0 or 1 to
every vertex in $V$, then our problem is Minimum Vertex Cut—remove a minimum
number of vertices to disconnect $s$ and $t$. We will discretize our problem
by replacing each vertex $v\in V$ by multiple copies of $v$ such that removing
one copy corresponds to assigning a small fraction of the maximum power to
$v$. A similar approach was used, in a geometric setting, by Agarwal et al.
[1]. We want to ensure that the discretization introduces an error of at most
$\frac{\varepsilon}{n}$ for each vertex with respect to the optimum solution.

In order to carry out this plan, we need an upper bound on the maximum power
we might assign to any vertex, and, for the error analysis, we need a lower
bound on the optimum solution. We obtain these bounds from the minimum
bottleneck shared-power edge cut. Let $n=|V|$, let $p^{*}$ be the minimum
power for the bottleneck shared-power edge cut problem, and let _OPT_ be the
minimum power sum for _MSPEC_.

######  Lemma 2.

$p^{*}\leq\emph{OPT}\leq np^{*}$.

###### Proof.

Assigning power $p^{*}$ to every vertex in $V$ provides a feasible solution to
_MSPEC_ , and therefore $\emph{OPT}\leq np^{*}$.

For the other inequality, let $p_{\max}$ be the maximum power assigned to any
vertex of $V$ in an optimum solution to _MSPEC_. Then
$p_{\max}\leq\emph{OPT}$. Assigning $p_{\max}$ to every vertex in $V$ provides
a solution to the minimum bottleneck shared-power edge cut. Therefore
$p^{*}\leq p_{\max}\leq\emph{OPT}$. ∎

From this lemma, we know that the maximum power we might assign to a vertex is
$np^{*}$. The lemma also implies that if we introduce an error of at most
$\alpha=\frac{\varepsilon}{n}p^{*}$ for each vertex, then the total error over
all vertices will be at most $\varepsilon p^{*}\leq\varepsilon\emph{OPT}$. Our
plan is to construct a new graph $G^{\prime}=(V^{\prime},E^{\prime})$ in which
we replace each vertex of $V$ by $c$ copies, where each copy represents power
$\alpha$. Since the total power that we might assign to the vertex is
$np^{*}$, the number of copies of the vertex that we need is
$c=\lceil\frac{np^{*}}{\alpha}\rceil=\lceil\frac{n^{2}}{\varepsilon}\rceil$.
We will replace each vertex of $V$ by a sequence of $c$ vertices,
$v(0),v(1),\ldots,v(c-1)$.

Removing the first $k$ vertices of the sequence will correspond to assigning
power $k\alpha$ to $v$. In $G^{\prime}$ we will assign edges to the copies
$v(i)$ to reflect this. In particular, for $u,v\in V$ we put an edge
$(u(i),v(j))$ in $G^{\prime}$ if $i\alpha+j\alpha<w_{u,v}$. For $u\in
V,x\in\\{s,t\\}$ we put an edge $(u(i),x)$ in $G^{\prime}$ if
$i\alpha<w_{u,x}$. A related idea of discretizing the choices using vertices
combined with minimum cuts was developed by Hochbaum et al. [10, 11] for
integer linear programms with at most two variables per inequality. They rely
on an algorithm by Picard [22] for finding the minimum-cost closure of a
directed graph.

The precise construction of $G^{\prime}$ is given in Algorithm 1.

Algorithm 1 Construction of $G^{\prime}$

$\forall v\in V$, make $c=\lceil\frac{n^{2}}{\varepsilon}\rceil$ copies of $v$
numbered $v(0),v(1),\dots,v(c-1)$

$V^{\prime}=\\{v(i)\mid\forall v\in V,0\leq i<c\\}\cup\\{s,t\\}$

$\alpha=\frac{\varepsilon p^{*}}{n}$

$E^{\prime}=\\{(u(i),v(j))\mid i\alpha+j\alpha<w_{u,v}\\}\cup\\{(u(i),x)\mid
x\in\\{s,t\\},i\alpha<w_{u,x}\\}$

Our approximation algorithm now proceeds as follows. We find a minimum $s$-$t$
vertex cut in $G^{\prime}$, denoted $K^{*}$, and use it to define power values
on the vertices of $G$ as given in Algorithm 2.

Algorithm 2 Approximation Algorithm for _MSPEC_

Construct $G^{\prime}$ as in Algorithm 1

$K^{*}\leftarrow$ minimum $s$-$t$ vertex cut for $G^{\prime}$

$k^{*}_{v}=|\\{v(j)\in K^{*}\\}|$ for $v\in V$

$p_{v}=k^{*}_{v}\cdot\alpha$ for $v\in V$

return $p=(p_{v})_{v\in V}$ as the solution for _MSPEC_ on $G$

To prove that this algorithm is an FPTAS we will first prove that the solution
returned by the algorithm is indeed a feasible solution for _MSPEC_. Then, to
bound the approximation factor, we will derive an upper bound on the solution
returned by the algorithm in terms of the optimum solution to _MSPEC_. We
first prove some properties of $G^{\prime}$ and of $K^{*}$.

######  Claim 2.

If $v\in V$ and $i_{1}<i_{2}$, then in $G^{\prime}$ the neighbourhoods of
$v(i_{1})$ and $v(i_{2})$ are related by $N(v(i_{1}))\supseteq N(v(i_{2}))$.

###### Proof.

We will show that $(v(i_{2}),x)\in E^{\prime}$ implies $(v(i_{1}),x)\in
E^{\prime}$.

Case 1. $x=u(j)$ for $u\in V$. Since the edge $(v(i_{2}),u(j))$ is in
$E^{\prime}$ we have $i_{2}\alpha+j\alpha<w_{v,u}$ so
$i_{1}\alpha+j\alpha<w_{v,u}$ which implies $(v(i_{1}),u(j))\in E^{\prime}$.

Case 2. $x\in\\{s,t\\}$. Since the edge $(v(i_{2}),x)$ is in $E^{\prime}$ we
have $i_{2}\alpha<w_{v,x}$ so $i_{1}\alpha<w_{v,x}$ which implies
$(v(i_{1}),x)\in E^{\prime}$. ∎

######  Claim 3.

The copies of $v$ in $K^{*}$ are $v(0),v(1),\ldots,v(k^{*}_{v}-1)$.

###### Proof.

We will prove that the copies of $v$ in $K^{*}$ form a prefix of
$v(0),v(1),\ldots v(c-1)$. Then the result follows since there are $k_{v}^{*}$
copies of $v$ in $K^{*}$.

Consider $i_{1}<i_{2}$. By Claim 2, $N(v(i_{1}))\supseteq N(v(i_{2}))$. Now
observe that if a graph contains vertices $u$ and $v$ with $N(u)\supseteq
N(v)$ and $v$ is in a minimum vertex cut, then $u$ must be as well, since $u$
is a duplicate of $v$ with possibly some more edges. Therefore if $v(i_{2})$
is in $K^{*}$ then so is $v(i_{1})$. ∎

######  Lemma 3.

A solution of Algorithm 2 is a feasible solution for MSPEC and the sum of the
assigned powers is $\alpha|K^{*}|$.

###### Proof.

Let $G_{p}$ be the result of removing from $G$ all the edges $(u,v)$ with
$p_{u}+p_{v}\geq w_{u,v}$ where $p$ is as defined by Algorithm 2. (Recall that
we always set $p_{s}=p_{t}=0$.) We must show that $s$ and $t$ are disconnected
in $G_{p}$. Suppose not. Then there is an $s$-$t$ path $P$ in $G_{p}$, say
$s,x_{1},x_{2},\ldots,x_{l},t$. We will show that the path
$P^{\prime}=s,x_{1}(k_{x_{1}}^{*}),x_{2}(k_{x_{2}}^{*}),\ldots,x_{l}(k_{x_{l}}^{*}),t$
exists in $G^{\prime}-K^{*}$, a contradiction to $K^{*}$ being an $s$-$t$
vertex cut.

First, note that all the vertices of $P^{\prime}$ lie in $G^{\prime}-K^{*}$ by
Claim 3. Consider an edge $(u,v)$ of the path $P$ with $u,v\in V$. Since this
edge is still present in $G_{p}$, we know that $p_{u}+p_{v}<w_{u,v}$. Thus by
the definition of the $p$ values, $k^{*}_{u}\alpha+k^{*}_{v}\alpha<w_{u,v}$.
By the construction of $G^{\prime}$, the edge $(u(k_{u}^{*}),v(k_{v}^{*}))$ is
in $E^{\prime}$.

It remains to consider the edges of $P$ incident to $s$ and $t$. Since the
edge $(s,x_{1})$ is in $G_{p}$, we know that $p_{x_{1}}<w_{s,x_{1}}$. Thus by
the definition of the $p$ values, $k^{*}_{x_{1}}\alpha<w(s,x_{1})$. By the
construction of $G^{\prime}$, the edge $(s,x_{1}(k_{x_{1}}^{*}))$ is in
$E^{\prime}$. The argument for edge $(x_{l},t)$ is similar.

Thus the path $P^{\prime}$ exists in $G^{\prime}-K^{*}$ which gives the
desired contradiction.

In our solution we assign a power of $p_{v}$ to vertex $v$, so the total power
assigned is:

$\sum_{v\in V}p_{v}=\sum_{v\in V}k^{*}_{v}\cdot\alpha=\alpha\sum_{v\in
V}k^{*}_{v}=\alpha|K^{*}|\qed$ (2)

Next we prove an upper bound on the size of the set $K^{*}$ (a minimum $s$-$t$
vertex cut in $G^{\prime}$) in terms of an optimum solution to _MSPEC_. Let
$p^{*}_{v},v\in V$ be an optimum power assignment for _MSPEC_. Let
$p^{*}_{s}=p^{*}_{t}=0$.

######  Lemma 4.

$G^{\prime}$ has a vertex cut $K$ of size
$\sum\lceil\frac{p_{v}^{*}}{\alpha}\rceil$. Thus
$|K^{*}|\leq\sum\lceil\frac{p_{v}^{*}}{\alpha}\rceil$.

###### Proof.

Let $M^{*}$ be the set of edges of $G$ that are removed by the optimum power
assignment $p^{*}_{v},v\in V$, i.e., $M^{*}=\\{(u,v):p^{*}_{u}+p^{*}_{v}\geq
w_{u,v}\\}$. $M^{*}$ is an $s$-$t$ cut in $G$.

Define $k_{v}=\lceil\frac{p_{v}^{*}}{\alpha}\rceil$ for $v\in V$. Define $K$,
a set of vertices of $G^{\prime}$, to consist of the first $k_{v}$ copies of
each vertex $v\in V$, i.e., $K=\\{v(i):v\in V,0\leq i<k_{v}\\}$. Observe that
$|K|=\sum\lceil\frac{p_{v}^{*}}{\alpha}\rceil$. To prove the lemma, we just
need to show that $K$ is an $s$-$t$ vertex cut in $G^{\prime}$.

It suffices to show that if $(u,v)\in M^{*}$ then there is no copy of edge
$(u,v)$ in $G^{\prime}-K$. Consider an edge $(u,v)\in M^{*}$. Then
$p^{*}_{u}+p^{*}_{v}\geq w_{u,v}$, so
$\lceil\frac{p_{u}^{*}}{\alpha}\rceil\alpha+\lceil\frac{p_{v}^{*}}{\alpha}\rceil\alpha\geq
w_{u,v}$, i.e., $k_{u}\alpha+k_{v}\alpha\geq w_{u,v}$.

Now observe that if $i\geq k_{u}$ and $j\geq k_{v}$ then $i\alpha+j\alpha\geq
k_{u}\alpha+k_{v}\alpha\geq w_{u,v}$, so $(u(i),v(j))$ is not an edge of
$G^{\prime}$ (by definition of $G^{\prime}$). On the other hand, if $i<k_{u}$
then $u(i)\in K$, so $u(i)$ is not a vertex of $G^{\prime}-K$, and similarly,
if $j<k_{v}$ then $v(j)\in K$, so $v(j)$ is not a vertex of $G^{\prime}-K$.
Thus no copy of the edge $(u,v)$ exists in $G^{\prime}-K$. This proves that
$K$ is an $s$-$t$ vertex cut in $G^{\prime}$ and completes the proof of the
lemma. ∎

######  Theorem 5.

Algorithm 2 is a fully polynomial time approximation scheme (FPTAS) for the
Minimum Shared-Power Edge Cut problem (MSPEC). Furthermore, the running time
of Algorithm 2 is $O(n^{5.5}m\varepsilon^{-2.5})$.

###### Proof.

By Lemma 3 we know that Algorithm 2 gives a solution to _MSPEC_ of cost
$\alpha|K^{*}|$, and by Lemma 4 we have
$|K^{*}|\leq\sum\lceil\frac{p_{v}^{*}}{\alpha}\rceil$.

Approximate solution $\displaystyle=~{}\alpha|K^{*}|\leq\sum_{v\in
V}\Big{\lceil}\frac{p_{v}^{*}}{\alpha}\Big{\rceil}\cdot\alpha~{}<~{}\sum_{v\in
V}\Big{(}\frac{p_{v}^{*}}{\alpha}+1\Big{)}\cdot\alpha$
$\displaystyle=~{}\sum_{v\in V}\Big{(}p_{v}^{*}+\alpha\Big{)}~{}=~{}\sum_{v\in
V}p_{v}^{*}+n\alpha~{}=~{}OPT+n\alpha.$

Thus the approximation ratio is at most
$\frac{OPT+n\alpha}{OPT}=\frac{OPT+\frac{n\varepsilon
p^{*}}{n}}{OPT}=1+\frac{\varepsilon p^{*}}{OPT}\leq(1+\varepsilon)$, since
$OPT\geq p^{*}$. The running time of Algorithm 2 depends on the running time
of finding a minimum $s$-$t$ vertex cut and this can be done in time
$O(n^{1/2}m)=O(n^{2.5})$ for a graph with $n$ vertices and $m$ edges using a
modified version of Dinitz’s flow algorithm [18, Chapter 1] [23, Corollary
9.7a]. If our original graph $G$ has $n$ vertices and $m$ edges, then the
graph $G^{\prime}$ has $|V^{\prime}|=nc=O(\frac{n^{3}}{\varepsilon})$ vertices
and at most $|E^{\prime}|\leq|E|c^{2}=O(\frac{mn^{4}}{\varepsilon^{2}})$
edges, and Algorithm 2 finds a vertex cut in graph $G^{\prime}$ in
$O(n^{5.5}m\varepsilon^{-2.5})$ time. ∎

##  6 Variations of _MSPEC_

In this section we give polynomial time algorithms for three special cases of
_MSPEC_ , when the edge weights are uniform, or integral, and when the power
values at each vertex are restricted to a polynomially bounded domain. In the
final section we show that our FPTAS extends to a more general version of
_MSPEC_ where there are costs on the vertices.

###  6.1 Uniform/Integral edge weights

We use the alternative formulation of _MSPEC_ given at the start of Section 2.
For any instance of _MSPEC_ there is a vertex partition $S,T$ with $s\in S$
and $t\in T$, such that the minimum power sum is equal to the minimum
“$w$-vertex cover” in the bipartite graph $B$ of edges between $S$ and $T$,
and this is equal to the weight of a maximum matching in $B$. By Kőnig’s
Theorem and its generalization to weights (Egerváry’s Theorem, see [23,
Theorem 17.1]) we know that if the edge weights are integral then there is an
optimal solution where the power values are also integral, and if the edge
weights are all 1 then it suffices to consider power values that are
$\\{0,1\\}$-valued.

For _MSPEC_ with uniform edge weights, we can scale so that all edge weights
are 1. Then, by the above, the power values will be 0 or 1 and the problem
reduces to Minimum Vertex Cut, which can be solved in time $O(n^{1/2}m)$ time
as discussed in the previous section.

For _MSPEC_ with integer edge weights, we can assume that the power values are
integral. Furthermore, if the edge weights are bounded by $W$, then so are the
power values. We can then use the same approach as Algorithm 1, but make $W+1$
copies of each vertex, and set $\alpha=1$. This solves _MSPEC_ exactly, with a
running time of $O((nW)^{1/2}(mW^{2}))=O(n^{1/2}mW^{5/2})$. Thus it provides a
pseudo polynomial time algorithm for _MSPEC_ with integral edge weights.

###  6.2 Polynomial Domain

In activation network design problems, one of the most common assumptions is
that of a ‘polynomial domain’ for the power values [20, 19]. This means that
the power values for vertex $v$ come from a set $D^{v}$ whose size is bounded
by a polynomial in $n=|V|$. The polynomial domain assumption is realistic for
wireless networks when there are a small number of possible powers that can be
assigned to a vertex. However, this does not apply to the minimum shrinkage
problem because we are using shrinkage as a measure of barrier coverage rather
than making any assumption about sensor powers.

Under the polynomial domain assumption, _MSPEC_ admits a polynomial time
algorithm. We sketch the algorithm. The technique is similar to the one we
used in the previous section. We assume $0\in D^{v}$ for all $v$ (otherwise,
we must pay $\min(D^{v})$ directly, and can then subtract it from all later
values). Let the values in $D^{v}$ be
$d^{v}_{0},d^{v}_{1},\ldots,d^{v}_{c_{v}}$ in increasing order. We modify the
construction of graph $G^{\prime}$ from Algorithm 1, to create
$|D^{v}|=c_{v}+1$ copies of each vertex $v$, which we number
$v(0),v(1),\ldots,v(c_{v})$. We assign a cost of $d^{v}_{i+1}-d^{v}_{i}$ to
$v(i)$ for $i=0,\ldots,c_{v}-1$, and $\infty$ to $v(c_{v})$.

In graph $G^{\prime}$ we add an edge between two vertices $u(i)$ and $v(j)$ if
$d^{u}_{i}+d^{v}_{j}<w_{u,v}$. We now run a max flow algorithm to find the
minimum cost $s$-$t$ vertex cut in $G^{\prime}$ by applying the standard graph
transformation (see [26]) to convert a vertex cut to an edge cut, and vertex
weights to edge capacities. If the minimum cost is $\infty$ then there is no
feasible assignment of powers from the given domains. Otherwise, for vertex
$v$, if $i$ is the maximum index for which $v(i)$ is included in the cut, then
we assign $p_{v}=d^{v}_{i+1}$. Note that a feasible solution has $i<c_{v}$ so
this is well-defined.

For correctness, first observe that the prefix property, as mentioned in Claim
3, still holds. Next, we claim that if the assigned powers do not remove edge
$(u,v)$ then there was a copy of that edge in $G^{\prime}$ after removing the
optimum vertex cut. Suppose we assigned $p_{u}=d^{u}_{i+1}$ and
$p_{v}=d^{v}_{j+1}$ but $p_{u}+p_{v}<w_{u,v}$. Then the edge $(u(i+1),v(j+1))$
still exists in $G^{\prime}$. In the other direction, a solution to _MSPEC_
with powers from the given domains yields a vertex cut in $G^{\prime}$ of
equal cost.

The running time for the algorithm is determined by the running time of the
standard max-flow algorithms, which is $O(n^{3}/\log n)$ [6] (or see [23,
Section 10.8]). The number of vertices in the new graph $G^{\prime}$ is
$\sum_{v}|D^{v}|$, thus the running time is
$O((\sum_{v}|D^{v}|)^{3}/\log(\sum_{v}|D^{v}|))$.

###  6.3 _MSPEC_ with Vertex Costs

In this section we outline an FPTAS for a more general version of _MSPEC_ with
multiplicative vertex costs. Formally, the problem is defined as:

Input: Graph $G=(V\cup\\{s,t\\},E)$ with a non-negative weight $w_{u,v}$ on
each edge $(u,v)\in E$ and a non-negative cost $c_{v}$ on every vertex $v\in
V$ .

Problem: Assign a non-negative power $p_{v}$ to each $v\in V$ and assign
$p_{s}=p_{t}=0$ such that removing the edge set $\\{(u,v)\in E:p_{u}+p_{v}\geq
w_{u,v}\\}$ disconnects $s$ and $t$ and $\sum_{v\in V}c_{v}p_{v}$ is
minimized.

Using a similar bottleneck and discretization approach, we can get an FPTAS
for _MSPEC_ with vertex costs.

The key idea is to consider the power-cost $c_{v}p_{v}$ instead of the power
at each vertex. This enables us to get a bottleneck solution analogous to
Theorem 1 by doing a binary search on the vertex power-costs. Similarly, for
the construction phase of graph $G^{\prime}$ as described in Algorithm 1, we
add an edge between $u(i)$ and $v(j)$ to $G^{\prime}$ if
$\frac{i\alpha}{c_{u}}+\frac{j\alpha}{c_{v}}<w_{u,v}$. The remainder of the
algorithm and the proofs carry over after similar modifications.

##  7 Faster Approximation for _MSPEC_

In this section, we will briefly mention how to speed up our FPTAS from the
current running time of $O(n^{5.5}m\varepsilon^{-2.5})$ to
$O(n^{3}m\varepsilon^{-2.5}+m^{3}/\log m)$. To accomplish this, we discretize
the problem using a faster $2$-approximation for _MSPEC_ instead of the
$n$-approximation given by the minimum bottleneck shared power edge cut. Let
_OPT_ be the optimum solution value for _MSPEC_.

For the 2-approximation, we consider a discrete version of _MSPEC_ where a
vertex can only be assigned a power equal to the weight of one of its incident
edges.

With this restriction, the number of possible choices of power assignment at a
given vertex is equal to the degree of the vertex in $G$.

Thus the polynomial domain assumption is satisfied and the algorithm of
Subsection 6.2 solves this discrete version in time $O((\sum_{v}{\rm
deg}(v))^{3}/\log(\sum_{v}{\rm deg}(v)))=O(m^{3}/\log m)$.

We now use the fact that the discrete _MSPEC_ provides a 2-approximation. This
was proved more generally by Panigrahi [20, Lemma 3.11], but we include his
short argument.

######  Theorem 6.

[20] Discrete _MSPEC_ is an 2-approximation for _MSPEC_.

###### Proof.

We will show that $2\emph{OPT}$ is an upper bound for the discrete version of
_MSPEC_ , which proves the theorem. Let $C$ be the set of edges in the $s$-$t$
cut determined by an optimum solution. For each edge $e=(u,v)\in C$, select
the endpoint $v$ of higher power. Then $p_{v}\geq\frac{1}{2}w_{u,v}$. For each
selected vertex we raise $p_{v}$ to the maximum $w_{x,v}$ where $(x,v)$ is an
edge of $C$ that selects $v$. Then we at most double the power of $v$.
Furthermore, any vertex not selected can have its power decreased to 0. The
new power values still activate all edges of $C$ and provide a solution to
discrete _MSPEC_. ∎

Let $Z$ be the optimal value of a solution to the discrete _MSPEC_ problem on
graph $G$. Clearly $\emph{OPT}\leq Z$, and from Theorem 6, we have
$Z\leq~{}2\emph{OPT}$. Thus:

$\frac{Z}{2}\leq OPT\leq Z$ (3)

We can use these bounds in place of those in Lemma 2 to obtain a faster
approximation algorithm for _MSPEC_. From Equation (3), the maximum power we
assign to any vertex is $Z$. If we introduce an error of at most
$\alpha=\frac{\varepsilon Z}{2n}$ at each vertex, the total error will be at
most $n\alpha\leq\varepsilon\emph{OPT}$. We construct the graph $G^{\prime}$
as in Algorithm 1, though instead of taking
$\lceil\frac{n^{2}}{\varepsilon}\rceil$ copies of each vertex, we only use
$c=\lceil\frac{Z}{\alpha}\rceil=\lceil\frac{2Zn}{\varepsilon
Z}\rceil=\lceil\frac{2n}{\varepsilon}\rceil$ copies.

Algorithm 2 on this new $G^{\prime}$ is an FPTAS with a running time of
$O(|V^{\prime}|^{1/2}|E^{\prime}|)$=
$O((n\frac{n}{\varepsilon})^{1/2}(m(\frac{n}{\varepsilon})^{2}))$
$=O(n^{3}m\varepsilon^{-2.5})$. Since the time to compute $Z$ is
$O(m^{3}/\log(m))$, the overall running time of our fast FPTAS is
$O(n^{3}m\varepsilon^{-2.5}+m^{3}/\log m)$. In addition to improving the
running time, this algorithm also improves the space complexity by at least
$O(n^{2})$.

##  8 Open Problems

The biggest open question is to settle the complexity of the _MSPEC_
problem—is it in P? NP-hard? For hardness, a starting point would be to show
that _MSPEC_ with vertex costs is NP-hard. On the other side, the complexity
of the minimum shrinkage problem (i.e., the special case of _MSPEC_ arising
from shrinking unit disks in the plane) is also open. Can the geometry of unit
disk graphs be used to develop a polynomial time algorithm?

Acknowledgements. This work was begun at the Fifth Annual Workshop on Geometry
and Graphs, held at the Bellairs Research Institute in Barbados, March 5-10,
2017. We thank the organizers and all participants for the productive and
positive atmosphere. We thank Lap Chi Lau for helpful suggestions.

## References

  * [1] Pankaj K. Agarwal, Sariel Har-Peled, Haim Kaplan, and Micha Sharir.  Union of random Minkowski sums and network vulnerability analysis.  Discrete & Computational Geometry, 52(3):551–582, 2014.
  * [2] Hasna Mohsen Alqahtani and Thomas Erlebach.  Approximation algorithms for disjoint st-paths with minimum activation cost.  In Proceedings of the International Conference on Algorithms and Complexity (CIAC), pages 1–12. Springer, 2013.
  * [3] Ernst Althaus, Gruia Calinescu, Ion I. Mandoiu, Sushil Prasad, Nickolay Tchervenski, and Alexander Zelikovsky.  Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks.  Wireless Networks, 12(3):287–299, 2006.
  * [4] Eric Angel, Evripidis Bampis, Vincent Chau, and Alexander Kononov.  Min-power covering problems.  In Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pages 367–377. Springer, 2015.
  * [5] Sergey Bereg and David G. Kirkpatrick.  Approximating barrier resilience in wireless sensor networks.  In Proceedings of the 5th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), volume 5804 of Lecture Notes in Computer Science, pages 29–40. Springer, 2009.
  * [6] Joseph Cheriyan, Torben Hagerup, and Kurt Mehlhorn.  An $o(n^{3})$-time maximum-flow algorithm.  SIAM Journal on Computing, 25(6):1144–1170, 1996.
  * [7] Nachshon Cohen and Zeev Nutov.  Approximating minimum power edge-multi-covers.  Journal of Combinatorial Optimization, 30(3):563–578, 2015.
  * [8] Hristo N. Djidjev.  Approximation algorithms for computing minimum exposure paths in a sensor field.  ACM Transactions on Sensor Networks (TOSN), 7(3):23, 2010.
  * [9] Mohammad T. Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, and Zeev Nutov.  Power optimization for connectivity problems.  Mathematical Programming, 110(1):195–208, 2007.
  * [10] Dorit S Hochbaum, Nimrod Megiddo, Joseph Seffi Naor, and Arie Tamir.  Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality.  Mathematical Programming, 62(1-3):69–83, 1993.
  * [11] Dorit S. Hochbaum and Joseph Naor.  Simple and fast algorithms for linear and integer programs with two variables per inequality.  SIAM J. Comput., 23(6):1179–1192, 1994.
  * [12] Matias Korman, Maarten Löffler, Rodrigo I. Silveira, and Darren Strash.  On the complexity of barrier resilience for fat regions.  In Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), volume 8243 of LNCS, pages 201–216. Springer, 2013\.
  * [13] Santosh Kumar, Ten H. Lai, and Anish Arora.  Barrier coverage with wireless sensors.  Wireless Networks, 13(6):817–834, 2007.
  * [14] Yuval Lando and Zeev Nutov.  On minimum power connectivity problems.  Journal of Discrete Algorithms, 8(2):164–173, 2010.
  * [15] Seapahn Megerian, Farinaz Koushanfar, Gang Qu, Giacomino Veltri, and Miodrag Potkonjak.  Exposure in wireless sensor networks: Theory and practical solutions.  Wireless Networks, 8(5):443–454, 2002.
  * [16] Seapahn Meguerdichian, Farinaz Houshanfar, Miodrag Potkonjak, and Mani B. Srinivasta.  Coverage problems in wireless ad-hoc sensor networks.  In Proceedings INFOCOM, page 1380–1387, 2001.
  * [17] Joseph S.B. Mitchell.  On maximum flows in polyhedral domains.  Journal of Computer and System Sciences, 40(1):88–123, 1990.
  * [18] Hiroshi Nagamochi and Toshihide Ibaraki.  Algorithmic Aspects of Graph Connectivity.  Cambridge University Press, New York, NY, USA, 1 edition, 2008.
  * [19] Zeev Nutov.  Survivable network activation problems.  Theoretical Computer Science, 514:105–115, 2013.
  * [20] Debmalya Panigrahi.  Survivable network design problems in wireless networks.  In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1014–1027, 2011.
  * [21] Debmalya Panigrahi, Partha Dutta, Sharad Jaiswal, K.V.M. Naidu, and Rajeev Rastogi.  Minimum cost topology construction for rural wireless mesh networks.  In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pages 771–779. IEEE, 2008.
  * [22] Jean-Claude Picard.  Maximal closure of a graph and applications to combinatorial problems.  Management science, 22(11):1268–1272, 1976.
  * [23] Alexander Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency, volume A.  Springer Science & Business Media, 2003.
  * [24] Gilbert Strang.  Maximal flow through a domain.  Mathematical Programming, 26(2):123–143, 1983.
  * [25] Bang Wang.  Coverage problems in sensor networks: A survey.  ACM Computing Surveys, 43(4):32:1–32:53, October 2011.
  * [26] Douglas B. West.  Introduction to Graph Theory.  Pearson, 2000.