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

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 a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph $H$ and a fixed $r\geq 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 w...