Result: On the approximability of the L(h, k)-labelling problem on bipartite graphs (extended abstract)

Given an undirected graph G, an L(h, k)-labelling of G assigns colors to vertices from the integer set {0,...,λh,k}, such that any two vertices vi and vj receive colors c(vi) and c(vj) satisfying the following conditions: i) if vi and vj are adjacent then |c(vi) - c(vj)| > h; ii) if vi and vj are at distance two then |c(vi) - c(vj)| ≥ k. The aim of the L(h, k)-labelling problem is to minimize λh,k. In this paper we study the approximability of the L(h, k)-labelling 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 L(h, k)-labelling 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 4 3D2, 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 L(h, k)-labelling problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by min(h, 2k)n+o(kn), assuming h ≥ k. Hence, the first technique is competitive when D = O(n1/4). These algorithms match with a result in [2] stating that L(1, 1)-labelling n-vertex bipartite graphs is hard to approximate within n1/2-∈, for any ∈ > 0, unless NP=ZPP. We then extend the latter approximation strategy to s-partite graphs, obtaining a (min(h, sk)√n + o(sk√n))-approximation ratio, and to general graphs deriving an (h√n + o(h√n))-approximation algorithm, assuming h ≥ k. Finally, we prove that the L(h, k)-labelling problem is not easier than coloring the square of a graph.