The S-labeling problem: An algorithmic tour

Given a graph G=(V,E) of order n and maximum degree Δ, the NP-complete S-labeling problem consists in finding a labeling of G, i.e. a bijective mapping ϕ:V→{1,2…n}, such that SLϕ(G)=∑uv∈Emin{ϕ(u),ϕ(v)} is minimized. In this paper, we study the S-labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SLϕ(G), together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs-in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SLϕ(G)≤|E|+k is solvable in O∗(22k(2k)!) time, thus fixed-parameterized tractable in k. We finally show that the S-Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars.