Paper Info
Title
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 2(O(k log log k+k log r))(n + m)(O(1)) 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(n+m)) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, UNIQUE MAXIMUM COLORING.
Year
DOI
Venue
2018
10.1137/16M1107462
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
conflict-free coloring,unique-maximum coloring,FPT algorithms,maximization algorithms
Discrete mathematics,Combinatorics,Constraint graph,Hypergraph,Mathematics
Journal
Volume
Issue
ISSN
32
2
0895-4801
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Pradeesha Ashok1116.11
Aditi Dudeja211.05
Sudeshna Kolay32512.77
Saket Saurabh42023179.50