×

Approximation algorithms for geometric conflict free covering problems. (English) Zbl 1444.68272

Summary: In the Geometric Conflict Free Covering, we are given a set of points \(P\), a set of closed geometric objects \(\mathcal{O}\) and a conflict graph \(\mathcal{CG}_{\mathcal{O}}\) with \(\mathcal{O}\) as vertex set. An edge \(( O_i, O_j)\) in \(\mathcal{CG}_{\mathcal{O}}\) denotes conflict between \(O_i\) and \(O_j\) and at most one among these can be part of any feasible solution. A set of objects is conflict free if they form an independent set in \(\mathcal{CG}_{\mathcal{O}} \). The objective is to find a conflict free set of objects that maximizes the number of points covered. We consider the Unit Interval Covering where \(P\) is a set of points on the real line, and \(\mathcal{O}\) is a set of closed unit-length intervals. The objective is to find a smallest subset of given intervals that covers \(P\). We prove that for an arbitrary conflict graph the problem is Poly-APX -hard. We present an approximation algorithm for a special class of conflict graphs with a bounded graph parameter Clique Partition. A Clique Partition of the graph \(G\) is a set of cliques such that every vertex in the graph is part of exactly one clique. For any Clique Partition \(\mathcal{C} \), we define the Clique Partition Graph, \( G^{\mathcal{C}}\) with vertex set \(\mathcal{C}\) and there is an edge \(( C_i, C_j)\) in \(G^{\mathcal{C}} \), if and only if there exist two vertices in \(G, v_a \in C_i\) and \(v_b \in C_j\) such that there is an edge \(( v_a, v_b)\) in \(G\). For a graph \(G\), Clique Partition Chromatic Number is defined as the minimum chromatic number among all possible Clique Partitions of the Clique Partition Graph. In this paper, we consider those graph classes for which Clique Partition Chromatic Number can be computed in polynomial time. We present a \(4 \gamma\) approximation algorithm for conflict graphs having Clique Partition Chromatic Number \(\gamma \). We show that unit interval graphs and unit disk graphs have constant Clique Partition Chromatic Number while for chordal graphs, it is bounded by \(\log n\). Note that, Clique Partition Chromatic Number is less than or equal to the chromatic number. Thus our algorithm achieves a constant approximation factor for graphs with constant chromatic number (e.g. planar graphs ). This is the first result regarding the approximability in Geometric Conflict Free Covering.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C62 Graph representations (geometric and intersection representations, etc.)
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.M. Arkin, A. Banik, P. Carmi, G. Citovsky, S. Jia, M.J. Katz, T. Mayer, J.S.B. Mitchell, Network optimization on partitioned pairs of points, in: Okamoto and Tokuyama [12], pp. 6:1-6:12.
[2] Arkin, E. M.; Banik, A.; Carmi, P.; Citovsky, G.; Katz, M. J.; Mitchell, J. S.B.; Simakov, M., Choice is hard, (Elbassioni, Khaled M.; Makino, Kazuhisa, Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings. Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9472 (2015), Springer), 318-328 · Zbl 1472.68061
[3] Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, Joseph S.B. Mitchell, Network optimization on partitioned pairs of points, in: Okamoto and Tokuyama [12], pp. 6:1-6:12.
[4] Ausiello, Giorgio; Protasi, M.; Marchetti-Spaccamela, A.; Gambosi, G.; Crescenzi, P.; Kann, V., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 0937.68002
[5] Banik, A.; Panolan, F.; Raman, V.; Sahlot, V., Fréchet distance between a line and avatar point set, (36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India (2016)), 32:1-32:14 · Zbl 1390.68705
[6] Banik, A.; Panolan, F.; Raman, V.; Sahlot, V.; Saurabh, S., Parameterized complexity of geometric covering problems having conflicts, (Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings (2017)), 61-72 · Zbl 1436.68144
[7] Consuegra, M. E.; Narasimhan, G., Geometric avatar problems, (IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, LIPIcs, vol. 24 (2013)), 389-400 · Zbl 1359.68281
[8] Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2012), Springer
[9] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory, Ser. B, 16, 1, 47-56 (1974) · Zbl 0266.05101
[10] Håstad, J., Some optimal inapproximability results, J. ACM, 48, 4, 798-859 (July 2001) · Zbl 1127.68405
[11] Mustafa, Nabil H.; Ray, Saurabh, Improved results on geometric hitting set problems, Discrete Comput. Geom., 44, 4, 883-895 (2010) · Zbl 1207.68420
[12] Okamoto, Yoshio; Tokuyama, Takeshi, (28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand. 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, LIPIcs, vol. 92 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik) · Zbl 1376.68013
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.