On the Approximability of Time Disjoint Walks
Alexandre Bayen Jesse Goodman Eugene Vinitsky




On the Approximability of Time Disjoint Walks
    
Alexandre BayenUniversity of California, Berkeley. {bayen,evinitsky}@berkeley.edu.
Jesse GoodmanCornell University. jpmgoodman@cs.cornell.edu.
Eugene Vinitsky[1]
    December 30, 2023
======================================================================================================================================================================




We introduce the combinatorial optimization problem Time Disjoint Walks (TDW), which has applications in collision-free routing of discrete objects (e.g., autonomous vehicles) over a network. This problem takes as input a digraph G with positive integer arc lengths, and k pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a walk and delay for each demand so that no two trips occupy the same vertex at the same time, and so that a min-max or min-sum objective over the trip durations is realized.

We focus here on the min-sum variant of Time Disjoint Walks, although most of our results carry over to the min-max case. We restrict our study to various subclasses of DAGs, and observe that there is a sharp complexity boundary between Time Disjoint Walks on oriented stars and on oriented stars with the central vertex replaced by a path. In particular, we present a poly-time algorithm for min-sum and min-max TDW on the former, but show that min-sum TDW on the latter is NP-hard.

Our main hardness result is that for DAGs with max degree Δ≤3, min-sum Time Disjoint Walks is APX-hard. We present a natural approximation algorithm for the same class, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.







§ INTRODUCTION



 §.§ Related work

Disjoint Paths is a classic problem in combinatorial optimization that asks: given an undirected graph G, and k pairs of vertices, do there exist vertex-disjoint paths that connect each pair? This problem captures the general notion of connection without interference, and has subsequently received much attention due to its applicability in areas like VLSI design <cit.> and communication networks <cit.>.

These applications have motivated many variants of this basic problem. For example, one may choose the underlying graph to be undirected or directed, and the disjointness constraint to be over vertices or edges. As an optimization problem, one may consider the maximum number of pairs that can be connected with disjoint paths, the minimum number of rounds necessary to connect all pairs (where all paths in a round must be disjoint) <cit.>, or the shortest set of disjoint paths to connect all pairs (if all pairs can, in fact, be disjointly connected) <cit.>.

A few flavors of Disjoint Paths are tractable: for example, if k is fixed or G has bounded tree-width, then there exists a poly-time algorithm for finding vertex-disjoint paths on undirected graphs <cit.>. Many interesting variants of Disjoint Paths are, however, extremely difficult. Indeed, finding vertex-disjoint paths on undirected graphs is one of Karp's NP-complete problems <cit.>. Furthermore, nearly-tight hardness results are known for finding the maximum set of edge-disjoint paths in a directed graph with m edges: there exists an O(√(m))-approximation algorithm <cit.>, and it is NP-hard to approximate within a factor of m^1/2-ϵ, for any ϵ>0 <cit.>. For detailed surveys on the complexity landscape of Disjoint Paths variants, see <cit.>.



 §.§ Contributions

Despite the great variety of Disjoint Paths problems that have been considered in the literature, it appears that little attention has been given to variants that relax the disjointness constraint, even though many natural applications do not always require paths to be completely disjoint. Consider, for example, the application of safely routing a collection of fully autonomous (and obedient) vehicles through an otherwise empty road network. In such a situation, we can certainly prevent collisions by routing all vehicles on disjoint paths. However, it is not difficult to see that if we have full control over the vehicles, using disjoint paths is rarely necessary (and, in fact, can be highly suboptimal).

Applications of this flavor motivate a new variant of Disjoint Paths, which roughly asks: given a graph G and k pairs of vertices that each represent a trip demand, how should we assign a delay and a path to each trip so that (1) trips are completed as quickly as possible, and (2) no two trips collide (i.e., occupy the same location at the same time). While there are problems in the literature (that do not wield the name “Disjoint Paths”) that seemingly come close to capturing this goal, they exhibit some key differences. In particular, multicommodity flows over time <cit.> and job shop scheduling <cit.> seem, at first glance, very related to our problem. However, the former does not support “atomic” commodities (i.e., whose demand-satisfying flow must be unsplittable over the network and time), and the latter does not capture the flexibility of scheduling job operations over any appropriate walk in a network.

As such, we are motivated to formalize and study this new variant of Disjoint Paths that relaxes the classical disjointness constraint to a “time disjointness” constraint. In particular, our contributions are fourfold:


  * We introduce a natural variant of Disjoint Paths, which we call Time Disjoint Walks (TDW). To the best of our knowledge, this is the first simple model that captures the notion of collision-free routing of discrete objects over a shared network.


  * We give an intuitive sense for precisely when Time Disjoint Walks becomes hard, by showing that it can be exactly solved (under min-sum and min-max objectives) in poly-time on oriented stars, but is NP-hard (under the min-sum objective) on a slightly more expressive class.


  * We prove that min-sum Time Disjoint Walks is APX-hard, by providing an L-reduction from a variant of SAT. In fact, our reduction shows that this result holds even for directed acyclic graphs (DAGs) of max degree three (Δ≤ 3).


  * We describe an intuitive approximation algorithm for min-sum Time Disjoint Walks, and provide a tight analysis: we show that it achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs, and Θ(k) on DAGs and bounded-degree digraphs.




We formally introduce Time Disjoint Walks in <ref>. In <ref>, we present an exact poly-time algorithm for TDW on oriented stars, and show that min-sum TDW is NP-hard on a slightly more complex class. In <ref> we provide some useful definitions regarding approximation. In <ref> we prove our APX-hardness result. In <ref> we describe our approximation algorithm, and provide bounds on its performance. In <ref> we state our conclusions and present some open problems. A preliminary version of this paper appeared in <cit.>.



§ TIME DISJOINT WALKS




We must first mention a few preliminaries: given a, b∈, define [a,b]:={x∈| a≤ x ≤ b}, and for b∈, we write [b]:=[1,b]. Note that for b<1, [b]=∅. We assume directed graphs (digraphs) have no parallel arcs in the same direction, and for a digraph G, we let Δ denote its max total degree (indegree and outdegree contribute to a vertex's total degree). Given a digraph G:=(V,E), and u,v∈ V, we define a walk W from u to v in G as a tuple (w_1,w_2,…,w_l) of vertices such that w_1=u, w_l=v, and (w_i,w_i+1)∈ E for each i ∈ [l-1]. Note that a vertex may be repeated.

Given a digraph G with arc lengths λ:E→_≥1, and a walk W=(w_1,w_2,…,w_l) in G, we let |W|:= l denote the cardinality of the walk, and we define for every j∈[l] the length of the walk up to its j^th vertex as

    λ(W,j) := ∑_i∈[j-1]λ(w_i,w_i+1).

For convenience, we let λ(W) := λ(W,l) denote the total length of the walk, and if W is a path (i.e., no repeated vertices), we use λ(W,j) and λ(W,w_j) interchangeably. 

Finally, given delays d_1,d_2∈_≥0 and walks W_1,W_2 in G, we say that (d_1,W_1) and (d_2,W_2) are time disjoint if, intuitively, a small object traversing W_1 at constant speed after waiting d_1 units of time does not collide/interfere with a small object traversing W_2 at the same speed after waiting d_2 units of time. We consider walks that have not departed, and walks that have already ended, to no longer exist on the network (and thereby not occupy any vertices). Formally, we have: for every j_1∈[|W_1|],j_2∈[|W_2|] such that the j_1^th vertex of W_1 is equal to the j_2^th vertex of W_2,

    d_1 + λ(W_1,j_1)≠ d_2+λ(W_2,j_2).


We are now ready to formally define the problem examined in this paper:

 Let G:=(V,E) be a digraph, let λ:E→ℤ_≥1 define arc lengths, and let 𝒯:={(s_1,t_1),(s_2,t_2),…,(s_k,t_k)}⊆ V^2 define a set of demands across unique vertices. For each i∈[k], find a delay d_i∈ℤ_≥0 and walk W_i from s_i to t_i such that the tuples in {(d_i,W_i)| i∈[k]} are pairwise time disjoint, and such that ∑_i∈[k](d_i+λ(W_i)) or max_i∈[k](d_i+λ(W_i)) is minimized.[We assume G contains, for each (s_i,t_i), at least one walk connecting the two vertices.] We refer to the former as min-sum Time Disjoint Walks, and the latter as min-max Time Disjoint Walks.


We note that one can construct analogous problems by considering undirected graphs as input, edge lengths and delays that are real-valued, or a definition of time disjoint that requires large gaps between arrival times at common vertices (whereas the definition above simply requires a nonzero gap). We leave these variants to future work, noting that our primary goal in this paper is to study a basic flavor of this new combinatorial problem.

Furthermore, our selection of this variant is well-motivated by our original application of routing a collection of identical autonomous vehicles over an empty road network (which, for the sake of this futuristic application, we may assume was built specifically for these vehicles). In particular, we may (1) model the road network as a directed graph, (2) assume that all routed vehicles traverse their walk at the same constant velocity, (3) measure road lengths as the time necessary to traverse it at that velocity, and (4) assume that road lengths are integer multiples of the time length of each vehicle. Additionally, we may motivate our focus on the min-sum objective by the desire to find a socially optimal solution.

Finally, we emphasize the novelty of our time disjoint constraint by comparing it to the standard disjoint constraint used in classical variants of Disjoint Paths. In particular, observe that if we modify the definition of Time Disjoint Walks to use the latter constraint instead of the former, we arrive at the Shortest Disjoint Paths problem <cit.>. However, this constraint makes all the difference: given an instance of Time Disjoint Walks, it is often the case that a solution under the standard disjoint constraint is suboptimal if examined under the time disjoint constraint. Indeed, the optimal solution under the latter constraint may even include paths that repeat vertices - hence the name Time Disjoint Walks; see <ref>, part (i). On the other hand, it is easy to construct an instance of Shortest Disjoint Paths that admits an obvious optimal solution under the time disjoint constraint, but does not yield any solution at all under the classical disjoint constraint; see <ref>, part (ii).

These observations strongly suggest that there is no simple reduction, in either direction, between Time Disjoint Walks and Disjoint Paths. Furthermore, using time-expanded networks <cit.> to reduce Time Disjoint Walks into Disjoint Paths appears to offer little hope: such reductions will approximately square the size of the original graph, and many variants of Disjoint Paths are hard to approximate within m^1/2-ϵ, for any ϵ>0 <cit.>. Thus, an approximation algorithm for Disjoint Paths, applied to a transformed Time Disjoint Walks instance, would likely fail to perform better than a trivial approximation algorithm for Time Disjoint Walks. These observations highlight the novelty of our problem and results.



§ A COMPLEXITY BOUNDARY

In order to get an idea of the difficulty of Time Disjoint Walks, we show that min-sum TDW exhibits a sharp complexity boundary, in the sense that it is poly-time solvable on one subclass of DAGs, but becomes NP-hard if we make this class slightly more expressive. In particular, we consider the following two subclasses of DAGs:
 A digraph G is an oriented star if it is composed of a central vertex with any number of leaves attached by directed edges.

Equivalently, an oriented star on n vertices is simply the complete bipartite graph K_1,n-1 with some orientation applied to the edges.

A digraph G is a runway if it is composed of a central directed path with any number of leaves attached (anywhere along the path) by directed edges.


One may think of a runway as an oriented star with the central vertex replaced by a directed path, or as a caterpillar graph with an orientation applied to the edges so as to produce a central directed path.



 §.§ Time Disjoint Walks on oriented stars in polynomial time

We present poly-time <ref> for Time Disjoint Walks on oriented stars, and show that it in fact optimally solves both min-sum and min-max TDW. The main idea in this algorithm and its analysis is that each trip i∈[k] is allocated a unique time slot during which it is “allowed” to utilize the central vertex of the oriented star (i.e., the only vertex it will share with other paths). We often toggle between reasoning about the delay assigned to a trip and the time slot (on the central vertex) assigned to a trip - note that these two notions are essentially equivalent, and that it only makes sense to assign a time slot to a trip i if the time slot has value at least equal to the length of the first segment of trip i (i.e., from the source to the central vertex).

It may help to visualize this algorithm as taking a histogram over _≥0 of arrival times of each trip at the central vertex (under 0 delay), and drawing an arrow from each element (trip) of this histogram forward (i.e., to a number that is no smaller) to a distinct slot (element of _≥0) during which that trip will pass through the central vertex. The length of this arrow is the delay assigned to that trip.





Note that for brevity, we have excluded from <ref> the pseudocode to check that G is indeed an oriented star with central vertex 𝖼𝖾𝗇𝗍𝗋𝖺𝗅_𝗏𝖾𝗋𝗍𝖾𝗑(G), and the pseudocode to handle the case where some s_i or t_i is the central vertex (for such an i, W_i should instead be set to (s_i,t_i), and one of a_i,b_i should be set to 0, according to whether s_i or t_i is the central vertex). Also, we allow ties encountered when setting i^∗ to be broken arbitrarily.[In our analyses that follow, we also assume all ties are broken arbitrarily.] It is clear that the algorithm runs in polynomial time, and that its output is always feasible: i^∗ is always defined (due to 𝗆𝗂𝗇_𝗎𝗌𝖾𝖿𝗎𝗅_𝗌𝗅𝗈𝗍), all delays are nonnegative (by definition of i^∗), and collisions - which can only occur at the central vertex - are avoided (due to 𝗈𝖼𝖼𝗎𝗉𝗂𝖾𝖽_𝗌𝗅𝗈𝗍𝗌). We now prove that <ref> optimally solves both min-sum and min-max TDW on oriented stars.


<ref> is an exact poly-time algorithm for min-sum Time Disjoint Walks on oriented stars.


Let (G,λ,𝒯) be a TDW instance, where G is an oriented star with central vertex x. Let (d_1,W_1),…,(d_k,W_k) be the solution outputted by <ref>, and let (d_1^∗,W_1^∗),…,(d_k^∗,W_k^∗) be an optimal solution under the min-sum objective. For each i∈[k], define a_i=a_i^∗=λ(W_i,x), b_i=b_i^∗=λ(W_i)-λ(W_i,x), and y_i:= d_i+a_i, y_i^∗ := d_i^∗ + a_i^∗. Let S:={y_i| i∈[k]} denote the time slots during which the central vertex is busy under our algorithm's solution, and let S^∗:={y_i^∗| i∈[k]} denote the same notion under a min-sum optimal solution. By the time-disjointness constraint of TDW, we know that |S|=|S^∗|=k. Recall that the min-sum objective sums delays and walk lengths over all trips, and that a unique walk satisfies each demand in an oriented star. Using these, we know that our solution will have the same min-sum cost as the optimal min-sum cost if S=S^∗.

Assume for contradiction that S≠ S^∗. Let β be the smallest element in the symmetric difference of S and S^∗. If β∈ S∖ S^∗, then define T:={i∈[k]| y_i≤β} to contain the trips that our algorithm schedules on a slot no later than β. Now, note that there must exist some i∈ T such that y_i^∗>β, since β is the smallest element at which S,S^∗ differ, and i≠ j∈ T y_i^∗≠ y_j^∗, by the time-disjointness constraint of TDW. But this means that we can reset d_i^∗ to β-a_i^∗=β-a_i (which is guaranteed to be nonnegative, by our algorithm description) and obtain a valid solution to this TDW instance that costs less than the optimal, which is a contradiction.

If β∈ S^∗∖ S, then by almost identical reasoning as above, we know that if we define T^∗ := {i∈[k]| y_i^∗≤β}, then there must exist some i∈ T^∗ such that y_i>β and β-a_i is nonnegative. But this would mean that during the iteration of the main while loop at which i gets assigned a delay, β≥𝗆𝗂𝗇_𝗎𝗌𝖾𝖿𝗎𝗅_𝗌𝗅𝗈𝗍 and β∉𝗈𝖼𝖼𝗎𝗉𝗂𝖾𝖽_𝗌𝗅𝗈𝗍𝗌 and β<y_i, yet 𝗌𝗅𝗈𝗍 is set to y_i, which contradicts the definition of the min function (in our algorithm description). This completes the proof.



<ref> is an exact poly-time algorithm for min-max Time Disjoint Walks on oriented stars.


First, define the same variables as in the proof to <ref>, replacing the words “min-sum” with “min-max” as necessary. Our goal here will be to find a sequence of consecutive slots Q:=[q_start,q_end]⊆_≥0 with the following properties:


  * Q⊆ S.

  * If we define I_Q:={i∈[k]| d_i+a_i∈ Q}, then A_Q:={a_i | i∈ I_Q}⊆ Q.

  * If we define γ∈ I_Q such that d_γ+a_γ=q_end, then d_γ+a_γ+b_γ≥ d_j+a_j+b_j, for all j∈[k].

  * For all j∈ I_Q, we have b_j≥ b_γ.

Given such a Q, the first two properties ensure |I_Q|=|Q| and that these |Q| trips (indexed by I_Q), under 0 delay, would arrive at the central vertex at some time in Q. Thus, the min-max optimal solution (and, in general, any feasible solution) to the TDW instance must set, for some h∈ I_Q, d_h^∗+a_h^∗≥ q_end (otherwise, because delays are nonnegative, the pigeonhole principle shows that the optimal solution schedules two trips in I_Q to share a slot in Q). The third and fourth property ensure that for this same h∈ I_Q, b_h^∗=b_h≥ b_γ and thus d_h^∗+a_h^∗+b_h^∗≥ q_end+b_γ= d_γ+a_γ+b_γ≥ d_j+a_j+b_j, for all j∈[k]. This shows that the max trip time in any solution to the TDW instance is at least the max trip time on the solution produced by our algorithm, proving that our algorithm is optimal under the min-max constraint. We construct such a Q, below.

First, define γ := _i∈[k](d_i+a_i+b_i), and set q_end:=d_γ+a_γ. Define 𝖺𝗇𝖼𝗁𝗈𝗋:=γ, 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍:= q_end, and repeat the following while a_𝖺𝗇𝖼𝗁𝗈𝗋≠𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍: decrement 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍, let α∈[k] be the index such that d_α+a_α=𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍, and reset 𝖺𝗇𝖼𝗁𝗈𝗋 to _i∈{𝖺𝗇𝖼𝗁𝗈𝗋,α}(a_i). Finally, after quitting the loop, set q_start:=a_𝖺𝗇𝖼𝗁𝗈𝗋, and set Q:=[q_start,q_end].

We must argue that the above process is well-defined (in particular, that α is always defined and that the process terminates) and that Q has all the properties we desire. To see the former, note that if we reach some 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍 such that there is no α∈[k] with d_α+a_α=𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍, then the description of <ref> is contradicted, because when this algorithm is picking a delay for trip 𝖺𝗇𝖼𝗁𝗈𝗋, the above analysis suggests that it picks a delay larger than 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍-a_𝖺𝗇𝖼𝗁𝗈𝗋, even though 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍≥𝗆𝗂𝗇_𝗎𝗌𝖾𝖿𝗎𝗅_𝗌𝗅𝗈𝗍 and 𝖼𝗎𝗋𝗋_𝗌𝗅𝗈𝗍∉𝗈𝖼𝖼𝗎𝗉𝗂𝖾𝖽_𝗌𝗅𝗈𝗍𝗌. Thus, α is always defined, and so each iteration of the loop is well defined. Because k is finite, the process must end.

Now, note that the well-definedness of α and the stopping condition of the loop also shows that Q:=[q_start,q_end]⊆ S. Next, A_Q⊆ Q by the setting of 𝖺𝗇𝖼𝗁𝗈𝗋 and q_start. The third desirable property of Q trivially holds by selection of γ. All that remains is to show that for all j∈ I_Q, b_j≥ b_γ. To see this, consider any j∈ I_Q∖{γ} and the value of 𝖺𝗇𝖼𝗁𝗈𝗋 during the Q-creation process right after α is set to j (i.e., before 𝖺𝗇𝖼𝗁𝗈𝗋 is potentially reset). Observe that d_j+a_j < d_𝖺𝗇𝖼𝗁𝗈𝗋+a_𝖺𝗇𝖼𝗁𝗈𝗋 and that a_j,a_𝖺𝗇𝖼𝗁𝗈𝗋≤ d_j+a_j by the while loop condition. Thus, by description of <ref>, we must have that b_𝖺𝗇𝖼𝗁𝗈𝗋≤ b_j, for otherwise our algorithm would have preferred to set d_𝖺𝗇𝖼𝗁𝗈𝗋 to d_j+a_j-a_𝖺𝗇𝖼𝗁𝗈𝗋. Since 𝖺𝗇𝖼𝗁𝗈𝗋 is initialized to γ, we have we have b_γ≤ b_j, ∀ j∈ I_Q.





 §.§ Min-sum Time Disjoint Walks on runways is NP-hard

We will reduce from min-sum coloring on interval graphs. We define this problem and state its NP-hardness,[Whenever we refer to an optimization problem as NP-hard, we mean the natural corresponding decision problem.] below.


Given an undirected graph G, find a coloring c:V(G)→_≥1 such that adjacent vertices get different colors and ∑_v∈ Vc(v) is minimized.


An undirected graph G:=(V,E) such that each v∈ V may be identified with an interval S_v:=[v_start,v_end]⊆ℝ such that xy∈ E S_x∩ S_y≠∅.

Min-sum coloring of interval graphs is NP-hard, even for intervals taken over .

We are now ready to prove our result.

Min-sum Time Disjoint Walks on runways is NP-hard.


Given an interval graph G and a parameter q (for which we ask whether there is a coloring of G whose sum adds up to at most q), we efficiently construct a TDW instance (G^',λ,𝒯) and parameter q^' such that G admits a solution of (sum-)cost at most q if and only if (G^',λ,𝒯) admits a solution of (sum-)cost at most q^'.

Given an interval graph G and parameter q, let {S_v:=[v_start,v_end]⊆| v ∈ V} denote its interval representation, let P=⋃_v∈ V{v_start,v_end} denote all the interval endpoints, and construct a bijection π:P→[|P|] that orders the endpoints such that p_1≤ p_2∈ Pπ(p_1)≤π(p_2). Clearly, we may equivalently represent G as the intervals {S^'_v:=[π(v_start),π(v_end)]⊆_≥1| v∈ V}.

Now, construct a runway digraph G^' with arc lengths λ:E(G^')→_≥1 as follows: add to V(G^') the vertices x_1,x_2,…,x_|P|; turn these vertices into a directed path from x_1 to x_|P| by adding the appropriate arcs to E(G^'); and let λ assign a length of 1 to each such arc. Then, for each v∈ V(G): add to V(G^') two distinct nodes v_L,v_R; add to E(G^') two distinct arcs (v_L,x_π(v_start)) and (x_π(v_end),v_R); and set λ(v_L,x_π(v_start)):=π(v_start) and λ(x_π(v_end),v_R):=|P|+1-π(v_end). Finally, define the set of demands 𝒯 as {(v_L,v_R)| v∈ V(G)}, and let q^':=|V(G)|·|P|+q. This completes the reduction.

To prove the correctness of our reduction, we first make several key observations. By construction, we have that for any i∈[|P|], W_v includes the vertex x_i iff i∈ S_v^'. Furthermore, for any i∈[|P|] such that x_i is hit by W_v, we have λ(W_v,x_i)=i. Thus, we see that two walks W_u,W_v share a vertex x_i iff S_u^'∩ S_v^'≠∅ iff uv∈ E(G), and that for any such shared vertex x, λ(W_u,x)=λ(W_v,x). Finally, note that for any v∈ V(G), λ(W_v)=|P|+1.

Consider the case where G has a solution of sum-cost at most q. Let c:V(G)→_≥1 be a proper coloring that achieves this sum. We can construct a solution {(d_v,W_v)| v∈ V(G)} to TDW instance (G^',λ,𝒯), where (d_v,W_v) are the delay and walk for demand (v_L,v_R), as follows: set d_v=c(v)-1, and let W_v be the unique walk from v_L to v_R in G^'. By our key observations, we have ∑_v∈ V(G)(d_v+λ(W_v))=∑_v∈ V(G)(c(v)-1)+|V(G)|·(|P|+1)≤ q+|V(G)|·|P|=q^', and we know that if two walks W_u,W_v share a vertex x, then c(u)≠ c(v) (by the validity of c), and so d_u≠ d_v. Thus, d_u+λ(W_u,x)≠ d_v+λ(W_v,x), and so this solution to the TDW instance is valid.

Consider the case where (G^',λ,𝒯) has a solution of sum-cost at most q^'. Let {(d_v,W_v)| v∈ V(G)} be such a solution. We construct a solution c:V(G)→_≥1 to min-sum coloring instance G by setting c(v):=d_v+1. By our key observations, we know that uv∈ V(G) W_u,W_v share some vertex x where λ(W_u,x)=λ(W_v,x); thus, by the validity of our TDW solution, we know that d_u≠ d_v, which means c(u)≠ c(v). Thus, c is a valid coloring of V(G), and ∑_v∈ V(G)c(v)=∑_v∈ V(G)(d_v+1)≤ q^' - (|P|+1)·|V(G)| +|V(G)|=q. Thus, our reduction is correct, and it can clearly be done in poly time.





§ APPROXIMATION PRELIMINARIES


Given an optimization problem 𝒫, we let I_𝒫 denote the instances of 𝒫, SOL_𝒫 map each x∈ I_𝒫 to a set of feasible solutions, and let c_𝒫 assign a real cost to each pair (x,y) where x∈ I_𝒫 and y∈ SOL_𝒫(x). For x∈ I_𝒫, we let OPT_𝒫(x) := min_y^∗∈ SOL_𝒫(x)c_𝒫(x,y^∗) if 𝒫 is a minimization problem, and OPT_𝒫(x) := max_y^∗∈ SOL_𝒫(x)c_𝒫(x,y^∗) otherwise.

If 𝒜 is a polynomial time algorithm with input x∈ I_𝒫 and output y∈ SOL_𝒫(x), we say that 𝒜 is a ρ-approximation algorithm, or has approximation ratio ρ, if 𝒫 is a minimization problem and c_𝒫(x,𝒜(x))/OPT_𝒫(x)≤ρ, or 𝒫 is a maximization problem and OPT_𝒫(x)/c_𝒫(x,𝒜(x))≤ρ, for all x∈ I_𝒫. Note that ρ≥1.

The class APX contains all optimization problems that admit a ρ-approximation algorithm, for some constant ρ>1. An optimization problem is said to be APX-hard if every problem in APX can be reduced to it through an approximation-preserving reduction. One reduction of this type is the L-reduction:

An L-reduction from an optimization problem 𝒫 to an optimization problem 𝒬, denoted 𝒫≤_L𝒬, is a tuple (f,g,α,β), where:


  * For each x∈ I_𝒫, f(x)∈ I_𝒬 and can be computed in polynomial time.

  * For each y∈ SOL_𝒬(f(x)), g(x,y)∈ SOL_𝒫(x) and can be computed in polynomial time.

  * α is a positive real constant such that for each x∈ I_𝒫,

    OPT_𝒬(f(x))≤α· OPT_𝒫(x).


  * β is a positive real constant such that for each x∈ I_𝒫,y∈ SOL_𝒬(f(x)),

    |OPT_𝒫(x)-c_𝒫(x,g(x,y))|≤β·|OPT_𝒬(f(x))-c_𝒬(f(x),y)|.



If a problem is APX-hard, it is NP-hard to ρ-approximate for some constant ρ>1; thus, showing APX-hardness is strictly stronger than showing NP-hardness. To show APX-hardness, one can simply L-reduce from a known APX-hard problem. We refer the reader to <cit.> for a good reference on approximation.



§ HARDNESS OF APPROXIMATION

To show the hardness of min-sum TDW on bounded-degree DAGs, we show an L-reduction from MAX-E2SAT(3), which is known to be APX-hard <cit.>. We remind the reader of the definition, below, and then proceed with our proof.

 Let ϕ be a CNF formula in which (i) each clause contains exactly two literals on distinct variables, and (ii) each variable appears in at most three clauses. Find a truth assignment to the variables in ϕ that maximizes the number of satisfied clauses.


Min-sum Time Disjoint Walks is APX-hard, even for DAGs with Δ≤3.


We let 𝒫:= MAX-E2SAT(3), 𝒬:= TDW with instances restricted to those containing DAGs with Δ≤3, and show that 𝒫≤_L𝒬. Below, we describe our L-reduction (f,g,α,β).

Description of f: Given an instance ϕ∈ I_𝒫 with n variables and m clauses, we let X:={x_1,…,x_n} refer to its variables and 𝒞:={C_1,…,C_m} refer to its clauses. We let L:={x_1,…,x_n,x_1,…,x_n} refer to its literals. For convenience, we define e:L→ X that extracts the variable from a given literal; i.e., e(x_i)=e(x_i)=x_i. We label the literals in clause C_j as l^1_j,l^2_j. For each l∈ L, we let S_l := {l^a_j| a∈[2],j∈[m],l^a_j=l} capture all occurrences of literal l in ϕ. Finally, for each l∈ L, we define an arbitrary bijection π_l:S_l→[|S_l|] to induce an ordering on S_l. We will let π_l^-1 denote its inverse: i.e., π_l^-1(1) is the first element in S_l in the order induced by π_l.

We may now describe f, which constructs an instance (G,λ,𝒯)∈ I_𝒬 from ϕ. We start with the construction of G (see <ref>), which closely follows the standard proof of NP-hardness for Disjoint Paths: for each clause C_j=(l_j^1 l_j^2) in ϕ, we create a new clause gadget and add it to G. That is, for each clause C_j, we add the following vertex and arc set to our construction:

    V_C_j   := {c_j^s,l_j^1,l_j^2,l_j^1^',l_j^2^',c_j^t}
    
    E_C_j   := {(c_j^s,l_j^1),(c_j^s,l_j^2),(l_j^1,l_j^1^'),(l_j^2,l_j^2^'),(l_j^1^',c_j^t),(l_j^2^',c_j^t)}


Next, for each x_i∈ X, we add an interleaving variable gadget as follows: first, we add two vertices x_i^s,x_i^t to V(G). Then, we wish to create exactly two directed paths (walks), W_x_i^+,W_x_i^-, from x_i^s to x_i^t: we want W_x_i^+ to travel through all vertices corresponding to positive literals of x_i, and W_x_i^- to travel through all vertices corresponding to negative literals of x_i. Formally, for each l∈{x_i,x_i}, we create a path from x_i^s to x_i^t as follows. First, if |S_l|=0, we add arc (x_i^s,x_i^t) to E(G). Otherwise, we add arcs (x_i^s,π_l^-1(1)) and ((π_l^-1(|S_l|))^',x_i^t) to E(G), and then for each j∈[|S_l|-1], we add arc ((π_l^-1(j))^',π_l^-1(j+1)). Note that the prime symbols are merely labels, and are used in our construction to ensure that the max degree of G remains at most three.



This completes our construction of G. We now define a set of n+m demands, where each corresponds to a variable or a clause:

    𝒯 := {(x_i^s,x_i^t)| i∈[n]}∪{(c_j^s,c_j^t)| j∈[m]}


Finally, we must define arc lengths λ:E→ℤ_≥1. We will do this in a way that for each j∈[m],a∈[2], we have λ(W_c_j^s,l_j^a)=λ(W_x^s_i,l_j^a), where W_c_j^s is the unique walk in G from c_j^s to l_j^a, and W_x_i^s is the unique walk in G from x_i^s=e(l_j^a)^s to l_j^a. Call this property (∗). To facilitate our analysis, we will also want every demand-satisfying path in G to have the same length.

Since ϕ is an instance of MAX-E2SAT(3), we know that for each i∈[n], each of the two paths between x_i^s and x_i^t passes through at most 3 clause gadgets. Thus, by our construction, each such path includes at most 7 arcs, and any path from a variable x_i^s to some literal l_j^a with x_i=e(l_j^a) can use at most 5 arcs. Thus, we can successfully force each demand-satisfying path in G to have length 7 while maintaining property (∗) by defining λ:E→ℤ_≥1 as follows, completing our construction of (G,λ,𝒯)∈ I_𝒬:

    λ(u,v):=
    1,   if (u,v)=(l_j^a,l_j^a^'), j∈[m],a∈[2]; or
       if (u,v)=(x_i^s,l_j^a),i∈[n],j∈[m],a∈[2]; or
       if (u,v)=(l_h^a^',l_j^b),h,j∈[m], a,b∈[2];
    
    7,   if (u,v)=(x_i^s,x_i^t),i∈[n]
    
    7-2|S_l|,   if (u,v)=(l_j^a^',x_i^t),j∈[m],a∈[2],i∈[n],l_j^a=l
    
    2π_l(l_j^a)-1,   if (u,v)=(c_j^s,l_j^a),j∈[m],a∈[2],l_j^a=l
    
    7-1-λ(c_j^s,l_j^a),   if (u,v)=(l_j^a^',c_j^t),j∈[m],a∈[2]


Description of g: Given a solution y∈ SOL_𝒬(f(ϕ)), we construct a solution g(ϕ,y)∈ SOL_𝒫(ϕ) through two consecutive transformations: z, followed by q. That is, we will define transformations z and q such that g is the composition g(ϕ,y) := q(ϕ,z(y)).

We define z to transform solution y into another solution y^'∈ SOL_𝒬(f(ϕ)) such that c_𝒬(f(ϕ),y^')≤ c_𝒬(f(ϕ),y) and such that y^' assigns 0 delay to demands associated with interleaving variable gadgets. To accomplish this, recall that y={(d_1,W_1),…,(d_n+m,W_n+m)}, by definition of SOL_𝒬. Without loss of generality, we may assume tuples indexed with [n] correspond to demands on interleaving variable gadgets, and tuples indexed with [n+m]∖[n] correspond to demands on clause gadgets.

Now, while there exists some i∈[n] such that d_i>0 (and thus d_i≥1), we perform the following modification on y: first, we reset W_i to be the path traveling through at most one clause gadget - the positive or negative path must have this property, because each variable appears in ϕ at most three times, by definition of MAX-E2SAT(3). Now, reset d_i to 0. If W_i shares a vertex with another walk W_j, we know j∈[n+m]∖[n], by construction of G. In this case, reset d_j to 1 if and only if d_j is currently 0. By construction of λ, the walks remain time disjoint and the cost of the solution does not increase.

In the second transformation, q, we transform modified solution y^' into an assignment (A:X→{T,F})∈ SOL_𝒫(ϕ) as follows: for each i∈[n], set A(x_i)=T if and only if W_x_i, the walk from x_i^s to x_i^t, takes the negative literal path.

Valid value for α: We will show that for α=29, OPT_𝒬(f(ϕ))≤α· OPT_𝒫(ϕ). To see this, we make two observations. First observation: if A:X→{T,F} is a truth assignment for ϕ, then we can construct a solution to f(ϕ) as follows: for each i∈[n], connect demand (x_i^s,x_i^t) using the negative literal path if A(x_i)=T, and the positive literal path if A(x_i)=F. Either way, assign a delay of 0. Then, for each j∈[m] where clause C_j is satisfied by assignment A, connect demand (c_j^s,c_j^t) using a walk that goes through a literal that evaluates to true under A. Assign a delay of 0 to this demand. For each clause C_j that isn't satisfied by A, select an arbitrary walk to complete the corresponding demand (c_j^s,c_j^t). Assign a delay of 1 to this demand. It is clear that this is a valid solution to f(ϕ). Furthermore, the cost of our solution is 7(n+m)+U(A,ϕ), where U(A,ϕ) is the number of clauses in ϕ unsatisfied by A. Second observation: by linearity of expectation, if ϕ is an instance of MAX-E2SAT(3), then there must exist an assignment A:X(ϕ)→{T,F} that satisfies at least 3/4 of the clauses. 

We may now prove the desired inequality for α=29. From our first observation and the fact that n≤ 2m (since each of the m clauses has 2 literals),

    ineq]eq:opt-ineq-lemma
    OPT_𝒬(f(ϕ)) ≤ 7(n+m) + (m-OPT_𝒫(ϕ))≤ 22m-OPT_𝒫(ϕ).

Now, by our second observation, we know OPT_𝒫(ϕ)≥ 3m/4. Thus, we have:

    OPT_𝒬(f(ϕ)) ≤ 22·(4/3)· OPT_𝒫(ϕ)-OPT_𝒫(ϕ)≤ 29· OPT_𝒫(ϕ).


Valid value for β: We will show that for β=1 and any y∈ SOL_𝒬(f(ϕ)), (OPT_𝒫(ϕ)-c_𝒫(ϕ,g(ϕ,y)))≤β·(c_𝒬(f(ϕ),y)-OPT_𝒬(f(ϕ))), as required. As a first step, we recall that transformations z,q define g, and let γ denote the number of clause gadget demands assigned a delay of 0 by solution z(y) to f(ϕ). We make the following crucial claim:

    ineq]eq:crucial-claim
    c_𝒫(ϕ,g(ϕ,y)):=c_𝒫(ϕ,q(ϕ,z(y))) ≥γ.

To see this, note the following: by construction, z(y) is a valid solution to f(ϕ). Thus, if z(y) assigns clause gadget demand (c_j^s,c_j^t) a delay d_j=0 and walk W_j that passes through literal l, then l is a positive literal if and only if the walk selected for the interleaving variable gadget demand (x_i^s,x_i^t) (where x_i=e(l)) does not travel through the positive literals of x_i. By definition of q, this occurs if and only if g(ϕ,y) assigns true to x_i. Thus, a clause gadget demand given 0 delay by z(y) corresponds to a clause in ϕ satisfied by g(ϕ,y), thus proving <ref>.

Next, by definition of γ and z, we have:

    ineq]eq:gamma-z
    7(n+m)+(m-γ)≤ c_𝒬(f(ϕ),z(y))≤ c_𝒬(f(ϕ),y).

Combining <ref>, we get:

    ineq]eq:super-ineq
    c_𝒫(ϕ,g(ϕ,y))≥γ≥ 7n+8m-c_𝒬(f(ϕ),y).

Finally, <ref> give us:

    OPT_𝒫(ϕ)-c_𝒫(ϕ,g(ϕ,y))    ≤(7n+8m-OPT_𝒬(f(ϕ)))-(7n+8m-c_𝒬(f(ϕ),y))
    
       =β·(c_𝒬(f(ϕ),y)-OPT_𝒬(f(ϕ))),

for β=1, as desired. This completes the proof.


It is straightforward to tweak the above construction and analysis to show that min-max Time Disjoint Walks is NP-hard on DAGs with Δ≤ 3.




§ APPROXIMATION ALGORITHM



 §.§ Algorithm

We present <ref>, which approximates TDW by finding shortest paths to satisfy each demand, and then greedily assigning delays to each trip (with priority given to shorter trips). To simplify notation, we assume that the inputted terminal pairs are ordered by nondecreasing shortest path length (if not, we may simply sort the indices after finding the shortest demand-satisfying paths). The algorithm clearly runs in polynomial time, and the 𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒 variables ensure the feasibility of its output. Next, we briefly note the following easy bound:





prop]prop:very-easy-bound
<ref> has an approximation ratio of O(k) for min-sum Time Disjoint Walks on general digraphs.


Let x:=(G,λ,𝒯)∈ I_TDW, and let 𝒜(x)∈ SOL_TDW be the output of <ref> on x. First, we show by induction that for each i∈[k],

    d_i≤2∑_h∈[i-1]λ(W_h).

For the base case i=1, note that 𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i=∅ and so d_i = 0. For i>1, first observe that by definition of 𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒, we have d_i≤1+max_h∈[i-1](d_h+λ(W_h)). Thus,

    d_i≤    1+max_h∈[i-1](2∑_h^'∈[h-1]λ(W_h^')+λ(W_h)) *(induction hypothesis)
    ≤    1+2∑_h^'∈[i-2]λ(W_h^') + λ(W_i-1) *(pick h=i-1)
    ≤    2∑_h^'∈[i-1]λ(W_h^'), *(trips have length ≥ 1)

completing the induction. Now, recallling that our algorithm uses the shortest paths to satisfy each demand, and that it assigns delays to shorter paths first, we can bound the approximation ratio as follows:

    ρ≤c_TDW(x,𝒜(x))/OPT_TDW(x)   ≤∑_i∈[k](d_i+λ(W_i))/∑_i∈[k]λ(W_i)≤ 1 + 2∑_i∈[k]∑_h∈[i-1]λ(W_h)/∑_i∈[k]λ(W_i)
       ≤ 1 + 2k∑_i∈[k]λ(W_i)/∑_i∈[k]λ(W_i) = O(k).



It is straightforward to tweak the above analysis to show that for min-max Time Disjoint Walks, <ref> has an approximation ratio of O(k) on general digraphs.





 §.§ Analysis on bounded-degree DAGs

We now show that our algorithm is able to achieve a better approximation ratio on bounded-degree DAGs. In what follows, we call a directed graph a “(2,l)-in-tree” if it is a perfect binary tree of depth l, in which every arc points toward the root. Analogously, a “(2,l)-out-tree” is a perfect binary tree of depth l, in which every arc points away from the root.


<ref> achieves an approximation ratio of Θ(k/log k) for min-sum Time Disjoint Walks on bounded-degree DAGs.


Upper bound:
Let x:=(G,λ,𝒯)∈ I_TDW such that G is a bounded-degree DAG. Let 𝒜(x)∈ SOL_TDW be the output of <ref> on x. We may assume Δ>1, because otherwise it is straightforward to show 𝒜(x) is optimal. In what follows, we will justify the following string of inequalities that proves the upper bound:

    ρ≤c_TDW(x,𝒜(x))/OPT_TDW(x)   ≤∑_i∈[k](d_i+λ(W_i))/∑_i∈[k]λ(W_i)ineq]eq:FIRST
       ≤1+d_i^∗/λ(W_i^∗), i^∗:=_i∈[k](d_i/λ(W_i))ineq]eq:SECOND
       ≤1+O(1)·d_i^∗/log d_i^∗ineq]eq:THIRD
       ≤ 1+O(1)·k/log k=O(k/log k).ineq]eq:FOURTH

<Ref> is clear, because our algorithm takes the shortest path to satisfy each demand. <Ref> follows (by induction) from the following general observation: given d_1,d_2∈ℤ_≥0 and λ_1,λ_2∈ℤ_≥1, observe d_1/λ_1≤ d_2/λ_2 (d_1+d_2)/(λ_1+λ_2)≤ d_2/λ_2, and thus (d_1+d_2)/(λ_1+λ_2)≤max(d_1/λ_1,d_2/λ_2).

To show <ref>, we need two observations. We first observe that for each i∈[k]:

    d_i≤|𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i|≤|{h∈[i-1]| W_h∩ W_i≠∅}|=:μ_i

To see this, suppose for contradiction that there exists some h∈[i-1] with W_h∩ W_i≠∅ and |𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i,h| > 1. Then, by definition of 𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒, there exist vertices u,v∈ W_h∩ W_i and delays δ_u≠δ_v∈ℤ_≥0 such that:

    δ_u+λ(W_i,u)   =d_h+λ(W_h,u),
    δ_v+λ(W_i,v)   =d_h+λ(W_h,v),
    λ(W_h,u)
    -λ(W_h,v)
       =λ(W_i,u)-
    λ(W_i,v)
    +(δ_u-δ_v),

where the last equality follows from the first two. But because δ_u≠δ_v, this implies that the length of the path that W_h and W_i use to travel between u and v is not the same. Because G is a DAG, W_h and W_i must visit u and v in the same order, implying that one of these walks is not taking the shortest path from u to v, which contradicts the definition of the algorithm. Because |𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i,h|=0 if W_h∩ W_i=∅, we have d_i≤μ_i.

Next, we observe that:

    μ_i≤min(Δ^4λ(W_i),k).

Showing μ_i≤ k is trivial, by definition of μ_i and because i∈[k]. To show μ_i≤Δ^4λ(W_i), first note that in a digraph with max degree Δ, the number of paths that (i) have z arcs, (ii) start at distinct vertices, and (iii) all end at a common vertex, is upper bounded by Δ^z (this is easy to show by induction on z). Thus, the number of paths with ≤ z arcs, in addition to properties (ii) and (iii), is upper bounded by ∑_l=0^zΔ^l≤Δ^z+1, for Δ>1. Call this lemma (∗).

Now, note that for each h∈[i-1] we may consider each W_h to terminate once it first hits a vertex in W_i (i.e., cut off all vertices that are hit afterwards) without changing the value of μ_i. Now, recall the following facts about our problem and algorithm: (I) each inputted demand has a unique source; (II) each edge in our digraph has length ≥1; (III) for all h∈[i-1], λ(W_h)≤λ(W_i). Thus, by (III) and lemma (∗), each vertex in W_i can be hit by at most Δ^λ(W_i)+1 walks in {W_1,…,W_i-1}. Furthermore, (II) tells us that the number of vertices in W_i is no more than λ(W_i)+1. Thus, recalling that Δ>1, and that no demands have the same source and destination, and (II), we see that

    μ_i ≤ (λ(W_i)+1)Δ^λ(W_i)+1≤Δ^2(λ(W_i)+1)≤Δ^4λ(W_i),

as desired. We now note that we may assume d_i is greater than any constant (otherwise, <ref> automatically proves a constant approximation ratio, completing the proof). Thus, from this and the above observations, we have log(d_i)≤ 4λ(W_i)log(Δ). This proves <ref>, because our graph has bounded degree.

<Ref> is not difficult: as stated above, we will always have d_i≤ k, and we may always assume d_i≥ 3. Basic calculus shows the function x/log x increases over x≥3.

Lower bound: We show ∀ l∈_≥1,k:=2^l, ∃ (G_k,λ_k,𝒯_k)∈ I_TDW such that G_k is a bounded-degree DAG and <ref> achieves an approximation ratio of Ω(k/log k). Construct G_k by taking a (2,l)-in-tree A_S and a (2,l)-out-tree A_T. Draw an arc from the root of the former to the root of the latter. Then, arbitrarily pair each leaf (source) in A_S with a unique leaf (destination) in A_T. For each such pair, draw an arc from source to destination (called a “bypass arc”), and add a demand to 𝒯_k. Finally, define λ_k to assign length 1+2l to each “bypass” arc, and length 1 to all other arcs. We refer the reader to <ref>, part (i).

We may assume our algorithm does not satisfy demands using the bypass arcs (as all demand-satisfying paths have length 2l+1, and no tie-breaking scheme is specified). Thus, each demand-satisfying path uses the root of A_S, which incurs a total delay of 0+1+…+(k-1)=Ω(k^2) and total path length of k·(1+2l). Had the bypass arcs been used, no delay would have been required, and the total path length would have still been k·(1+2l). Thus, our algorithm achieves an approximation ratio of (Ω(k^2)+k·(1+2l))/(k·(1+2l))=Ω(k/log k).


It is straightforward to tweak the above analysis to show that for min-max Time Disjoint Walks, <ref> achieves an approximation ratio of Θ(k/log k) on bounded-degree DAGs.







 §.§ Analysis on DAGs

We show that if we no longer require the graph family in <ref> to have bounded degree, our algorithm loses its improved approximation ratio.

<ref> has an approximation ratio of Θ(k) for min-sum Time Disjoint Walks on DAGs.


By <ref>, it suffices to construct a family of TDW instances on DAGs, defined over all k∈ℕ_≥1, for which our algorithm achieves an approximation ratio of Ω(k). Construct G_k by fixing a “root” vertex and directly attaching 2k leaves. Orient half of these arcs towards the root, and half of the arcs away from the root. Call each vertex with out-degree 1 a source, and each vertex with in-degree 1 a destination. Then, arbitrarily pair each source with a unique destination. For each pair, add an arc from the source to the destination (called a “bypass arc”), and add a demand to 𝒯_k. Finally, let λ_k assign length 2 to each bypass arc, and length 1 to all other arcs. We refer the reader to <ref>, part (ii).

We may assume our algorithm does not satisfy demands using the bypass arcs (as all demand-satisfying paths have length 2, and no tie-breaking scheme is specified). Thus, each demand-satisfying path uses the root vertex, which incurs a total delay of 0+1+…+(k-1)=Ω(k^2) and total path length of 2k. Had the bypass arcs been used, no delay would have been required, and the total path length would have still been 2k. Thus, our algorithm achieves an approximation ratio of (Ω(k^2)+2k)/(2k)=Ω(k).


It is straightforward to slightly tweak the above analysis to show that for min-max Time Disjoint Walks, <ref> has an approximation ratio of Θ(k) on DAGs.




 §.§ Analysis on bounded-degree digraphs

In this section, we show that if we no longer require the graph family in <ref> to be acyclic, our algorithm loses its improved approximation ratio.

<ref> has an approximation ratio of Θ(k) for min-sum Time Disjoint Walks on bounded-degree digraphs.


By <ref>, it suffices to construct a family of TDW instances on bounded-degree digraphs, defined over all l∈_≥2 with k̂:=2^l, k:=2k̂, for which our algorithm achieves an approximation ratio of Ω(k). Construct G_k by taking two (2,l)-in-trees A_S and B_S, and two (2,l)-out-trees A_T and B_T. Call their roots r_A_S,r_B_S,r_A_T, and r_B_T, respectively. Then, add a “central path” C consisting of vertices {c_1,c_2,…,c_k̂}, “forward” arcs {(c_i,c_i+1)| i∈[k̂-1]}, and “backward” arcs {(c_j,c_j-3)| j∈[4,k̂], j2=0}. Attach the directed trees to the central path with arcs {(r_A_S,c_1),(r_B_S,c_k̂-1),(c_k̂,r_A_T),(c_2,r_B_T)}. Next, pair each leaf (source) in A_S with an arbitrary, but unique, leaf (destination) in A_T. Do the same for B_S and B_T. For each such pair, add an arc from the source to destination (called a “bypass arc”), and add a demand to 𝒯_k. Finally, let λ_k assign length 2k̂+2l-1 to each bypass arc, length k̂-1 to arcs (r_B_S,c_k̂-1) and (c_k̂,r_A_T), and length 1 to all other arcs. We refer the reader to <ref>, part (iii).

Observe that for each demand, there exist two shortest demand-satisfying paths, each of length 2k̂+2l-1. In particular, observe that a demand between leaves of A_S and A_T may be satisfied by a bypass arc, or by a path that travels from the source in A_S, towards the root of A_S, onto the central path vertex c_1, along all forward arcs of C, onto the root of A_T, and towards the destination in A_T. Similarly, a demand between leaves of B_S and B_T may be satisfied by a bypass arc, or by a path that travels from the source in B_S, towards the root of B_S, onto the central vertex c_k̂-1, across C by alternating between forward and backward arcs (until arriving at c_2), onto the root of B_T, and towards the destination in B_T. We call the paths that do not use the bypass arcs the “meandering paths.”

Because our algorithm specifies no tie-breaking scheme, we may assume that it satisfies demands using the meandering paths, and that it alternates between assigning delays to demands from A_S and assigning delays to demands from B_S every four iterations. In other words, out of the 2k̂ demands created above and fed as input to our algorithm, we may assume that those from A_S to A_T are labeled with indices I_A:={i∈[2k̂]|⌊(i-1)/4⌋≡ 0  2}, while those from B_S to B_T are labeled with I_B:={i∈[2k̂]|⌊(i-1)/4⌋≡ 1  2}.

To understand the suboptimality of this situation, we make several observations that help us determine the values our algorithm assigns to each d_i. First, note that for each i∈[2k̂], z∈[k̂], the length of walk W_i up to vertex c_z on the central path is:

    λ_k(W_i,c_z) =
    
    l+z,   if i∈ I_A
    
    l+2k̂-z-2·(z 2),   if i∈ I_B

Using this, we see that the details of <ref> give us the following relation, which is defined over i∈[k],h∈[i-1]:

    𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i,h =
    {d_h},   if i,h∈ I_A or
       if i,h∈ I_B
    {d_h-2k̂+2z+2·(z 2)| z∈[k̂]},   if i∈ I_B,h∈ I_A
    {d_h+2k̂-2z-2·(z2)| z∈[k̂]},   if i∈ I_A,h∈ I_B

Because our algorithm defines 𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i:=⋃_h∈[i-1]𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i,h and d_i:=min(ℤ_≥0∖𝖻𝖺𝖽_𝖽𝖾𝗅𝖺𝗒𝗌_i), observe that the above relation is in fact a recurrence relation. As such, after noting that d_1=0, it is straightforward to use the above relation to show by induction that for all i∈[2k̂],

    d_i = i-1 + ⌊i-1/8⌋(2k̂-4).

Thus, our algorithm incurs a total delay of ∑_i∈[2k̂](i-1+⌊(i-1)/8⌋(2k̂-4))=Ω(k̂^3)=Ω(k^3) and total walk length of 2k̂·(2k̂+2l-1))=Θ(k̂^2)=Θ(k^2). Had the algorithm opted to use the bypass arcs, no delay would have been required, and the total walk length would have been the same. Thus, our algorithm achieves an approximation ratio of Ω(k).


It is straightforward to slightly tweak the above analysis to show that for min-max Time Disjoint Walks, <ref> has an approximation ratio of Θ(k) on bounded-degree digraphs.





§ CONCLUSIONS

In this paper, we introduce Time Disjoint Walks, a new variant of (shortest) Disjoint Paths that similarly seeks to connect k demands in a network, but relaxes the disjointness constraint by permitting vertices to be shared across multiple walks, as long as no two walks arrive at the same vertex at the same time. We present and analyze a poly-time exact algorithm for both min-sum and min-max TDW on oriented stars, and show that min-sum TDW becomes NP-hard on a slightly more expressive class of inputs. We show that min-sum Time Disjoint Walks is APX-hard, even for DAGs of max degree three. On the other hand, we provide a natural Θ(k/log k)-approximation algorithm for directed acyclic graphs of bounded degree. Interestingly, we also show that for general digraphs with just one of these two properties, the approximation ratio of our algorithm is bumped up to Θ(k).

An interesting future work is to tighten the gap between these inapproximability and approximability results for TDW on bounded-degree DAGs. We conjecture that our approximation algorithm is almost optimal, but that our hardness of approximation result can be strengthened to nearly match our algorithm's approximation ratio of Θ(k/log k). This belief is based on the observation that TDW is a complex problem that involves both routing and scheduling, and many problems of the latter variety (of size n) are NP-hard to approximate within a factor of n^1-ϵ, for any ϵ>0 <cit.>. One may also wish to explore similar complexity questions for the many variants of Time Disjoint Walks discussed in <ref>.




alpha


