Gibson, MatthewKanade, GauravPenninger, RainerVaradarajan, KasturiVigo, Ivo2021-12-072021-12-0720161920-180Xhttps://hdl.handle.net/20.500.12588/760Given a set of points in the plane and a set of disks which separate the points, we consider the problem of selecting a minimum size subset of the disks such that any path between any pair of points is intersected by at least one of the selected disks. We present a (9 + epsilon)-approximation algorithm for this problem and show that it is NP-complete even if all disks have unit radius and no disk contains any points. Using a similar reduction, we further show that the Multiterminal Cut problem [9] remains NP-complete on unit disk graphs. Lastly, we prove that removing a minimum subset of a collection of unit disks, such that the plane minus the arrangement of the remaining disks consists of a single connected region is also NP-complete.en-USAttribution 3.0 United Stateshttp://creativecommons.org/licenses/by/3.0/us/Article