Two-Class (r,k)-Coloring: Coloring with Service Guarantees
Authors:
Pál András Papp,
Roland Schmid,
Valentin Stoppiello, and
Roger Wattenhofer
arXiv CoRR 2021
Abstract
This paper introduces the Two-Class $(r,k)$-Coloring problem: Given a fixed number of k colors, such that only $r$ of these $k$ colors allow conflicts, what is the minimal number of conflicts incurred by an optimal coloring of the graph?
We establish that the family of Two-Class $(r,k)$-Coloring problems is NP-complete for any $k≥2$ when $(r,k)≠(0,2)$. Furthermore, we show that Two-Class $(r,k)$-Coloring for $k≥2$ colors with one ($r=1$) relaxed color cannot be approximated to any constant factor (∉ APX). Finally, we show that Two-Class $(r,k)$-Coloring with $k≥r≥2$ colors is APX-complete.
People
Roland Schmid
PhD student
BibTex
@article{twoclass-r-k-coloring-abs/2108.03882,
author = {Pal Andras Papp and Roland Schmid and Valentin Stoppiello and Roger Wattenhofer},
title = {Two-Class (r,k)-Coloring: Coloring with Service Guarantees},
journal = {CoRR},
volume = {abs/2108.03882},
year = {2021},
url = {https://arxiv.org/abs/2108.03882},
archivePrefix = {arXiv},
eprint = {2108.03882}
}