On k-strong conflict-free multicoloring

Let H= (V, E) be a hypergraph. A k-strong conflict-free coloring of H is an assignment of colors to the members of the vertex set V such that every hyperedge E ∈ ε, |E| ≥ k, contains k nodes whose colors are pairwise distinct and different from the colors assigned to all the other nodes in E, whereas if | E| < k all nodes in E get distinct colors. The parameter to optimize is the total number of colors. The need for such colorings originally arose as a problem of frequency assignment for cellular networks, but since then it has found applications in a variety of different areas. In this paper we consider a generalization of the above problem, where one is allowed to assign more than one color to each node. When k= 1, our generalization reduces to the conflict-free multicoloring problem introduced by Even et al. [2003], and recently studied by Bärtschi and Grandoni [2015], and Ghaffari et al. [2017]. We motivate our generalized formulation and we point out that it includes a vast class of well known combinatorial and algorithmic problems, when the hypergraph H and the parameter k are properly instantiated. Our main result is an algorithm to construct a k-strong conflict-free multicolorings of an input hypergraph H that utilizes a total number of colors O(min(k+log(r/k))logΓ+k(k+log2(r/k)),(k2+r)logn), where n is the number of nodes, r is the maximum hyperedge size, and Γ is the maximum hyperedge degree; the expected number of colors per node is O(mink+logΓ,(k+log(r/k))logn). Although derived for arbitrary k, our result improves on the corresponding result by Bärtschi and Grandoni [2015], when instantiated for k= 1. We also provide lower bounds on the number of colors needed in any k-strong conflict-free multicoloring, thus showing that our algorithm is not too far from being optimal.