  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.
