Detecting Disjoint Shortest Paths in Linear Time and More
Shyan Akmal Virginia Vassilevska Williams Nicole Wein


An Element-Wise Weights Aggregation Method for Federated Learning
    
1st Yi Hu
Department of Computer Science 

Swansea University

Swansea, United Kingdom 

845700@swansea.ac.uk
2nd Hanchi Ren∗
Department of Computer Science 

Swansea University

Swansea, United Kingdom 

hanchi.ren@swansea.ac.uk
3th Chen Hu
Department of Computer Science 

Swansea University

Swansea, United Kingdom 

2100552@swansea.ac.uk
4rd Jingjing Deng
Department of Computer Science 

Durham University

Durham, United Kingdom 

jingjing.deng@durham.ac.uk
5th Xianghua Xie∗
Department of Computer Science 

Swansea University

Swansea, United Kingdom 

x.xie@swansea.ac.uk
∗ The corresponding authors are Hanchi Ren and Xianghua Xie.










    April 29, 2024
=================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






    In the  problem, we are given a graph G (with positive edge weights) on n nodes and m edges with specified source vertices s_1, …, s_k, and target vertices t_1, …, t_k, and are tasked with determining if G contains vertex-disjoint (s_i,t_i)-shortest paths.
    For any constant k, it is known that  can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs).
    
     However, the exact time complexity of  remains mysterious,
    with large gaps between the fastest known algorithms and best conditional lower bounds.
    In this paper, we obtain faster algorithms for important cases of , and present better conditional lower bounds for  and its variants.
    
    Previous work solved  over weighted undirected graphs in O(n^7) time, 
    
    and weighted DAGs in O(mn) time. 
    
    For the main result of this paper, we present optimal linear time  algorithms for solving  on weighted undirected graphs and DAGs.
    Our linear time algorithms are algebraic however, and so only solve the detection rather than search version of  (we show how to solve the search version in O(mn) time, which is  faster than the previous best runtime in weighted undirected graphs, but only matches the previous best runtime for DAGs).

    We also obtain a faster algorithm for  in DAGs, the variant of  where one seeks edge-disjoint instead of vertex-disjoint paths between sources and their corresponding targets.
    Algorithms for  on DAGs from previous work take  Ω(m^k) time.
    We show that  can be solved over DAGs in O(mn^k-1) time, matching the fastest known runtime for solving  over DAGs.

    Previous work established conditional lower bounds for solving  and its variants via reductions from detecting cliques in graphs.
    Prior work implied 
    that  can be reduced to  in DAGs and undirected graphs with O((kn)^2) nodes.
    We improve this reduction, by showing how to reduce from  to   in DAGs and undirected graphs with O((kn)^2) nodes (halving the number of paths needed in the reduced instance).
    A variant of  is the  problem, where the solution paths no longer need to be shortest paths.
    Previous work reduced from  to 
     in DAGs with O(kn) nodes, for p= k  + k(k-1)/2.
    
We improve this by showing a reduction from  to , for p=k + ⌊ k^2/4⌋.


Under the  from fine-grained complexity, our results establish better conditional lower bounds for  for all k≥ 4, and better conditional lower bounds for  for all p≤ 4031.
Notably, our work gives the first nontrivial conditional lower bounds  in DAGs and  in undirected graphs and DAGs.
Before our work, nontrivial conditional lower bounds were only known for  and  on such graphs when k≥ 6.









  
*Acknowledgements
We thank an anonymous reviewer for pointing out issues with a proof in a previous version of this work, and another anonymous reviewer for simplifying our construction of covering families.
We thank Malte Renken and André Nichterlein for answering questions about previous work. 
The first author additionally thanks Ryan Williams and Zixuan Xu for conversations about early versions of  ideas presented here, and Yinzhan Xu for nice discussions about the arguments in this paper.  



 
gobble
arabic





§ INTRODUCTION



Routing disjoint paths in graphs is a classical problem in computer science.
For positive integer k, in the  problem, we are given a graph G with n vertices and m edges, with specified source nodes s_1, …, s_k and target nodes t_1, …, t_k, and are tasked with determining if G contains (s_i,t_i)-paths which are internally vertex-disjoint.
Beyond being a natural graph theoretic problem to study,   is important because of its deep connections with various computational tasks from the Graph Minors project <cit.>.

Following a long line of research, the polynomial-time complexity of  has essentially been settled: in directed graphs the  problem is -hard <cit.>, and so is unlikely to admit a polynomial time algorithm, while in undirected graphs  can be solved in Õ(m+n) time for k=2 <cit.>, and in O(n^2) time or m^1+o(1) time for any constant k≥ 3 <cit.>. 

In this work we study an optimization variant of , the  problem.
In  we are given the same input as in , but are now tasked with determining if the input  contains (s_i,t_i)-shortest paths which are internally vertex-disjoint.
This problem is interesting both because it is a natural graph algorithms question to investigate from the perspective of combinatorial optimization, and because understanding the complexity of  could lead to a deeper understanding of the interaction between shortest paths structures in graphs (analogous to how studying  helped develop the rich theory surrounding forbidden minors in graphs). 

Compared to , not much is known about the exact time complexity of .
In directed graphs,  can be solved in polynomial time <cit.>, but no polynomial-time algorithm (or -hardness proof) is known for  for any constant k≥ 3.
In undirected graphs, it was recently shown that for any constant k,  can be solved in polynomial time <cit.>. 
However,
the current best algorithms for  in undirected graphs run in 
n^O(k· k!) time, so in general this polynomial runtime is quite large for k≥ 3.
For example, the current fastest algorithm for  in undirected graphs takes O(n^292) time <cit.>.


Significantly faster algorithms are known for detecting k=2 disjoint shortest paths.
The paper which first introduced the  problem in 1998 also presented an O(n^8) time algorithm for solving  in weighted[Throughout, we assume that weighted graphs have positive edge weights.] undirected graphs <cit.>.
The first improvement for this problem came over twenty years later in <cit.>, 
which presented an algorithm solving  in weighted undirected graphs in O(n^7) time, and in unweighted undirected graphs in O(n^6) time.
Soon after, <cit.> presented an even faster O(mn) time algorithm for solving  in the special case of unweighted undirected graphs.[It seems plausible that the method of <cit.> could be adapted to handle weighted undirected graphs as well, but such a generalization does not appear to currently be known.]

The main result of our work is an optimal algorithm for  in weighted undirected graphs.

theoremtwodspundir
    
    The  problem can be solved in weighted undirected graphs in O(m+n) time.







This result pins down the true time complexity of  in undirected graphs, and (up to certain limitations of our algorithm, which we discuss later) closes the line of research for this specific problem, initiated twenty-five years ago in <cit.>.

As discussed previously, over  directed graphs the   problem is -hard, and the complexity of   is open even for k=3.
This lack of algorithmic progress in general directed graphs has motivated researchers to characterize the complexity of disjoint path problems in restricted classes of directed graphs.
In this context, studying algorithms for routing disjoint paths in directed acyclic graphs (DAGs) has proved to be particularly fruitful.
For example, the only known polynomial time algorithm for  on general directed graphs works by reducing to several instances of  on DAGs <cit.>.
Similarly, the fastest known algorithm for  on undirected graphs works by reducing to several instances of disjoint paths on DAGs <cit.>.

It is known that  in DAGs can be solved in linear time <cit.>.
More generally, since 1980 it has been known that  in DAGs can be solved in O(mn^k-1) time, and this remains the fastest known algorithm for these problems for all k≥ 3 <cit.>.

As observed in <cit.>, the algorithm of <cit.> for  on DAGs can be  modified to solve  in weighted DAGs in the same O(mn^k-1) runtime.
This is the fastest known runtime for  in DAGs.
In particular, the fastest algorithm for  from previous work runs in O(mn) time.




The second result of our work is an optimal algorithm for  in weighted DAGs.

theoremtwodspDAG
    
    The  problem can be solved in weighted DAGs in O(m+n) time.


This settles the  time complexity of  in DAGs, and marks the first improvement over the O(mn) time algorithm implied by <cit.> from over thirty years ago.
The  problem in weighted DAGs generalizes the  problem in DAGs, and so <Ref> also offers an alternate linear time algorithm for  in DAGs, which is arguably simpler than the previous approaches leading up to <cit.>, many of which involved  tricky case analyses and carefully constructed data structures.

Our algorithms for solving  in undirected graphs and DAGs are algebraic, and work by testing whether certain polynomials, whose terms encode pairs of disjoint shortest paths in the input graph, are nonzero.
As a consequence, the algorithms establishing <Ref> are randomized, and solve  with high probability.
Moreover, these algorithms determine whether the input graph has a solution, but do not explicitly return solution paths.
So while our algorithms solve the decision problem , they do not solve the search problem of returning two disjoint shortest paths if they exist.
This is a common limitation for algebraic graph algorithms.

The  problem does admit a search to decision reduction – with O(m) calls to an algorithm which detects whether a graph contains two disjoint shortest paths, we can actually find two disjoint shortest paths if they exist.
Thanks to the algebraic nature of our algorithms, we can get a slightly better reduction, and find two disjoint shortest paths when they exist with only O(n) calls to the algorithms from <Ref>.

theoremsearch
    
    We can solve  over weighted DAGs and undirected graphs, and find a solution if it exists, in O(mn) time.


So we can find two disjoint shortest paths in weighted undirected graphs in O(mn) time (which still beats the previous fastest O(n^7) time algorithm for weighted undirected graphs, and matches the previous fastest algorithm for unweighted undirected graphs), and in weighted DAGs in O(mn) time (which only matches, rather than beats, the previous fastest runtime for  in DAGs).


Finally, one can also consider edge-disjoint versions of all the problems discussed thus far.
The  and  problems are the same as the respective  and  problems, except the solutions paths merely need to be edge-disjoint instead of internally vertex-disjoint. 



For any constant k, there is a simple reduction from  on n nodes and m edges to  on O(m+n) nodes and O(m) edges (see <Ref> for the details).
Combining this reduction with <Ref>, we get that we can solve  over weighted DAGs and undirected graphs in linear time as well.


    
    We can solve  over weighted DAGs and undirected graphs in O(m+n) time.


More generally, for all k≥ 3 the fastest known algorithms for  on DAGs in the literature work by reducing this problem to  using the reduction mentioned in the previous paragraph.
Consequently, the current fastest algorithm for  in DAGs runs in O(m^k) time, which in dense graphs is much slower than the O(mn^k-1) time algorithm known for .
For the same reason, the fastest known algorithm for  in DAGs for k≥ 3 runs in O(m^k) time.

Our final algorithmic result is that we can solve  in weighted DAGs as quickly as the fastest known algorithms for .

theoremedsp
    
        The  problem can be solved in weighted DAGs in O(mn^k-1) time.    


Since  in weighted DAGs generalizes the  problem in DAGs (see <Ref> for details),
<Ref> also implies faster algorithms for this latter problem.
Our algorithm is simple and employs the same general approach used by previous routines <cit.> for this problem.



 §.§ Lower Bounds


For k≥ 3, the known O(mn^k-1) algorithms for  and  in DAGs have resisted any improvements over the past three decades.
Thus, it is natural to wonder whether there is complexity theoretic evidence that solving these problems significantly faster would be difficult. 
Researchers have presented some evidence in this vein, in the form of reductions from the conjectured hard problem of detecting  cliques in graphs.



Let k = Θ(1) be a positive integer.
A k-clique is a collection of k mutually adjacent vertices in a graph.
In the  problem,[This problem is sometimes referred to in the literature as . A folklore argument reduces from detecting a k-clique in an arbitrary n-node graph to the  problem as defined here, by making k copies of the input graph, and only including edges between different copies, e.g. as in  <cit.>. ]
 we are given a k-partite graph G with vertex set V_1⊔⋯⊔ V_k, where each part V_i has n vertices,
and
are tasked with determining if G contains a k-clique.

We can of course solve  in O(n^k) time, just by trying out all possible k-tuples of vertices.
Better algorithms for  are known, which employ fast matrix multiplication.
Let ω denote the exponent of matrix multiplication (i.e., ω is the smallest real such that two n× n matrices can be multiplied in n^ω+o(1) time).
Given positive reals a,b,c, we more generally write ω(a,b,c) to denote 
the smallest real such that we can compute the product of an n^a× n^b matrix and an n^b× n^c matrix in n^ω(a,b,c)+o(1) time.
Then it is known that  can be solved in 
    C(n,k) = Θ(n^ω(⌊ k/3⌋, ⌈ (k-1)/3⌉, ⌈ k/3⌉))

time <cit.>.



The current fastest matrix multiplication algorithms yield ω < 2.37156 <cit.>.
A popular fine-grained hardness hypothesis posits (e.g., in  <cit.>) that current algorithms for  are optimal.

[] For any integer constant k ≥ 3,  solving  requires at least C(n,k)^1-o(1) time.



In this context, previous work  provided reductions from  to disjoint path problems. 
For example,
<cit.> presents a reduction from  to  on undirected graphs with O((kn)^2) vertices (and this reduction easily extends to DAGs).
Our first conditional lower bound improves this result for DAGs, by halving the number of paths needed in the reduction.


theoremlbdspboth
    
    There is a reduction from   to  on unweighted DAGs with O((kn)^2) vertices, that runs in O((kn)^2) time.


















    Assuming the ,  requires C(n^1/2,k)^1-o(1) time to solve on unweighted DAGs.


The previous reduction of <cit.>  yields a  weaker bound of C(n^1/2,⌊ k/2⌋ )^1-o(1) for the time needed to solve , assuming the  Hypothesis.
If ω > 2, this earlier result only gives nontrivial (that is, superquadratic) lower bounds for k≥ 10, and if ω  = 2 is only nontrivial for k≥ 14.
In comparison, if ω > 2, <Ref> is nontrivial for k≥ 5, and if ω = 2, <Ref> is still nontrivial for k≥ 7.
See <Ref> for the concrete lower bounds we achieve for small k.

As mentioned before (and as shown in detail in <Ref>), the  problem in weighted DAGs generalizes  in DAGs.
However, the current fastest algorithms for  have the same time complexity as the current best algorithms for the more general  problem.
To explain this behavior, it is desirable to show conditional lower bounds for  in DAGs, which are similar in quality to the known lower bounds for  in DAGs.


Such lower bounds have been shown by <cit.>.
In particular, <cit.> together with standard reductions in parameterized complexity <cit.>
implies that there is a reduction from  to   on graphs with O((kn)^4) nodes.
One can easily modify this reduction, using the idea in the construction from <cit.>, to instead reduce from  to  on graphs with O((kn)^4) nodes.

This reduction implies that  requires C(n^1/4,⌊ k/8⌋)^1-o(1) time to solve on DAGs, assuming the .
For large k, this is the current best  conditional lower bound for  in DAGs.
However, the blow-up in the graph size and parameter value in this reduction makes this lower bound irrelevant for small  k
(in fact, the reduction only yields nontrivial lower bounds under the  Hypothesis for k≥ 96).




For small values of k, better conditional lower bounds are known for .
In particular, <cit.> presents reductions from  to  and  on DAGs with O(kn) vertices, for parameter value p = k + k2.
For our final conditional lower bound, we improve this reduction, by reducing the number of paths needed to k+ ⌊ k^2/4⌋.



theoremlbdp
    
    Let k≥ 3 be a constant integer, and set p=k+ ⌊ k^2/4⌋.
    There are O((kn)^2) time reductions from  to  and  on unweighted DAGs with O(kn) vertices.






For each integer p≥ 5, we can find the largest integer k≥ 3 such that k + ⌊ k^2/4⌋≤ p, and then apply <Ref> to obtain conditional lower bounds for  and  on DAGs.


Assuming the , the  and  problems require 

    max(C(n,k_even(p)), C(n,k_odd(p)))^1-o(1)

time to solve on unweighted DAGs for all integers p≥ 5, where 
    
    k_even(p) = 2⌊√(p+1)⌋ -2

and
    
    k_odd(p) = 2⌊√(p+5)-1/2⌋ - 1

    are the largest even and odd integers k such that k + ⌊ k^2/4⌋≤ p respectively.




Assuming the , <Ref> shows that  requires at least n^ω - o(1) time and  requires at least C(n,4)^1-o(1) time to solve.
For the current value of ω, these yield lower bounds of n^2.371-o(1) for  and n^3.198-o(1) for , which are better than the lower bounds implied by <Ref> (see <Ref>).
If ω = 2 however, <Ref> does not yield better lower bounds than <Ref> for .

Previous reductions give nontrivial lower bounds for  only when p≥ 6 if ω > 2, and  p≥ 10 if ω = 2.
In comparison,
<Ref> yields nontrivial lower bounds for  under the  for p≥ 5 if ω > 2, and p≥ 8 if ω = 2.

Previously, the reduction of <cit.> yielded the best lower bounds for  for p≤ 2016, and otherwise the reduction of <cit.> yielded better lower bounds.
In comparison, <Ref> yields lower bounds matching the reduction from <cit.>  for p∈6,7,10, and  otherwise, for ω > 2, yields strictly better lower bounds for  for all p ≥ 5.
Moreover, for ω = 2,  <Ref> yields the best lower bounds for  for all p≤ 4031 (with <cit.> yielding better lower bounds only for larger p). 

To see quantitatively how <Ref> improves the best conditional lower bounds for  from previous work at various concrete values of p, see <Ref>.





















 §.§ Comparison with Previous Algorithms





Previous algorithms for  and  in DAGs are combinatorial in nature: they observe certain structural properties of candidate solutions, and then leverage these observations to build up pairs of disjoint paths.
In the special case of unweighted undirected graphs, <cit.> presented an algebraic algorithm for solving a generalization of , but all other prior algorithms for  and  in undirected graphs are combinatorial.
Our work is the first to employ algebraic methods to tackle the general weighted  problem: our algorithms for  on undirected graphs and DAGs work by checking that a certain polynomial, whose monomials correspond uniquely to pairs of disjoint shortest paths in the input graph, is nonzero. 
To obtain the fast runtimes in <Ref>, we evaluate this polynomial over a field of characteristic two, and crucially exploit certain symmetries 

which make efficient evaluation possible when working modulo two.

Such “mod 2 vanishing” methods have appeared previously in the literature for algebraic graph algorithms, but the symmetries we exploit in our algorithms for  differ in interesting ways from those of previous approaches. 
For example, previous methods tend to work exclusively in undirected graphs (relying on the ability to traverse cycles in both the forwards and backwards directions to produce terms in polynomials which cancel modulo 2), while our approach is able to handle  in both undirected graphs and DAGs.
It is also interesting that our algorithms solve  in weighted graphs without any issue, since the previous algebraic graph algorithms we are aware of are efficient in unweighted graphs, but in weighted graphs have a runtime which depends polynomially on the value of the maximum edge weight.

Below, we compare our techniques to previous algebraic algorithms  in the literature.



  
Two Disjoint Paths with Minimum Total Length

The most relevant examples of algebraic graph algorithms in the literature to our work are previous algorithms for the  problem:
in this problem, we are given a graph G on n vertices, with specified sources s_1,s_2 and targets t_1,t_2, and are tasked with finding internally vertex-disjoint paths P_i from s_i to t_i, such that the sum of the lengths of P_1 and P_2 is minimized, or reporting that no such paths exists.


In unweighted undirected graphs, <cit.>  showed that  can be solved in 
polynomial time, with 
<cit.> providing a faster implementation of this approach running in  Õ(n^4+ω) time.
Similar to our work, these algorithms
 check if a certain polynomial enumerating disjoint pairs of paths in G is nonzero or not.
These methods rely on G being undirected, and are based off computing determinants of n× n matrices.

Our approach for  differs from these arguments because we seek linear time algorithms, and so avoid computing determinants (which would yield Ω(n^ω) runtimes).
We instead directly enumerate pairs of intersecting paths and subtract them out.
This alternate approach also allows us to obtain algorithms which apply to both  undirected graphs and DAGs, whereas the cycle-reversing arguments of <cit.> do not appear to extend to DAGs.



  
Paths and Linkages with Satisfying Length Conditions
Given sets S and T of p source and target vertices respectively, an (S,T)-linkage is a set of p vertex-disjoint paths, beginning at different nodes in S and ending at different nodes in T.
The length of such a linkage is the sum of the lengths of the paths it contains.
Recent work has presented algorithms for the problem of finding (S,T)-linkages in undirected graphs of length at least k, fixed-parameter tractable in k.
In particular, <cit.> presents an algorithm solving this problem in 2^k+p(n) time.
Their algorithm enumerates collections of p walks beginning at different nodes in S and ending at different nodes in T.
They then argue that all terms in this enumeration with intersecting walks cancel modulo 2, leaving only the  (S,T)-linkages.
One idea used in the above cancellation argument is that if two paths P and Q in a collection intersect at a vertex v, then we can pair this collection with a new collection obtained by swapping the suffixes of P and Q after vertex v.

In the  problem, solution paths must connect sources s_i to corresponding targets t_i instead of to arbitrary targets, and so we cannot use the above suffix-swapping argument to get cancellation.
So to enumerate disjoint shortest paths in our algorithms, we employ somewhat trickier cancellation arguments than what was previously used.

More recently, <cit.> presented an algorithm solving the linkage problem discussed above in 2^k(n) time (with runtime independent of p).
Their approach uses determinants to enumerate (S,T)-linkages.
As mentioned previously, we explicitly avoid using determinants so that we can obtain linear time algorithms.



  
Additional Related Work
There are many additional examples of algebraic graph algorithms in the literature.
For example, <cit.> presents an efficient algorithm for finding shortest cycles through specified subsets of vertices, <cit.> presents algorithms for finding shortest cycles and perfect matchings in essentially matrix multiplication time, and <cit.> presents a polynomial time algorithm for finding a shortest cycle of even length in a directed graph.
Even more examples of algebraic methods in  parameterized algorithms are listed in <cit.>.



 §.§ Organization

In <Ref> we introduce notation and recall useful facts about graphs and polynomials used in our results. 
In <Ref> we provide some intuition for the proofs of our results.
In <Ref> we present our linear time algorithms for  in weighted undirected graphs and DAGs. In <ref> we present our algorithm for . In <ref> we present our lower bounds.
Finally, we conclude in <Ref> by highlighting some open problems motivated by this work.

See <Ref> for proofs of some simple reductions between variants of disjoint path problems which were mentioned previously.



§ PRELIMINARIES





  §.§.§ General Notation


Given a positive integer a, we let [a] = 1, …, a denote the set of the first  a positive integers.
Given positive integers a and b, we let [a,b] = a, …, b denote the set of consecutive integers from a to b inclusive (if a > b, then [a,b] is the empty set).

Throughout, we let k denote a constant positive integer parameter.



  §.§.§ Graph Notation and Assumptions


Throughout, we let G denote the input graph on n vertices and m edges.
We let s_1, …, s_k denote the source vertices of G, and t_1, …, t_k denote the target vertices of G.
A terminal is a source or target node.
We assume without loss of generality that G is weakly connected (we can do this because we only care about solving disjoint path problems on G, and if terminals of G are in separate weakly connected components, we can solve smaller disjoint path problems on each component separately).

Given an edge e = (u,v), we let ℓ(u,v) denote the weight of e in G.
We assume all edge weights are positive.
We let (u,v) denote the distance of a shortest path (i.e., the sum of the weights of the edges used in a shortest path) from u to v. 
When we write “path P traverses edge (u,v)” we mean that P first enters u, then immediately goes to v.

We represent paths P = ⟨ v_0, …, v_r⟩ as sequences of vertices.
If the path P passes through vertices u and v in that order, we let P[u,v] denote the subpath of P which begins at u and ends at v. 
We let P denote the reverse path of P, which traverses the vertices of P in reverse order.
Given two paths P and Q such that the final vertex of P is the same as the first vertex of Q, we let P Q denote the concatenation of P and Q.





  §.§.§ Shortest Path DAGs


Given a graph G and specified vertex s, the s-shortest paths DAG of G is the graph with the same vertex set as G, which includes edge (u,v) if and only if (u,v) is an edge traversed by an (s,v)-shortest path in G.
From this definition, it is easy to see that a sequence of vertices is an (s,v)-shortest path of G if and only if it is an (s,v)-path in the s-shortest paths DAG of G.
Indeed, every edge of an (s,v)-shortest path in G is contained in the s-shortest paths DAG by definition, and so forms a path in this graph.
Conversely, if the sequence of vertices P = ⟨ v_0, …, v_r⟩ is an (s,v)-path in the s-shortest paths DAG of G, then we can inductively show that P[s,v_i] is a shortest path in G for each index i.

We observe that shortest paths DAGs can be constructed in linear time.


    
    Let G be a weighted DAG or undirected graph with distinguished vertex s.
    Then we can construct the s-shortest paths DAG of G in linear time.


    By definition, an edge (u,v) is in the s-shortest paths DAG of G if and only if (u,v) is the last edge of some  (s,v)-shortest path in G.
    This is equivalent to the condition that (u,v) is an edge in G, and 
        
    (s,v) = (s,u) + ℓ(u,v).

    So, we can construct the s-shortest paths DAG of G by computing the values of (s,v) for all vertices v, and then going through each edge (u,v) in G (if G is undirected, we try out both ordered pairs (u,v) and (v,u) of an edge u,v) and checking if <ref> holds.

    So to prove the claim, it suffices to compute (s,v) for all vertices v in linear time.

    When G is a weighted DAG, we can compute a topological order of G in linear time, and then perform dynamic programming over the vertices in this order to compute (s,v) for all vertices v in linear time (this procedure is just a modified breadth-first search routine).

    When G is an undirected graph, we instead use Thorup's linear-time algorithm for single-source shortest paths in weighted undirected graphs <cit.> to compute (s,v) for all vertices v.







  §.§.§ Finite Fields


Our algorithms for  in undirected graphs and DAGs involve working over a finite field 𝔽_2^q of characteristic two, where q = O(log n).
We work in the Word-RAM model with words of size O(log n), so that 
addition and multiplication over this field take constant time.

We make use of the following classical result, which shows that we can test if a polynomial is nonzero by evaluating it at a random point of a sufficiently large finite field. 



    Let f be a nonzero polynomial of degree at most d.
    Then a uniform random evaluation of f over 𝔽 is nonzero with probability at least 1-d/|𝔽|.












§ TECHNICAL OVERVIEW





 §.§ 2-DSP Algorithms


We first outline a linear time algorithm solving  in DAGs.
We then discuss the changes needed to solve the  problem in weighted DAGs, and then the additional ideas used to solve  in weighted undirected graphs.

Let G be the input DAG.
For each edge (u,v) in G, we introduce an indeterminate x_uv.
We assign each pair of paths in G a certain monomial over the x_uv variables, which records the pairs of consecutive vertices traversed by the paths.
These monomials are constructed so that any pair of disjoint paths has a unique monomial.

Let F be the sum of monomials corresponding to all pairs of paths P_1,P_2 such that P_i is an (s_i,t_i)-path in G.
Let F_ and F_∩ be the sums of monomials corresponding to all such pairs of paths which are disjoint and intersecting respectively.
Since each disjoint pair of paths produces a distinct monomial, we can solve  by testing whether F_ is a nonzero polynomial. 
We can perform this test by evaluating F_ at a random point, by the Schwartz-Zippel lemma (<Ref>).





Since every pair of paths is either disjoint or intersecting, we have 
    
    F = F_ + F_∩

which implies that 
    
    F_ = F - F_∩.

This relationship is pictured in <Ref>.



Thus, in order to evaluate F_, it suffices to evaluate F and F_∩.
Since F enumerates  pairs of paths from the sources to their corresponding targets with no constraints, it turns out that F is easy to evaluate.
So solving  amounts to evaluating F_∩ efficiently.


To evaluate F_∩, we need a way of enumerating over all pairs of intersecting paths. 
Each pair of intersecting paths overlaps at a unique earliest vertex v (with respect to the topological order of G).
Consequently, if we let F_v be the sum of monomials of pairs of intersecting paths with first intersection at v, we have 
    
    F_∩ = ∑_v∈ V F_v

as depicted in <Ref>.

We evaluate each F_v by relating it to a seemingly simpler polynomial.
Let F̃_v be the polynomial enumerating pairs of paths P_1,P_2 where P_i is an (s_i,t_i)-path in G such that

    
  * P_1 and P_2 intersect at vertex v, and 
    
  * the vertices appearing immediately before v on P_1 and P_2 are distinct.


We can think of property 2

as a relaxation of the condition that P_1 and P_2 have v as their earliest intersection point: instead of requiring that P_1[s_1,v] and P_2[s_2,v] never overlap before v, we merely require that these subpaths do not overlap at the  position immediately before v.
It turns out evaluating F̃_v is easy, because we can enforce property 2 above by enumerating over all pairs of paths which intersect at v, and then subtracting out all such pairs  which overlap at some edge ending at v.
Simultaneously evaluating all F̃_v can then be done in O(m) time, roughly because we perform one subtraction for each possible edge the paths could overlap at.


So far, we have explained how to compute all F̃_v values in linear time.
Now comes the key idea behind our algorithm: over fields of characteristic two,  the polynomials F̃_v and F_v are actually identical! 
Indeed, consider a pair of paths P_1, P_2 enumerated by F̃_v, which intersects before v.
Let the first intersection point of these paths be some vertex u.
Then by condition 2 above, the subpaths P_1[u,v] and P_2[u,v] are distinct, because their penultimate vertices are distinct.
So if we define new paths 
    
    Q_1 = P_1[s_1,u] P_2[u,v] P_1[v,t_1]
          and   
        Q_2 = P_2[s_2,u] P_1[u,v] P_2[v,t_2]

obtained by swapping the u to v subpaths in P_1 and P_2, we get a new pair of paths Q_1,Q_2 satisfying conditions 1 and 2 from before, such that each Q_i is an (s_i,t_i)-path in G, which produces the same monomial as P_1,P_2.
This subpath swapping operation is depicted in <Ref>, for u=a and v=b.
Then modulo two, the contributions of the pairs P_1,P_2 and Q_1,Q_2 to F̃_v will cancel out.
It follows that all pairs of paths which intersect before v have net zero contribution to  F̃_v, and so F̃_v = F_v as claimed.
This congruence is depicted in <Ref>,



Given this observation, we can use our evaluations of F̃_v in <ref> to evaluate F_∩ and thus, by the previous discussion, solve the  problem.



  §.§.§ From Disjoint Paths to Disjoint Shortest Paths


To solve  in weighted DAGS, we can modify the  algorithm sketched above as follows.
First, for i∈ [2], we compute G_i, the s_i-shortest paths DAG of G.
We then construct polynomials as above, but with the additional constraint that they only enumerate pairs of paths ⟨ P_1,P_2⟩ with the property that every edge in path P_i lies in G_i.
This ensures that we only enumerate pairs of paths which are shortest paths between their terminals.

With this change, the above algorithm for  generalizes to solving . 





Previous near-linear time algorithms for  in DAGs and undirected graphs do not easily generalize to solving .
In contrast, as outlined above, in our approach moving from  to  is simple.
Why is this?

Intuitively, this happens because our algorithms take an enumerative perspective on , rather than the detection-based strategy of previous algorithms.
Older algorithms iteratively build up solutions to  or . 
Depending on the problem, this involves enforcing different sorts of constraints, since partial solutions to these problems may look quite different. 
In our approach, we just need to enumerate paths to solve  and enumerate shortest paths to solve .
Enumerating paths and shortest paths are both easy in DAGs by dynamic programming.
Hence algorithms for these two problems end up being essentially the same in our framework.






  §.§.§ From DAGs to Undirected Graphs


When solving  in DAGs, we used the fact that DAGs have a topological order, so that any pair of paths intersects at a unique earliest vertex v in this order.
This simple decomposition does not apply to solving  in undirected graphs, since we cannot rely on a fixed topological order.

Instead, we perform casework on the first vertex v in P_1 lying in P_1∩ P_2.
We observe that in undirected graphs, there are two possibilities: v is either the first vertex in P_2 lying in P_1∩ P_2, or it is the final vertex in P_2 lying in P_1∩ P_2.
Intuitively, the paths either “agree” and go in the same direction, or “disagree” and go in opposite directions. 

We then argue that over a field of characteristic two, we can efficiently enumerate over pairs of paths in each of these cases.
As with DAGs, 
we make this enumeration efficient by arguing that modulo 2 we can relax the (a priori difficult to check) condition of v being the first intersection point on P_1 to some simpler “local” condition.
When the paths agree, this argument is similar to the reasoning used for solving  in DAGs.

For the case where the paths disagree, this enumeration is  more complicated, because there is no consistent linear ordering of the vertices neighboring v on the two shortest paths, but can still be implemented in linear time using a more sophisticated local condition.
Specifically, if we let a_i and b_i denote the nodes appearing immediately before and after v on path P_i, then to enumerate the `disagreeing paths” modulo two, we prove that it suffices to enumerate paths P_1 and P_2 which intersect at v and have the properties that a_1≠ a_2, b_1≠ b_2, and a_1≠ b_2.
Intuitively, using the subpath swapping idea depicted in <Ref>, the conditions that a_1≠ a_2 and a_1≠ b_2 ensure that v is the first vertex of P_1 lying in P_1∩ P_2, and the condition that b_1≠ b_2  ensures that the paths disagree.
To implement this idea, we need a slightly more complicated subpath swapping argument, which can also handle the case where two paths P_1 and P_2 intersect at vertices u and v, with u appearing before v on P_1 but u appearing after v on P_2 (this situation does not occur in DAGs, but can occur in undirected graphs).
We do this by combining the previous subpath swapping idea with the observation that in undirected graphs we can also traverse subpaths in the reverse direction (so it is possible to swap the subpaths P_1[u,v] and P_2[v,u] in P_1 and P_2, even though u and v appear in different orders on P_1 and P_2).

By combining the enumerations for both cases, we can evaluate F_, and thus solve  over undirected graphs.









 §.§ k-EDSP Algorithm


The previous algorithm of <cit.> for  works by constructing a graph G' encoding information about k-tuples of edge-disjoint shortest paths in the original graph G.
This new graph G' has special nodes s⃗ and t⃗, such that there is a path from s⃗ to t⃗ in G' if and only if G contains k edge-disjoint shortest paths connecting its terminals.
The nodes of the new graph G' are k-tuples of edges (e_1, …, e_k) where each e_i is an edge in G.
So constructing G' already takes Ω(m^k) time.

Our algorithm for  uses the same general idea.
We construct an alternate graph G' which still has the property that finding a single path between two specified vertices of G' solves the  problem in G.
However, we design G' to have nodes of the form (v_1, …, v_k), where each v_i is a vertex in G.
Our construction produces a graph with n^k nodes and O(mn^k-1) edges, which yields the speed-up. 
We avoid the Ω(m^k) bottleneck of the previous algorithm by showing how to encode edge-disjointness information simply through the k-tuples of vertices, rather than edges, that the k potential solution paths in G traverse.





 §.§ Lower Bounds




  §.§.§ Disjoint Shortest Paths


Our proof of <ref> is based on the reduction of 
 
<cit.> from  to 2k- on undirected graphs, which also easily extends to DAGs. 
Our contribution is a transformation that reduces the number of paths in their reduction from 2k to k by exploiting the symmetry of the construction. 

The reduction of <cit.> maps each vertex v in the  instance to a horizontal path P_v and a vertical path Q_v, each of length n. These paths are arranged so that for each pair of vertices (v,w) in the input graph, the paths P_v and Q_w intersect if and only if (v,w) is not an edge in the input graph. To achieve this, the paths are placed along a grid, and at the intersection point in the grid between paths P_v and Q_w, these two paths are modified to bypass each other to avoid intersection if (v,w) is an edge in the input graph.

The main idea of our transformation is the following. Since the known reduction is symmetric along the diagonal of the grid, it contains some redundancy. 
We remove this redundancy by only keeping the portion of the grid below the diagonal. 
To do this, we only have one path P_v for each vertex v in the input graph, and each such path has both a horizontal component and a vertical component. Each path turns from horizontal to vertical when it hits the diagonal. 
As a result, each pair of paths (P_v, P_w) has exactly one intersection point in the grid (which we bypass if (v,w) is an edge in the input graph). 
Since we produce only a single path P_v for each vertex v, we obtain a reduction to k- instead of 2k-.




  §.§.§ Disjoint Paths


The starting point for <ref> is the work of <cit.>, which reduces from  to  in a DAG with O(kn) nodes, for p=k + k2. 
The parameter blows up from k to p in this way because the reduction uses k solution paths to pick k vertices in the original graph, and then for each of the k2 pairs of vertices chosen, uses an additional solution path to verify that the vertices in that pair are adjacent in the original graph. 

We improve upon this by modifying the reduction graph to allow some solution paths to check multiple edges simultaneously.
This lets us avoid using k2 solution paths to separately check for edges between each pair of nodes in a candidate k-clique. 
Instead, we employ just ⌊ k^2/4⌋ solution paths in the reduction, roughly halving the number of paths needed. 

To do this, we need to precisely identify which paths can check for multiple edges without compromising the correctness of the reduction. 
To this end, we examine the structure of the reduction and define a notion of a covering family which characterizes which paths can safely check for multiple edges at once. 
Formally, a k-covering family is a collection ℒ of increasing lists of positive integers, with the property that for all integers i,j with 1≤ i < j≤ k, some list in ℒ contains i and j as consecutive members.

We show that for any k, the smallest number of lists in a k-covering family is λ(k)  = ⌊ k^2/4⌋ (note that merely obtaining asymptotically tight bounds would not suffice for designing interesting conditional lower bounds). 
We then insert this construction of a minimum size covering family into the framework of the reduction and prove that the reduction remains correct. 
Intuitively, given lists in a covering family, we can map each list L to a path  which checks edges between vertex parts V_i and V_j for each (i,j) pair appearing as consecutive members of L.

The original reduction of <cit.> corresponds to implementing this strategy with the trivial k-covering family using k2 lists, achieved by taking a single increasing list of two elements for each unordered pair of integers from [k].
Our improved reduction comes from implementing this framework with the optimal bound of ⌊ k^2/4⌋ lists.

This yields reductions from  to  and  for p= k + λ(k) = k + ⌊ k^2/4⌋.


 














§ 2-DSP



In this section, we present our new algorithms for .

We begin in <Ref> by introducing notation and terminology used in our algorithms.
We also present a general “subpath swapping lemma,” which we repeatedly invoke to efficiently evaluate polynomials modulo 2.
Then in <Ref> we define and prove results about various  polynomials used in our algorithms.
All the definitions and results in <Ref> and <Ref> apply to both DAGs and undirected graphs.

Following this setup, in <Ref> we present an algorithm for  in DAGs proving <Ref>, and in <Ref> we present an algorithm for  in undirected graphs proving <Ref>.
We note that
<Ref> can be read independently of <Ref> (but both <Ref>
rely on the definitions and results from <Ref>).



 §.§ Graph and Polynomial Preliminaries





  §.§.§ Graph Notation

Let G denote the input graph on n vertices and m edges.
Let V be the vertex set of G.

For each i∈ [2], we define G_i to be the s_i-shortest paths DAG of G.

Given i∈ [2] and vertex v, we let V_in^i(v) denote the in-neighbors of v in G_i, and ^i(v) denote the out-neighbors of v in G_i.
We further let (v) = ^1(v)∩^2(v) and (v) = ^1(v)∩^2(v) be the sets of in-neighbors and out-neighbors respectively of node v common to both G_1 and G_2.
Furthermore, we define (v) = ^1(v)∩^2(2) to be the “mixed neighborhood” of v. 

We call a pair of paths ⟨ P_1,P_2⟩ standard if each P_i is an (s_i,t_i)-path in G_i.



  §.§.§ Algebraic Preliminaries


For each edge e = (u,v), we introduce an indeterminate x_uv.

If G is undirected, we set 
x_uv = x_vu = x_u,v
to reflect that edges are unordered pairs of vertices.

Given a path P = ⟨ v_0, …, v_r⟩, we assign it the monomial
    
    f(P) = ∏_j=0^r-1x_v_jv_j+1.
    
Given a pair of paths P = ⟨ P_1, P_2⟩, we assign it monomial 
    
    f(P) = f(P_1,P_2) = f(P_1)f(P_2).

Given a collection S of paths or pairs of paths, we say that a “polynomial F enumerates S,” or equivalently “F is the enumerating polynomial for S,” if 
    
    F = ∑_S∈S f(S).




  §.§.§ Subpath Swapping




    Let P_1 and P_2 be shortest paths passing through vertices a and b in that order.
    Then the walks obtained by swapping the a to b subpaths in P_1 and P_2 are also shortest paths.


Since P_1 and P_2 are shortest paths, each of their a to b subpaths have length (a,b).
Since these subpaths have the same length, swapping the a to b subpaths of P_1 and P_2 produce walks with the same endpoints and lengths as P_1 and P_2 respectively.
Since all edge weights are positive, these walks have no repeat vertices (since if one of the walks did have repeat vertices, then it would contain a cycle which we could remove to produce a walk of shorter total length between its endpoints, which would then contradict the assumption that P_1 and P_2 are shortest paths).
Thus these walks must be shortest paths as claimed.




We will repeatedly make use of the following result, which gives a way of simplifying enumerating polynomials for certain families of pairs of paths.
Although the statement may appear technical, the lemma simply formalizes the idea that for certain enumerating polynomials, we can pair up terms of equal value and get cancellation modulo two.



    Let F be a family of pairs of paths in G, and let S⊆F.
    Suppose there exists maps α, β: S→ V and Φ: S→S such that for all P = ⟨ P_1,P_2⟩∈S, 
    
        
  * the vertices a = α(P) and b=β(P) lie in P_1∩ P_2, a appears before b in P_1 and P_2, and the subpaths P_1[a,b] and P_2[a,b] are distinct;
        
        
  * we have 
        Φ(P) = ⟨ Q_1, Q_2⟩, where Q_1 is obtained by replacing the a to b subpath in P_1 with P_2[a,b], and Q_2 is obtained by replacing the a to b subpath in P_2 with P_1[a,b]; and

        
  * we have Φ(Φ(P)) = P.
    
    Then the enumerating polynomial for F is the same as the enumerating polynomial for F∖S.


    Let F be the enumerating polynomial for F.
    By definition, we have 
        
    F = ∑_P∈F f(P) = ∑_P∈F∖S f(P) + ∑_P∈S f(P).

Take any P = ⟨ P_1,P_2⟩∈S.
By property 1 from the lemma statement, the subpaths from α(P) to β(P) in P_1 and P_2 are distinct.
Then by property 2, Φ(P)≠P.
Consequently, by property 3, we can partition S = S_1∪S_2 into two equally sized pieces such that Φ is a bijection from S_1 to S_2.
So we can write 
    
    ∑_P∈S f(P) = ∑_P∈S_1 f(P) + ∑_P∈S_2 f(P) = ∑_P∈S_1f(P) + f(Φ(P)).

By property 2, the multiset of edges traversed by the pair P is the same as the multiset of edges traversed by Φ(P), for all P∈S.
Consequently, f(P) = f(Φ(P)) for all P∈S.



The subpath swapping procedure determined by Φ is depicted in <Ref>.

Since we work over a field of characteristic two, this implies that 

    ∑_P∈S_1f(P) + f(Φ(P)) = 0.


Substituting the above equation into <ref> implies that 
    
    ∑_P∈S f(P) = 0.


Then substituting the above equation into <ref> yields 
    
    F = ∑_P∈F∖S f(P).


This proves that F is the enumerating polynomial for F∖S as desired.

















    





 §.§ Helper Polynomials



In this section we define various enumerating polynomials which will help us solve .
All of the results in this section hold if the input graph G is a DAG or is undirected.



  §.§.§ Paths to and from Terminals


For each i∈ [2] and vertex v, 
let L_i(v) be the enumerating polynomial for the set of (s_i,v)-paths in G_i, and let R_i(v) be the enumerating polynomial for the set of (v,t_i)-paths in G_i.

    
    For each i∈ [2] and vertex v, we have 
        
    L_i(v) = ∑_u∈^i(v) L_i(u)x_uv

    and
        
    R_i(v) = ∑_w∈^i(v) x_vwR_i(w).



    Since L_i(u) enumerates (s_i,u)-paths in G_i, the polynomial
        
    L_i(u)x_uv

    enumerates (s_i,v)-paths in G_i, whose penultimate vertex is u.
    Every (s_i,v)-path in G_i has some unique penultimate vertex u∈^i(v).
    Consequently
    
    ∑_u∈^i(v) L_i(u)x_uv

    enumerates all (s_i,v)-paths in G_i, which proves <ref> as desired.
    
    Symmetric reasoning proves <ref>.




  §.§.§ Intersecting Paths


Let F_ be the enumerating polynomial for the collection of vertex-disjoint, standard pairs of paths.
Let F_∩ be the enumerating polynomial for the collection of intersecting, standard pairs of paths.

Our algorithms for  work by evaluating F_ at a random point.
The following observation shows that we can compute an evaluation of F_ by evaluating F_∩ instead.


    
    We have
    
    F_ = L_1(t_1)L_2(t_2) - F_∩.



            By expanding out the product, we see that L_1(t_1)L_2(t_2) enumerates all standard pairs of paths ⟨ P_1,P_2⟩.
            Each such pair is either vertex-disjoint or consists of paths intersecting at a common node, so we have 
            
    L_1(t_1)L_2(t_2) = F_ + F_∩

            which implies the desired result.




  §.§.§ Linkages from Two Sources to a Common Vertex


Our algorithms will use the following “linkage” polynomials, which enumerate pairs of internally vertex-disjoint paths beginning at the source nodes s_1 and s_2, and ending at a common vertex.



Given a vertex v, let D(v) be the set of pairs of paths ⟨ P_1,P_2⟩ where each P_i is an (s_i,v)-path in G_i and the paths intersect only at v.
Let D(v) be the enumerating polynomial for D(v).


We now observe that for the purpose of enumeration modulo two, one can replace the “global constraint” that a pairs of paths in D(v) has no intersection anywhere before v with the easier to check “local constraint” that a pair of paths has no intersection immediately before v.


    Given a vertex v, let D̃(v) be the set of pairs of paths ⟨ P_1,P_2⟩, where each P_i is an (s_i,v)-path in G_i, such that the penultimate vertices of P_1 and P_2 are distinct.



    
    For each vertex v, the polynomial D(v) enumerates D̃(v).


    For convenience, let F = D̃(v).
    Let S = F∖D(v) be the family of pairs of paths ⟨ P_1,P_2⟩ where each P_i is an (s_i,v)-path in G_i, such that 
    
        
  * the paths P_1 and P_2 intersect at some node other than v, and 
        
  * the nodes immediately before v on P_1 and P_2 are distinct.
    
    Take arbitrary ⟨ P_1,P_2⟩∈S.
    Let u be the vertex in P_1∩ P_2 maximizing the value of (u,v).
    By condition 1 above, u≠ v.
    By condition 2 above, P_1[u,v] and P_2[u,v] are distinct.

        Now define paths 
        
    Q_1 = P_1[s_1,u] P_2[u,v]   and  
            Q_2 = P_2[s_2,u] P_1[u,v].

    By <Ref> each Q_i is a shortest path, and thus an (s_i,v)-path in G_i.

    The pair ⟨ Q_1,Q_2⟩ satisfies condition 1 above, since Q_1 and Q_2 intersect at u.
    This pair also satisfies condition 2 above, since the penultimate vertices of Q_1 and Q_2 are the same as the penultimate vertices of P_2 and P_1 respectively.
    Also, u is the node in Q_1∩ Q_2 maximizing (u,v), so we can perform the same subpath swapping operation as above to go from ⟨ Q_1, Q_2⟩ to ⟨ P_1, P_2⟩.

    Then by the discussion in the previous paragraph, <Ref> implies that the enumerating polynomial for F is the same as the enumerating polynomial for F∖S = D(v).
   The enumerating polynomial for D(v) is D(v), so this proves the desired result.




    For each vertex v, the polynomial
            
    L_1(v)L_2(v) - ∑_u∈(v) L_1(u)L_2(u)x_uv^2

        enumerates D̃(v).


        By expanding out the product, we see that the polynomial  L_1(v)L_2(v)  enumerates all pairs of paths ⟨ P_1,P_2⟩ where each P_i is an (s_i,v)-path in G_i.
    We claim that 
    
    ∑_u∈(v) L_1(u)L_2(u)x_uv^2

    enumerates all pairs of paths ⟨ P_1,P_2⟩ such that each P_i is a path in G_i beginning at s_i and ending at an edge (u,v) for some node u∈(v).

    Indeed, paths P_1 and P_2 from any such pair can be split along their final edges into  
        
    P_1 = P_1[s_1,u] (u,v)   and  
            P_2 = P_2[s_2,u]  (u,v).

    The paths P_i[s_i,u] are enumerated by the L_i(u) factors in <ref>, and the two copies of  (u,v) are encoded by the x_uv^2 factor in <ref>.
    Conversely, any monomial in the expansion of
    
    L_1(u)L_2(u)x_uv^2

    is the product of monomials for some (s_i,u)-paths Q_i in G_i and two occurrences of the edge (u,v), so that if we define
        
    P_1 = Q_1  (u,v)  and  
            P_2 = Q_2  (u,v)

    then the monomial we were considering is precisely the monomial for the pair ⟨ P_1, P_2⟩.
    Summing over all vertices u∈ proves that <ref> enumerates the pairs of paths we described above.

    From the discussion above, it follows that 
    
    L_1(v)L_2(v) - ∑_u∈(v) L_1(u)L_2(u)x_uv^2

    enumerates all pairs of paths ⟨ P_1,P_2⟩, where  P_i is an (s_i,v)-path in G_i, such that P_1 and P_2 have distinct penultimate vertices.
    Thus this polynomial enumerates D̃(v) as desired.




    For each vertex v, we have 

    D(v) = L_1(v)L_2(v) - ∑_u∈(v) L_1(u)L_2(u)x_uv^2.



    This result follows by combining <Ref>.



    
    
    
    



 §.§ 2-DSP in DAGs



In this subsection, assume that G is a weighted DAG, and recall the definitions from <Ref>.
We fix an arbitrary topological order on the vertices of G.

Our main goal is to efficiently evaluate a polynomial encoding pairs of disjoint shortest paths in G.
By <Ref>, it suffices to evaluate a polynomial enumerating pairs of intersecting shortest paths in G.
We do this by casework on the first intersection point of these paths. 


    
    We have 
        
    F_∩ =  ∑_v∈ V D(v)R_1(v)R_2(v).


        
For any fixed vertex v, we claim that 
            
    D(v)R_1(v)R_2(v)

        enumerates all standard pairs of paths ⟨ P_1,P_2⟩ such that P_1 and P_2 have first  intersection at v.
        Indeed, given any such pair of paths ⟨ P_1,P_2⟩, we can decompose
            
    P_i = P_i[s_i,v] P_i[v,t_i]

        and observe that the pair ⟨ P_1[s_1,v],P_2[s_2,v]⟩ is enumerated by the D(v) factor in <ref>, and the P_i[v,t_i] paths are enumerated by the respective R_i(v) factors from <ref>.
        Conversely, any monomial in the expansion of <ref> is the product of monomials encoding the edges of a pair of paths ⟨ A_1,A_2⟩, where A_i is an (s_i,v)-path in G_i such that A_1 and A_2 only intersect at v, and paths B_i from v to t_i in G_i.
        Then if we define 
            
    P_i = A_i B_i

        we see that the P_i are (s_i,t_i)-paths in G_i with the property that P_1 and P_2 first intersect at v.
        Here, we are using the fact that G is a DAG—this ensures that every node in A_1 or A_2 appears at or before v in the topological order, and that every node in B_1 or B_2 appears at or after v in the topological order, so that 
        A_1∩ B_2 = A_2∩ B_1 = v.

        Since every pair of intersecting paths intersects at a unique earliest vertex, it follows that 
        
    ∑_v∈ V D(v)R_1(v)R_2(v)

        enumerates all intersecting, standard pairs of paths ⟨ P_1,P_2⟩.
        This proves the desired result.


























*

    Each pair of internally vertex-disjoint paths produces a distinct monomial in F_.
    It follows that disjoint (s_i,t_i)-shortest paths exist in G if and only if F_ is nonzero as a polynomial.

    So we can solve  as follows.
    We assign each x_uv variable an independent, uniform random element of 𝔽_2^q, and then evaluate F_ on this assignment.
    If the evaluation is nonzero we return YES (two disjoint shortest paths exist), and otherwise we return NO.
    
    If two disjoint shortest paths do not exist, then F_ is the zero polynomial, and our algorithm correctly returns NO.
    If two disjoint shortest paths do exist, then F_ is a nonzero polynomial of degree strictly less than 2n, so by Schwartz-Zippel (<Ref>) our algorithm correctly returns YES with high probability for large enough q = O(log n).

    It remains to show that we can compute F_ in linear time.

    First, we can compute G_1 and G_2 in linear time by <Ref>.
    
    Then, by dynamic programming forwards and backwards over the topological order of G, we can evaluate the polynomials  L_i(v)   and R_i(v) for each i∈ [2] and vertex v at our given assignment in linear time, using the recurrences from <Ref>.
    
    Having computed these values, <Ref> shows that for any vertex v we can compute D(v) at the given assignment in O(_in(v)) time.
    So we can evaluate D(v) for all v in O(m) time.
    
    Given the above evaluations, we can compute F_∩ at the given point in O(n)  time by <Ref>.
    
     Finally, given the value of F_∩, we can evaluate F_ in O(1) additional time by <Ref>.

     Thus we can solve  in linear time.





 §.§ 2-DSP in Undirected Graphs



In this subsection, we assume that G is a weighted undirected graph.

To solve  in G, we will show how to efficiently evaluate a polynomial enumerating pairs of disjoint shortest paths in G.
To help construct this polynomial, it will first be helpful to characterize the ways in which two shortest paths can intersect in an undirected graph.



  §.§.§ Structure of Shortest Paths


We begin with the following simple observation about shortest paths in undirected graphs.



Let G be an undirected graph.
    Suppose vertices a,b,c appear in that order on some shortest path of G.
    Then on any shortest path in G passing through these three nodes, b appears between a and c.    


    Since some shortest path in G passes through vertices a,b,c in that order, we know that (a,b) and (b,c) are both less than (a,c).

    Now, consider any shortest path in G which passes through these three vertices.
    If a appears between b and c in this shortest path, then 
        
    (a,c) < (b,c)

    which contradicts the observation from the first sentence.
    
    Similarly, if c appears between a and b in this shortest path, then
        
    (a,c) < (a,b)

    which again contradicts the observation  from the first sentence of this proof.

    Thus b must appear between a and c on the shortest path as claimed.







    Let P_1 and P_2 be intersecting shortest paths in an undirected graph.
    Let v be the first vertex in P_1 appearing in P_1∩ P_2.

    
  * If P_1∩ P_2 = v, we say P_1 and P_2 have single 
    intersection.
    
  * If |P_1∩ P_2|≥ 2 and v is also the first vertex of P_2 in P_1∩ P_2, we say P_1 and P_2 agree.
    
  * If |P_1∩ P_2|≥ 2 and v is the last vertex of P_2 in P_1∩ P_2, we say P_1 and P_2 are reversing.

If P_1 and P_2 do not agree, we say they disagree.


In other words, P_1 and P_2 disagree if the first vertex v of P_1 appearing in P_1∩ P_2 is also the last vertex of P_2 appearing in P_1∩ P_2.
Equivalently, paths P_1 and P_2 disagree if they have single intersection or are reversing.



      Let P_1 and P_2 be intersecting shortest paths in an undirected graph.
    Then either P_1 and P_2 agree, are reversing, or have single intersection.  


    If |P_1∩ P_2| = 1, then the paths have single intersection.

    Otherwise, |P_1∩ P_2| ≥ 2.
Let v be the first vertex in P_1 appearing in P_1∩ P_2.
It suffices to show v is either the first or last vertex in P_2 appearing in P_1∩ P_2.

Suppose to the contrary this is not the case.
Then let u and w be the first and last vertices respectively in path P_2 appearing in P_1∩ P_2.
By assumption, u,v,w are all distinct.
By definition, u,v,w appear in that order on P_2.
Since P_2 is a shortest path, by <Ref>, v must appear between u and w on P_1 as well.
This contradicts the definition of v as the first vertex on P_1 lying in the intersection P_1∩ P_2.
    
Thus our original supposition was false, and the paths P_1 and P_2 must agree or be reversing whenever |P_1∩ P_2|≥ 2, which proves the desired result.






  §.§.§ Agreeing and Disagreeing Polynomials


Let  be the enumerating polynomial for the collection of standard pairs of paths ⟨ P_1, P_2⟩ which agree.
Let  be the enumerating polynomial for the collection of standard pairs of paths ⟨ P_1, P_2⟩ which disagree.
Any intersecting paths either agree or disagree, so

    F_∩ =  + .

Thus, to compute F_∩, it suffices to compute  and  separately.



  §.§.§ Agreeing Paths


We first show how to evaluate  efficiently.

 

If paths P_1 and P_2 agree, then they have a common last intersection point, distinct from their common first intersection point.


    Since P_1 and P_2 agree, they have a common first intersection point at some vertex v.
    Then the vertex w∈ P_1∩ P_2 which maximizes (v,w) must be the last node on both paths in P_1∩ P_2.
    Since the paths agree, we have |P_1∩ P_2|≥ 2, so w≠ v.


We say a pair of paths ⟨ P_1,P_2⟩ is edge-agreeing if P_i is an (s_i,t_i)-path in G_i, and P_1 and P_2 traverse a common edge in the same direction.

    
        
        Any edge-agreeing pair is agreeing.
    
    
        Suppose pair ⟨ P_1,P_2⟩ is edge-agreeing.
        
        Let e = (a,b) be a common edge traversed  by both P_1 and P_2.

        Since a,b⊆ P_1∩ P_2, we have |P_1∩ P_2|≥ 2.
        
    So by <Ref>, P_1 and P_2 are either agreeing or reversing.

        Suppose to the contrary that P_1 and P_2 are reversing.
        Let v be the first vertex on P_1 in P_1∩ P_2.
        Then v≠ b, since a appears before b on P_1.
        
        Since the paths are reversing, v is the final vertex on P_2 in P_1∩ P_2.
        Then v≠ a, since b appears after a on P_2.
        Path P_1 passes through v, a, b in that order.
        Then by <Ref>, a must appear between v and b on any shortest path containing these three vertices.
        However, this contradicts the fact that b is between a and v on P_2.

        Thus P_1 and P_2 are not reversing, and so must agree as claimed.
    



    The polynomial  enumerates the collection of edge-agreeing paths in G.


By <Ref>, the set of pairs  enumerates includes all edge-agreeing pairs.

    Let F be the family of standard pairs of paths ⟨ P_1,P_2⟩ such that P_1 and P_2 agree.
    
    By definition,  enumerates F.
    
    By <Ref>, every edge-agreeing standard pair of paths is in F.

    Let S be the collection of pairs which are agreeing but not edge-agreeing.
    To prove the desired result, it suffices to show that the monomials corresponding to pairs in S have net zero contribution to  over a field of characteristic two.

    To that end, take any pair ⟨ P_1,P_2⟩∈S.
    Since ⟨ P_1,P_2⟩ is agreeing, P_1 and P_2 have a unique first intersection point v.
    By <Ref>, these paths also have a unique last intersection point w≠ v.

    Hence, we can decompose the paths into
    
    P_1 = P_1[s_1,v]  P_1[v,w]  P_1[w,t_1]   and   
        P_2 = P_2[s_2,v]  P_2[v,w]  P_2[w,t_2].

    
    Define the paths 
        
    Q_1 = P_1[s_1,v]  P_2[v,w]  P_1[w,t_1]   and   
        Q_2 = P_2[s_2,v]  P_1[v,w]  P_2[w,t_2]

    by swapping the v to w subpaths of P_1 and P_2.

    By <Ref> the Q_i are (s_i,t_i)-shortest paths.

    
        Since P_1 and P_2 are not edge-agreeing, the subpaths P_1[v,w] and P_2[v,w] are distinct.
        

    

    The paths Q_1 and Q_2 have a common first intersection point of v, and so the pair ⟨ Q_1, Q_2⟩ is agreeing.
    Since ⟨ P_1,P_2⟩ is not edge-agreeing, neither is ⟨ Q_1, Q_2⟩.
    Thus ⟨ Q_1,Q_2⟩∈S.
    
        
    
    Finally, if we swap the v to w subpaths of Q_1 and Q_2, we recover P_1 and P_2.

    The above discussion implies that the map Φ from ⟨ P_1, P_2⟩ to ⟨ Q_1, Q_2⟩ described above
    
    
    
    satisfies all conditions of <Ref>, and so  is the enumerating polynomial for F∖S, which is precisely the set of edge-agreeing pairs.





    We have 
        
    = 
            ∑_v∈ V∑_w∈(v)D(v)x_vw^2 R_1(w)R_2(w).



Let F be the family of edge-agreeing pairs.
    By <Ref>, it suffices to show that 
    
    ∑_v∈ V∑_w∈(v)D(v)x_vw^2 R_1(w)R_2(w)

    is the enumerating polynomial for F.
    To that end, the following claim about the individual terms of the above sum will be useful.

    
        
        For any choice of vertices v and w with w∈(v),
        the polynomial
            
    D(v)x_vw^2 R_1(w)R_2(w)

            enumerates all standard pairs of paths ⟨ P_1, P_2⟩ such that P_1 and P_2 overlap at edge e = (v,w), and have common first intersection at vertex v.
    
    
       Take any pair ⟨ P_1,P_2⟩ satisfying the conditions from the statement of the claim.
       Then we can decompose these paths in the form
        
    P_i = P_i[s_i,v] (v,w)  P_i[w,t_i]

        such that the P_i[s_i,v] subpaths  intersect only at v.
        
            This means that the pair ⟨ P_1[s_1,v], P_2[s_2,v]⟩ is enumerated by D(v), the two edges (v,w) are enumerated by x_vw^2, and each path P_i[v,t_i] is enumerated by R_i(v), so that the expansion of the polynomial <ref>
            includes some monomial corresponding to the given pair.

            Conversely, any monomial in the expansion of <ref> is the product of monomials recording the edges traversed by a pair of paths ⟨ A_1, A_2⟩ only intersecting at node v, where A_i is an (s_i,v)-path in G_i, two copies of the edge (v,w), and some (w,t_i)-paths B_i in G_i.
            This product is equal to the monomial given by  
                
    f(A_1 (v,w) B_1, A_2 (v,w) B_2).

            Define the paths P_i = A_i (v,w) B_i for each i∈ [2].
            Since A_i and B_i are paths in G_i, and (v,w) is an edge in both G_1 and G_2, we know that each P_i is an (s_i,t_i)-shortest path.
                
            We claim that A_1 does not intersect B_2.
            Indeed, suppose to the contrary that A_1 and B_2 intersect at some node u.
            Then P_1 is a shortest path which passes through nodes u,v,w in that order, yet P_2 is a shortest path which passes through v,w,u in that order, which contradicts <Ref>.

            Hence A_1 does not intersect B_2.
            Symmetric reasoning shows that A_2 does not intersect B_1.
            
            Thus the paths P_1 and P_2 have common first intersection at v.
            Then the pair P_1,P_2 satisfies the conditions from the claim statement, so the polynomial from <ref> enumerates all pairs of paths described in the claim.
    
    By <Ref>, the sum 
   
    ∑_v∈ V∑_w∈(v)D(v)x_vw^2 R_1(w)R_2(w)

   enumerates all edge-agreeing pairs  whose first intersection point v is the beginning of an edge traversed by both paths in the pair.
   Let H be the set of such pairs, and let S=F∖H.

   We claim that the set of pairs in S has net zero contribution to .
   
   Indeed, take any pair ⟨ P_1, P_2⟩∈S.
    Since the pair is edge-agreeing, by <Ref> the pair is agreeing.
    Hence 
    P_1 and P_2 have a common first intersection at some node v.
    By <Ref>, these paths also have a common last intersection point at some node w≠ v.
    Since the pair is not in S, the subpaths P_1[v,w] and P_2[v,w] are distinct.
    If we swap these subpaths 
    to produce paths 
        
    Q_1 = P_1[s_1,v]  P_2[v,w] P_1[w,t_1]  and   
            Q_2 = P_2[s_2,v] P_1[v,w] P_2[w,t_2]

    then by <Ref> each Q_i is still an (s_i,t_i)-path in G_i.
    
    Since the P_i are edge-agreeing, and this edge-overlap must occur in their v to w subpaths, the  Q_i are also edge-agreeing.
    By assumption, v is not the beginning of a common edge traversed by the P_i, so it is also not such a beginning for Q_i.
    These observations combined show that ⟨ Q_1,Q_2⟩∈S.
    Also, swapping v to w subpaths in the Q_i recover the P_i paths.
    It follows that the map Φ sending ⟨ P_1,P_2⟩ to ⟨ Q_1,Q_2⟩ satisfies all the conditions of <Ref>, so in fact  enumerates F∖S = H.
    
    Since <ref> also enumerates H, this proves the desired result.




  §.§.§ Disagreeing Paths


Let  be the family of disagreeing pairs of paths.
Recall that  enumerates .
Our goal is to show how to efficiently evaluate .
To do this, we describe a subfamily of pairs in , and argue that  enumerates this subfamily.




For each node v, let B̃(v) be the set of standard pairs of paths ⟨ P_1,P_2⟩ intersecting at v, such that 
    if we let a_i and b_i denote the nodes appearing immediately before and after v on P_i respectively, then
    
    
  * a_1≠ a_2, 
    
  * b_1≠ b_2, and 
    
  * a_1≠ b_2.

Let B(v)⊆B̃(v) be the subfamily of such pairs such that v is the first vertex in P_1 lying in P_1∩ P_2.
Then define the collection
    
    B = ⋃_v∈ VB(v).




Next, we prove some lemmas, which will help us prove that to enumerate , it suffices to design enumerating polynomials for B̃(v) for each vertex v. 



    For each vertex v, the  enumerating polynomial for B̃(v) enumerates B(v).


    Fix a vertex v.
    Let S = B̃(v)∖B(v).
    

    Take any pair ⟨ P_1,P_2⟩∈S.
    Let u be the first vertex in P_1 lying in P_1∩ P_2.
    Since the pair is not in B(v), we know that u≠ v.
    
    There are two cases to consider, based off the relative positions of u and v on P_2.

    

  
Case 1: u before v  Suppose that u appears before v in P_2.
    In this case, we  form paths 
        
    Q_1 = P_1[s_1,u] P_2[u,v] P_1[v,t_1]  and   Q_2 = P_2[s_2,u] P_1[u,v] P_2[v,t_2]

    by swapping the u to v subpaths in P_1 and P_2.
    By <Ref>, each Q_i is still an (s_i,t_i)-path in G_i.
    After this subpath swap, the vertices immediately before  v in the Q_i are still distinct, and the vertices immediately after v in the Q_i are still distinct.
    Moreover, the vertex immediately before v in Q_1 is not equal to the vertex immediately after v in Q_2, since these are distinct nodes on  P_2.
    Then by <Ref>, ⟨ Q_1,Q_2⟩∈B̃(v).
    Also, since Q_1 and Q_2 intersect at u, ⟨ Q_1,Q_2⟩∉B(v).
    Finally, since u is the first vertex in Q_1 lying in Q_1∩ Q_2, applying the same subpath swap procedure as above to ⟨ Q_1,Q_2⟩ recovers ⟨ P_1,P_2⟩.
    
    So the map Φ sending ⟨ P_1,P_2⟩ to ⟨ Q_1,Q_2⟩ as above satisfies all conditions of <Ref>.

    

  
Case 2: u after v Suppose that u appears after v on P_2.
        In this case, we form paths 
        
    Q_1 = P_1[s_1,u]P_2[u,v] P_1[v,t_i]  and   
            Q_2 = P_2[s_1,v]P_1[v,u] P_2[u,t_i]

    by swapping the u to v subpaths in P_1 and P_2 (and using the fact that G is undirected, so we can traverse the edges in these subpaths backwards).
    Since the u to v subpaths of P_1  and P_2 both have length (u,v), each path Q_i has the same length as P_i, and is thus still an (s_i,t_i)-path in G_i.

    Let a_i and b_i denote the vertices on P_i immediately before and after v respectively.

    
    Then the nodes immediately before and after v on Q_1 are b_2 and b_1 respectively, and the nodes immediately before and after v on Q_2 are a_2 and a_1.
    
    We know that b_i≠ a_i, since a_i and b_i are distinct vertices on the path P_i.
    Thus ⟨ Q_1,Q_2⟩ satisfies the first two conditions from <Ref>.
    
    Since ⟨ P_1,P_2⟩∈S, by condition three of <Ref>, we know that b_2≠ a_1.
    Since b_2 is the node immediately before v in Q_1 and a_1 is the node immediately after v in Q_2, we see that ⟨ Q_1,Q_2⟩ satisfies condition three of <Ref> as well.
    
Thus  ⟨ Q_1,Q_2⟩∈B̃(v).

    Furthermore, since u∈ Q_1∩ Q_2 appears before v in Q_1, we have Q_1,Q_2∉B(v).

    Thus Q_1,Q_2∈S.

    This shows that the swapping procedure described above, sending P_1,P_2 to Q_1,Q_2, is a map from S to itself.
    Moreover, because u is the first vertex on P_1 lying in P_1∩ P_2 and the first vertex on Q_1 lying in Q_1∩ Q_2, performing the above swapping procedure on Q_1,Q_2 recovers P_1,P_2.
    Finally, since the multisets of edges traversed by P_1,P_2 and Q_1,Q_2 are the same, we have 
        
    f(P_1,P_2) = f(Q_1,Q_2).

    The above discussion shows that S can be partitioned into groups of size two, with each group consisting of two pairs with the same monomial.
    Then the monomials from pairs in S have net zero contribution to the enumerating polynomial for B̃(v) modulo two.
    
    Hence the enumerating polynomial for B̃(v) actually enumerates B̃(v)∖S = B(v), as claimed.






    The enumerating polynomial for B is .


    First, observe that B.
    Indeed, suppose ⟨ P_1,P_2⟩∈ is a standard pair of paths which disagree.
    Let v be the first vertex of P_1 in P_1∩ P_2.
    Let a_i and b_i be the vertices immediately before and after v in P_i.
    Then a_1∉a_2,b_2 by the definition of v, and b_1≠ b_2 because P_1 and P_2 disagree.
    Thus ⟨ P_1,P_2⟩ satisfies all the conditions from <Ref>, so this pair is in B.
    Since we chose an arbitrary pair ⟨ P_1,P_2⟩ from , we have B as claimed.

    Let S = B∖ be the set of agreeing pairs in B.

    Take any pair ⟨ P_1,P_2⟩∈S.
    Let v be the first common intersection point of the pair.
    Let w be the last common intersection point of the pair.
    By <Ref>, w≠ v.
    For each i∈ [2], let
        
    Q_i = P_i[s_i,v] P_i[v,w] P_i[v,t_i]

    be the paths formed by swapping the v to w subpaths in P_1 and P_2.

    We claim that ⟨ Q_1,Q_2⟩∈S as well.

    
    By <Ref> each Q_i is still an (s_i,t_i)-path in G_i.
    The first and last intersection points of these paths are still v and w, so the new pair is still agreeing.
    
    Let vertices a_i and b_i be vertices immediately before and after v on each P_i respectively.
    Since the a_i occur before v, the nodes before v on Q_1 and Q_2 are distinct.
    Since the nodes after v on Q_1 and Q_2 are b_1, b_2, these nodes are also distinct.
    Finally, the node before v on Q_1 is a_1  and the node after v on Q_2 is b_1, and a_1≠ b_1 since a_1 and b_1 are distinct vertices on path P_1, the node before v on Q_1 and after v on Q_2 are distinct.
    
    The discussion in the previous paragraph shows that ⟨ Q_1,Q_2⟩∈S.

    Finally, if we apply the subpath swapping procedure above to ⟨ Q_1,Q_2⟩, we recover ⟨ P_1,P_2⟩.
    Then the map Φ on S sending ⟨ P_1,P_2⟩ to ⟨ Q_1,Q_2⟩ satisfies the conditions from the statement of <Ref>, so the enumerating polynomial for B in fact enumerates B∖S = as claimed.


By <Ref>, enumerating  reduces to enumerating ℬ̃(v) for each vertex v.
Our next goal is to  perform this enumeration efficiently.
To do this, we start by defining and establishing formulas for  some additional helper polynomials.



For each vertex v, let T(v) be the enumerating polynomial for the set of pairs of paths ⟨ P_1,P_2⟩ where 

    
  * each P_i is a (v,t_i)-path in G_i, and
    
  * the second nodes of P_1 and P_2 are distinct.
 




    For each vertex v, we have 
       
    T(v) = R_1(v)R_2(v) - ∑_w∈(v)x_vw^2R_1(w)R_2(w).



    This follows from symmetric reasoning to the proof of <Ref>.




    For each vertex v, let H(v) be the enumerating polynomial for the set of standard pairs of paths ⟨ P_1,P_2⟩ intersecting at v, such that the vertex immediately before v on P_1 is the same as the vertex immediately after v on P_2.


Intuitively, H(v) is a polynomial we use to enforce the a_1≠ b_2 condition from <Ref>.



    For each vertex v, we have 
    
    
    H(v) = ∑_u∈(v) L_1(u)x_uvR_1(v)L_2(v)x_vuR_2(u).



For any pair of paths ⟨ P_1,P_2⟩ satisfying the conditions from <Ref>, there exists a unique vertex u such that u appears immediately before v on P_1 and immediately after v on P_2.
Any such u must lie in ^1(v)∩^2(v) = (v) by definition.

Given v∈ V and u∈(v),
let F(u,v) be the set of all standard pairs of paths ⟨ P_1,P_2⟩ such that P_1 traverses edge (u,v) and P_2 traverses edge (v,u).
The discussion in the previous paragraph implies that to prove the lemma, it suffices to show that the polynomial 

    L_1(u)x_uvR_1(v)· L_2(v)x_vuR_2(u)

enumerates F(u,v) for all v and u.

To that end, let P_1,P_2∈F(u,v).
We claim the monomial f(P_1,P_2) appears in the expansion of <ref>.
Indeed, by definition, we can split 
    
    P_1 = P_1[s_1,u] (u,v) P_1[v,t_1]  and  
        P_2 = P_2[s_2,v] (v,u) P_2[u,t_2].

Then path P_1[s,u] is enumerated by L_1(u), edge (u,v) is enumerated by x_uv, path P_1[v,t_1] is enumerated by R_1(v), path P_2[s,v] is enumerated by L_2(v), edge (v,u) is enumerated by x_vu, and path P_2[u,t_2] is enumerated by R_2(u), so the expansion of <ref> has the term f(P_1,P_2).

Conversely, we claim that any monomial in the expansion of <ref> corresponds to a pair of paths in F(u,v).
Indeed, any such monomial is the product of monomials from each of the factors in <ref>.
By definition, L_1(u) enumerates (s_1,u)-paths A_1 in G_1, R_1(v) enumerates (v,t_1)-paths B_1 in G_1, L_2(v) enumerates (s_2,v)-paths A_2 in G_2, and R_2(u) enumerates (u,t_2)-paths B_2 in G_2.
So an arbitrary monomial in <ref> is of the form 
    
    f(A_1)x_uvf(B_1)· f(A_2)x_vuf(B_2)

for A_i and B_i satisfying the conditions above.

Since u∈(v), if we define paths 
    
    P_1 = A_1 (u,v) B_1  and   P_2=A_2 (v,u) B_2

then we see that P_i is an (s_i,t_i)-path in G_i.
Moreover, P_1 traverses (u,v) and P_2 traverses (v,u).
So P_1,P_2∈F(u,v), and since 
    
    f(P_1,P_2) = f(P_1)· f(P_2) = f(A_1)x_uvf(B_1)· f(A_2)x_vuf(B_2)

we get that monomials of <ref> correspond to pairs in F(u,v).
Thus <ref> enumerates F(u,v).

By the discussion at the beginning of the proof, this proves the claim.




    We have 
    
    = ∑_v∈ VD(v)T(v) - H(v) .



    By <Ref>,  is the enumerating polynomial for B.
    By <Ref>, the enumerating polynomial for B is the sum of the enumerating polynomials for B(v) over all vertices v
    (here, we are using the fact that the B(v) are disjoint for each v by definition).
    Applying <Ref>, we see this sum is equal to the sum of the enumerating polynomials for B̃(v) over all vertices v.
    So, it suffices to show that for each vertex v, the polynomial
        
    D(v)T(v) - H(v)

    enumerates B̃(v).

    By <Ref>, the polynomial D(v) enumerates all pairs ⟨ A_1,A_2⟩ where each A_i is an (s_i,v)-path in G_i, and the vertices a_i immediately before v in A_i are distinct.
    By <Ref>, the polynomial T(v) enumerates all pairs ⟨ B_1,B_2⟩ where each B_i is a (v,t_i)-path in G_i, and the  vertices b_i after v in B_i are distinct.
    
    Then the product D(v)T(v) enumerates all pairs of paths 
    ⟨ A_1 B_1,A_2 B_2⟩
 for A_i and B_i satisfying the conditions from the previous paragraph.
    Note that this pair satisfies conditions 1 and 2 from <Ref>.
    Moreover, any standard pair of paths ⟨ P_1,P_2⟩ satisfying conditions 1 and 2 from <Ref> can be decomposed into 
        
    P_i = A_i B_i

    where A_i is an (s_i,v)-path in G_i, B_i is a (v,t_i)-path in G_i, the penultimate vertices of the A_i  are distinct, and the second vertices of the B_i are distinct.

    Thus D(v)T(v) enumerates precisely all standard pairs of paths satisfying the first two conditions from <Ref>.

    By <Ref>, H(v) enumerates the standard pairs of paths ⟨ P_1,P_2⟩ intersecting at v, such that the node immediately before v on P_1 is the same as the node immediately after v on P_2.
    If we let a_i and b_i again denote the nodes immediately before and after v on P_i respectively, this means we are enumerating all standard pairs of paths intersecting at v such that a_1 = b_2.
    Note that all such paths also have a_1≠ a_2 (since a_2 and b_2 are distinct nodes in P_2) and b_1≠ b_2 (since a_1 and b_1 are distinct nodes in P_1).

    Thus H(v) enumerates precisely the standard pairs of paths which satisfy the first two conditions but fail the third condition of <Ref>.

    Consequently, the difference <ref> enumerates the standard pairs of paths which satisfy all conditions from <Ref>.
    Thus the polynomial from <ref>   enumerates B̃(v) as claimed, which proves the desired result.














    



We are finally ready to prove our main theorem.
Note that the first part of the proof is completely identical to the proof of <Ref>, since our algorithms for  in DAGs and undirected graphs have the same overall structure.

*


    Each pair of internally vertex-disjoint paths produces a distinct monomial in F_.
    It follows that disjoint (s_i,t_i)-shortest paths exist in G if and only if F_ is nonzero as a polynomial.

    So we can solve  as follows.
    We assign each x_uv variable an independent, uniform random element of 𝔽_2^q, and then evaluate F_ on this assignment.
    If the evaluation is nonzero we return YES (two disjoint shortest paths exist), and otherwise we return NO.
    
    If two disjoint shortest paths do not exist, then F_ is the zero polynomial, and our algorithm correctly returns NO.
    If two disjoint shortest paths do exist, then F_ is a nonzero polynomial of degree strictly less than 2n, so by Schwartz-Zippel (<Ref>) our algorithm correctly returns YES with high probability for large enough q = O(log n).

    It remains to show that we can compute F_ in linear time.

        First, we can compute G_1 and G_2 in linear time by <Ref>.

            Then, by dynamic programming forwards and backwards over the topological order of G, we can evaluate the polynomials  L_i(v)   and R_i(v) for each i∈1,2 and vertex v at our given assignment in linear time, using the recurrences from <Ref>.


    
    
    Having computed these values, <Ref> shows that for any vertex v we can compute D(v) and T(v) at the given assignment in O(_in(v)) and O(_out(v)) time respectively.
    So we can evaluate D(v) and T(v) for all v in O(m) time.

    Then by <Ref>, we can evaluate  in O(m) time.

    By <Ref>, we can compute H(v) at any given vertex v in O(_in(v)) time.
    So we can evaluate H(v) for all vertices v in O(m) time.

    From the values for D(v), T(v), and H(v), by <Ref> we can compute  in O(n) time. 

    Having computed  and , by <ref> we can compute F_∩ as well in O(1) time.

    Finally, given the value of F_∩, we can evaluate F_ in O(1) additional time by <Ref>.

     Thus we can solve  in linear time.
    



 §.§ Search to Decision Reduction

*




    The proofs of <Ref> construct arithmetic circuits of size O(m) for the two disjoint shortest paths polynomial F_ for DAGs and undirected graphs.
    By the Baur-Strassen theorem (see <cit.> for the original proof, and <cit.> for a more recent exposition), we can construct arithmetic circuits of size O(m) which simultaneously compute all single-order partial derivatives of F_.

    Given an edge (u,v), the polynomial (∂ /∂ x_uv)  F_ is nonzero if and only if  edge (u,v) appears in some solution to the  problem.
    So by Schwartz-Zippel (<Ref>), with high probability,  (∂ /∂ x_uv)  F_ has nonzero evaluation at a uniform random assignment over 𝔽_2^q if and only if (u,v) is an edge occurring in some pair of disjoint shortest paths, for q = O(log n) sufficiently large.

    We can compute all partial derivatives at some random evaluation point in O(m) time using the arithmetic circuit for these polynomials.
    We pick an edge (s_1, v) such that (∂ /∂ x_s_1v)  F_ has nonzero evaluation.
    Then we delete vertex s_1 from G, and consider a smaller instance of  on the graph, where source s_1 is replaced with v.
    We can repeat this process on the new instance, to find the first edge on a (v,t_1)-shortest path which is disjoint from some (s_2,t_2)-shortest path.
    Repeating this process at most n times, we can recover an (s_1,t_1)-shortest path P_1, which is disjoint from some (s_2,t_2)-shortest path.
    
    At this point, we just delete all vertices of P_1 from the original graph G, find an (s_2,t_2)-shortest path P_2 in the resulting graph in linear time, and then return ⟨ P_1,P_2⟩ as our answer.

    Overall, we compute at most n evaluations of arithmetic circuits of size O(m), so the algorithm runs in O(mn) time.





§ EDGE-DISJOINT PATHS ALGORITHM


In this section, we present our algorithm for  in weighted DAGs and prove <Ref>. 
The algorithm works by constructing a large graph on n^k nodes, whose paths correspond to collections of edge-disjoint paths in the original graph.
As we previously mentioned in <Ref>, our algorithm uses the same framework as that of <cit.>.

Throughout this section, we let G be the input DAG on n nodes and m edges.
For each i∈ [k], we let G_i denote the s_i-shortest paths DAG of G.






    Fix a topological order (≺) of G.
    
    We construct a graph G' on n^k nodes, whose paths encode k-tuples of paths in G.

    The graph G' has a node for each k-tuple of vertices from G.

    Given a node v⃗ = (v_1, …, v_k) in G' (where each v_i is a vertex in G), let v = (v⃗) be the unique vertex v such that 
        
            
  * v = v_i for some index i∈ [k], and 
            
  * v≼ v_j for all j∈ [k].
        
    In other words, (v⃗) is the earliest coordinate of v⃗ with respect to the topological order of G.
    Let I(v⃗) denote the set of indices i∈ [k] such that v_i = (v⃗).
    Then we include an edge from node v⃗ = (v_1, …, v_k) to node w⃗ = (w_1,…, w_k) in G' precisely when 

    
        
  * for all i∈ I(v⃗), the pair (v_i,w_i) is an edge in G_i,
        
  * the vertices w_i are pairwise distinct over all i∈ I(v⃗), and 
        
  * for all j∉I(v⃗), we have w_j = v_j.
    
        We refer to the rules above as the conditions for edges of G'.
    Intuitively, the conditions say that we can move from a node v⃗ consisting of k vertices v_i by stepping from all of the earliest vertices to new distinct vertices.
    An example of these edge transitions is depicted in <Ref>.


    Let s⃗ = (s_1, …, s_k) and t⃗ = (t_1, …, t_k) be nodes in G' containing all of the source and target vertices in G respectively.
    As the following lemmas show, our conditions for including edges in G' allow us to relate paths from s⃗ to t⃗ in G' to solutions to the  problem in G.



    
        
        If G contains edge-disjoint (s_i,t_i)-shortest paths, then G' contains a path from s⃗ to t⃗.
    
    
        For i∈ [k], let P_i  be (s_i,t_i)-shortest paths in G which are all edge-disjoint.
        We show how to simultaneously traverse these paths P_i to recover a path in G' from s⃗ to t⃗.

                Initialize P ←⟨s⃗ ⟩ and  v⃗←s⃗.

        Suppose v⃗ = (v_1, …, v_k).
        Define the new node w⃗ = (w_1, …, w_k) in G' by setting w_i to be the node after v_i on P_i for each i∈ I(v⃗), and setting w_j = v_j for all j∉I(v⃗).
        Then append w⃗ to P, and update v⃗←w⃗.

        Repeat the process in the above paragraph until v⃗ = t⃗.
        We claim this procedure halts and produces a path P from s⃗ to t⃗ in G'.

        Indeed, an easy induction argument shows that the value of v⃗ = (v_1, …, v_k) always has the property that v_i is a vertex in P_i, and each step strictly decreases the value of 
            
    ∑_i=1^k (v_i,t_i).

        The above quantity is a nonnegative integer, and so stops decreasing once it reaches zero, at which point we must have v⃗ = t⃗.
        Moreover, our procedure is designed so that each step from a node v⃗ to a node w⃗ on P satisfies conditions 1 and 3 for edges in G'.
        Condition 2 for edges in G' is also satisfied, because the P_i are edge-disjoint, so P is a valid path in G' as desired.
    
    

    
        
        If G' contains a path form s⃗ to t⃗, then G contains edge-disjoint (s_i,t_i)-shortest paths.
    
    
        Let P be a path from s⃗ to t⃗ in G'.
        We show how to recover edge-disjoint paths in G by reading off the edges traversed in P.

        Initialize v⃗←s⃗. 
        For each i∈ [k], initialize P_i ←⟨ s_i⟩.

        Suppose v⃗ = (v_1, …, v_k).
        Let w⃗ = (w_1, …, w_k) be the node after v⃗ on P.
        For each index i with w_i≠ v_i, append w_i to P_i.
        Then update v⃗←w⃗.

        Repeat the process in the above paragraph until v⃗ = t⃗.
        We claim this procedure produces edge-disjoint shortest paths P_i from s_i to t_i.

        Indeed, an easy induction argument shows that at any time in the procedure, the i^th coordinate of v⃗ is the last vertex in path P_i.
        Since v⃗ begins at s⃗ and ends at t⃗, and G is a DAG, each P_i is an (s_i,t_i)-path.
        By condition 1 of edges in G', any edge (v⃗,w⃗) in G' which changes the value of the i^th coordinate must change that coordinate by stepping along an edge lying in a shortest path from s_i.
        It follows that each P_i is an (s_i,t_i)-shortest path.

        It remains to prove that the P_i are edge-disjoint.
        Suppose to the contrary that some of these paths overlap at some edge. 
        Without loss of generality, suppose paths P_1 and P_2 overlap at some edge (a,b).

        Let v⃗ = (v_1, …, v_k) be the last node in P which has v_1 = a as its first coordinate. 
        Such a node exists since P_1 passes through a.
        By condition 3 for edges in G', we must have a = (v⃗).
        We claim that v_2 = a as well.

        Suppose v_2≠ a.
        Then since a = (v⃗), we must have v_2 ≻ a.
        
        In this case, define u⃗ to be the last node in P which has u_2 = a as its second coordinate.
        Such a node exists since P_2 passes through a.
        By condition 3 for edges in G', we have a = (u⃗).
        
        By the assumption that v_2≻ a and condition 1 for edges of G', node u⃗ occurs before v⃗ in P.
        Then since v_1 = a, by condition 1 for edges of G', the first coordinate u_1 of u⃗ must satisfy u_1≼ a.
        Since a = (u⃗), this forces u_1 = a = (u⃗).

        Since u_1 = (u⃗),
        by conditions 1 and 2 for edges in G', all nodes in P after u⃗ cannot have first coordinate equal to a.
        This contradicts the fact that u⃗ occurs before v⃗ in P.
        So our initial assumption was false, and in fact v_2 = a as claimed.

        Let w⃗ = (w_1, …, w_k) be the node after v⃗ on P.
        Since v_1 = v_2 = (v⃗), by condition 2 for edges of G' we have w_1≠ w_2.
        Our procedure for constructing the paths P_i from P has P_1 traverse edge (a,w_1) and P_2 traverse edge (a,w_2).
        Since w_1 and w_2 distinct, this contradicts the assumption that paths P_1 and P_2 both traverse edge (a,b).

        It follows that our original assumption was false, and the paths P_i are edge-disjoint as claimed.
        This completes the proof.   
    





*


    First, we compute a topological order of G in linear time.
    Then we compute the s_i-shortest paths DAGs G_i of G for all i∈ [k], which takes linear time by <Ref>.

    By <Ref>, we can solve  on G by constructing the graph G' described in 
    
    this section,
    and checking whether this graph contains a path from s⃗ to t⃗.
    Checking whether there is a path from s⃗ to t⃗ takes time linear in the size of G', so to prove the theorem, it suffices to show that we can construct G' in O(mn^k-1) time.


    We can construct all nodes of G' in O(n^k) time.
    We then go through each node v⃗ in G, and add in edges from v⃗ to w⃗ in the out-neighborhood of v⃗ according to the three conditions.
    Each addition of an edge takes O(1) time, so it suffices to show that G' has O(mn^k-1) edges.

    Consider a node v⃗ in G.
    Let v = (v⃗) be the earliest coordinate of v⃗, and let ℓ = |I(v⃗)| denote the number of coordinates in v⃗ equal to this earliest vertex.
    There are at most n^k-ℓ choices for the coordinates of v⃗ not equal to v.
    By conditions 1 and 3 for edges in G', the node v⃗  can have edges to at most (v)^ℓ nodes in G'.

    Summing over all possible values for ℓ = |I(v⃗)| and v=(v⃗), we see that the number of edges in G' is bounded above by 
        
    ∑_ℓ=1^k∑_v∈ V  n^k-ℓ(v)^ℓ = ∑_ℓ=1^k∑_v∈ Vn^k-ℓ(v)^ℓ-1·(v).

    Substituting the inequality (v)≤ n in the right hand side above, we see that the number of edges in G' is at most 
    
    ∑_ℓ=1^k∑_v∈ Vn^k-ℓ· n^ℓ-1·(v) = kn^k-1∑_v∈ V(v) = kmn^k-1.

    For constant k, the above expression is O(mn^k-1), which proves the desired result.




§ LOWER BOUNDS






 §.§ Disjoint Shortest Paths


Our goal in this section is to prove the following theorem. 

*






  
Construction

Let G = V_1⊔…⊔ V_k be the input instance of .

Order each of the vertices in each V_i.
Order the set of all vertices V in the graph, by putting all vertices of V_i before vertices of V_j for i < j (and within a part V_i using the order of V_i).
For each index i, let V̅_i = V∖ V_i.
The order on V induces an order on each V̅_i as well.

We now produce an instance G' of , depicted in <Ref>.



For each i∈[k], graph G' has a source node s_i and a target node t_i.

For each choice of vertices v,w from different parts, we introduce node v(w) in G'.


For every vertex v∈ V_i, the graph G' includes a path P(v) from s_i to t_i, whose internal nodes are all the nodes  of the form v(w) where w∈V̅_i, traversed according to the order of V̅_i.

Finally, for each pair (v,w) which is not an edge in G, we identify the nodes v(w)=w(v) in G'.

This completes the construction of G'.



  
Correctness

To prove our reduction is correct, we characterize shortest paths in G'.



    The (s_i,t_i)-shortest paths in G' are precisely the P(v) paths for vertices v∈ V_i.


Fix i∈[k].

Given a vertex w∈V̅_i, let (w) denote the position of w in V from the end of this list.
For example, if w is the final vertex in V_i we set (w) = 1, and if w is the first vertex in V̅_i, we set (w) = |V̅_i| = (k-1)n.

Given nodes a and b in G', in this proof we let (a,b) denote the distance from a to b in G'.



    For every v∈ V_i and w∈V̅_i,
    we have 
    
    (v(w),t_i) ≥(w)  and  (w(v),t_i)≥(w).



    We prove the inequalities by induction on the value of (w).

    For the base case, suppose (w) = 1.
    Then v(w)≠ t_i and w(v)≠ t_i, so the distance from these nodes to t_i is at least 1 as claimed.

    For the inductive step, suppose now that (w) ≥ 2, and we have already proven the claim for all vertices occurring after w in V̅_i.
    
    
    
    
    
    
    The only edges exiting v(w) and w(v) come from the paths P(v) and P(w).
    We consider these two cases separately below.

Suppose we take a path from v(w) or w(v) which begins with an edge from P(v).
Let w' be the node after w in V̅_i.
Then v(w') is the second vertex in this path.
By the induction hypothesis, 

    (v(w'),t_i) ≥(w') = (w)-1.

By the above equation, any path from v(w) or w(v) to t_i in this case has length at least 
    
    (v(w'),t_i) + 1  ≥(w).


Suppose now instead that we take a path from v(w) or w(v) to t_i which begins with an edge from P(w).
No such path exists if v is the final vertex in V_i, so we may assume that v is not the final vertex in V_i.
Let v' be the vertex after v in V_i.
Then w(v') is the second vertex in our path.
By the induction hypothesis, 

    (w(v'),t_i)≥(w)

which implies that the path in this case has length at least (w) as well.

So in either case, <ref> holds.
This completes the induction, and proves the desired result.


By <Ref>, for any v∈ V_i and w∈V̅_i we have 
    
    (v(w),t_i)≥(w).


The v(w) to t_i subpath of P(v) shows that (v(w),t_i)≤(w), so in fact we have 
    
    (v(w),t_i)= (w).


Now, every out-neighbor of s_i is of the form v(w^⋆), where v∈ V_i and w^⋆ is the first node in V̅_i.
Then by the above discussion,
    
    (s_i,t_i) = |V̅_i| + 1.

This immediately implies that for all v∈ V_i, each P(v) is an (s_i,t_i)-shortest path.

It remains to show that these are the only (s_i,t_i)-shortest paths in G'.

To that end, let Q be an (s_i,t_i)-shortest path in G'.
Then the the second vertex in Q is of the form v(w^⋆), for v∈ V_i and w^⋆ defined as above.
Let w be the last vertex in V̅_i with the property that the s_i to v(w) subpaths of Q and P(v) agree.

Suppose w is not the final vertex in V̅_i.
In case, immediately after v(w), path Q must traverse an edge of P(w).

If v is the final vertex in V_i, then this edge brings Q to a node of the form w(v'), where v'∈ V_j for some j > i.
However, there is no path from such a node w(v') to t_i.
Since we assumed Q is a path to t_i, this case cannot occur.

So v is not the final vertex in V_i.
Let v' be the vertex after v in V_i.

Then using the edge of P(w), Q goes from node v(w) to w(v').
By <Ref>, we know that 
    
    (w(v'),t_i)≥(w).


So the w(v') to t_i subpath of Q has length at least (w).

However, we know that P(v) and Q agree up to v(w), so the s_i to v(w) subpath of Q has length 
    
    |V̅_i| - (w) + 1.

    
The path Q consists of these two subpaths and the edge from v(w) to w(v').

Thus, Q has length at least 

    |V̅_i| - (w) + 1 + 1 + (w) = |V̅_i| + 2


which is greater than (s_i,t_i) by <ref>.

This violates the definition of Q as a shortest path.
So w must be the final vertex in V̅_i, which forces Q = P(v).
So all (s_i,t_i)-shortest paths in G' are of the desired form.



We are now ready to prove our lower bound for .






*

    Let G = V_1⊔…⊔ V_k instance of .
    Construct the graph G' defined in this section in O((kn)^2) time.
    By definition, G' has O((kn)^2) nodes.
    
    We claim that G contains a k-clique if and only if G' contains disjoint (s_i,t_i)-shortest paths.

    Indeed, suppose G contains a clique of the form (v_1, …, v_k)∈ V_1×…× V_k.
    
    Take the P(v_i) paths.
    By <Ref> these are (s_i,t_i)-shortest paths.
    
    The internal nodes of P(v_i) are of the form v_i(w), for w∈V̅_i.
    
    Thus the only way paths P(v_i) and P(v_j) could intersect for i≠ j is if v_i(v_j) = v_j(v_i) in G'.
    However, vertices v_i and v_j belong to a clique, which means (v_i,v_j) is an edge in G, so v_i(v_j)≠ v_j(v_i).

    Hence the P(v_i) are vertex-disjoint paths.

    Conversely, suppose G' contains disjoint (s_i,t_i)-shortest paths.
    By <Ref>, these paths are of the form P(v_i) for some vertices v_i∈ V_i.
    Since these paths are vertex-disjoint, we must have v_i(v_j)≠ v_j(v_i) for all i≠ j.
    This means that (v_i,v_j) are edges in G for all i≠ j.
    
    Thus (v_1,…, v_k) forms a clique in G, which proves the desired result.    
















    








 §.§ Disjoint Paths


Our goal in this section is to prove the following theorem.

*

To establish these reductions, we first introduce the notion of a covering family of increasing lists, and then apply the construction of such a family to the reduction framework of <cit.>.






  §.§.§ Covering Pairs with Lists









    Given a positive integer k, we say a collection of lists L of increasing integers is a k-covering family if for all integers i,j with 1≤ i<j ≤ k, the integers i and j appear as consecutive members of some list in ℒ.
    We let λ(k) denote the minimum possible number of lists in a k-covering family.




The following lemma lower bounds the minimum possible size of a k-covering family. 


    
        We have λ(k)≥⌊ k^2/4⌋.


Partition the set of the first k positive integers into sets 
    
    [k] = A⊔ B

of consecutive positive integers 
    
    A = [1, ⌊ k/2⌋]   and   B = [⌊ k/2⌋ + 1, k]

of size ⌊ k/2 ⌋ and ⌈ k/2 ⌉ respectively. 
We claim that it cannot be the case that for a,a'∈ A and b,b'∈ B both (a,b) and (a',b') appear consecutively in the same list L. 
This is because L must be increasing, so both a and a' must appear before both b and b' in L. 
This means that whichever of a or a' appears first, cannot appear consecutively with b or b'.

It follows that the number of lists needed to cover all pairs (i,j)∈ [k]^2 with i<j is at least 
    
    |A||B| = ⌊ k/2⌋⌈ k/2⌉ = ⌊ k^2/4⌋

    
    as claimed.


In light of <Ref>, the following lemma shows that we can efficiently construct a minimum size k-covering family (and that λ(k) = ⌊ k^2/4⌋).
This construction will be helpful in designing a reduction from .
The proof of this lemma is due to an anonymous reviewer. 


    
    There is an algorithm which, given a positive integer k, runs in O(k^3) time and constructs a 
     k-covering family ℒ of ⌊ k^2/4⌋ lists with elements from [k], with the property that each integer in [k] appears in fewer than k lists of ℒ.


 

    For each pair (a,d) of positive integers with d≤ k-1 and a≤min(d,k-d), define L_a,d to be the list of positive integers in [k] whose (j+1)^st term is (a+jd) for each j≥ 0.
    Let ℒ be the collection of all the L_a,d lists, for the pairs (a,d) satisfying the aforementioned conditions. 

    We claim that any integer x∈ [k] shows up in fewer than k lists of ℒ.
    This is because for any d∈ [k-1], we have x∈ L_a,d only if a≡ x d.
    Since a∈ [d], this means that for each d, there is at most one a for which x∈ L_a,d.
    Since d∈ [k-1] takes on fewer than k values,  x appears in fewer than k lists of ℒ.

    We now show that ℒ is a k-covering family.
    Take arbitrary integers i,j∈ [k] with i < j.
    
    Set d = j-i, and take a to be the smallest positive integer with a≡ i d.
    
    By construction, a≤ d.
    Moreover, we have a+d≤ i+d = j≤ k, so a≤ k-d as well.
    So the pair (a,d) corresponds to a list L_a,d.
    Then i and j are both in L_a,d because j≡ i≡ a d.
    Finally, because d = j-i, we know that i and j are consecutive elements in L_a,d.
    So ℒ is a  k-covering family as claimed.

    The number of lists in ℒ is 
        
    ∑_d=1^k-1min(d,k-d) = ∑_d=1^⌊ k/2⌋ d + ∑_d=⌊ k/2⌋ + 1^k-1 (k-d).


    We now perform casework on the parity of k.

    Case 1: k is even

        If k is even, we can write k=2ℓ for some positive integer ℓ.
        Then <ref> simplifies to
            
    (1 + 2 + … + ℓ) + (1 + 2 + … + ℓ-1) = ℓ(ℓ+1)/2 + ℓ(ℓ-1)/2 = ℓ^2 = ⌊ k^2/4⌋.


        Case 2: k is odd

    If k is odd, we can write k=2ℓ+1 for some positive integer ℓ.
    Then <ref> simplifies to

        
    (1 + 2 + … + ℓ) + (1 + 2 + … + ℓ) = ℓ^2 + ℓ = ⌊ k^2/4⌋.


    In either case, we get that the number of lists in ℒ is ⌊ k^2/4⌋ as claimed.

    We can easily construct ℒ in O(k^3) time by going through each of the O(k^2) pairs (a,d) defining a list L_a,d and then listing its at most O(k) elements by starting at a, and incrementing by d until we reach an integer greater than k.
    This completes the proof of the lemma. 





















        


    


    



    


    


    




    
    


    





















    





















    





    




    





    




















    

   





   


































































  §.§.§ The Reduction







    Let G = V_1⊔…⊔ V_k be an instance of  on kn vertices.
    
    We assume n≥ 2, since otherwise the problem is trivial.

    Set λ = ⌊ k^2/4⌋.
    By <Ref>, there exist a collection L of λ increasing lists of integers from [k], such that for every choice of i,j∈ [k] with i < j, the integers i and j appear as consecutive elements in some list of L.
    Moreover, we can construct L in O(1) time for constant k.
    We give this collection of lists some arbitrary order.
    
    Given i∈ [k], let l(i) denote the number of lists in L containing i.
    



    

    Vertex Gadgets

    

    For each i∈ [k] and  vertex v∈ V_i, we construct a gadget graph G_v as depicted in <Ref>.
    
    For every r∈ [l(i)], we include nodes a_r(v) and b_r(v).
    
    We call the a_r(v) and b_r(v) the top and bottom nodes of G_v respectively.
    
    For every r∈ [l(i)], we include edges e_r(v) = (a_r(v), b_r(v)).
    For each r∈ [l(i)-1], we include  edges from a_r(v) to a_r+1(v) and from b_r(v) to b_r+1(v).
    
    This completes the description of G_v.
    
    For convenience, if L is the r^th list containing v, we write a_L(v) = a_r(v) and b_L(v) = b_r(v).


    

    Arranging Gadgets in Rows


    

    For each i∈ [k], we list the vertices of V_i in some arbitrary order
        
    v_i,1, …, v_i,n.




    For every j∈ [n-1], we connect G_v_i,j to G_v_i,j+1 by  including edges from 
    
    a_l(i)(v_i,j) to a_1(v_i,j+1)  and   b_l(i)(v_i,j) to b_1(v_i,j+1).

    
    For every j∈ [n-2], we additionally include the edge  from a_l(i)(v_i,j) to b_1(v_i,j+2), which we call the  skip edge for v_i,j+1, because traversing this edge corresponds to skipping the gadget for v_i,j+1.
    Skip edges are depicted with dashed lines in <Ref>.
    We view this construction as arranging the G_v gadgets for all v∈ V_i in the “i^th row of G'.”



    

    Terminal Vertices Checking Nodes


    We now introduce source and target nodes and describe how they connect to the G_v gadgets.

For each i∈ [k], we introduce new vertices s_i and t_i.

    We include edges from s_i to a_1(v_i,1) and from b_l(i)(v_i,n) to t_i.

    Additionally, we include skip edges from s_i to b_1(v_i,2) and from a_l(i)(v_i,n-1) to t_i (traversing these edges corresponds to skipping G_v_i,1 and G_v_i,n respectively).

        

    Paths Between Rows of Gadgets
For every choice of indices x,y∈ [k] with x<y, list L∈L covering (x,y), and vertices u∈ V_x  and w∈ V_y such that (u,w) is an edge in G, we include a path 
        Π_L(u,w) of length 2(y-x) - 1 from b_L(u) to a_L(w) in G'.
    These paths encode adjacency information about G.
    We say the Π_L(u,w) are the paths between rows corresponding to list L.
    

    

    Terminal Vertices Checking Edges


    For each list L in our collection, we introduce source node s_L and target node t_L.
    
    Suppose i is the first element in L.
    Then for all v∈ V_i, we have edges from s_L to a_L(v).

    Suppose j is the final element in L.
    Then for all v∈ V_j, we have edges from a_L(v) to t_L.

    We observe that any (s_L,t_L)-path in G' must  pass through nodes in row i of G' for all i∈ L.

    This completes our construction of the graph G', an example of which is depicted in <Ref>.
    
    We claim that G' has disjoint paths from its sources to its targets if and only if G has a k-clique.

    To prove this result, it will be helpful to first identify some special paths in G'.

    For any i∈ [k] and v∈ V_i, we let P(v) be the path which begins at s_i, passes through the top nodes of G_u for all  u∈ V_i before v, then takes the skip edge skipping over G_v, passes through the bottom nodes of G_w for all w∈ V_i after v, and then finally ends at t_i.

    
        
        For every v∈ V, P(v) is a shortest path in G'.
    
    
        Fix v∈ V.
        Let i∈ [k] be the index such that v∈ V_i.

        Recall that for any j∈ [k], row j of G' consists of the all gadgets G_u for vertices u∈ V_i.
        The graph G' is structured so that there is no edge from row q to p whenever q > p.
        Then since s_i only has edges to nodes in row i and t_i only has edges from nodes in row i, any (s_i,t_i)-path in G' must lie completely in row i.
        Such a path can use at most one skip edge, since a skip edge goes from a top node to a bottom node, and there are no edges from bottom nodes to top nodes within row i.
        If an (s_i,t_i)-path uses no skip edges, it has exactly n· l(i) + 1 internal nodes.
        If instead the path uses one skip edge, it has exactly (n-1)· l(i)+1 internal nodes, because it skips over one gadget.
        
        This implies that any (s_i,t_i)-path in G' which uses a skip edge is a shortest path.
        
        Since P(v) uses a skip edge, it is an (s_i,t_i)-shortest path as claimed.
    
    
        
    

    
    
    
    
        
    


    
    
        If G has a k-clique, then G' has node-disjoint shortest paths from its sources to its targets.
    
    
        Let (v_1,…,v_k)∈ V_1×…× V_k be a k-clique in G.

        For each list 
        
    L = i_1, …, i_ℓ
 in L, 
        let Q(L) be the path which begins at s_L, passes through nodes         
            
    a_L(v_i_1), b_L(v_i_1), …, a_L(v_i_ℓ), b_L(v_i_ℓ)

        in that order using the paths corresponding to list L, and then ends at t_L.
        More precisely, Q(L) goes from a_L(v_i_j) to b_L(v_i_j) for each j∈ [ℓ] by taking the edge between these vertices in G', and goes from b_L(v_i_j) to a_L(v_i_j+1) for each j∈ [ℓ-1] by traversing the path Π(v_i_j, v_i_j+1).
        

        
            
            For every list L∈L,  Q(L) is a shortest path. 
        
        
            The path Π(v_i_j, v_i_j+1) has length 2(i_j+1 - i_j) - 1.
            By telescoping, this means the sum of the lengths of the paths of Π(v_i_j, v_i_j+1) over all j∈ [ℓ-1] is 2(i_ℓ - i_1) - ℓ.
            The only edges of Q(L)  not in the Π(v_i_j, v_i_j+1) paths are the edge from s_L to a_L(v_i_1), the edges from a_L(v_i_j) to b_L(v_i_j) for each j∈ [ℓ], and the edge from b_L(v_i_ℓ) to t_L.
            It follows that the length of Q(L) is
            
    2 + ℓ + (2(i_ℓ - i_1) - ℓ) = 2(i_ℓ - i_1 + 1).
 

            To prove the claim, it suffices to show that any (s_L,t_L)-path in G' has length at least 
    2(i_ℓ - i_1 + 1).


            To that end, take an arbitrary (s_L, t_L)-path Q in G'.
            Let j_1, …, j_r∈ [k] be the sequence of distinct rows Q visits in order. 
            Since G' only includes edges going from row x to row y for x < y, we must have j_1 < j_2 < … < j_r.

            By construction the only way to go from row x to row y in G' is to traverse a path Π_L'(u,w) for some nodes u∈ V_x and w∈ V_y, and list L'∈ℒ.
            Such a path begins at the bottom of row x at b_L'(u), ends at the top of row y at a_L'(w), and has length 2(y-x) - 1.
            So the sum of the lengths of all such paths Q traverses to hit rows j_1, …, j_r is at least 2(j_r - j_1) - r by telescoping. 
            Moreover, Q must traverse at least one edge within each row it visits, to get from the top of that row to the bottom of that row. 
            This accounts for at least r additional edges, so Q has length at least
                
    (2(j_r-j_1) - r) + r = 2(j_r - j_1).

            Finally, Q also must contain an edge leaving s_L, and an edge entering t_L.
            This accounts for two more edges, so Q has length at least 2(j_r-j_1+1).

            By definition, i_1 and i_ℓ are the first and final elements in list L respectively.
            Consequently, edges exiting s_L must go to row i_1, and edges entering t_L must depart from i_ℓ.
            This forces j_1 = i_1 to be the first row Q enters, and j_r = i_ℓ to be the last row Q enters.
            Thus Q has length at least 
                
    2(j_r-j_1+1) = 2(i_ℓ - i_1 + 1).

            This lower bound for the length of an arbitrary (s_L,t_L)-path in G' is equal to the length of Q(L).
            Thus Q(L) is a shortest path in G', as claimed.
        

        We claim that the collection of paths obtained by taking P(v_i) for each i∈ [k] and Q(L) for each L∈L is a collection of node-disjoint paths in G'.

        Indeed, for each i∈ [k], P(v_i) is in the i^th row of G', so P(v_i) and P(v_j) are disjoint for i≠ j.
        Similarly, for each choice of lists L≠ K in L, Q(L) and Q(K) pass through distinct vertices.

        Take i∈ [k] and L∈L.
        The only way Q(L) can intersect P(v_i) is if i∈ L.
        If i∈ L, the only nodes at which Q(L) can intersect P(v_i) are a_L(v_i) and b_L(v_i).
        However, P(v_i) skips G_v_i, so neither of these nodes occur in P(v_i).
        Thus P(v_i) and Q(L) are disjoint.

        Since by <Ref> the P(v_i) are shortest paths, and by <Ref> the Q(L) are shortest paths, we have proven the desired result. 
    

    
    
        If G' has node-disjoint paths from its sources to its targets, then G has a k-clique.
    
    
        Let F be a family of node-disjoint paths from the sources to the targets of G'.

        For each i∈ [k], let P_i denote the (s_i,t_i)-path in F.
        
        For each L∈L, let Q_L denote the (s_L,t_L)-path in F.

        By construction of G', each P_i must stay in row i.
        Since skip edges take us from the top of a row to the bottom of a row, each P_i uses at most one skip edge. 

        We say a path Q “uses the edges corresponding to a list L∈ℒ” if Q uses an edge of Π_L(u,w), for some vertices u and w.

        
            
            For each list L∈L, the path Q_L does not use edges corresponding to list L'∈ℒ, for any L'≠ L.
        
        
            Suppose to the contrary that there does exist a list L∈L such that Q_L uses edges corresponding to lists distinct from L.
            Pick such an L which occurs latest in the ordering of L.

            Consider the first edge Q_L uses which corresponds to another list.
            
            Suppose this edge belongs to  Π_L'(u,w) for some list L'≠ L, and vertices u and w.
            Let x∈ [k] be the index such that u∈ V_x.
            Since the edge we are considering is the first edge Q_L uses which corresponds
            to a list other than L, before  this edge Q_L can only have entered rows with indices contained in L.
            Thus x∈ L, and Q_L must have entered row x at a vertex a_L(v), for some v∈ V_x.
            We also know that x∈ L', since otherwise Π_L'(u,w) would not exist.
            Since Q_L uses an edge of Π_L'(u,w), we know that the starting vertex of this path b_L'(u) must occur after a_L(v) in the topological order of G'.
            
            Previously, we observed that each P_i uses at most one skip edge.
            We claim that path P_x uses the skip edge to skip gadget G_v in row x.
            Suppose to the contrary that P_x does not use this skip edge.
            Since P_x and Q_L are disjoint, P_x must pass through b_L(v) (otherwise it would hit a_L(v)).
            Since b_L'(u) occurs after a_L(v) in the topological order, this means that P_x passes through b_L'(u).
            This contradicts our assumption that P_x and Q_L are disjoint.

            Thus P_x uses the skip edge corresponding to G_v in row x, as claimed.

            Since P_x uses this skip edge, we know that P_x passes through b_K(v') for all lists K containing x and all v'∈ V_x after v in the order on V_x.
            Since b_L'(u) is not in P_x (because P_x and Q_L are disjoint), we must have u=v.

            Then for a_L(v) to occur before b_L'(v) in the topological order, we must have L occur before L' in the ordering for L.

            Now, observe that Q_L' cannot cross between rows while only using edges corresponding to L'.
            Indeed, if Q_L' only uses edges corresponding to L' to go between rows, it would pass through a column of row x, since x∈ L'.
            To be disjoint from P_x, this is only possible if Q_L' uses a column of G_v, since P_x hits the columns of every other gadget in row x. 
            But Q_L and Q_L' are disjoint, and we already said that Q_L hits the column of G_v corresponding to L'.

            Thus, Q_L' must use an edge corresponding to a list distinct from L'.
            We also observed earlier that L' occurs after L in the ordering on L.

            This contradicts our choice of L as the final list in L with the property that Q_L uses an edge corresponding to a list distinct from L.

            Thus our initial assumption was false, and the claim holds.            
        

        
            
            For every i∈ [k], P_i uses a skip edge.
        
        
        Suppose to the contrary that there exists an index i∈ [k] such that P_i does not use a skip edge.
        Then for every v∈ V_i and r∈ [s(i)], the path P_i passes through  at least one of a_r(v) and b_r(v).
        Let L∈L be a list containing i (such a list exists because
        L is a k-covering family).
        By <Ref> and the fact that each P_i uses at most one skip edge, the path Q_L must pass through vertices a_L(v) and b_L(v) for some v∈ V_i.
        Consequently, Q_L intersects P_i, which contradicts the assumption that paths in F are disjoint.
        So each P_i traverses a skip edge as claimed.
        


        Since a skip edge moves a path from the top nodes to the bottom nodes of a row, by <Ref> we know that each P_i traverses exactly one skip edge.    
        
        For each i∈ [k], let v_i∈ V_i be the unique vertex such that P_i traverses the edge skipping G_v_i.
        Then we claim that (v_1, …, v_k) is a clique in G.

        Indeed, take any pair (i,j)∈[k]^2 with i<j.
        Let L∈L be a list covering (i,j).

By <Ref>,  
        the path Q_L traverses a path Π_L(u,w) for some u∈ V_i and w∈ V_j.
        
        Since the only gadgets skipped by P_i and P_j are G_v_i and G_v_j respectively, and Q_L is disjoint from P_i and P_j, we see that in fact Q_L traverses the path Π_L(v_i,v_j).
        
        But this path exists in G' only if (v_i,v_j) is an edge in G.
        
        So (v_i,v_j) is an edge in G for all i<j, and thus G contains a k-clique as claimed.        
    

*

    Construct a collection L of λ=⌊ k^2/4⌋ lists which form a k-covering family using <Ref>.
    For constant k, this takes O(1) time.
    This collection has the property that each element of [k] shows up in fewer than k list of ℒ.

    Let G be the input instance of .

    Using L and G, construct the graph G' described previously in this section.
    
    By <Ref>, solving  or  on G' solves  on G, where 
        
    p = k + λ = k + ⌊ k^2/4⌋.

    
    Since G' consists of 2(k + λ) terminals and kn gadget graphs G_v, each on fewer than 2k nodes, the graph G' has at most O(kn) nodes.
    Since we can construct G' in time linear in its size, this proves the desired result.





§ CONCLUSION



In this work, we obtained linear time algorithms for  in undirected graphs and DAGs.
These algorithms are based off algebraic methods, and as a consequence are randomized and only solve the decision, rather than search, version of .
This motivates the following questions:


    Is there a deterministic linear time algorithm solving ?



    Given a DAG or undirected graph G  with sources s_1, s_2 and targets t_1, t_2, is there a linear time algorithm finding disjoint (s_i,t_i)-shortest paths in G for i∈1,2?


It is also an interesting research direction to see if algebraic methods can help design faster algorithms for  in undirected graphs and DAGs when k≥ 3, or help tackle this problem in the case of general directed graphs.


In this work, we also established tighter reductions from finding cliques to disjoint path and shortest path problems.
There still remain large gaps however, between the current best conditional lower bounds and current fastest algorithms for these problems.


    Is there a fixed integer k≥ 3 and constant δ > 0 such that  in DAGs can be solved in O(n^k+1-δ) time? 
    Or does some popular hypothesis rule out such an algorithm?


Since  admits nontrivial algorithms by reduction to matrix multiplication, it is possible that  can be solved faster using fast matrix multiplication algorithms.
On the other hand, if we want to rule out this possibility and obtain better conditional lower bounds for , we should design reductions from problems which are harder than .
In this context, a natural strategy would be to reduce from  and  instead, since these problems are conjectured to require n^k-o(k) time to solve (and it is not known how to leverage matrix multiplication to solve these problems faster than exhaustive search).

For all k≥ 3, the current fastest algorithm for  in undirected graphs takes n^O(k· k!) time, much slower than the O(mn^k-1) time algorithm known for the problem in DAGs.
Despite this, every conditional lower bound that has been established for  in undirected graphs so far also extends to showing the same lower bound for the problem in DAGs.
This is bizarre behavior, and suggests we should try establishing a lower bound which separates the complexities of  in undirected graphs and DAGs.
If designing such a lower bound proves difficult, that would offer circumstantial evidence that far faster algorithms for  in undirected graphs exist.


    Can we show a conditional lower bound for  in undirected graphs, which is stronger than any conditional lower bound known for  in DAGs? 


Finally, for large k, the best conditional time lower bounds we have for  in DAGs are far weaker than the analogous lower bounds we have for  in DAGs.
This is despite the fact that the fastest algorithms we have for both problems run in the same time.
It would nice to resolve this discrepancy, either by designing faster algorithms for the latter problem, or showing better lower bounds for the former problem.


Is there a fixed integer k≥ 3  such that we can solve  in DAGs faster than we can solve  in weighted DAGs? 



    Can we show a conditional lower bound for  in DAGs matching the best known conditional lower bound for  in DAGs? 




alpha











§ STANDARD REDUCTIONS



In this section, we collect proofs of some standard reductions that allow us to move between different variants of disjoint path problems.


    
    There is a reduction from  on n vertices and m edges to  on m+k(n+2) nodes and 2k(m+1) edges.


    Let G be the instance of  on n vertices and m edges, with sources s_1, …, s_k and targets t_1, …, t_k.
    Let V and E be the vertex and edge sets of G respectively.
    
    We construct a graph G' as follows.
    For every vertex v∈ V, G' has k nodes v_1, …, v_k (we call these the copies of v in G').
    For every edge e∈ E, G' has a node e.
    For every edge e = (v,w)∈ E, we include edges in G' from v_i to e and from e to w_i for all i∈ [k].
    If e = (v,w) had weight ℓ(v,w) in G, then the (v_i,e) and (e,w_i) edges in G each have weight ℓ(v,w).

    Finally, we introduce new sources s'_1, …, s'_k and targets t'_1, …, t'_k in G'.
    Then for every i,j∈ [k], we add edges from s'_i to (s_i)_j and from (t_i)_j to t'_i of weight 1.

    From this construction, G' has m+kn + 2k nodes and 2km + 2k edges as claimed.


    Suppose we have vertex-disjoint (s'_i,t'_i)-shortest paths P'_i in G'.
    We can assume each P'_i never traverses two copies of the same vertex v∈ V (otherwise, we could remove the subpath between two copies of v and obtain a shorter path than P'_i).
    We map each P'_i to an (s_i,t_i)-shortest path P_i in G, by having P_i pass through the vertices v∈ V for which P'_i contains a copy of v, in the order the copies appear in P'_i.

    By construction, if P_i has length ℓ, then P'_i has length 2ℓ + 2.
    So since the P'_i are shortest paths, the P_i are also shortest paths.
    The P_i are also edge-disjoint, since if some P_i and P_j overlap at an edge e, the paths P'_i and P'_j would overlap at node e in G', which would contradict the assumption that the P'_i are vertex-disjoint.

    So any solution to  on G' pulls back to a solution to  on G.

    Conversely, given edge-disjoint (s_i,t_i)-shortest paths P_i in G of the form 
    
    P_i = ⟨ v_i,1, …, v_i,ℓ_i⟩

    we can produce (s'_i,t'_i)-paths P'_i in G' of the form 
    
    P'_i = ⟨ s'_i, (v_i,1)_i, ((v_i,1)_i, (v_i,2)_i), (v_i,2)_i, …, (v_i,ℓ_i)_i, t'_i⟩.

    Similar reasoning to the above shows that the P'_i are shortest paths in G'.
    These paths are vertex-disjoint because each P'_i only uses the i^th copies of v∈ V, and the P_i were edge-disjoint, so the P'_i cannot overlap at any nodes of the form e∈ E.

    So any solution to  in G has a corresponding solution to  in G'.

    This proves the desired result.


As mentioned in <Ref>, <Ref> combined with <Ref> implies <Ref>, and  <Ref> combined with the O(mn^k-1) time algorithm for  in DAGs from  <cit.> implies that  in DAGs can be solved in O(m^k) time for constant k.



    
    There are reductions from  on DAGs  to   on DAGs and from  on DAGs to  on DAGs with the same number of nodes and edges respectively.


    Let G be the DAG which is an instance of  or .
    Take a topological order v_1, …, v_n of the vertices in G.
    Let G' be the DAG with the same vertex and edge sets as G, but where each edge (v_i,v_j) has weight (j-i).
    Then by telescoping, for any vertices v_i and v_j in G', every path from v_i to v_j in G' has total length (j-i).
    
    Consequently, every path in G becomes a shortest path in G'.
    
    So solving  and  in G' corresponds to solving  and  respectively in G, which proves the desired result.


As mentioned in <Ref>, <Ref> shows that  in weighted DAGs generalizes the  problem in DAGs.
