Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs

We require different reductions for directed and undirected graphs. In both cases, substitute a gadget in place of each edge in the original instance, and increase the lifetime of the instance. Both constructions preserve planarity, and the DelayBetter-instance has final lifetime at most $2T_{\max }+2\delta +1$ (directed) or $T_{\max }+\delta +2$ (undirected), where $T_{\max }$ is the final lifetime of the $\delta$-DelayBetter instance.

We first deal with the undirected case. We begin with a $\delta$-DelayBetter instance $((G,\lambda ),D,\delta )$ having the property that every time is at time $3$ or later (if necessary, this can be achieved by uniformly incrementing all times in the demands and in the temporal assignment by $2$). We then create, for every time-edge $(u,v,t)$, a gadget on $3\delta +3$ new vertices $\{u{v}_t,\mathrm{\dots },u{v}_{t+\delta },u_1,\mathrm{\dots },u_{\delta },v_1,\mathrm{\dots },v_{\delta },u^{\prime },v^{\prime }\}$ and $\delta +1$ new demands $\{(u{v}_i,v^{\prime },i+1):i\in [t,t+\delta ]\}$, as shown in Figure 2.

Now each of the $\delta +1$ demands into $v^{\prime }$ must be routed through a different path. Because there are $\delta +1$ possible paths in total, some demand $(u{v}_i,v^{\prime },t)$ must be routed through the edge $(u,v)$ – and this entails that ${\lambda }^{\prime }(u,v)=i$, yielding the desired result since $i\in [t,t+\delta ]$ by construction.

We now give the proof for the directed case. Given an instance $(𝒢=(G,\lambda ),D,\delta )$ of $\delta$-DelayBetter, we produce an instance $({𝒢}^{\prime }=(G^{\prime },{\lambda }^{\prime }),D^{\prime })$ of DelayBetter as follows. (For this proof, we use ${\lambda }^{\prime }$ to refer to the initial assignment of the new instance, not the delaying of $\lambda$.) We first include $\{(u,v,2t)|(u,v,t)\in D\}$ as demands, which we call travelers. Next, we replace every time-edge $(u,v)$ at time $t$ with the gadget pictured in Figure 3, and add the demand $(u^{\prime },v^{\prime },2t+2\delta +1)$. We call demands introduced in this step hermits, the edge $(u^{\prime },u)$ that hermit’s trailhead, and the edge $(u,uv)$ (resp. $(uv,v)$) a first-half (resp. second-half) edge. This concludes the construction.

Clearly, if the $\delta$-DB instance reduced from was a yes-instance, then the DelayBetter instance obtained is also a yes-instance: whenever some edge $(u,v)$ is delayed by some amount $x$ in the original instance, delay both $(u,uv)$ and $(uv,v)$ by $2x$. It remains to show the converse.

Let ${\lambda }^{\ast }$ be a solution to our modified problem with a pareto-optimal time-assignment of the edges (that is, one such that there is no other solution whose time-labels are all strictly smaller or equal to those under ${\lambda }^{\ast }$).

Suppose otherwise. We must deal with two cases:

We deal first with the case where the earliest edge violating this claim is a first-half at an odd time. Let $(u,uv)$ be the earliest first-half edge assigned an odd time (say, $t^{\prime }$) under ${\lambda }^{\ast }$. By pareto-optimality of ${\lambda }^{\ast }$ is must be that assigning time $t^{\prime }-1$ to the edge $(u,uv)$ would stop some demand from being satisfied. This demand cannot be a hermit because of Claim 4 – so there must be some traveler arriving at $u$ at time $t^{\prime }-1$, a contradiction since our premise for this case was that $(u,uv)$ was the earliest edge violating the claim.

Suppose instead that the earliest offending edge is a second-half edge $(wu,u)$ assigned an even time (say, $t^{\prime }-1$). We again quickly find that this can only be due to the first-half edge $(w,wu)$ being used by a traveler at time $t^{\prime }-2$ - again reaching a contradiction, since this is a strictly earlier odd time assigned to a first-half edge. $\mathrm{⊲}$

Claim 5 allows us to recover a time-labeling for our initial $\delta$-DelayBetter instance by assigning to each the edge $(u,v)$ the time $\frac{(u,uv)}{2}$ while preserving the temporal paths of travelers. Claim 6 entails that this time-labeling does not delay any edge by more than $\delta$, and the result follows. $◀$

We use the One Source Reach Fast algorithm from [6]: They show that the time-assignment of their algorithm computes, for a given source $v\in V$ and every remaining vertex $u\in V$, the individual minimum time that $v$ needs to reach $u$. If this computed minimum time is at most our demanded arrival time for all demands $(v,u,t)\in D$, then we have a YES-instance, otherwise we have a NO-instance. $◀$

We now turn to the case where passenger demands fully prescribe the path they must be routed along, establishing tractability through a linear programming argument.

Let $((G,\lambda ),D)$ be an instance of Path DelayBetter (or, let $((G,\lambda ),D,\delta )$ be an instance of $\delta$-Path-DelayBetter – the proof differs only in a few details).

We begin by introducing some notation. Our proof is for directed and undirected inputs – we shall use $uv$ to mean the edge $(u,v)$, but in the undirected case $uv=vu$ whereas in the directed case these are $uv\ne vu$. For a demand $d\in D$, we denote by $d_P$ the specified static path in $G$ from $d_s$ to $d_z$, and $d_f$ the final edge of $d_P$, which is incident to $d_z$ and must be at time $d_t$ or earlier to satisfy the demand. We also use $t_{uv}$ as shorthand for $\lambda (u,v)$, and $t_{uv}^{\prime }$ for ${\lambda }^{\prime }(u,v)$. Lastly, we define the relation $(u,v)\prec (v,w)$, to be true if and only if $(u,v)$ immediately precedes $(v,w)$ in the path $d_P$ for some $d\in D$.

Consider the following linear program:

This LP has $\{t_{uv}^{\prime }:(u,v)\in E(G)\}$ as its set of unknown variables. The variables $\{t_{uv}:(u,v)\in E(G)\}\cup \{d_t:d\in D\}$ correspond to given integers fully specified by the Path-DB instance $((G,\lambda ),D)$ (and $d_f$ likewise refers to a specific edge of $G$).

Since linear programs are solvable in polynomial time [19], we may first solve the LP and then (if the solution is not already integral) apply Claim 11 to recover an integral solution. We note here that a modification of Kahn’s algorithm [18] for topological sorting may be used to compute a solution to this particular LP directly and more efficiently. A detailed proof would be quite technical and incongruous with the rest of the paper, so has been omitted.

An integral solution to this LP fully specifies a delaying ${\lambda }^{\prime }$ satisfying the ($\delta$-)Path DB instance. Note that: ${\lambda }^{\prime }$ is indeed a ($\delta$-)delaying of $\lambda$ (due to Equations 2 and 3); enables strict temporal paths along each path specified in $D$ (due to Equation 4); and that each of these paths reaches the destination vertex by the arrival time prescribed (due to Equation 5). Conversely, it should be clear that any delaying ${\lambda }^{\prime }$ satisfying the ($\delta$-)Path DB instance specifies a (not necessarily optimal) solution to the LP. In fact, the LP allows us not only to decide ($\delta$-)Path DB, but more strongly to solve its optimization variant. $◀$

Since trees are characterized by any pair $(u,v)$ being connected by a unique (static) path, we obtain the following corollary:

Next, we are able to extend this result to “tree-like” graphs, by parameterizing by the size of the instance’s feedback edge set.

The proofs for directed and undirected graphs differ only in small details, and those for for $\delta$-DB and DelayBetter are identical (until we apply Theorem 10).

Let $E^{\prime }$ be a feedback edge set of (the undirected version of) ${𝒢}_{\downarrow }$ of size $\rho$. We iterate over each of the $\rho !$ possible orderings $(e_1,e_2,\mathrm{\dots }{e}_{\rho })$ of $E^{\prime }$, and require that $t_{e_1}\le t_{e_2}\le \mathrm{\dots }\le t_{e_{\rho }}$. (Note that if $T_{\max }$ is small and $\rho$ is large, we may prefer to iterate over all ${(T_{\max })}^{\rho }$ assignments and obtain an ordering from those.)

In any solution, each demand $d\in D$ is satisfied by a strict temporal path from $d_u$ to $d_v$ using some subset of the edges of $E^{\prime }$. In the directed case, specifying this subset (together with the ordering fixed earlier) fully specifies the path from $d_u$ to $d_v$; in the undirected case, it is also necessary to specify the direction taken for each edge. The journey from one edge in the subset to the next is uniquely determined due to the fact that it can only use the edges of the spanning tree obtained by removing $E^{\prime }$ from $𝒢$.

For directed graphs, this means there are at most $2^{\rho }$ possible paths for each demand (an edge is either chosen or not), and thus $2^{\rho \cdot |D|}$ for all demands. For undirected graphs, we get $3^{\rho }$ possible paths per demand (an edge $(u,v)\in E^{\prime }$ is either traversed from $u$ to $v$, from $v$ to $u$, or not at all), and thus $3^{\rho \cdot |D|}$ for all demands. For each ordering of $E^{\prime }$ and collection of subsets of $E^{\prime }$, there is a corresponding instance of ($\delta$-)Path DB.

In total, it is sufficient to solve $\rho !\cdot 2^{\rho \cdot |D|}$ such instances of ($\delta$-)Path DB for directed graphs, and $\rho !\cdot 3^{\rho \cdot |D|}$ instances of ($\delta$-)Path DB for undirected graphs. Since ($\delta$-)Path DB is solvable in polynomial time by Theorem 10, we obtain the desired result. $◀$

Our reduction is from Positive Not-All-Equal Exactly 3SAT [11], an NP-complete problem taking as input a formula $\varphi$ consisting of triples of variables (which appear only positively). The formula $\varphi$ is a yes-instance if there is an assignment to the variables such that every triple contains at least one true variable and at least one false variable.

We shall construct a graph $G$ which admits a temporal assignment ${\lambda }^{\prime }:E(G)\to \{1,2\}$ satisfying all our demands if and only if $\varphi$ admits a satisfying assignment. Figure 4 may be of use to the reader in following the proof. Solid (resp. dashed) edges in bold are ones which are necessarily assigned $1$ (resp. $2$) in any temporal assignment ${\lambda }^{\prime }$ satisfying all demands.

We shall refer to the demand $(u,v,t)$ as a $t$-demand from $u$ to $v$. We begin with four special vertices $F,F^{\prime },T,T^{\prime }$, with $1$-demands from $F^{\prime }$ to $F$ and $T^{\prime }$ to $T$. Then, for each variable $x$ in $\varphi$, we introduce vertices $s_x,t_x,m_x$ and edges from each of these to each of $T,F$. We further introduce 1-demands from $s_x$ to each of $T,F$ (enforcing that both edges must be assigned time $1$) and 2-demands from each of $T^{\prime },F^{\prime }$ to $t_x$ (enforcing that both of $(T,t_x),(F,t_x)$ must be assigned time $2$). Lastly, we introduce 2-demands from $s_x$ to $m_x$ and from $m_x$ to $t_x$, which together with the previous constraints, guarantees that ${\lambda }^{\prime }(m_x,T)\ne {\lambda }^{\prime }(m_x,F)$.

Next, for each triple $c$ in $\varphi$, we create vertices $c$ and $c^{\prime }$ and a 1-demand between these, and connect the vertex $c$ to $m_x$ by an edge if $x$ appears in the triple $c$ and introduce a 2-demand from $c^{\prime }$ to $m_x$. We also introduce $2$-demands from each of $T$ and $F$ to $c$.

The intention is that assigning ${\lambda }^{\prime }(m_x,T)=1$ will correspond to an assignment of true to $x$ in $\varphi$, and assigning ${\lambda }^{\prime }(m_x,F)=1$ will correspond to an assignment of false to $x$ in $\varphi$. Suppose that some ${\lambda }^{\prime }$ satisfies all demands. Then the assignment in which variable $x$ is set to true if ${\lambda }^{\prime }(m_x,T)=1$ and false otherwise is a satisfying assignment of $\varphi$.

Suppose that $\varphi$ has a satisfying assignment $X$. Consider the temporal assignment ${\lambda }^{\prime }$ in which ${\lambda }^{\prime }(m_x,T)=1$ and ${\lambda }^{\prime }(m_x,F)=2$ if $x$ is true under $X$ and ${\lambda }^{\prime }(m_x,T)=2$ and ${\lambda }^{\prime }(m_x,F)=1$ otherwise (and all other values of ${\lambda }^{\prime }$ are as specified in Figure 4). Under ${\lambda }^{\prime }$, every clause $c$ is adjacent to some pair of vertices $m_x,m_y$ such that $x=\text{true}$ under $X$ and $y=\text{false}$ under $X$ – so the 2-demand from $T$ (resp. $F$) to $c$ can be routed through $m_x$ (resp. $m_y$). It is clear that ${\lambda }^{\prime }$ satisfies all other demands. $◀$

Our result for directed graphs requires a slightly different proof:

The reduction is again from Positive Not-All-Equal Exactly 3SAT. Given a formula $\varphi$, we construct a directed graph $G$ as follows: Then, for each variable $x$ in $\varphi$, we introduce six vertices $s_x,s_x^T,s_x^F,t_x,t_x^T,t_x^F$ and connect them as shown in Figure 5. Further, we introduce a vertex $c$ identified with each triple $c$ in $\varphi$, and create directed edges from $c$ to $s_x^T$ and from $c$ to $s_x^F$.

We now specify the demands for our instance; for each variable $x$, we have 2-demands from $s_x$ (resp. $s_x^T$, $s_x^F$) to $t_x$ (resp. $t_x^T,s_x^F$), and for each clause $c$ we have 2-demands from $c$ to each of $T$ and $F$. (All of our demands are 2-demands, and these are shown as red dashed arrows in Figure 5.) We let the constant function $\mathrm{𝟏}$ be the initial temporal assignment for our directed graph, and this concludes the construction of our ($\delta$-)DelayBetter instance (together with specifying $\delta =1$, if necessary).

Suppose ${\lambda }^{\prime }(s_x^T,T)=2$ for some $x$. Since all our demands are satisfied, we have that there must be a temporal path from $s_x^T$ to $t_x^T$ arriving at time 2. Such a path necessarily leaves at time 1 (since the two vertices are at distance 2). Consequently, ${\lambda }^{\prime }(s_x^T,s_x)=1$ and ${\lambda }^{\prime }(s_x,t_x^T)=2$. Similarly, we now must have that the 2-demand from $s_x$ to $t_x$ is routed through $t_x^F$, entailing that ${\lambda }^{\prime }(s_x,t_x^F)=1$ and ${\lambda }^{\prime }(t_x^F,t_x)=2$. Applying the same logic a third time, the 2-demand from $s_x^F$ to $t_x^F$ must be routed through $F$, and the desired claim follows. (The other direction is symmetric.) $\mathrm{⊲}$

Suppose that some ${\lambda }^{\prime }$ satisfies all demands. Consider the truth assignment in which a variable $x$ is set to true if ${\lambda }^{\prime }(s_x^T,T)=2$, and false otherwise. Suppose for contradiction that under this truth assignment, some triple $c$ is not satisfied. Then either: (a) all variables in $c$ are true under our truth assignment, and leveraging Claim 16, the vertex $c$ cannot reach the vertex $F$ by time $2$; or, (b), all variables in $c$ are false under our truth assignment, and there $c$ cannot reach the vertex $T$ by time $2$. In either case, some demand is not satisfied and we derive the desired contradiction.

Now suppose that there is some truth assignment satisfying $\varphi$. Consider the temporal assignment ${\lambda }^{\prime }$ in which:

• $\mathrm{■}$

  If $x\in c$ and $x$ is true (resp. false) under the assignment, then ${\lambda }^{\prime }(c,s_x^T)=1$ (resp. ${\lambda }^{\prime }(c,s_x^F)=1$), and

• $\mathrm{■}$

  If $x$ is true (resp. false) under the truth assignment, then ${\lambda }^{\prime }(s_x^T,T)=2$ (resp. ${\lambda }^{\prime }(s_x^F,F)=2$) and temporal assignments to other directed edges in each variable gadget being chosen consistently with the proof of Claim 16 to satisfy demands within the variable gadget, as shown in Figure 5.

• $\mathrm{■}$

  All other edges are assigned times arbitrarily.

Under ${\lambda }^{\prime }$, $c$ has a path to $T$ (resp. $F$) through $s_x^T$ (resp. $s_x^F$) if and only if $x\in c$ is assigned true (resp. false). It should be clear that ${\lambda }^{\prime }$ satisfies all other demands in our instance by construction, and the result follows. $◀$

Having shown that the instance being a tree yields tractability in Corollary 12, we consider the case of planar graphs - a well-studied superclass of trees.

Our reduction is from Cubic Bipartite Planar Edge Precoloring Extension (CBP-EPE). That problem asks, given an undirected graph $G$ (which is planar, bipartite, and cubic) and a precoloring of its edges $P:E(G)\to \{R,G,B,U\}$ (indicating red, green, blue, and uncolored edges respectively) whether there is a proper edge-coloring $C:E(G)\to \{R,G,B\}$ of $G$ such that $P(e)\in \{R,G,B\}⟹C(e)=P(e)$. Let $A,B$ be an arbitrary bipartition of $V(G)$, and fix an arbitrary order on $V(G)$ (so we may refer to the $i$th neighbor of some vertex).

We shall make use of the following hardness result: