The inverse Voronoi problem in graphs. I: Hardness. (English) Zbl 1455.68135
Summary: We introduce the inverse Voronoi diagram problem in graphs: given a graph \(G\) with positive edge-lengths and a collection \({\mathbb{U}}\) of subsets of vertices of \(V(G)\), decide whether \({\mathbb{U}}\) is a Voronoi diagram in \(G\) with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C12 | Distance in graphs |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
distances in graphs; Voronoi diagram; inverse Voronoi problem; NP-completeness; parameterized complexitySoftware:
SANETReferences:
| [1] | Aloupis, G., Pérez-Rosés, H., Pineda-Villavicencio, G., Taslakian, P., Trinchet-Almaguer, D.: Fitting Voronoi diagrams to planar tesselations. In: Combinatorial Algorithms—24th International Workshop, IWOCA Lecture Notes in Computer Science, vol. 8288. Springer,, pp. 349-361 (2013). 10.1007/978-3-642-45278-9_30 · Zbl 1408.68141 |
| [2] | Ash, PF; Bolker, ED, Recognizing Dirichlet tessellations, Geom. Dedic., 19, 2, 175-206 (1985) · Zbl 0572.52022 · doi:10.1007/BF00181470 |
| [3] | Bandyapadhyay, S.; Banik, A.; Das, S.; Sarkar, H., Voronoi game on graphs, Theor. Comput. Sci., 562, 270-282 (2015) · Zbl 1303.90057 · doi:10.1016/j.tcs.2014.10.003 |
| [4] | Banerjee, S., Bhattacharya, B.B., Das, S., Karmakar, A., Maheshwari, A., Roy, S.: On the construction of generalized Voronoi inverse of a rectangular tessellation. Transactions on Computational Science. Lecture Notes in Computer Science, vol. 8110. Springer, pp. 22-38 (2013). 10.1007/978-3-642-41905-8_3 · Zbl 1406.68112 |
| [5] | Biniaz, A., Cabello, S., Carmi, P., De Carufel, J., Maheshwari, A., Mehrabi, S., Smid, M.: On the minimum consistent subset problem. CoRR arXiv:1810.09232 (2018) · Zbl 1498.68356 |
| [6] | Bonnet, É., Cabello, S., Mohar, B., Pérez-Rosés, H.: The inverse Voronoi problem in graphs II: trees (2018). Manuscript. Its content is included in arXiv:1811.12547 |
| [7] | Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms (to appear). Preliminary version presented at SODA (2017). Full version available at arXiv:1702.07815 · Zbl 1403.68151 |
| [8] | Colin de Verdière, É.: Shortest cut graph of a surface with prescribed vertex set. In: Algorithms - ESA 2010, 18th Annual European Symposium, Part II. Lecture Notes in Computer Science, vol. 6347. Springer, pp. 100-111 (2010) 10.1007/978-3-642-15781-3_9 · Zbl 1287.05154 |
| [9] | Cygan, M.; Fomin, FV; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Berlin: Springer, Berlin · Zbl 1334.90001 |
| [10] | Dey, TK; Fan, F.; Wang, Y., Graph induced complex on point data, Comput. Geom., 48, 8, 575-588 (2015) · Zbl 1329.62295 · doi:10.1016/j.comgeo.2015.04.003 |
| [11] | Diestel, R., Graph Theory Graduate Texts in Mathematics (2012), Berlin: Springer, Berlin |
| [12] | Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156-163 (2000). 10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L · Zbl 0963.68148 |
| [13] | Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{o}(n^{5/3})\) time. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SIAM, pp. 495-514 (2018). 10.1137/1.9781611975031.33. Full version available at arXiv:1704.02793 · Zbl 1403.68162 |
| [14] | Gawrychowski, P., Mozes, S., Weimann, O., Wulff-Nilsen, C.: Better tradeoffs for exact distance oracles in planar graphs. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 515-529 (2018). 10.1137/1.9781611975031.34 · Zbl 1403.68163 |
| [15] | Gerbner, D.; Mészáros, V.; Pálvölgyi, D.; Pokrovskiy, A.; Rote, G., Advantage in the discrete Voronoi game, J. Graph Algorithms Appl., 18, 3, 439-457 (2014) · Zbl 1302.05118 · doi:10.7155/jgaa.00331 |
| [16] | Gottlieb, L.; Kontorovich, A.; Nisnevitch, P., Near-optimal sample compression for nearest neighbors, IEEE Trans. Inf. Theory, 64, 6, 4120-4128 (2018) · Zbl 1395.94224 · doi:10.1109/TIT.2018.2822267 |
| [17] | Hart, PE, The condensed nearest neighbor rule (corresp.), IEEE Trans. Inf. Theory, 14, 3, 515-516 (1968) · doi:10.1109/TIT.1968.1054155 |
| [18] | Impagliazzo, R.; Paturi, R., On the complexity of k-SAT, J. Comput. Syst. Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727 |
| [19] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774 |
| [20] | Kannan, S.; Mathieu, C.; Zhou, H., Graph reconstruction and verification, ACM Trans. Algorithms, 14, 4, 40:1-40:30 (2018) · Zbl 1454.68106 · doi:10.1145/3199606 |
| [21] | Kirousis, LM; Papadimitriou, CH, Interval graphs and seatching, Discrete Math., 55, 2, 181-184 (1985) · Zbl 0566.05056 · doi:10.1016/0012-365X(85)90046-9 |
| [22] | Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 2, 329-343 (1982) · Zbl 0478.68043 · doi:10.1137/0211025 |
| [23] | Marx, D., Can you beat treewidth?, Theory Comput., 6, 1, 85-112 (2010) · Zbl 1213.68316 · doi:10.4086/toc.2010.v006a005 |
| [24] | Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. CoRR arXiv:1504.05476 (2015). Preliminary version at ESA 2015 · Zbl 1422.68253 |
| [25] | Mulzer, W.; Rote, G., Minimum-weight triangulation is NP-hard, J. ACM, 55, 2, 11:1-11:29 (2008) · Zbl 1311.05134 · doi:10.1145/1346330.1346336 |
| [26] | Okabe, A.; Sugihara, K., Spatial Analysis along Networks. Statistical and Computational Methods (2012), Hoboken: Wiley, Hoboken · Zbl 1256.62056 |
| [27] | Ritter, GL; Woodruff, HB; Lowry, SR; Isenhour, TL, An algorithm for a selective nearest neighbor decision rule (corresp.), IEEE Trans. Inf. Theory, 21, 6, 665-669 (1975) · Zbl 0323.68023 · doi:10.1109/TIT.1975.1055464 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
