Computational complexity and approximability of guarding of proximity graphs
Konstantin S. Kobylkin · arXiv (Cornell University) · 2016
Computational complexity and approximability are studied for a problem of intersecting a set of straight line segments with the smallest cardinality set of disks of fixed radii $r\geq 0$ where the set of segments forms a straight line drawing $G=(V,E,F)$ of a planar graph without edge crossings. This problem arises in network security applications (Agarwal et al., 2013). We claim strong NP-hardness of the problem within the class of (edge sets of) Delaunay, TD-Delaunay triangulations and their subgraphs for $r\in [d_{\min},d_{\max}]$ and $r\in [d_{\max},\eta d_{\max}]$ for some large constant $\eta$ as well as within the class of 4-connected TD-Delaunay triangulations for $r=0$ where $d_{\max}$ and $d_{\min}$ are Euclidean lengths of the longest and shortest graph edges respectively. Fast $O(|E|\log|E|)$-time $O(1)$-approximation algorithm is proposed within the class of straight line drawings of planar graphs for which the inequality $r\geq \eta d_{\max}$ holds uniformly for some constant $\eta>0.$