Abstract
Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph \(H=(U, \mathcal F)\), a conflict-free coloring of H refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of natural maximization version of this problem, namely, Max-CFC: For a given hypergraph H and a fixed \(r\ge 2\), color the vertices of U using r colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NP-hard.
We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to the natural parameter, the solution size. In particular, we study the following question: p-CFC: For a given hypergraph, can we conflict-free color at least k hyperedges with at most r colors, the parameter being k. We show that this problem is FPT by designing an algorithm with running time \(2^{\mathcal {O}(k \log \log k + k \log r)}(n+m)^{\mathcal {O}(1)}\) using a novel connection to the Unique Coverage problem and applying the method of color coding in a non-trivial manner. For the special case for hypergraphs induced by graph neighbourhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in \(\mathcal {O}(2^{n+m})\) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring.
The research leading to these results has received partial funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 306992.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Proofs labelled with \(\dagger \) can be found in the full version.
References
Ajwani, D., Elbassioni, K., Govindarajan, S., Ray, S.: Conflict-free coloring for rectangle ranges using \(O(n^.382)\) colors. Discrete Comput. Geom. 48(1), 39–52 (2012)
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Cheilaris, P., Tóth, G.: Graph unique-maximum and conflict-free colorings. J. Discrete Algorithms 9(3), 241–251 (2011)
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. In: 2002 Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 691–700 (2002)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin (2006)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, New York (2010)
Gargano, L., Rescigno, A.A.: Complexity of conflict-free colourings of graphs. Theoret. Comput. Sci. 566, 39–49 (2015)
Har-Peled, S., Smorodinsky, S.: Conflict-free coloring of points and simple regions in the plane. Discrete Comput. Geom. 34(1), 47–70 (2005)
Jukna, S.: Extremal Combinatorics: With Applications in Computer Science. Springer Science & Business Media, New York (2011)
Misra, N., Moser, H., Raman, V., Saurabh, S., Sikdar, S.: The parameterized complexity of unique coverage and its variants. Algorithmica 65(3), 517–544 (2013)
Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, 23–25 October 1995, Milwaukee, Wisconsin, pp. 182–191 (1995)
Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Comb. Probab. Comput. 18(05), 819–834 (2009)
Smorodinsky, S.: On the chromatic number of geometric hypergraphs. SIAM J. Discrete Math. 21(3), 676–687 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ashok, P., Dudeja, A., Kolay, S. (2015). Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs. In: Elbassioni, K., Makino, K. (eds) Algorithms and Computation. ISAAC 2015. Lecture Notes in Computer Science(), vol 9472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48971-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-48971-0_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48970-3
Online ISBN: 978-3-662-48971-0
eBook Packages: Computer ScienceComputer Science (R0)