Parameterized and Approximation Algorithms for the Load Coloring Problem
Florian Barbero, Gregory Gutin, Mark E Jones, Bin Sheng · Algorithmica · 2016
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 $$\varphi : V \rightarrow [c]$$ such that for every $$i \in [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+\sqrt{2})\sqrt{k}+4$$ edges. These results imply that for any fixed $$c\ge 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.