Distance constrained labellings and the channel assignment problem

The channel assignment problems asks for assignment of frequencies (channels) to transmitters to avoid or minimize interference. This is a rather important and intesively studied question. Several models of the situation provide some interesting graph theoretical questions.
In the following two formulations, we assume that the transmitters are vertices of a graph, whose edges represent the constraints. In all cases the channels are asumed to be nonnegative integers ranging from 0 to \lambda. Hence we talk about graph labellings.

1. Constrained Matrix Span Problem
Every edge e of the graph is given a length l(e). The labeling f is required to satisfy |f(x)-f(y)|>=l(xy) for every edge xy.

Known: Deciding the existence of such a labelling is NP-complete for graphs of tree-width bounded by 3 (McDiarmid, Reed 2001) and polynomial for trees (because it is polynomial for bipartite graphs).
Open problem Complexity of CMSP for series-parallel graphs.
Comment The question is for unbounded l(e). If the edge weights are bounded, the problem becomes polynomially solvable for bounded treewidth graphs.

2. L(2,1)-labellings
In this approach the edges are not weighted, but the labelling is constrained by distances in the input graph. The labels of adjacent vertices are required to differ by at least 2, and the labels of vertices at graph distance two are required to be different.

Deciding existence of such labelling is NP-complete in general graphs even for fixed \lambda>=4 (Fiala, Kloks, Kratochvil 1999). Bounded \lambda is polynomial for bounded tree-width graphs (via MSOL). If \lambda is part of input, the problem is solvable in polynomial time for trees (Chang, Kuo 1996, see also Fiala, Kratochvil, Proskurowski 2001).
Open problem Complexity of deciding the existence of an L(2,1)-labelling for graphs of bounded tree-width (even series-parallel graphs are open).
Comment For trees, the question remains polynomailly solvable if some vertices of the input tree are prelabelled.

3. L(p,q)-labellings
Similarly to above, the labels of adjacent vertices are required to differ by at least p, and the labels of vertices at graph distance two are required to differ by at least q.

Known: Deciding existence of such labelling is still polynomial for bounded \lambda and bounded tree-width graphs (via MSOL).
Open problem Complexity of deciding the existence of an L(p,q)-labelling for trees (q>1, \lambda is part of input).
Comment Unbounded \lambda and q>1 do seem to define a difficult problem. Already for trees, the question becomes NP-complete if some vertices of the input tree are prelabelled (Fiala, Kratochvil, Proskurowski 2001).

Back to the Problem Session page and to the workshop page