Distance constrained labeling on graphs with bounded neighborhood diversity.
Jiřı́ Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, Jan Kratochvı́l · arXiv (Cornell University) · 2015
We study the complexity of a group of distance-constrained graph labeling problems when parameterized by the neighborhood diversity ($nd$), which is a natural graph parameter between vertex cover and clique width. Neighborhood diversity has been used to generalize and speed up \sf{FPT} algorithms previously parameterized by vertex cover, as is also demonstrated by our paper. We show that the {\sc Uniform Channel Assignment} problem is fixed parameter tractable when parameterized by $nd$ and the largest weight and that every {\sc $L(p_1, p_2,\dots, p_k)$-labeling} problem is \sf{FPT} when parameterized by $nd$, maximum $p_i$ and $k$. These results furthermore yield an \sf{FPT} algorithms for {\sc $L(p_1, p_2,\dots, p_k)$-labeling} and {\sc Channel Assignment} problems when parameterized by vertex cover size, answering an open question of Fiala et al.: {\emph Parameterized complexity of coloring problems: Treewidth versus vertex cover}, generalizing their results beyond $L(2,1)$-labeling, and tightening the complexity gap to clique width, where the problems are already hard for constant clique width.