Parameterized and Approximation Algorithms for the Load Coloring Problem. / Barbero, Florian; Gutin, Gregory; Jones, Mark; Sheng, Bin.

In: Algorithmica, Vol. 79, No. 1, 09.2017, p. 211–229.

Research output: Contribution to journalArticlepeer-review




Let c, k be two positive integers. Given a graph G = (V, E), the c-Load Coloring problem asks whether there is a c-coloring ϕ : V → [c] such that for every i ∈ [c], there are at least k edges with both endvertices colored i. Gutin and Jones (Inf Process Lett 114:446–449, 2014) studied this problem with c = 2. They showed 2-Load Coloring to be fixed-parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear-vertex and a linear-edge kernel. In the particular case of c = 2, we obtain a kernel with less than 4k vertices and less than 6k +(3+√2)√k +4 edges. These results imply that for any fixed c ≥ 2, c-Load Coloring is FPT and the optimization version of c-Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.
Original languageEnglish
Pages (from-to)211–229
Number of pages19
Issue number1
Early online date30 Nov 2016
Publication statusPublished - Sep 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 27255865