Conflict-free coloring with respect to a subset of intervals Academic Article uri icon

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, ie, 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. Subjects: Combinatorics (math. CO); Discrete Mathematics (cs. DM); Data …

publication date

  • January 1, 2012

published in