Abstract
The input for the Geometric Coverage problem consists of a pair \(\varSigma =(P,\mathcal {R})\), where P is a set of points in \(\mathbb {R}^d\) and \(\mathcal {R}\) is a set of subsets of P defined by the intersection of P with some geometric objects in \(\mathbb {R}^d\). These coverage problems form special instances of the Set Cover problem which is notoriously hard in several paradigms including approximation and parameterized complexity. Motivated by what are called choice problems in geometry, we consider a variation of the Geometric Coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution.
As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. We consider the parameterized complexity of the problem based on the structure of the conflict relation. Our main result is that as long as the conflict graph has bounded arboricity (that includes all the families of intersection graphs of low density objects in low dimensional Euclidean space), there is a parameterized reduction to the problem without conflicts on the covering objects. This is achieved through a randomization-derandomization trick. As a consequence, we have the following results when the conflict graph has bounded arboricity.
-
If the Geometric Coverage problem is fixed parameter tractable (FPT), then so is the conflict free version.
-
If the Geometric Coverage problem admits a factor \(\alpha \)-approximation, then the conflict free version admits a factor \(\alpha \)-approximation algorithm running in FPT time.
As a corollary to our main result we get a plethora of approximation algorithms running in FPT time. Our other results include an FPT algorithm and a W[1]-hardness proof for the conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid, and the W[1]-hardness result is for all the families of conflict graphs for which the Independent Set problem is W[1]-hard.
Supported by Parameterized Approximation, ERC Starting Grant 306992, and Rigorous Theory of Preprocessing, ERC Advanced Investigator Grant 267959.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Choice is hard. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 318–328. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48971-0_28
Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Conflict-free covering. In: CCCG (2015)
Banik, A., Panolan, F., Raman, V., Sahlot, V.: Fréchet distance between a line and avatar point set. In: FSTTCS, pp. 32: 1–32: 14 (2016)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer (2015)
Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol. 173. Springer (2012)
Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29 (2016)
Gabow, H.N., Westermann, H.H.: Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7(5&6), 465–497 (1992)
Har-Peled, S., Quanrud, K.: Approximation algorithms for low-density graphs. CoRR abs/1501.00721 (2015)
Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 717–728. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_60
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238–274 (1998)
Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations. pp. 85–103 (1972)
Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 922–934. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_75
Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., Zehavi, M.: Covering small independent sets and separators with applications to parameterized algorithms, May 2017. ArXiv e-prints
Marx, Dániel: Parameterized complexity of independence and domination on geometric graphs. In: Bodlaender, Hans L., Langston, Michael A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154–165. Springer, Heidelberg (2006). doi:10.1007/11847250_14
Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471–4479 (2009)
Naor, M., Schulman, J.L., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS, pp. 182–191 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Banik, A., Panolan, F., Raman, V., Sahlot, V., Saurabh, S. (2017). Parameterized Complexity of Geometric Covering Problems Having Conflicts. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)