Conflict-free coloring with respect to a subset of intervals

arXiv1204.6422MaRDI QIDQ6232647FDOQ6232647

Authors: Panagiotis Cheilaris, Shakhar Smorodinsky 

Publication date: 28 April 2012

Abstract: Given a hypergraph H = (V, E), a coloring of its vertices is said to be conflict-free if for every hyperedge S in E there is at least one vertex in S whose color is distinct from the colors of all other vertices in S. The discrete interval hypergraph Hn is the hypergraph with vertex set {1,...,n} and hyperedge set the family of all subsets of consecutive integers in {1,...,n}. We provide a polynomial time algorithm for conflict-free coloring any subhypergraph of Hn, we show that the algorithm has approximation ratio 2, and we prove that our analysis is tight, i.e., there is a subhypergraph for which the algorithm computes a solution which uses twice the number of colors of the optimal solution. We also show that the problem of deciding whether a given subhypergraph of Hn can be colored with at most k colors has a quasipolynomial time algorithm.

This page was built for publication: Conflict-free coloring with respect to a subset of intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232647)