Parameterized and approximation algorithms for the load coloring problem

DOI10.1007/S00453-016-0259-ZzbMath1372.68117DBLPjournals/algorithmica/BarberoGJS17arXiv1412.3023OpenAlexW2964301921WikidataQ59613524 ScholiaQ59613524MaRDI QIDQ2408202

Yanyan Li

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Let $c, k$ be two positive integers and let $G=(V,E)$ be a graph. The $(c,k)$-Load Coloring Problem (denoted $(c,k)$-LCP) asks whether there is a $c$-coloring $varphi: V ightarrow [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,k)$-LCP 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 $cge 2$, $(c,k)$-LCP is FPT and that the optimization version of $(c,k)$-LCP (where $k$ is to be maximized) has an approximation algorithm with a constant ratio for any fixed $cge 2$.

Full work available at URL: https://arxiv.org/abs/1412.3023

zbMATH Keywords

kernelsapproximation algorithmsparameterized algorithmsFPTload coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Fixed-parameter complexity of minimum profile problems
• The ring of \(k\)-regular sequences. II.
• Parameterized algorithms for load coloring problem
• The linear arrangement problem parameterized above guaranteed value
• On the minimum load coloring problem
• Kernelization – Preprocessing with a Guarantee
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• (Meta) Kernelization
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Parameterized Algorithms

Related Items (6)

On structural parameterizations of load coloring ⋮ Dealing with several parameterized problems by random methods ⋮ Reinforcement learning based tabu search for the minimum load coloring problem ⋮ A general variable neighborhood search approach for the minimum load coloring problem ⋮ On structural parameterizations of load coloring ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable

Uses Software

• OEIS

This page was built for publication: Parameterized and approximation algorithms for the load coloring problem