×

Exact multi-covering problems with geometric sets. (English) Zbl 1533.68346

Summary: The \(b\)-Exact Multicover problem takes a universe \(U\) of \(n\) elements, a family \(\mathcal{F}\) of \(m\) subsets of \(U\), a function \(\mathsf{dem}: U \rightarrow \{1,\dots,b\}\) and a positive integer \(k\), and decides whether there exists a subfamily(set cover) \( \mathcal{F}^{\prime}\) of size at most \(k\) such that each element \(u \in U\) is covered by exactly \(\mathsf{dem}(u)\) sets of \(\mathcal{F}^{\prime} \). The \(b\)-Exact Coverage problem also takes the same input and decides whether there is a subfamily \(\mathcal{F}^{\prime } \subseteq \mathcal{F}\) such that there are at least \(k\) elements that satisfy the following property: \(u \in U\) is covered by exactly \(\mathsf{dem}(u)\) sets of \(\mathcal{F}^{\prime } \). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by \(k\), \(b\)-Exact Multicover is W[1]-hard even when \(b = 1\). While \(b\)-Exact Coverage is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions, even when \(b = 1\). In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property \(\pi \). Specifically, we consider the universe to be a set of \(n\) points in a real space \(\mathbb{R}^d\), \(d\) being a positive integer. When \(d = 2\) we consider the problem when \(\pi\) requires all sets to be unit squares or lines. When \(d > 2\), we consider the problem where \(\pi\) requires all sets to be hyperplanes in \(\mathbb{R}^d \). These special versions of the problems are also known to be NP-complete. When parameterized by \(k\), the \(b\)-Exact Coverage problem has a polynomial size kernel for all the above geometric versions. The \(b\)-Exact Multicover problem turns out to be W[1]-hard for squares even when \(b = 1\), but FPT for lines and hyperplanes. Further, we also consider the \(b\)-Exact Max. Multicover problem, which takes the same input and decides whether there is a set cover \(\mathcal{F}^{\prime}\) such that every element \(u \in U\) is covered by at least \(\mathsf{dem}(u)\) sets and at least \(k\) elements satisfy the following property: \(u \in U\) is covered by exactly \(\mathsf{dem}(u)\) sets of \(\mathcal{F}^{\prime} \). To the best of our knowledge, this problem has not been studied before, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W[1]-hard in the general setting, when parameterized by \(k\). However, when we restrict the sets to lines and hyperplanes, we obtain FPT algorithms.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q27 Parameterized complexity, tractability and kernelization
68W25 Approximation algorithms
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Ashok, P., Kolay, S., Misra, N., Saurabh, S.: Unique covering problems with geometric sets International Computing and Combinatorics Conference, pp. 548-558. Springer (2015) · Zbl 1391.68103
[2] Ashok, P.; Roy, AB; Govindarajan, S., Local search strikes again: Ptas for variants of geometric covering and packing, J. Comb. Optim., 39, 2, 618-635 (2020) · Zbl 1434.68597 · doi:10.1007/s10878-019-00432-y
[3] Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: European Symposium on Algorithms, pages 145-156. Springer (2012) · Zbl 1365.68436
[4] Chekuri, C.; Clarkson, KL; Har-Peled, S., On the set multicover problem in geometric settings, ACM Trans. Algorithms (TALG), 9, 1, 1-17 (2012) · Zbl 1301.68237 · doi:10.1145/2390176.2390185
[5] Demaine, ED; Feige, U.; Hajiaghayi, M-T; Salavatipour, MR, Combination can be hard: Approximability of the unique coverage problem, SIAM J. Comput., 38, 4, 1464-1483 (2008) · Zbl 1192.68353 · doi:10.1137/060656048
[6] Dom, M.; Lokshtanov, D.; Saurabh, S., Kernelization lower bounds through colors and ids, ACM Trans. Algorithms, 11, 2, 13:1-13:20 (2014) · Zbl 1398.68226 · doi:10.1145/2650261
[7] Downey, RG; Fellows, MR, Parameterized Complexity, 530-530 (1999), Berlin: Springer, Berlin · doi:10.1007/978-1-4612-0515-9
[8] Fellows, MR; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038 · doi:10.1016/j.tcs.2008.09.065
[9] Flum, J.; Grohe, M., Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series) (2006), Secaucus: Springer-Verlag New York, Inc., Secaucus · Zbl 1143.68016
[10] Fowler, RJ; Paterson, MS; Tanimoto, SL, Optimal packing and covering in the plane are np-complete, Inf Process. Lett., 12, 3, 133-137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3
[11] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, pp. 47-63. New York, NY. ACM, USA (1974)
[12] Hall, NG; Hochbaum, DS, A fast approximation algorithm for the multicovering problem, Discret. Appl. Math., 15, 1, 35-40 (1986) · Zbl 0602.90110 · doi:10.1016/0166-218X(86)90016-8
[13] Hall, NG; Hochbaum, DS, The multicovering problem, Eur. J. Oper. Res., 62, 3, 323-339 (1992) · Zbl 0759.90072 · doi:10.1016/0377-2217(92)90122-P
[14] Hochbaum, DS; Maass, W., Fast approximation algorithms for a nonconvex covering problem, J. Algorithms, 8, 3, 305-323 (1987) · Zbl 0636.68082 · doi:10.1016/0196-6774(87)90012-5
[15] Ito, T.; Nakano, Shin-ichi; Okamoto, Y.; Otachi, Y.; Uehara, R.; Uno, T.; Uno, Y., A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, Comput. Geom., 51, 25-39 (2016) · Zbl 1333.65021 · doi:10.1016/j.comgeo.2015.10.004
[16] Karp, R.M.: Reducibility among combinatorial problems. Complex. Comput. Comput., 85-103 (1972) · Zbl 1467.68065
[17] Anil Kumar, V.S., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: International Colloquium on Automata, Languages, and Programming, pp. 624-635. Springer (2000) · Zbl 0973.68080
[18] Langerman, S.; Morin, P., Covering things with things, Discrete Comput. Geom., 33, 4, 717-729 (2005) · Zbl 1079.68102 · doi:10.1007/s00454-004-1108-4
[19] Marx, D.: Efficient approximation schemes for geometric problems?. In: ESA, pp 448-459. Springer (2005) · Zbl 1162.68822
[20] Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, pp. 154-165 (2006) · Zbl 1154.68431
[21] Matoušek, J., Lectures on discrete geometry, vol. 108 (2002), New York: Springer, New York · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7
[22] Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 5, 194-197 (1982) · Zbl 0507.90025 · doi:10.1016/0167-6377(82)90039-6
[23] Misra, N., Moser, H., Raman, V., Saurabh, S., Sikdar, S.: The parameterized complexity of unique coverage and its variants. Algorithmica, 517-544 (2013) · Zbl 1290.68059
[24] Mustafa, N., Ray, S.: Ptas for geometric hitting set problems via local search. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 17-22. ACM (2009) · Zbl 1380.68403
[25] Peleg, D.; Schechtman, G.; Wool, A., Randomized approximation of bounded multicovering problems, Algorithmica, 18, 1, 44-66 (1997) · Zbl 0873.68077 · doi:10.1007/BF02523687
[26] Vapnik, VN; Ya Chervonenkis, A., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 2, 264-280 (1971) · Zbl 0247.60005 · doi:10.1137/1116025
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.