On the hardness of computing span of subcubic graphs

• Computing the span of subcubic graphs is NP-hard in the strong sense.
• It is polynomially solvable and approximable under some extra assumptions.

Given a nonempty graph G and a function ξ that assigns positive integers to the edges of G, a ξ-coloring of G is a vertex coloring of G such that for every edge uv of G the colors assigned to the vertices u and v   differ by at least ξ(uv)ξ(uv). In the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used. We show that the problem, restricted to subcubic graphs, is:
• NP-hard in the strong sense but polynomially 32-approximable for functions ξ that take at most two values;
• polynomially 2-approximable and not (1+ε)(1+ε)-approximable for any ε<12, unless P=NPP=NP. We also show that, if we additionally assume that the edges that received the largest of the values of ξ induce a spanning and connected subgraph, then it becomes
• polynomially 43-approximable;
• polynomially solvable provided ξ takes at most two values.