On k-Strong Conflict–Free Multicoloring

Let \(\mathcal{H}=(\mathcal{V},\mathcal{E})\) be a hypergraph. A k-strong conflict-free coloring of \(\mathcal{H}\) is an assignment of colors to the members of the vertex set \(\mathcal{V}\) such that every hyperedge \(E\in \mathcal{E}\), \(|E|\ge 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 \(\mathcal{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 \(\mathcal{H}\) that utilizes a total number of colors \(O( \min \{(k+\log ({r}/{k}) )\log {\varGamma }+ k( k+\log ^2 ({r}/{k})), \ (k^2 + r ) \log n \})\), where n is the number of nodes, \(r\) is the maximum hyperedge size, and \({\varGamma }\) is the maximum hyperedge degree; the expected number of colors per node is \(O(\min \{k+\log {\varGamma }, \ (k + \log ({r}/{k})) \log n \})\). 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.