Algorithmic Aspects of the S-Labeling Problem

Abstract

Given a graph $G = (V,E)$ of order n and maximum degree $\varDelta$, the NP-complete S-labeling problem consists in finding a labeling of G, i.e. a bijective mapping $\phi : V \rightarrow \{1, 2 \ldots n\}$, such that $\mathrm{SL}_{\phi }(G)=\sum _{\{u,v\} \in E} \min \{\phi (u), \phi (v)\}$ is minimized. A preliminary study of the S-labeling problem has been undertaken in [9]; here, we prolongate this study, and focus more specifically on algorithmic results concerning the problem. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then show that the S-Labeling problem is polynomial-time solvable for (sets of) caterpillars. We also provide upper and lower bounds on $\mathrm{SL}_{\phi }(G)$, that in turn allow us to determine polynomial-time approximation algorithms for different classes of graphs such as regular graphs, connected graphs and forests, but also for general graphs. Concerning exact algorithms, we show that the problem is solvable in $O^*(1.44225^{n\varDelta })$ time, and that deciding whether there exist a labeling $\phi$ of G such that $\mathrm{SL}_{\phi }(G) \le |E| + k$ is solvable in $O^*(2^{2\sqrt{k}}\ (2 \sqrt{k})!)$.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A labeling of a graph G is an assignment of distinct integers to its vertices, in such a way that a certain objective function is optimized. In the literature, a graph labeling of G is also called a linear arrangement, a linear layout or a numbering of the vertices of G. A large amount of relevant combinatorial problems in different areas can be rephrased as graph labeling problems, which have been widely investigated during the last decades. These include numerical analysis [17], VLSI circuit design [4], network reliability [15], computational biology [16], scheduling [1], parallel processing [18], etc. However, for most objective functions, the derived graph labeling problem turns out to be NP-complete. Popular graph labeling problems arising in the above-mentioned applications include Bandwidth [10], Minimum Linear Arrangement [13], Cutwidth [2] and Vertex Separation [19]. There exist several surveys that deal with different aspects of graph labeling problems [3, 5, 8].

In this paper, we are interested in the S-Labeling problem [9, 22], which, given a graph $G = (V,E)$, asks for a graph labeling $\phi : V \rightarrow \{1,2\ldots |V|\}$ such that the total sum $\mathrm{SL}_{\phi }(G)=\sum _{\{u,v\} \in E} \min \{\phi (u), \phi (v)\}$ is minimized, and we write $\mathrm{SL}(G)$ for the minimum $\mathrm{SL}_{\phi }(G)$ over all possible labelings of G. Note that, in this problem (and thus, all along this paper), we do not require G to be connected. However, we can always assume G has no isolated vertices. Indeed, if this was the case, let $V_I$ be the set of isolated vertices in G. Since in any labeling $\phi$ of G, no vertex from $V_I$ contributes to $\mathrm{SL}_{\phi }(G)$, we can always label the vertices with the highest possible labels from $V_I$, or equivalently, change G into $G'=(V{\setminus } V_I,E)$.

The S-Labeling problem has been proved to be NP-complete for planar at most cubic graphs [22], but its complexity is unknown for trees, forests, and more generally, for bipartite graphs. The problem has also been studied in [9], where SL(G) is determined for classical classes of graphs (paths, cycles, complete (bipartite) graphs). Upper and lower bounds are also given for general graphs, and approximation ratios are given for trees, regular graphs, and general graphs. The S-Labeling problem has also been proved to be polynomial-time solvable for split graphs [9].

This paper can be seen as a (late) follow-up of [9], mainly focused on algorithmic aspects of the S-Labeling problem, and is organized as follows. Section 2 introduces terminology used throughout this paper. Section 3 presents essential properties of optimal labelings. In Sect. 4, we prove that the S-Labeling problem is polynomial-time solvable for (sets of) caterpillars. In Sect. 5, we investigate polynomial-time approximation and exponential-time algorithms. Due to space constraints, most proofs are omitted and deferred to the full version of this paper.

2 Notations

A graph is an ordered pair $G = (V, E)$ comprising a set V of vertices together with a set E of edges, which are 2-element subsets of V. The order n (resp. size m) of G is its number of vertices (resp. edges). The degree of a vertex $u \in V$, denoted $d_G(u)$ (or d(u) if clear from the context), is the number of edges that are incident to u. We write $\varDelta (G)$ (or $\varDelta$, if clear from the context) for the maximum degree of G. A vertex cover of $G = (V, E)$ is a subset of vertices $V' \subseteq V$ such that each edge $e \in E$ is incident to at least one vertex of $V'$. The size of a minimum cardinality vertex cover of G is denoted $\tau (G)$ (or $\tau$, if clear from the context). An independent set of $G = (V, E)$ is a subset of vertices $V' \subseteq V$, no two of which are adjacent. A tree is a graph in which any two vertices are connected by exactly one simple path, and a caterpillar is a tree in which all the vertices are within distance 1 of a central path (equivalently, caterpillars are the trees in which there exists a path that contains every node of degree two or more). A forest is a collection of trees.

Fig. 1.

A graph G together with a labeling $\phi$. Vertices in $V^+_\phi$ are in grey. We have $c_\phi (\phi ^{-1}(1)) = c_\phi (\phi ^{-1}(2)) = c_\phi (\phi ^{-1}(3)) = 3$, $c_\phi (\phi ^{-1}(4)) = 2$, $c_\phi (\phi ^{-1}(5)) = 1$, and $c_\phi (\phi ^{-1}(6)) = c_\phi (\phi ^{-1}(7)) = c_\phi (\phi ^{-1}(8)) = 0$, yielding $\mathrm{SL}_\phi (G) = (3 \times 1) + (3 \times 2) + (3 \times ~3) + (2 \times 4) + (1 \times 5) + (0 \times 6) + (0 \times 7) + (0 \times 8) = 31$.

Let $G = (V, E)$ be a graph of order n. A labeling of G is a bijective mapping $\phi : V \rightarrow \{1, 2, \ldots , n\}$, and we denote by $\Phi (G)$ the set of all labelings of G. The S-labeling number of G with respect to some labeling $\phi \in \Phi (G)$, denoted $\mathrm{SL}_{\phi }(G)$, is defined to be $\mathrm{SL}_{\phi }(G)=\sum _{\{u,v\} \in E} \min \{\phi (u), \phi (v)\}$. To abbreviate notations, we write $\mathrm{SL}(G)=\min \{{\mathrm{SL}_{\phi }(G) : \phi \in \Phi (G)}\}$ and we let ${\Phi _\mathbf{{opt}}(G) \subseteq \Phi (G)}$ stand for the set of all optimal labelings (i.e., ${\Phi _\mathbf{{opt}}(G) = \{\phi \in \Phi (G) : \mathrm{SL}_{\phi }(G) = \mathrm{SL}(G)\}}$). Let $\phi \in \Phi (G)$ be a labeling of G. For any vertex $u\in V$, the contribution $c_{\phi }(u)$ of u to the S-labeling number $\mathrm{SL}_{\phi }$ is the integer defined as $c_{\phi }(u)=|\{v\in V : \{u,v\} \in E \;\text {and}\; \phi (u) < \phi (v)\}|$. We will be mostly interested, in the rest of the paper, in those vertices with non-zero contribution. To this aim, we define $V^+_\phi = \{u \in V : c_{\phi }(u)> 0\}$. An example illustrating these notions is given in Fig. 1.

3 Properties of Optimal Labelings

Towards investigating computational issues, it is critical to support a deeper understanding of the structure of optimal labelings. This is the purpose of the current section.

Property 1

For any graph $G = (V,E)$ and any labeling $\phi \in \Phi (G)$: (a) $V^+_\phi$ is a vertex cover of G, (b) $\sum _{u \in V^+_\phi } c_\phi (u) = |E|$, and (c) $\mathrm{SL}_{\phi }(G) = \sum _{u \in V^+_\phi } c_\phi (u)\,\phi (u)$.

Lemma 1

[9] Let $G = (V, E)$ be a graph, and ${\phi \in \Phi _\mathbf{{opt}}(G)}$. For any two vertices $u, v \in V$, if $\phi (u) < \phi (v)$ then $c_\phi (u) \ge c_\phi (v)$.

Lemma 2

Let $G = (V, E)$ be a graph, and ${\phi \in \Phi _\mathbf{{opt}}(G)}$. For any distinct vertices $u, v \in V$, if $c_{\phi }(u) = c_{\phi }(v)$ then $\{u,v\}\not \in E$.

We now turn to proving that, in any optimal labeling $\phi$ of G, the vertex ranked first by $\phi$ is a maximum degree vertex.

Lemma 3

Let $G = (V, E)$ be a graph, let $\phi \in \Phi _\mathbf{{opt}}(G)$, and let $u \in V$ be the vertex satisfying $\phi (u) = 1$. Then $c_\phi (u) = \varDelta (G)$.

Proof

Let $G = (V, E)$ be a graph, and ${\phi \in \Phi _\mathbf{{opt}}(G)}$ be an optimal labeling of G. Let $k = \min \{\phi (u) : u \in V \wedge c_\phi (u) = \varDelta (G)\}$. We show that $k = 1$ thereby proving the lemma. Write $\varDelta$ for $\varDelta (G)$. For convenience, for $1 \le i \le n$, let $u_i$ and $c_i$ stand for $\phi ^{-1}(i)$ and $c_\phi (\phi ^{-1}(i)) = c_\phi (u_i)$, respectively.

Suppose, aiming at a contradiction, that $k > 1$. Consider the labeling $\phi '$ of G defined as follows: $\phi '(u_k) = 1$, $\phi '(u_i) = \phi (u_i) + 1$ for any $1 \le i \le k-1$ and $\phi '(u_i) = \phi (u_i)$ for any $k+1 \le i \le n$. For convenience, for $1 \le i \le n$, $i \ne k$, let $c'_i$ stand for $c_{\phi '}(u_i)$ (see above figure). We thus have $\mathrm{SL}_{\phi }(G)=\sum _{i=1}^{n} i c_i$ and $\mathrm{SL}_{\phi '}(G) = \varDelta + \sum _{i=1}^{k-1} (i+1) c'_i + \sum _{i=k+1}^{n} i c_i$. Now, if we let D stand for $\mathrm{SL}_{\phi }(G) - \mathrm{SL}_{\phi '}(G)$, we obtain $D=\sum _{i=1}^{n} i c_i - \varDelta - \sum _{i=1}^{k-1} (i+1) c'_i - \sum _{i=k+1}^{n} i c_i= \sum _{i=1}^{k} i c_i - \varDelta - \sum _{i=1}^{k-1} (i+1) c'_i$ (Eq. 1). We need the following inequality.

Claim 1

$\sum _{i=1}^{k-1} (i+1)c'_i\le \sum _{i=1}^{\varDelta -c_k} (i+1)(c_i-1) + \sum _{i=\varDelta -c_k+1}^{k-1} (i+1)c_i$.

Proof

By construction, $c_i -1 \le c'_i \le c_i$ for $1 \le i \le k-1$. Moreover, since exactly $\varDelta - c_k$ vertices of $\{u_1, u_2, \ldots , u_{k-1}\}$ are connected with vertex $u_k$, then there exist $S \subseteq \{1, 2, \ldots , k-1\}$ of size $\varDelta - c_k$ such that $c'_i = c_i - 1$ if and only if $i \in S$. If we let $\overline{S}$ stand for $\{1, 2, \ldots , k-1\} {\setminus } S$, then $\sum _{i=1}^{k-1} (i+1)c'_i=\sum _{i \in S} (i+1)(c_i-1) + \sum _{i \in \overline{S}} (i+1)c_i= \sum _{i=1}^{k-1} (i+1)c_i - \sum _{i \in S} (i+1)$. This latter sum is certainly maximized for $S = \{1, 2, \ldots \varDelta -c_k\}$, and hence $\sum _{i=1}^{k-1} (i+1)c'_i \le \sum _{i=1}^{\varDelta -c_k} (i+1)(c_i-1) + \sum _{i=\varDelta -c_k+1}^{k-1} (i+1)c_i$.    $\square$

Combining Claim 1 with (Eq. 1) yields $D\ge \sum _{i=1}^{k} i c_i-\varDelta - \sum _{i=1}^{\varDelta -c_k} (i+1)(c_i-1)- \sum _{i=\varDelta -c_k+1}^{k-1} (i+1)c_i=\sum _{i=1}^{k} i c_i- \varDelta - \sum _{i=1}^{k-1} i c_i - \sum _{i=1}^{k-1} c_i + \sum _{i=1}^{\varDelta -c_k} (i+1) = k c_k - \varDelta - \sum _{i=1}^{k-1} c_i + \sum _{i=1}^{\varDelta -c_k} (i+1) = kc_k - \varDelta - \sum _{i=1}^{k-1} c_i + \frac{(\varDelta -c_k+3)(\varDelta -c_k)}{2}$.

But $c_i \le \varDelta -1$ for $1 \le i \le k-1$ (this follows from $k > 1$ and Lemma 1), and hence $\sum _{i=1}^{k-1} c_i \le (k-1)(\varDelta -1)$. Then it follows that $D\ge kc_k - \varDelta - (k-1)(\varDelta -1) + \frac{(\varDelta -c_k+3)(\varDelta -c_k)}{2} = (k-1) - k(\varDelta -c_k) + \frac{(\varDelta -c_k+3)(\varDelta -c_k)}{2} = (k-1) + \frac{(\varDelta -c_k)(\varDelta -c_k-2k+3)}{2}$. Combining the above with $\varDelta - c_k \ge 1$ yields $D \ge (k-1) + \frac{4-2k}{2} \ge 1$, and hence $\mathrm{SL}_{\phi }(G) > \mathrm{SL}_{\phi '}(G)$. This is the desired contradiction since $\phi$ is an optimal labeling of G.    $\square$

Lemma 4

Let $G = (V, E)$ be a graph, ${\phi \in \Phi _\mathbf{{opt}}(G)}$, and let $\phi '$ be the labeling obtained from $\phi$ by swapping the labels of any two vertices $u,v \in V$ such that $c_{\phi }(u) = c_{\phi }(v)$. Then ${\phi ' \in \Phi _\mathbf{{opt}}(G)}$.

Lemma 5

Let $G = (V, E)$ be a graph, ${\phi \in \Phi _\mathbf{{opt}}(G)}$, and let $u,v\in V$ such that $\{u,v\}\in E$ and $c_{\phi }(u)=c_{\phi }(v)-1$. Then an optimal labeling $\phi '$ with $\phi '(u)=\phi '(v)-1$ may be obtained from $\phi$ by a series of label swaps involving only vertices $z\in V$ with $c_{\phi }(z)\in \{c_{\phi }(u),c_{\phi }(v)\}$ and $\phi (v)<\phi (z)<\phi (u)$.

Coming back to $V^+_\phi$, and as discussed in [9], in the light of Property 1(a), it would be tempting to claim that $\tau (G) = |V^+_\phi |$ for any –or at least one– optimal labeling ${\phi \in \Phi _\mathbf{{opt}}(G)}$. Unfortunately, this is not true: there exist a graph G for which any optimal labeling $\phi$ satisfies $\frac{|V^+_\phi |}{\tau (G)}=\frac{5}{4}$ [9]. This raises the following question: for any graph G, does there exist a labeling ${\phi \in \Phi _\mathbf{{opt}}(G)}$ such that $\frac{|V^+_\phi |}{\tau (G)}=O(1)$? This question remains open. However, we have the following result, which improves Lemma 1.3 from [9] by a factor $\sqrt{2}$.

Lemma 6

For any graph G of maximum degree $\varDelta$, there exist an optimal labeling ${\phi \in \Phi _\mathbf{{opt}}(G)}$ for which $\frac{|V^+_\phi |}{\tau (G)} < \sqrt{\varDelta }$.

4 A Polynomial-Time Algorithm for Sets of Caterpillars

In this section, we prove that the S-labeling problem is in P when the input instance is a (set of) caterpillar(s) (see Proposition 1). This result can be seen as a step towards understanding the complexity of the problem in trees and forests, which remains unknown. Recall that a caterpillar is a tree $G=(V,E)$ for which all the vertices are within distance 1 of a dominating path. It is easy to see that every longest path P of G has the property that, for all $v\in V$, either v belongs to P or v is a leaf adjacent to a vertex of P, which is not an endpoint of P. We call linear representation of G, denoted $\mathrm{LR}(G)$, any drawing of G in which the vertices of some longest path P of G lie along an horizontal line according to their order on the path. We call set of caterpillars any vertex-disjoint set of caterpillars. A set of caterpillars is seen as a graph $G=(V,E)$ whose connected components $C_1, C_2 \ldots C_p$ are caterpillars. The linear representation of G, still denoted $\mathrm{LR}(G)$, is in this case the sequence $\mathrm{LR}(C_1), \mathrm{LR}(C_2) \ldots \mathrm{LR}(C_p)$ of the linear representations of its connected components, successively on the same horizontal line. Recall that G being a set of caterpillars on n vertices, G contains O(n) edges.

Lemma 7

Let G be a set of caterpillars, and u be its leftmost vertex in $\mathrm{LR}(G)$ such that $d_G(u)=\varDelta$. There is an optimal labeling ${\phi _{\mathbf{{opt}}}}$ of G such that ${\phi _{\mathbf{{opt}}}(u)}$=1.

Proof

Notice that if we prove the existence of an optimal labeling ${\phi \in \Phi _\mathbf{{opt}}(G)}$ such that $c_{\phi }(u)=\varDelta$, then we are done. Indeed, by Lemma 3, we know that the vertex z with label 1 has contribution $\varDelta$, and by Lemma 4, we know that swapping the labels of u and z yields an optimal labeling ${\phi _{\mathbf{{opt}}}}$ such that ${\phi _{\mathbf{{opt}}}(u)=1}$.

We now show that there is an optimal labeling $\phi$ of G such that $c_{\phi }(u)=\varDelta$. Let $\phi '$ be an optimal labeling of G such that every leaf v of G that is adjacent to u (if any) satisfies $\phi '(v)>\phi '(u)$ (say this is a regular leaf). To prove that such a labeling exists, assume by contradiction that this is not the case, and let $\phi '$ be chosen so as to minimize the number of leaves with $\phi '(v)<\phi '(u)$. Denote $v_0$ the leaf with this property and such that $\phi '(v_0)$ is maximum. By Lemma 1, we know that $c_{\phi '}(u)\le c_{\phi '}(v_0)$, with $c_{\phi '}(v_0)=1$. We thus necessarily have $c_{\phi '}(u)=0$ and $c_{\phi '}(v_0)=1$ by Lemma 2, $\{u,v_0\}$ being an edge in G. In this case, Lemma 5 ensures that some labels of $\phi '$ may be swapped to ensure $\phi '(v_0)>\phi '(u)$, and that these swaps do not affect regular leaves. But this contradicts the initial choice of $\phi '$. As a consequence, all the leaves adjacent to u are regular, and $c_{\phi '(u)}\ge \varDelta -2$ since at most two neighbors of u are not leaves.

Now, let v (respectively w) be the right (respectively left) neighbor of u, if it exists. Then, since u is the leftmost vertex in $\mathrm{LR}(G)$ with degree $\varDelta$, we have $d_{G}(w)<\varDelta$ and $d_{G}(v)\le \varDelta$. We transform $\phi '$ into an optimal labeling $\phi$ such that $\phi (u)<\phi (w)$ and $\phi (u)<\phi (v)$, in two steps. First, if $\phi '(u)<\phi '(w)$, then we define $\phi ''=\phi '$. Otherwise, we have $\phi '(u)>\phi '(w)$, and since u and w are adjacent, we deduce that $c_{\phi '}(u)<c_{\phi '}(w)$ by Lemmas 1 and 2. The remarks that $c_{\phi '}(u)\ge \varDelta -2$ and $c_{\phi '}(w)\le \varDelta -1$ further imply that we necessarily have $c_{\phi '}(u)=\varDelta -2$ and $c_{\phi '}(w)=\varDelta -1$, thus allowing us to apply Lemma 5 in order to deduce the existence of an optimal labeling $\phi ''$ with $\phi ''(u)<\phi ''(w)$. Second, if $\phi ''(u)<\phi ''(v)$, then we define $\phi =\phi ''$. Otherwise, since u and v are adjacent, we deduce that $c_{\phi ''}(u)<c_{\phi ''}(v)$ by Lemmas 1 and 2. The remarks that $c_{\phi ''}(u)\ge \varDelta -1$ (we know that $\phi ''(w)>\phi ''(u)$) and $c_{\phi ''}(v)\le \varDelta$ further imply that we necessarily have $c_{\phi ''}(u)=\varDelta -1$ and $c_{\phi ''}(v)=\varDelta$, thus allowing us to apply Lemma 5 in order to deduce the existence of an optimal labeling $\phi$ with $\phi (u)<\phi (v)$. Notice that the label changes performed according to Lemma 5 do not affect the label of w. Then, $\phi (u)<\phi (x)$ for all the neighbors x of u, and thus $c_{\phi }(u)=\varDelta$.    $\square$

Proposition 1

Algorithm GreedyCat optimally solves the S-Labeling problem for any set of caterpillars of order n, in $O(n \log n)$ time.

Proof

By contradiction, assume the labeling $\phi$ obtained by GreedyCat is not an optimal labeling. Let $v_1, v_2 \ldots v_n$ be the vertices of G ordered such that $\phi (v_i)=i$. Now, consider an optimal labeling ${\phi _{\mathbf{{opt}}}}$ which maximizes the value k with the property that ${\phi _{\mathbf{{opt}}}(v_i)=\phi (v_i)}$ ($=i$) for all i, $1\le i\le k$. Let $G_{k+1}$ be the subgraph induced by $\{v_{k+1} \ldots v_n\}$ in G.

According to GreedyCat, $v_1 \ldots v_n$ are labeled successively in this order, and when $v_{k+1}$ is labeled, it has maximum degree in $G_{k+1}$ and is the leftmost in $\mathrm{LR}(G)$ with this property. It is easy to note that a labeling $\phi _0$ of G with $\phi _0(v_i)=i$ for all i, $1\le i\le k$, is optimal for G if and only if the labeling $\phi _1$ of $G_{k+1}$, defined by $\phi _1(v_i)=\phi _0(v_i)-k$ for $k+1\le i\le n$, is optimal for $G_{k+1}$. This is due to the constant cost of the edges $\{v_i,v_j\}$ with $i\le k$ or $j\le k$ within $\mathrm{SL}(G)$. By Lemma 7, there is an optimal labeling $\phi _1$ of $G_{k+1}$ such that $\phi _1(v_{k+1})=1$. The resulting labeling $\phi _0(v_i)=\phi _1(v_i)+k$ for $k+1\le i\le n$, extended to G by $\phi _0(v_i)=i$ for $1\le i\le k$, is then optimal and satisfies $\phi _0(v_i)=\phi (v_i)$ ($=i$) for all i, $1\le i\le k+1$. This contradicts the choice of ${\phi _{\mathbf{{opt}}}}$.

Concerning the complexity, the initial computation of $\mathrm{LR}(G)$ is done in O(n) time by using traversals starting with a 1-degree vertex. The vertices occurring on the horizontal line of the representation are then renumbered in increasing order from left to right, whereas the leaves receive the remaining numbers. Then, for each $d=0, 1, 2 \ldots \varDelta$, we store all vertices of degree d in a balanced BST denoted B[d]. We furthermore need another balanced BST to store all the degrees d for which B[d] is non-empty. It is easy to see that initializing all the BSTs is done in global time of $O(n \log n)$ by $n+\varDelta$ insertions taking $O(\log n)$ time each. The update of the data structures we use involves, at each step, only the neighbors of the vertex u removed from G. There are $O(d_G(u))$ such neighbors, and the operations take no more than $O(\log n)$ time for each neighbor, which yields the required complexity.    $\square$

5 Algorithmic Issues

This section contains two parts: the first one is devoted to approximating the S-labeling problem, whereas the second part focuses on exact (i.e. exponential-time algorithms.

Approximating the S-labeling Problem. We begin by giving accurate lower and upper bounds of optimal labelings. For completeness, in Lemma 8, we recall the lower bound given in [9].

Lemma 8

[9]. For any graph G of order n, size m and maximum degree $\varDelta$, $\mathrm{SL}(G) \ge (m-\frac{\varDelta }{2}\left\lfloor \frac{m}{\varDelta }\right\rfloor ) \left( \left\lfloor \frac{m}{\varDelta }\right\rfloor + 1\right) \text {.}$

Another general lower bound is given in Lemma 9 below.

Lemma 9

For any graph G of size m, let $\phi$ be any labeling of G, and $|V^+_\phi |=k$. Then $\mathrm{SL}_\phi (G) \ge \frac{k^2-k+2m}{2}$.

Proof

Let $\phi$ be any labeling of G, and let $|V^+_\phi |=k$. Since every vertex in $V^+_\phi$ has a strictly positive contribution (by definition), summing these over the k vertices in $V^+_\phi$ adds up to $\frac{k(k+1)}{2}$, and covers k edges. For the remaining $m-k$ edges in G, the best scenario is that they all are incident to the vertex having label 1, which adds up to $m-k$. Hence the result.    $\square$

We now turn to giving upper bounds for optimal labelings. The first two upper bounds are achieved by the following generic greedy algorithm, that we call GreedyGen: while G has edges, take a vertex u of maximum degree in G, assign the smallest available label to u (starting from 1), and remove u and its incident edges from G. Notice that a randomized algorithm achieving the same general upper bound as in Lemma 10 was given in [9]. Here, we improve this previous result by providing a deterministic algorithm, achieving the same performances for general graphs, and improving them for acyclic graphs.

Lemma 10

For any graph G of order n and size m, Algorithm GreedyGen computes, in $O(m \log n)$ time, a labeling $\phi$ such that $\mathrm{SL}_\phi (G) \le \frac{m(n+1)}{3}\text {.}$ Furthermore, if G is acyclic with $\varDelta \ge 3$, $\phi$ satisfies $\mathrm{SL}_\phi (G) \le \frac{m(n+1)}{4}\text {.}$

As a side remark, we observe that there exist classes of graphs for which each of the previously given upper and lower bounds are reached. Indeed, for any even n, $\mathrm{SL}(C_n)=\frac{n^2+2n}{4}=\frac{\varDelta \lfloor \frac{m}{\varDelta }\rfloor (\lfloor \frac{m}{\varDelta }\rfloor +1)}{2}$; for any $k\le m$, $\mathrm{SL}(K_{1,m-k+1}\cup (k-1)K_2)=\frac{k^2-k+2m}{2}$; $\mathrm{SL}(K_n)=\frac{1}{6}n(n^2-1) =\frac{m(n+1)}{3}$; and, finally, for any odd n, $\mathrm{SL}(P_n)=\frac{m(n+1)}{4}$. Another general upper bound can be obtained by starting from a vertex cover $V'$ of G, and applying a greedy strategy, similar to the one of Algorithm GreedyGen, but only taking into account vertices in $V'$. Since all vertices in $V{\setminus } V'$ have a zero contribution, they can be arbitrarily labeled from $|V'|+1$ to n.

Lemma 11

For any graph G of order n and size m, let $V'$ be a vertex cover of G, with $|V'|=p$. A labeling $\phi _{V'}$ satisfying $\mathrm{SL}_{\phi _{V'}}(G) \le \frac{1}{2}m(p+1)$ can be computed in $O(m \log p)$ time.

We are now ready to state our results concerning approximation algorithms, which essentially rely on using the proper upper and lower bounds among the ones presented above. Some of these results improve or generalize the ones from [9], others are new, and all are deterministic (as opposed to some results from [9]). If G is a graph of size m and order n, we denote by $d=\frac{2m}{n}$ its average degree. The first general result we have is the following.

Proposition 2

For any graph, GreedyGen is a $\frac{4\varDelta }{3d}$-approximation algorithm for the S-Labeling problem.

Since we can always assume that G has no isolated vertices, we always have $d\ge 1$, and thus for any graph, we now that a $\frac{4\varDelta }{3}$ approximation algorithm exists. Concerning regular graphs, setting $d=\varDelta$ in Proposition 2 yields the following corollary.

Corollary 1

For any regular graph, GreedyGen is a $\frac{4}{3}$-approximation algorithm for the S-Labeling problem.

Now, if we restrict ourselves to specific classes of graphs, we are able to obtain better approximation ratios. Let $\mathcal {F}_{\le C}$ (resp. $\mathcal {F}_{\ge C}$) be the set of forests having at most (resp. at least) C connected components.

Proposition 3

For any graph G, GreedyGen is an approximation algorithm having the following ratios: (a) $\frac{\varDelta }{2}$ if $G\in \mathcal {F}_{\le \varDelta -1}$, provided $\varDelta \ge 3$; (b) $\varDelta$ if $G\in \mathcal {F}_{\ge \varDelta }$; (c) $\frac{2\varDelta }{3}$ if G is connected.

We now give one more approximation algorithm, in relation to the Minimum Vertex Cover problem. Let $\mathcal {G^{\alpha }_{VC}}$ denote the class of graphs for which the cardinality of a minimum vertex cover can be approximated within ratio $\alpha$. The following result concerns graphs belonging to that class.

Proposition 4

For any graph G in $\mathcal {G^{\alpha }_{VC}}$, there exist an $\alpha \varDelta$-approximation algorithm for the S-Labeling problem.

In particular, for all graphs for which a minimum vertex cover can be computed in polynomial-time, the S-Labeling problem can be approximated within ratio $\varDelta$.

Exact Algorithms. After having discussed approximation algorithms, we now turn to exact algorithms. We first concentrate on exponential-time algorithms.

Proposition 5

For any graph G of order n and maximum degree $\varDelta$, the S-Labeling problem is solvable in time $O^*(1.44225^{n \varDelta })$, and in time $O^*(1.41422^{n \varDelta })$ if G is a tree.

Let G be a graph and ${\phi \in \Phi _\mathbf{{opt}}(G)}$ be an optimal labeling of G. For every positive integer $c\ne 0$, let $V^c_{\phi }=\{u : u \in V \;\wedge \; c_{\phi }(u) = c\}$, and, for any non-empty $V^c_{\phi }$, let $l^c_{min}=\min \{\phi (u): u\in V^c_{\phi }\}$ be the smallest label given by $\phi$ among the vertices in G having contribution equal to c by $\phi$. Because of Lemma 2, we have the following corollary.

Corollary 2

For any graph G, let ${\phi \in \Phi _\mathbf{{opt}}(G)}$ be an optimal labeling of G. Then $V^c_{\phi }$ is a maximal independent set on the vertices of maximum degree in the induced graph $G[\{v : \phi (v) \ge l^c_{min}\}]$.

Proof

(of Proposition 5 ). We use a $\varDelta$-bounded search tree based algorithm. The root of the search tree is labeled by $(G, 0, \emptyset )$. We explore the tree as follows. For a node (H, i, L), we consider all maximal independent sets on the maximum degree vertices of H. For each maximal independent set $V' = \{u_1, u_2, \ldots , u_k\}$, we get a child labeled $(H', i+k, L')$, where $H' = H{\setminus } V'$ and $L' = L \cup \{(u_j, i + j) : 1 \le j \le k\}$. A leaf in the search tree is labeled (H, i, L) for some edgeless graph H and it evaluates to $\sum _{\{u, v\} \in E} \min \{\phi (u), \phi (v)\}$, where $\phi \in \Phi (G)$ is obtained from L in the natural way, i.e., for every $u \in V$, $\phi (u) = i$ if $(u, i) \in L$. The optimal labeling is the minimum evaluation of a leaf of the search tree.

Correctness of the algorithm follows from Corollary 2. What is left is to prove that the search tree has depth bounded by $\varDelta (G)$. This is again a consequence of Corollary 2, since the maximum degree of the graphs strictly decreases during the exploration of the tree. The time complexity now follows from the following result from [14]: any graph of order n contains at most $1.44225^n$ maximal independent sets, and these maximal independent sets can be enumerated in $O^*(1.44225^n)$ time. Besides, if G is a tree, we know by [23] that the number of maximal independent sets G is upper bounded by $O((\sqrt{2})^n)$ (more precisely, the number is $2^{n/2-1} + 1$ if n is even, and $2^{(n-1)/2}$ is n is odd).    $\square$

As a side remark concerning Corollary 2, note that it would be tempting to push ahead and replace maximal by maximum in this corollary. However, that is pushing the argument too far, even for trees. Indeed, consider the tree given Fig. 2 with 3 maximum degree vertices. For one, starting from the unique maximum independent set $\{u,w\}$ on degree $\varDelta =3$ vertices yields a labeling with total sum 34. For another, starting from the other maximal independent set on degree $\varDelta =3$ vertices $\{v\}$ yields a labeling with total sum 31.

Fig. 2.

A graph G with three maximum degree vertices u, v and w, each of degree $\varDelta =3$. (Left) An S-labeling $\phi _1$ of G that starts with the unique maximum independent set on maximum degree vertices of cardinality 2 (namely, $\{u,w\}$), optimally completed with labels 3 to 8, yielding $\mathrm{SL}_{\phi _1}(G)= 34$. (Right) An S-labeling $\phi _2$ of G that starts with the unique maximal independent set on maximum degree vertices of cardinality 1 (namely, $\{v\}$), optimally completed with labels 3 to 8, yielding $\mathrm{SL}_{\phi _2}(G)= 31<\mathrm{SL}_{\phi _1}(G)$.

Now, note that for any graph G of order n and size m, $\mathrm{SL}(G)=\Omega (m)$. But since we can always assume G has no isolated vertices, $n\le 2m$ and thus $\mathrm{SL}(G)=\Omega (n)$. Therefore, the S-labeling problem is fixed-parameter tractable [21] for any graph G, when the parameter is the size of the solution $\mathrm{SL}(G)$. However, the above result relies on a parameter whose value can be considered as too high. Thus, we focus on the following problem: Given a graph $G = (V, E)$ of size $|E|=m$ and a positive integer k, is there a labeling $\phi \in \Phi (G)$ such that $\mathrm{SL}_{\phi }(G) \le m + k$? We need the following result that gives a lower bound for $\mathrm{SL}_\phi (G)$ in terms of $|V^+_\phi |$.

Lemma 12

For any graph G of size m, let $\phi \in \Phi (G)$ be a labeling of G such that $\mathrm{SL}_{\phi }(G) \le m + k$ for some positive integer k. Then $|V^+_\phi | \le 2\sqrt{k}$.

Proof

Let $G = (V, E)$ be a graph and $\phi \in \Phi (G)$ be a labeling of G such that $\mathrm{SL}_{\phi }(G) \le |E| + k$ for some positive integer k. By Lemma 9, we know that $\mathrm{SL}_\phi (G) \ge \frac{|V^+_\phi |^2-|V^+_\phi |+2m}{2}$, which yields $|V^+_\phi |^2-|V^+_\phi |\le 2k$. Solving this second degree inequality leads to $|V^+_\phi |\le x$, where $x=\frac{1+\sqrt{8k+1}}{2}$. A simple computation then shows that $x\le 2\sqrt{k}$ for any positive integer k, which proves the result.    $\square$

Proposition 6

For any graph G of size m and any positive integer k, it can be decided in $O^*(2^{2\sqrt{k}}\ (2 \sqrt{k})!)$ time whether $\mathrm{SL}(G) \le m + k$.

In the above proposition, it is worth noticing that $k \ge \frac{m(n-4)}{4}$ for regular graphs (see Lemma 8), and hence Proposition 6 does not give fixed-parameter tractability for the above-guarantee parameterization variant [11, 20]. However, supposing G is of order n, we now determine how Proposition 6 compares to the brute-force $O^*(n!)$ time algorithm. First, we have $\mathrm{SL}(G) \le mn$, therefore $\mathrm{SL}(G) \le m + k$ implies $k \le mn - m = m(n-1) \le \frac{n(n-1)^2}{2}$, and hence $k = O(n^3)$. We now need the following lemma.

Lemma 13

For positive x and n, if $2^x x! = n!$ then $x = \Theta (n)$.

Substituting x by $2\sqrt{k}$ in Lemma 13 yields $k = \Theta (n^2)$. Since $2^x x!$ is an increasing function, we conclude that Proposition 6 improves on the brute-force $O^*(n!)$ time algorithm for any k, up to $\Theta (n^2)$.

6 Conclusion

We would like to end this paper with several open problems. First, what is the complexity of the S-labeling problem for trees, forests, or more generally bipartite graphs? Second, does there exist a PTAS for the S-labeling problem, for any graph G, or at least for specific classes of graphs? The same question holds for constant approximation ratios.