Temporal Graph Realization with Bounded Stretch

STGR is a natural and well-motivated special case of the problem that we investigated in previous work [40], where the upper bounds can be arbitrary. In this work, we show that STGR is NP-hard and hard to approximate, where we consider the goal of the optimization version of the problem to minimize the stretch $\alpha$. Formally, we prove the following in Section 3.

• $\mathrm{■}$

  For every and every $c>1$, STGR is NP-hard to approximate within a factor of ${\mathrm{\Delta }}^{1-\epsilon }$ or within a factor of $2^{n^c}$.

Note that a stretch of $\mathrm{\Delta }$ can trivially be achieved by assigning the same label to each edge. To complement these results, we show that we can achieve a strictly better approximation ratio than $\mathrm{\Delta }$, especially on graphs with small radius or diameter. Formally, we prove the following in Section 4.

• $\mathrm{■}$

  We can compute in polynomial time a solution for a STGR instance with stretch at most $\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\min (\mathrm{rad}+1,\mathrm{diam})}$, where $\mathrm{diam}$ and $\mathrm{rad}$ denote the diameter and the radius of $G$, respectively.

Next, we focus on the decision version of the problem. We show that STGR is NP-hard even if $\mathrm{\Delta }$ and $\alpha$ are small constants and in cases where the input graphs have a constant diameter. Formally, we prove the following in Section 5.

• $\mathrm{■}$

  STGR is NP-hard if $\mathrm{\Delta }=3$, $\alpha =1$, and the input graph has diameter 2. This answers an open question by Erlebach et al. [23].

• $\mathrm{■}$

  STGR is NP-hard for each $\mathrm{\Delta }\ge 3$, even if the diameter is in $𝒪(\mathrm{\Delta })$.

Recall that we can assume that $\alpha$ is at most $\mathrm{\Delta }$. We also show that STGR is NP-hard for each constant value of $\alpha \ge 1$. To complement these hardness results, we give the following algorithmic results in Section 6. We use standard terminology from parameterized complexity theory [11].

• $\mathrm{■}$

  STGR is fixed-parameter tractable when parameterized by the neighborhood diversity of the input graph and $\mathrm{\Delta }$.

• $\mathrm{■}$

  STGR is fixed-parameter tractable when parameterized by the treewidth of the input graph, the diameter of the input graph, and $\mathrm{\Delta }$.

These results are obtained by using extensions of monadic second order logic (MSO) [9, 10, 34] to formulate STGR, and then applying extensions of Courcelle’s theorem [9, 10, 34].

Finally, we develop a local search algorithm for our problem. This algorithm, given a labeling, checks whether the stretch can be improved by changing at most a given number $k$ of labels. We call $k$ the search radius. We show the following in Section 7.

• $\mathrm{■}$

  Given a periodic labeling for a graph $G$ and some constant $k$, we can compute the best possible stretch that can be obtained by changing at most $k$ labels in polynomial time; that is, we present an algorithm that is in XP with respect to the parameter $k$.

• $\mathrm{■}$

  We show that the above-described local search problem is W[2]-hard when parameterized by the search radius $k$.

Proofs of results marked with $(\star )$ are deferred to the full version of the paper [38].

Since the 1960s, graph realization problems have been studied in many different settings. A complete literature review is beyond the scope of this work. While in the static setting, many different properties for realization have been studied, in particular, the realization of degree sequences, the previous work in the temporal setting considers mostly connectivity-related properties. We review the relevant work in the introduction.

The local search variant of our problem can also be seen as a temporal graph modification problem: we may modify up to $k$ labels to manipulate the graph’s connectivity properties. Many problems in this setting have been studies, where the modifications are typically edge removal, edge delay [14, 18, 37, 42], or vertex removal [25, 31, 46]. Finally, periodic temporal graphs also have been investigated in other problem settings, most prominently in the context of cop and robber games [13, 12, 4, 22, 44, 45].

We present a straightforward gap-introducing reduction from Gossiping [26].

Gossiping Input: A graph $G=(V,E)$. Question: Is there a labeling $\lambda :E\to \mathbb{N}$, such that for each pair $(u,v)$ of vertices of $V$, there is a temporal path in the temporal graph $(G,\lambda )$?

Given an instance $G$ of Gossiping, we produce a STGR instance as follows. We use the same graph $G$ and specify how to set $\mathrm{\Delta }$ later to get the two approximation hardness results.

Intuitively, if $G$ is a yes-instance of Gossiping, then there exists a labeling where it is not necessary to use any label from the second $\mathrm{\Delta }$-period and hence the stretch is independent from $\mathrm{\Delta }$. Whereas if $G$ is a no-instance of the gossiping problem, then there exists no such labeling. Then, informally speaking, there must be a path that crosses the period and has a duration that depends on $\mathrm{\Delta }$ and hence also the stretch depends on $\mathrm{\Delta }$. Now we can set $\mathrm{\Delta }$ to a very large value to create a gap.

Formally, assume that $G$ is a yes-instance of Gossipingand let $\lambda$ be a labeling such that the non-periodic temporal graph $(G,\lambda )$ is temporally connected. We can assume without loss of generality that the largest label in $\lambda$ is $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$. Now we use this labeling for our STGR instance. A very naïve estimation yields that the stretch is at most $\frac{1}{2}\cdot \left(\genfrac{}{}{0pt}{}{n}{2}\right)$: Consider a vertex pair $u,v$ of distance $2$ in $G$. Then the temporal path from $u$ to $v$ in $(G,\lambda )$ has duration at most $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$.

Now assume that $G$ is a no-instance of Gossipingand consider the instance $(G,\mathrm{\Delta })$ (for some $\mathrm{\Delta }>\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ that we specify later) of STGR. Let $\lambda$ be a $\mathrm{\Delta }$-periodic labeling for $G$ that minimizes the stretch. Note that we can obtain an equivalent labeling by adding a constant (modulo $\mathrm{\Delta }$) to every label. Hence, assume that $\delta =\mathrm{\Delta }-{\max }_{e\in E(G)}\lambda (e)$ is maximized. Then we have that $\delta \ge \frac{\mathrm{\Delta }}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}$. Since $G$ is a no-instance of the gossiping problem, there is a vertex pair $u,v$ in $G$ such that the temporal path from $u$ to $v$ in the $\mathrm{\Delta }$-periodic temporal graph $(G,\lambda )$ uses labels from different periods and hence has duration at least $\delta$ and hence a stretch of at least $\frac{\delta }{n}$.

Let ${\alpha }^{\star }$ denote the optimal stretch of $(G,\mathrm{\Delta })$. Summarizing, we have the following.

• $\mathrm{■}$

  If $G$ is a yes-instance of Gossiping, then we have that ${\alpha }^{\star }\le \frac{1}{2}\cdot \left(\genfrac{}{}{0pt}{}{n}{2}\right)={\alpha }_{\text{yes}}$.

• $\mathrm{■}$

  If $G$ is a no-instance of Gossiping, then we have that ${\alpha }^{\star }\ge \frac{\mathrm{\Delta }}{n\cdot \left(\genfrac{}{}{0pt}{}{n}{2}\right)}={\alpha }_{\text{no}}$.

If follows that if we set $\mathrm{\Delta }>\frac{n}{2}\cdot {\left(\genfrac{}{}{0pt}{}{n}{2}\right)}^2$, then we create a gap that allows us to distinguish yes-instance of Gossipingfrom no-instances.

In the remainder, we show how to set $\mathrm{\Delta }$ to obtain the approximation hardness results in the theorem statement. Note that in particular, we can distinguish yes-instance from no-instances whenever $\mathrm{\Delta }\ge n^5$, since $n^5>\frac{n}{2}\cdot {\left(\genfrac{}{}{0pt}{}{n}{2}\right)}^2$. This will make the calculations easier.

For the first statement, let and let ${\epsilon }^{\prime }=\frac{5(1-\epsilon )}{\epsilon }$. Note that $1-\epsilon =\frac{{\epsilon }^{\prime }}{5+{\epsilon }^{\prime }}$. Now we set $\mathrm{\Delta }=n^{5+{\epsilon }^{\prime }}$. Then we have that ${\mathrm{\Delta }}^{1-\epsilon }={\mathrm{\Delta }}^{\frac{{\epsilon }^{\prime }}{5+{\epsilon }^{\prime }}}=n^{{\epsilon }^{\prime }}$. It follows that $\frac{\mathrm{\Delta }}{{\mathrm{\Delta }}^{1-\epsilon }}=n^5$ and hence . We can conclude that there is no ${\mathrm{\Delta }}^{1-\epsilon }$-approximation algorithm.

For the second statement, let $c\ge 1$ and set $\mathrm{\Delta }=n^5{2}^{n^c}$. Note that the encoding of $\mathrm{\Delta }$ is polynomial in $n$, as $\log \mathrm{\Delta }=n^c+5\log n$. We have that $\frac{\mathrm{\Delta }}{2^{n^c}}=n^5$ and hence . We can conclude that there is no $2^{n^c}$-approximation algorithm. $◀$

Let $v_x$ be an arbitrary vertex of eccentricity equal to $\mathrm{rad}$ and let $\lambda$ be the $\mathrm{\Delta }$-labeling produced by the radius algorithm for root $v_x$. We give for each distance $\mathrm{\ell }\in [2,\mathrm{diam}]$ an upper bound ${\alpha }_{\mathrm{\ell }}$ for the stretch of distance-$\mathrm{\ell }$ vertex pairs.

For $\mathrm{\ell }\le \mathrm{rad}+1$, let $(u,v)$ be a pair of vertices of distance exactly $\mathrm{\ell }$ in $G$. Due to ˜2.1, ${\alpha }_{\mathrm{\ell }}:=\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\mathrm{\ell }}$ is an upper bound for the stretch of distance-$\mathrm{\ell }$ vertex pairs.

For $\mathrm{\ell }\ge \mathrm{rad}+2$, let $(u,v)$ be a pair of vertices of distance exactly $\mathrm{\ell }$ in $G$. Consider the journey $J$ that starts in $u$, goes over any shortest path $P_u$ to $v_x$ and then goes over any shortest path $P_v$ to $v$. The edges of $P_u$ ($P_v$) are alternatively labeled with $\mathrm{\Delta }$ and $\lceil \frac{\mathrm{\Delta }}{2}\rceil$ by the algorithms. Moreover, both path each have a length of at most $\mathrm{rad}$. Hence, in the worst case, $J$ traverses $2\mathrm{rad}$ edges. This implies that the duration of $J$ is at most $\mathrm{rad}\cdot \mathrm{\Delta }+1$, since $J$ only waits a full period at vertex $v_x$ and otherwise alternates between waiting $\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$ and $\lceil \frac{\mathrm{\Delta }}{2}\rceil$. Note that this also implies that there is a path of at most that duration from $u$ to $v$. Consequently, ${\alpha }_{\mathrm{\ell }}:=\frac{\mathrm{rad}\cdot \mathrm{\Delta }+1}{\mathrm{\ell }}=\mathrm{\Delta }+\frac{(\mathrm{rad}-\mathrm{\ell })\cdot \mathrm{\Delta }+1}{\mathrm{\ell }}=\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\mathrm{\ell }}-\frac{(\mathrm{\ell }-\mathrm{rad}-1)\cdot \mathrm{\Delta }}{\mathrm{\ell }}$ is an upper bound for the stretch of distance-$\mathrm{\ell }$ vertex pairs.

Note that the stretch achieved by $\lambda$ is thus at most $\max \{{\alpha }_{\mathrm{\ell }}\mid 2\le \mathrm{\ell }\le \mathrm{diam}\}$, if $\mathrm{diam}\ge 2$. (For $\mathrm{diam}=1$, the stretch is always $1$.) We show that the maximum is achieved for $\mathrm{\ell }=\mathrm{rad}+1$ if , and for $\mathrm{\ell }=\mathrm{rad}$ if $\mathrm{rad}=\mathrm{diam}$.

This thus proves that the stretch achieved by $\lambda$ is at most $\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\min (\mathrm{rad}+1,\mathrm{diam})}$. $◀$

Theorem 4.1 follows directly from Lemma 4.2 and the straightforward observation that the radius algorithm runs in polynomial time. However, we can show that in several restricted cases, the algorithm is guaranteed to achieve a better stretch.

As we will show in Section 5, there are instances, where this stretch is achieved by the radius algorithm and it is NP-hard to decide whether a better stretch is possible. This then shows that this simple algorithm produces the best possible stretch for some instances in polynomial time, unless P $=$ NP.

Finally, we can show that the radius algorithm performs well if the input graph is a tree.

Similar to the previous proofs, we give for each distance $\mathrm{\ell }\in [2,\mathrm{diam}]$ an upper bound ${\alpha }_{\mathrm{\ell }}$ for the stretch of distance $\mathrm{\ell }$ vertex pairs.

Let $u,v$ be a vertex pair of distance-$\mathrm{\ell }$. We make the following case distinction. Consider the case where $u$ is an ancestor of $v$ if the graph $G$ is rooted at $v_x$ or $v$ is an ancestor of $u$. In both cases, the edges of the fastest paths from $u$ to $v$ are alternatively labeled with $\mathrm{\Delta }$ and $\lceil \frac{\mathrm{\Delta }}{2}\rceil$ by the algorithm. Hence, we have that the duration of the fastest path from $u$ to $v$ is at most $\frac{\mathrm{\ell }-2}{2}\cdot \mathrm{\Delta }+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor +1$ if $\mathrm{\ell }$ is even, and at most $\frac{\mathrm{\ell }-1}{2}\cdot \mathrm{\Delta }+1$ if $\mathrm{\ell }$ is odd. Hence, the stretch is $\alpha \le \frac{\mathrm{\Delta }}{2}+\frac{1}{\mathrm{\ell }}$. Since $\mathrm{\ell }\ge 2$, we have that $\alpha \le \frac{\mathrm{\Delta }+1}{2}$.

Now consider the case that neither $u$ is an ancestor of $v$, nor is $v$ an ancestor of $u$. Let $w$ be the closest common ancestor of $v$ and $u$. Then we have that a fastest temporal path from $u$ to $v$ can be decomposed into a fastest temporal path from $u$ to $w$ and a fastest temporal path from $w$ to $v$. Note that the waiting time at $w$ is $\mathrm{\Delta }$, since all edges from $w$ to its children have the same label. All other waiting times are $\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$ and $\lceil \frac{\mathrm{\Delta }}{2}\rceil$, alternatingly. It follows that the duration of a fastest temporal path from $u$ to $v$ is at most $\frac{\mathrm{\ell }-1}{2}\cdot \mathrm{\Delta }+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor +1$ if $\mathrm{\ell }$ is even, and at most $\frac{\mathrm{\ell }}{2}\cdot \mathrm{\Delta }+1$ if $\mathrm{\ell }$ is odd. Then, again, we have that the stretch is $\alpha =\frac{\mathrm{\Delta }}{2}+\frac{1}{\mathrm{\ell }}$. Since $\mathrm{\ell }\ge 2$, we have that $\alpha \le \frac{\mathrm{\Delta }+1}{2}$. $◀$

On trees with a large maximum degree, we can show that our algorithm is optimal.

We now start by presenting our first hardness result.

We reduce from 3-Coloring. Let $G=(V,E)$ be an instance of 3-Coloring and assume that each vertex of $V$ has at least one non-neighbor. Moreover, let $\alpha \in [1,1.5)$. We obtain an instance $I^{\prime }:=(G^{\prime }=(V^{\prime },E^{\prime }),\mathrm{\Delta }=3,\alpha )$ of STGR as follows: We initialize the graph $G^{\prime }:=(V^{\prime },E^{\prime })$ as the star with center vertex $c$ and leaf set $V$. Additionally, we add for each non-edge $\{u,v\}$ of $G$ the vertices $x_{u,v}$ and $x_{v,u}$, and the edges $\{u,x_{u,v}\},\{u,x_{v,u}\},\{v,x_{u,v}\},\{v,x_{v,u}\}$, and $\{x_{u,v},x_{v,u}\}$ to $G^{\prime }$. That is, $G^{\prime }[\{u,v,x_{u,v},x_{v,u}\}]$ is a diamond. Finally, we add another vertex $c^{\ast }$ to $G^{\prime }$ and making $\{c^{\ast }\}\cup (V^{\prime }\setminus V)$ into a clique in $G^{\prime }$. This completes the construction of $I^{\prime }$. Note that $G^{\prime }$ has a diameter of $2$, since both vertices $c$ and $c^{\ast }$ are adjacent to all vertices. In the following, let $D$ be the distance matrix of $G^{\prime }$ and let $C:=\{c^{\ast }\}\cup (V^{\prime }\setminus V)$. The intuition of this reduction is that for each edge $\{u,v\}$ of $G$, $(u,c,v)$ and $(u,c^{\ast },v)$ are the only paths of length less than $\mathrm{\Delta }>2\cdot \alpha =\alpha \cdot D_{u,v}$. Hence, on both paths, the labels of both edges need to be distinct in any labeling $\lambda$ of stretch at most $\alpha$. Next, we show that $G$ is $3$-colorable if and only if $I$ is a yes-instance of STGR.

$(\Rightarrow )$ Let $\chi :V\to \{1,2,3\}$ be a $3$-coloring of $G$. We define a edge labeling $\lambda$ of $G^{\prime }$ of stretch $1$ as follows: For each vertex $v\in V$, we set $\lambda (\{c,v\}):=\chi (v)$ and $\lambda (\{c^{\ast },v\}):=4-\chi (v)$. For each non-edge $\{u,v\}$ of $G$, we set $\lambda (\{u,x_{u,v}\}):=\lambda (\{v,x_{v,u}\}):=1$ and $\lambda (\{u,x_{v,u}\}):=\lambda (\{v,x_{u,v}\}):=3$. For all other edges $e$ of $G^{\prime }$, we set $\lambda (e):=2$. Note that these latter edges are the edges of the clique $V^{\prime }\setminus V$. We now show that $\lambda$ has a stretch of $1$, that is, for each pair of vertices of distance $2$ in $G^{\prime }$, there are temporal paths of duration $2$ between them. Let $(a,b)$ be a pair of vertices of distance two in $G^{\prime }$. Since $V^{\prime }\setminus V$ is a clique in $G^{\prime }$, at least one of $a$ and $b$ is a vertex of $V$. Without loss of generality assume that $a\in V$. We distinguish two cases.

First, assume that $b\notin V$. By construction of $G^{\prime }$ this implies that $b=x_{u,v}$ for some non-edge $u,v$ of $G$ with $a\notin \{u,v\}$. Since we assumes that each vertex of $V$ has at least one non-neighbor in $G$, there is a vertex $w\in V$ such that the vertices $x_{a,w}$ and $x_{w,a}$ exist. Hence, by definition of $\lambda$, the path $(a,x_{a,w},x_{u,v}=b)$ uses the labels $1$ and $2$, and the path $(b=x_{u,v},x_{w,a},a)$ uses the labels $2$ and $3$. Consequently, there are temporal paths between $a$ and $b$ of durations $2$.

Second, assume that $b\in V$. If $\{a,b\}$ is a non-edge of $G$, then the vertices $x_{a,b}$ and $x_{b,a}$ exist. Hence, by definition of $\lambda$, the paths $(a,x_{b,a},b)$ and $(b,x_{a,b},a)$ uses the labels $3$ and $1$. Consequently, there are temporal paths between $a$ and $b$ of durations $2$. Otherwise, that is, if $\{a,b\}$ is an edge of $G$, then $\chi (a)\ne \chi (b)$ since $\chi$ is a proper coloring of $G$. Since $\mathrm{\Delta }=3$, this implies that $\chi (b)=\chi (a)+1$ (modulo $\mathrm{\Delta }$) or that $\chi (a)=\chi (b)+1$ (modulo $\mathrm{\Delta }$). Assume without loss of generality that the first is the case. Hence, by definition of $\lambda$, the path $(a,c,b)$ uses consecutive time-labels (modulo $\mathrm{\Delta }$) and the path $(b,c^{\ast },a)$ uses consecutive lime labels (modulo $\mathrm{\Delta }$). Consequently, there are temporal paths between $a$ and $b$ of durations $2$. Concluding, $\lambda$ has a stretch of $1\le \alpha$, which implies that $I^{\prime }$ is a yes-instance of STGR.

$(\Leftarrow )$ Let $\lambda :E^{\prime }\to \{1,2,3\}$ be an edge labeling of $G^{\prime }$ with stretch at most $\alpha$. We define a $3$-coloring $\chi$ of the vertices of $V$ as follows: For each vertex $v\in V$, we set $\chi (v):=\lambda (\{c,v\})$. Next, we show that for each edge $\{u,v\}\in E$, $u$ and $v$ receive distinct colors under $\chi$. Recall that for $\lambda$ to have a stretch of $\alpha$ for $G^{\prime }$, at least one path of length at most  from $u$ to $v$ in $G^{\prime }$ has duration at most . Since $\{u,v\}$ is an edge of $E$, the vertices $x_{u,v}$ and $x_{v,u}$ do not exist, which implies that $(u,c,v)$ and $(u,c^{\ast },v)$ are the only paths from $u$ to $v$ in $G^{\prime }$ of length less than $3$ and that $(v,c,u)$ and $(v,c^{\ast },u)$ are the only paths from $v$ to $u$ in $G^{\prime }$ of length less than $3$. Assume towards a contradiction that $\chi (u)=\chi (v)$. This implies that $\lambda (\{c,u\})=\lambda (\{c,v\})$. Hence, the paths $(u,c,v)$ and $(v,c,u)$ have a duration of exactly $\mathrm{\Delta }+1=4>2\cdot \alpha =\alpha \cdot D_{u,v}=\alpha \cdot D_{v,u}$. Consequently, for $\lambda$ to have a stretch of $\alpha$ for $G^{\prime }$, both paths $(u,c^{\ast },v)$ and $(v,c^{\ast },u)$ must have a duration of $2$. Since $\mathrm{\Delta }=3$, this is impossible. This contradicts the assumption that $\lambda$ is an edge labeling of $G^{\prime }$ with stretch at most $\alpha$. Thus, $\chi (u)=\lambda (\{c,u\})\ne \lambda (\{c,v\})=\chi (v)$, which implies that $\chi$ is a proper $3$-coloring for $G^{\prime }$ $◀$

Note that Lemma 5.1 answers (by setting $\alpha =1$) an open question by Erlebach et al. [23] about the complexity of finding a periodic $\mathrm{\Delta }$-labeling for a diameter-2 graph $G$, such that the fastest paths between any two vertices of $G$ equals their distance.

Next, we show that for each $\mathrm{\Delta }\ge 3$, it is NP-hard to decide whether a stretch in $[\frac{\mathrm{\Delta }}{2},\frac{\mathrm{\Delta }+1}{2})$ can be achieved. To this end, we define gadget graphs for each $\mathrm{\Delta }$ and some associated labelings. First, we define this gadgets for $\mathrm{\Delta }=3$ and present the first reduction. Afterwards, we define these gadgets for odd values of $\mathrm{\Delta }>3$ and even values of $\mathrm{\Delta }\ge 4$ and present similar reductions.

Figure 2 also shows what we call the sunglasses labeling.

We now show that there are graphs with diameter 3 and radius 2, for which it is NP-hard to decide whether one can achieve a better stretch than the one achieved by the radius-algorithm. This then shows that this simple and natural algorithm is tight on some hard instances.

Let $\mathrm{\Delta }=3$ and let $\alpha \in [1.5,2)$. We again reduce from 3-Coloring. Let $G=(V,E)$ be an instance of 3-Coloring. Again, assume that each vertex of $V$ has at least one non-neighbor, as otherwise we would know that this vertex receives a unique color in any $3$-coloring and the remaining vertices can only be colored in two colors, which can be checked in polynomial time. We obtain an equivalent instance $I:=(G^{\prime },\mathrm{\Delta },\alpha )$ of STGR as follows: We initialize the graph $G^{\prime }:=(V^{\prime },E^{\prime })$ as the star with center vertex $c$ and leaf set $V$. Additionally, we add for each non-edge $\{u,v\}$ of $G$ a $3$-sunglasses gadget $S_{\{u,v\}}$ with docking points $u$ and $v$ to $G^{\prime }$. Let $X$ denote the set of the central vertices of all added sunglasses gadgets.

To complete the definition of $G^{\prime }$, we add the vertices $\widehat{X}:=\{\widehat{x}\mid x\in X\}$ to $G^{\prime }$ and making each vertex of $\widehat{X}$ adjacent to each vertex of $X\cup \widehat{X}\cup \{c\}$ in $G^{\prime }$.

This completes the construction of $I$. In the following, let $D$ be the distance matrix of $G^{\prime }$. The intuitive idea is that for each edge $\{u,v\}\in E$, the path $(u,c,v)$ ($(v,c,u)$) is the only path of length less than $\mathrm{\Delta }+1=4>\alpha \cdot D_{u,v}=2\cdot \alpha$ from $u$ ($v$) to $v$ ($u$) in $G^{\prime }$. Hence, each labeling $\lambda$ of $G^{\prime }$ of stretch at most $\alpha$ has to assign distinct labels to the edges $\{c,u\}$ and $\{c,v\}$. In other words, if labeling $\lambda$ of $G^{\prime }$ has stretch at most $\alpha$, then the edges between $c$ and the vertices of $V$ imply a $3$-coloring for $G$.

Note that radius of $G^{\prime }$ is at most $2$: The neighborhood of vertex $c$ is $V\cap \widehat{X}$ and each vertex of $X=V^{\prime }\setminus (V\cup \widehat{X}\cup \{c\})$ is a neighbor of each vertex of $\widehat{X}$. Moreover, $G^{\prime }$ has a diameter of $3$, since (i) each vertex of $V$ has distance at most $2$ to each vertex of $V\cup \widehat{X}$ by going over $c$ and thus distance at most $3$ to each vertex of $X$ and (ii) each vertex of $X$ has distance at most $2$ to each vertex of $X\cup \{c\}$ by going over some vertex of $\widehat{X}$ and thus distance at most $3$ to each vertex of $V$. In particular, all vertex pairs of distance exactly $3$ in $G^{\prime }$ contain one vertex of $V$ and one vertex of $X$. Since $c$ is a neighbor of all vertices of $V$, $G^{\prime }$ fulfills the property of Lemma 4.4, which implies that the radius algorithm produces a labeling of stretch of at most $\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\mathrm{rad}}=2$.

We now show that $G$ is $3$-colorable if and only if $I$ is a yes-instance of STGR.

$(\Leftarrow )$ Let $\lambda :E^{\prime }\to \{1,2,3\}$ be an edge labeling of $G^{\prime }$ with stretch at most $\alpha$. We define a $3$-coloring $\chi :V\to \{1,2,3\}$ as follows: For each vertex $v\in V$, we set $\chi (v):=\lambda (\{c,v\})$. Next, we show that for each edge $\{u,v\}\in E$, $u$ and $v$ receive distinct colors under $\chi$. Since $\{u,v\}$ is an edge of $E$, there is no sunglasses gadget with docking points $u$ and $v$ in $G^{\prime }$. This implies that $(u,c,v)$ is the only path from $u$ to $v$ in $G^{\prime }$ of length less than $\mathrm{\Delta }+1=4>\alpha \cdot D_{u,v}=2\cdot \alpha$. Assume towards a contradiction that $\chi (u)=\chi (v)$. This would imply that $\lambda (\{c,u\})=\lambda (\{c,v\})$. Hence, the unique path $(u,c,v)$ from $u$ to $v$ in $G^{\prime }$ of length less than $\mathrm{\Delta }+1=4$ has a duration of exactly $4=\mathrm{\Delta }+1>2\cdot \alpha =\alpha \cdot D_{u,v}$. This contradicts the assumption that $\lambda$ is an edge labeling of $G^{\prime }$ with stretch at most $\alpha$. Thus, $\chi (u)=\lambda (\{c,u\})\ne \lambda (\{c,v\})=\chi (v)$, which implies that $\chi$ is a proper $3$-coloring for $G^{\prime }$.

$(\Rightarrow )$ Let $\chi :V\to \{1,2,3\}$ be a $3$-coloring of $G$. Assume without loss of generality that each of the three colors is assigned at least once. We define an edge labeling $\lambda$ of $G^{\prime }$ of stretch $\frac{\mathrm{\Delta }}{2}=1.5$ as follows: For each vertex $v\in V$, we set $\lambda (\{c,v\}):=\chi (v)$. For each non-edge $\{a,b\}$ of $G$ (that is, for each added sunglasses gadget), we label the edges of the sunglasses gadget $S_{x,y}$ according the sunglasses labeling (see Figure 2). To complete the definition of $\lambda$, it remains to define the labels of the edges incident with the vertices of $\widehat{X}$. For each vertex $\widehat{x}\in \widehat{X}$, we set $\lambda (\{x,\widehat{x}\}):=1$. For each other edge $e$ incident with at least one vertex of $\widehat{X}$, we set $\lambda (e):=2$.

This completes the definition of $\lambda$. Next, we show that $\lambda$ has a stretch of $1.5=\frac{\mathrm{\Delta }}{2}\le \alpha$.

First, we consider vertex pairs $\{y,z\}$ of distance 2 in $G^{\prime }$. For these vertex pairs, we show that there are paths of duration at most $3=1.5\cdot D_{y,z}$ between $y$ and $z$.

• $\mathrm{■}$

  If $y=c$, then by the initial argumentation, $z\in X$. Hence, $\widehat{z}$ is a nice neighbor of $c$ and $z$, which implies that the path $(c,\widehat{z},z)$ has duration at most $\mathrm{\Delta }=3$ is both directions.

• $\mathrm{■}$

  If $y\in \widehat{X}$, then by the initial argumentation, $z\in V$. Since $z$ is the docking point of at least one sunglasses gadget, there are at least two vertices $x_1$ and $x_2$ of $X$ adjacent to $z$. For at least one $i\in \{1,2\}$, $z\ne \widehat{x_i}$. Hence, the edge $\{x_i,z\}$ receives label $2$ under $\lambda$. This implies that $x_i$ is a nice neighbor, since the edge $\{y,x_i\}$ receives label either 1 or 3 under $\lambda$. Consequently, the path $(c,\widehat{z},z)$ has duration at most $\mathrm{\Delta }=3$ is both directions.

• $\mathrm{■}$

  If $y\in X$, then $z\in X\cup V\cup \{c\}$. The case for $z=c$ is covered by the above cases. If $z\in X$, the path $(y,\widehat{y},z)$ has labels $(1,2)$ and thus has duration at most $\mathrm{\Delta }=3$ in both directions. Otherwise, if $z\in V$, then by construction, $z$ is a docking point of the sunglasses gadget that contains $y$. Hence, by the sunglasses labeling, there is a nice neighbor of $y$ and $z$ in this sunglasses gadget which implies the existence of paths of duration at most $3$ between in $y$ and $z$.

• $\mathrm{■}$

  If $y\in V$, then $z\in X\cup \widehat{X}\cup V$. The case for $z\in X\cup \widehat{X}$ is covered by the above cases. If $z\in V$, we consider two cases. If $\{y,z\}$ is an edge of $E$, $c$ is a nice neighbor of $y$ and $z$, since $\chi$ is a proper 3-coloring of $G$. Otherwise, if $\{y,z\}$ is not an edge of $G$, there is a sunglasses gadget with docking points $y$ and $z$. By the sunglasses labeling, this gadget contains a path with labels $(1,2,3)$ from $y$ to $z$ and a path with labels $(1,2,3)$ from $z$ to $y$. In both cases, there are paths of duration at most $3$ between $y$ and $z$.

Next, we consider vertex pairs $\{y,z\}$ of distance 3 in $G^{\prime }$. For these vertex pairs, we show that there are paths of duration at most  between $y$ and $z$. By the initial argumentation about the structural properties of $G^{\prime }$, we can assume without loss of generality that $y\in V$ and $z\in X$. Moreover, $z$ is not part any sunglasses gadget attached to $y$, as otherwise, the distance between $y$ and $z$ would be at most $2$. Take an arbitrary sunglasses gadget attached to $y$ and let $x_1$ and $x_3$ be the neighbors of $y$ in this sunglasses gadget. By the sunglasses labeling, we can assume that the label of $\{y,x_i\}$ is equal to $i$ for each $i\in \{1,3\}$. Since $z\in X$, $\widehat{z}$ is a vertex of $\widehat{X}$, $\lambda (\{z,\widehat{z}\})=1$, and $\lambda (\{\widehat{z},x_1\})=\lambda (\{\widehat{z},x_3\})=2$. This implies that the path $(z,\widehat{z},x_3,y)$ has labels $(1,2,3)$ and thus a duration of $3$. For the other direction, the path $(y,x_1,\widehat{z},z)$ has labels $(1,2,1)$ and thus a duration of $4$. Hence, there are paths of duration at most $4$ between $y$ and $z$.

This implies that the stretch of $\lambda$ is at most $\frac{\mathrm{\Delta }}{2}=1.5\le \alpha$, which completes the proof. $◀$

In combination with Lemma 5.1, this implies that for $\mathrm{\Delta }=3$, STGR is NP-hard for each $\alpha \in [1,2)$.

We now proceed by showing that also for each $\mathrm{\Delta }>3$, STGR is NP-hard for each $\alpha \in [\frac{\mathrm{\Delta }}{2},\frac{\mathrm{\Delta }+1}{2})$. To obtain this result, we define for each $\mathrm{\Delta }>4$, $\mathrm{\Delta }$-sunglasses gadgets and replace the $3$-sunglasses gadgets in the reduction of the proof of Lemma 5.5 by the larger $\mathrm{\Delta }$-sunglasses gadgets. The definition of these larger gadgets and the reduction is deferred to the attached full version.

Recall that Lemma 5.1 shows that STGR is NP-hard for each $\alpha \in [1,1.5)$. Moreover, since for each constant $\alpha \ge 1.5$, there is a constant $\mathrm{\Delta }\ge 3$, such that $\alpha \in [\frac{\mathrm{\Delta }}{2},\frac{\mathrm{\Delta }+1}{2})$, Lemmas 5.1, 5.5, and 5.7 imply the following.

Theorem 6.1 follows directly from Lemma 6.5, Theorem 6.4, and from the fact that ${\varphi }_{G,\mathrm{\Delta },\alpha }$ is an MSO${}_{\text{lin}}{}^{}{}_{}{}^{\text{GL}}$-formula with a size in $𝒪({\mathrm{\Delta }}^2)$ that can be computed in $𝒪({\mathrm{\Delta }}^2)$ time. $◀$

Our algorithm iterates over all $𝒪({|E|}^k)$ subsets $F\subseteq E$ of size at most $k$. For each such subset $F$, we then ask the question, whether we can achieve a stretch of ${\alpha }_0$ by changing only the labels of edges of $F$. That is, we iteratively solve the following intermediate problem.

Fixed Edges Relabel STGR Input: A graph $G=(V,E)$, $\mathrm{\Delta }\in \mathbb{N}$, a set $F\subseteq E$, a labeling ${\lambda }^{\prime }:E\setminus F\to [1,\mathrm{\Delta }]$, and a number ${\alpha }_0\ge 1$. Question: Does there exist a labeling ${\lambda }_F:F\to [1,\mathrm{\Delta }]$, such that the stretch of ${\lambda }^{\prime }\cup {\lambda }_F$ is at most ${\alpha }_0$?

Based on the ${|E|}^k\cdot n^{𝒪(1)}$ time (which is XP time) for the iteration over all candidate sets $F$, to present our XP algorithm, it suffices to show that Fixed Edges Relabel STGR admits an XP algorithm for $k$.

Let $e_1,e_2,\mathrm{\dots },e_k$ be the edges of the given set $F$, enumerated arbitrarily, and assume that $k\ne |E|$, that is, there exists at least one edge of $E$ that is not in $F$. For every $1\le i\le k$ denote by $u_i$ and $v_i$ the endpoints of the edge $e_i$; note that some edges of $F$ may have common endpoints. Denote the set of all endpoints of the edges of $F$ by $V_F=\{u_i,v_i:1\le i\le k\}$. We now define the set $N_F={\bigcup }_{v\in V_F}\{e\in E\setminus F:v\in e\}$ of all edges in $G$ that are not in $F$ but share at least one common endpoint with some edge in $F$. Furthermore, we define the set $L_0=\{\lambda (e):e\in N_F\}$ of all distinct time-labels that appear in at least one edge of $N_F$. Let be the labels of $L_0$ in increasing order. For simplicity of the presentation, we assume without loss of generality that ${\mathrm{\ell }}_1=1$; this can be achieved by subtracting ${\mathrm{\ell }}_1-1$ from the time-label of every edge. Note that $t=|L_0|\le |N_F|\le {\sum }_{v\in V_F}|N(v)|-|F|\le k\cdot {\mathrm{deg}}_{\max }\in 𝒪(n^2)$. Finally, we define the $2t$ subsets $Z_1,\mathrm{\dots },Z_{2t}$ of time-labels, called zones, as follows. For every $j=1,2,\mathrm{\dots },t-1$, we define $Z_{2j-1}=\{{\mathrm{\ell }}_j\}$ and $Z_{2j}=\{{\mathrm{\ell }}_j+1,\mathrm{\dots },{\mathrm{\ell }}_{j+1}-1\}$. For $j=t$, we define $Z_{2t-1}=\{{\mathrm{\ell }}_t\}$ and $Z_{2t}=\{{\mathrm{\ell }}_t+1,\mathrm{\dots },\mathrm{\Delta }\}$.