Computational complexity and exact polynomial algorithms are reported for the problem of stabbing a set of straight line segments with a least cardinality set of disks of fixed radii r > 0, where the set of segments forms a straight line drawing G = (V,E) of a planar graph without edge crossings. Similar geometric problems arise in network security applications (Agarwal et al., 2013). We establish the strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs, and other subgraphs (which are often used in network design) for r ∈ [dmin,ηdmax] and some constant η, where dmax and dmin are the Euclidean lengths of the longest and shortest graph edges, respectively.
Keywords: computational complexity, Hitting Set Problem, Continuous Disk Cover problem, Delaunay triangulations.
The paper was received by the Editorial Office on May 19, 2017.
Konstantin Sergeevich Kobylkin, Cand. Phys.-Math. Sci., Krasovsky Institute of Mathematics and Mechanics, Ural branch of Russian Academy of Sciences, Ekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: kobylkinks@gmail.com.
REFERENCES
1. Agarwal P. K., Efrat A., Ganjugunte S. K., D. Hay D., Sankararaman S., Zussman G. The resilience of WDM networks to probabilistic geographical failures. IEEE/ACM Trans. on Networking, 2013, vol. 21, no. 5, pp. 1525–1538. doi: 10.1109/TNET.2012.2232111 .
2. Arkin E. M., Anta A. F., Mitchell J.S., Mosteiro M. A. Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in d dimensions. Comput. Geom., 2015, vol. 48, no. 2, pp. 134–146. doi: 10.1016/j.comgeo.2014.08.008 .
3. Bhattacharya B.K., Jadhav S., Mukhopadhyay A., Robert J.M. Optimal algorithms for some intersection radius problems. Computing, 1994, vol. 52, no. 3, pp. 269–279. doi: 10.1007/BF02246508 .
4. Bose P., Carufel J.L., Durocher S., Taslakian P. Competitive online routing on Delaunay triangulations. In: Ravi R., Gјrtz I.L. (eds) Algorithm Theory – SWAT 2014: Proc., Cham, Springer, 2014, Ser. Lecture Notes in Comput. Sci., vol. 8503, pp. 98–109. doi: 10.1007/978-3-319-08404-6_9 .
5. Bose P., Kirkpatrick D.G., Li Z. Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Comput. Geom., 2003, vol. 26, no. 3, pp. 209–219.
doi: 10.1016/S0925-7721(03)00027-0 .
6. Chan T.M., Grant E. Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom., 2014, vol. 47, no. 2, pp. 112–124. doi: 10.1016/j.comgeo.2012.04.001 .
7. Hasegawa T., Masuyama S., Ibaraki T. Computational complexity of the m-center problems on the plane. Trans. of the Institute of Electronics and Communication Engineers of Japan. Section E., 1981, vol. E64, no. 2, pp. 57–64.
8. Marx D. Efficient approximation schemes for geometric problems? In: Brodal G.S., Leonardi S. (eds) Algorithms — ESA 2005. Berlin, Heidelberg: Springer, 2005, Ser. Lecture Notes in Comput. Sci., vol. 3669, pp. 448–459. doi: 10.1007/11561071_41 .
9. Quanrud K., Har-Peled S. Approximation algorithms for polynomial-expansion and low-density graphs. Algorithms — ESA 2015: Proc. Berlin; Heidelberg: Springer, 2015, Ser. Lecture Notes in Comput. Sci., vol. 9294, pp. 717–728. doi: 10.1007/978-3-662-48350-3_60 .
10. O’Rourke J. Art gallery theorems and algorithms. Oxford: Oxford University Press, 1987. 282 p. ISBN: 0-19-503965-3 .
11. Stojmenovic I., Urrutia J., Bose P., Morin P. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 2001, vol. 7, no. 6, pp. 609–616. doi: 10.1023/A:1012319418150 .
12. Tamassia R., Tollis I.G. Planar grid embedding in linear time. IEEE Trans. on Circuits and Systems, 1989, vol. 36, pp. 1230–1234. doi: 10.1109/31.34669 .
