Journal of Graph Algorithms and Applications

Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021

DOI: 10.7155/jgaa.00592

Computing L(p,1)-Labeling with Combined Parameters

Tesshu Hanaka, Kazuma Kawai, and Hirotaka Ono

Vol. 26, no. 2, pp. 241-255, 2022. Regular paper.

Abstract Given a graph, an $L(p,1)$-labeling of the graph is an assignment $f$ from the vertex set to the set of nonnegative integers such that for any pair of vertices $u$ and $v$, $|f (u) - f (v)| \ge p$ if $u$ and $v$ are adjacent, and $f(u) \neq f(v)$ if $u$ and $v$ are at distance $2$. The \textsc{$L(p,1)$-labeling} problem is to minimize the span of $f$ (i.e.,$\max_{u\in V}(f(u)) - \min_{u\in V}(f(u))+1$). It is known to be NP-hard even for graphs of maximum degree $3$ or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for ${L(p,1)-{\rm L{\small ABELING}}}$ by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.