Given an undirected graph $G$, an \Lhk\ of $G$ assigns colors to vertices from the integer set $\{0, \ldots,\lambda_{h,k}\}$, such that any two vertices $v_i$ and $v_j$ receive colors $c(v_i)$ and $c(v_j)$ satisfying the following conditions: \emph{i)} if $v_i$ and $v_j$ are adjacent then $|c(v_i)-c(v_j)|\geq h$; \emph{ii)} if $v_i$ and $v_j$ are at distance two then $|c(v_i)-c(v_j)|\geq k$. The aim of the \Lhk\ problem is to minimize $\lambda_{h,k}$. In this paper we study the approximability of the \Lhk\ problem on bipartite graphs and extend the results to $s$-partite and general graphs. Indeed, the decision version of this problem is known to be NP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the \Lhk\ problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an $L(h,k)$-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by $\frac{4}{3} D^2$, where, $D$ is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension $d$, i.e. the maximum edge cardinality, with performance ratio $d$. Furthermore, we consider a different approximation technique based on the reduction of the \Lhk\ problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by $\mbox{min}(h,2k)\sqrt{n}+o(k\sqrt{n})$, assuming $h \geq k$. Hence, the first technique is competitive when $D=O(n^{1/4})$. These algorithms match with a result in \cite{AGH00} stating that $L(1,1)$-labelling $n$-vertex bipartite graphs is hard to approximate within $n^{1/2 - \epsilon}$, for any $\epsilon > 0$, unless NP=ZPP. We then extend the latter approximation strategy to $s$-partite graphs, obtaining a $(\mbox{min}(h,sk)\sqrt{n}+o(sk\sqrt{n}))$-approximation ratio, and to general graphs deriving an $(h\sqrt{n}+o(h\sqrt{n}))$-approximation algorithm, assuming $h\geq k$. Finally, we prove that the \Lhk\ problem is not easier than coloring the square of a graph
On the Approximability of the $L(h,k)$-Labelling Problem on Bipartite Graphs (Extended Abstract)
VOCCA, PAOLA
2005-01-01
Abstract
Given an undirected graph $G$, an \Lhk\ of $G$ assigns colors to vertices from the integer set $\{0, \ldots,\lambda_{h,k}\}$, such that any two vertices $v_i$ and $v_j$ receive colors $c(v_i)$ and $c(v_j)$ satisfying the following conditions: \emph{i)} if $v_i$ and $v_j$ are adjacent then $|c(v_i)-c(v_j)|\geq h$; \emph{ii)} if $v_i$ and $v_j$ are at distance two then $|c(v_i)-c(v_j)|\geq k$. The aim of the \Lhk\ problem is to minimize $\lambda_{h,k}$. In this paper we study the approximability of the \Lhk\ problem on bipartite graphs and extend the results to $s$-partite and general graphs. Indeed, the decision version of this problem is known to be NP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the \Lhk\ problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an $L(h,k)$-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by $\frac{4}{3} D^2$, where, $D$ is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension $d$, i.e. the maximum edge cardinality, with performance ratio $d$. Furthermore, we consider a different approximation technique based on the reduction of the \Lhk\ problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by $\mbox{min}(h,2k)\sqrt{n}+o(k\sqrt{n})$, assuming $h \geq k$. Hence, the first technique is competitive when $D=O(n^{1/4})$. These algorithms match with a result in \cite{AGH00} stating that $L(1,1)$-labelling $n$-vertex bipartite graphs is hard to approximate within $n^{1/2 - \epsilon}$, for any $\epsilon > 0$, unless NP=ZPP. We then extend the latter approximation strategy to $s$-partite graphs, obtaining a $(\mbox{min}(h,sk)\sqrt{n}+o(sk\sqrt{n}))$-approximation ratio, and to general graphs deriving an $(h\sqrt{n}+o(h\sqrt{n}))$-approximation algorithm, assuming $h\geq k$. Finally, we prove that the \Lhk\ problem is not easier than coloring the square of a graphI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
