Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs

Abstract

Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph H = (U, 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 a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph H and a fixed r ≥ 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 a natural parameter—the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least k hyperedges with at most r colors, the parameter being the solution size k. We show that this problem is fixed parameter tractable by designing an algorithm with running time 2O(k log log k+k log r⁾(n + m)O⁽¹⁾ using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in O(2ⁿ+m) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring.