2026-07-20T14:50:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5570 2024-03-06T10:36:34Z ddc:004 open_access

Parameterized and Approximation Algorithms for the Load Coloring Problem Barbero, Florian Gutin, Gregory Jones, Mark Sheng, Bin Load Coloring fixed-parameter tractability kernelization 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 => [c] such that for every i in [c], there are at least k edges with both endvertices colored i. Gutin and Jones (IPL 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 8k 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Barbero and Gregory Gutin and Mark Jones and Bin Sheng 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.43 urn:nbn:de:0030-drops-55703 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.43 eng https://creativecommons.org/licenses/by/3.0/legalcode