Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
Michał Włodarczyk


A Practical Approach to Evaluating the Adversarial Distance for Machine Learning Classifiers
    K. Grunthal 1kgrunthal@mpifr-bonn.mpg.de
          V. Venkatraman Krishnan 1
          P. C. C. Freire 1
          M. Kramer 1
          M. Bailes 8,9
          S. Buchner 7
          M. Burgay 5
          A. D. Cameron 8,9
          C.-H.R. Chen 1
          I. Cognard 2,3
          L. Guillemot 2,3
          M. E. Lower 6
          A. Possenti 5
          G. Theureau 2,3,4
          
    September 9, 2024
=======================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
    In the Disjoint Paths problem, one is given a 
    graph with a set of k vertex pairs (s_i,t_i) and the task is to connect each s_i to t_i with a path, so that the k paths are pairwise disjoint.
    In the optimization variant, Max Disjoint Paths, the goal is to maximize the number of vertex pairs to be connected.
    We study this problem on acyclic directed graphs, where Disjoint Paths is known to be W[1]-hard when parameterized by k.
    We show that in this setting Max Disjoint Paths is W[1]-hard to c-approximate for any constant c.
    To the best of our knowledge, this is the first non-trivial result regarding the parameterized approximation for Max Disjoint Paths with respect to the natural parameter k.
    Our proof is based on an elementary self-reduction that is guided by a certain combinatorial object constructed by the probabilistic method.




§ INTRODUCTION


The Disjoint Paths problem has attracted a lot of attention both from the perspective of graph theory and applications <cit.>.
Both decision variants, where one requires the paths to be either vertex-disjoint or edge-disjoint, are known to be NP-hard already on very simple graph classes <cit.>.
This has motivated the study of Disjoint Paths through the lens of parameterized complexity. Here, the aim is to develop algorithms with a running time of the form f(k)· n^(1), where f is some computable function of a parameter k and n is the input size.
A problem admitting such an algorithm is called fixed-parameter tractable (FPT).
In our setting, k is the number of vertex pairs to be connected.
On undirected graphs, both variants of Disjoint Paths have been classified as FPT thanks to the famous Graph Minors project by Robertson and Seymour <cit.> (see <cit.> for later improvements).
This was followed by a line of research devoted to designing faster FPT algorithms on planar graphs <cit.>.

On directed graphs, there is a simple polynomial transformation between the vertex-disjoint and the edge-disjoint variants, so these two problems turn out equivalent.
Here, the problem becomes significantly harder: It is already NP-hard for k=2 <cit.>.
The situation is slightly better for acyclic digraphs (DAGs) where Disjoint Paths can be solved in time n^(k) <cit.> but it is W[1]-hard <cit.> (cf. <cit.>) hence unlikely to be FPT.
In addition, no n^o(k)-time algorithm exists under the assumption of the Exponential Time Hypothesis (ETH) <cit.>.
Very recently, it has been announced that Disjoint Paths is FPT on Eulerian digraphs <cit.>.
It is also noteworthy that the vertex-disjoint and edge-disjoint variants are not equivalent on planar digraphs as the aforementioned reduction does not preserve planarity.
Indeed, here the vertex-disjoint version is FPT <cit.> whereas the edge-disjoint version is W[1]-hard <cit.>.


In the optimization variant, called Max Disjoint Paths, we want to maximize the number of terminals pairs connected by disjoint paths. 
The approximation status of this problem has been studied on various graph classes <cit.>. 
On acyclic digraphs the best approximation factor is (√(n)) <cit.> and this cannot be improved unless P=NP <cit.>.
A different relaxation is to allow the algorithm to output a solution in which every vertex appears in at most c paths (or to conclude that there is no vertex-disjoint solution).

Kawarabayashi, Kobayashi, and Kreutze <cit.> used the directed half-integral grid theorem  to design
a polynomial-time algorithm for directed Disjoint Paths with congestion c=4 for every k.
In other words, such a relaxed problem belongs to the class XP.
Subsequently, the congestion factor has been improved to c=3 <cit.> and c=2 <cit.>.



    Hardness of FPT approximation.

For problems that are hard from the perspective of both approximation and FPT algorithms,
it is natural to exploit the combined power of both paradigms and consider FPT approximation algorithms.
Some prominent examples are an FPT approximation scheme for k-Cut <cit.> and an FPT 2-approximation for Directed Odd Cycle Transversal <cit.> parameterized by the solution size k. 
However, several important problems proved to be resistant to FPT approximation as well.
The first hardness results in this paradigm have been obtained under a relatively strong hypothesis, called Gap-ETH <cit.>.
Subsequently, an (1)-approximation for k-Clique was shown to be W[1]-hard <cit.> and later the hardness bar was raised to k^o(1) <cit.>.
In turn, k-Dominating Set is W[1]-hard to f(k)-approximate for any function f <cit.> and W[2]-hard to (1)-approximate <cit.>.
More results are discussed in the survey <cit.>.

Proving approximation hardness under Gap-ETH is easier compared to the assumption FPTW[1] because Gap-ETH already assumes hardness of a problem with a gap.
Indeed, relying just on FPTW[1] requires the reduction to perform some kind of gap amplification, alike in the PCP theorem <cit.>.
Very recently, the so-called Parameterized Inapproximability Hypothesis (PIH) has been proven to follow from ETH <cit.>.
This means that ETH implies FPT approximation hardness of Max 2-CSP parameterized by the number of variables within some constant approximation factor c > 1, which has been previously used as a starting point for parameterized reductions <cit.>.
It remains open whether PIH can be derived from the weaker assumption FPTW[1].

Lampis and Vasilakis <cit.> showed that undirected Max Vertex-Disjoint Paths admits an FPT approximation scheme when parameterized by treedepth but, assuming PIH, this is not possible under parameterization by pathwdith.
See <cit.> for more results on approximation for Max Disjoint Paths under structural parameterizations. 
Bentert, Fomin, and Golovach <cit.>
considered the Max Vertex-Disjoint Shortest Paths problem where we additionaly require each path in a solution to be a shortest path between its endpoints.
They ruled out FPT(k) approximation with factor k^o(1) for this problem assuming FPTW[1] and with factor o(k) assuming Gap-ETH.





    Our contribution.

We extend the result by Slivkins <cit.> by showing that Max Disjoint Paths on acyclic digraphs does not admit an FPT algorithm that is a q-approximation, for any constant q.

We formulate our hardness result as W[1]-hardness of the task of distinguishing between instances that are fully solvable from those in which less than a 1/q-fraction of the requests can be served at once.
Since a q-approximation algorithm could be used to tell these two scenarios apart, the following result implies hardness of approximation.
We refer to a pair (s_i,t_i) as a request that should be served by a path connecting s_i to t_i.

theoremthmMain

    Let q ∈ be a constant.
    It is W[1]-hard to distinguish whether for a given instance of k-:
    
        
  * all the requests can be served simultaneously, or
        
  * no set of k/q requests can be served simultaneously.
    





Our proof is elementary and
does not rely on coding theory or communication complexity as some previous W[1]-hardness of approximation proofs <cit.>. 
Instead, we give a gap-amplifying self-reduction that is guided by a certain combinatorial object constructed via the probabilistic method.




    Techniques.


A similar parameterized gap amplification technique has been previously applied to the k-Steiner Orientation problem: given a graph G with both directed and undirected edges, together with a set of vertex pairs (s_1,t_1), …, (s_k,t_k), we want to orient all the undirected edges in G to maximize the number of pairs (s_i,t_i) for which t_i is reachable from s_i.
The problem is W[1]-hard and the gap amplification technique can be used to establish W[1]-hardness of constant approximation <cit.>.
The idea is to create multiple copies of the original instance and connect them sequentially into many layers, in such a way that the fraction of satisfiable requests decreases as the number of layers grows.
What distinguishes k-Steiner Orientation from our setting though is that therein we do not require the (s_i,t_i)-paths to be disjoint.
So it is allowed to make multiple copies of each request (s_i,t_i) and connect the t_i-vertices to the s_i-vertices in the next layer in one-to-many fashion.

Such a construction obviously cannot work for Dag Disjoint Paths.
Instead, will we construct a combinatorial object yielding a scheme of connections between the copies of the original instance, with just one-to-one relation between the terminals from the consecutive layers.

Imagine a following construction: given an instance I of k-we create 2k copies of I: I^1_1, …, I^1_k and  I^2_1, …, I^2_k.
Next, for each i ∈ [k] we choose some permutation π_i  [k] → [k] and for each j ∈ [k] we connect the sink t_j in I^1_i to the source s_i in I^2_π_i(j).
See <Ref> on page fig:construction.
Then for each (i,j) ∈ [k]^2 we request a path from the source  s_j in I^1_i to the sink t_i in I^2_π_i(j).
Observe that if I is a yes-instance then we can still serve all the requests in the new instance.
However, when I is a no-instance, then there is a family ℱ of 2k many k-tuples from [k]^2 so that each tuple represents k requests that cannot be served simultaneously.
Each tuple corresponds to some k requests that have to be routed through a single copy of I, which is impossible when I is a no-instance.


We can now iterate this argument.
In the next step we repeat this construction k times (but possibly with different permutations), place such k instances next to each other, and create the third layer comprising now k^2 copies of I.
Then for each i ∈ [k] we need a permutation π_i  [k^2] → [k^2] describing the connections between the sinks from the second layer to the sources from the third layer.
Again, if I is a no-instance, we obtain a family ℱ of 3k^2 many k-tuples from [k]^3
corresponding to subsets of requests that cannot be served simultaneously.
We want to show that after d = f(k) many iterations no subset A of 50% requests can be served.
In other words, 
the family ℱ should always contain a tuple contained in A, certifying that A is not realizable.
This will give a reduction from the exact version of to a version of with gap 1/2.
The crux of the proof is to find a collection of permutations that will guarantee the desired property of ℱ.

It is convenient to think about this construction as a game in which the first player chooses the permutations governing the connections between the layers (thus creating an instance of ) and the second player picks a subset A of 50% requests.
The first player wins whenever the family ℱ of forbidden k-tuples includes a tuple contained in A.
We need to show that the first player has a single winning strategy against every possible strategy of the second player.
We will prove that a good strategy for the first player is to choose every permutation independently and uniformly at random.
In fact, for a sufficiently large d and any fixed strategy A of the second player, the probability that A wins against a randomized strategy is smaller than 2^-k^d.
Since the number of possible strategies for the second player is at most 2^k^d (because there are k^d requests), the union bound implies that the first player has a positive probability of choosing a strategy that guarantees a victory against every strategy of the second player.
This translates to the existence of a family of permutations for which the gap amplification works.



§ PRELIMINARIES

We follow the convention [n] = {1,2,…,n} and use the standard graph theoretic terminology from Diestel's book <cit.>. 
We begin by formalizing the problem.

Max Disjoint PathsA digraph D, a set 𝒯 of k pairs (s_i,t_i) ∈ V(D)^2.kFind a largest collection 𝒫 of vertex-disjoint paths so that each path P∈𝒫 is an (s_i,t_i)-path for some (s_i,t_i) ∈𝒯.

We refer to the pairs from 𝒯 as requests.
A solution 𝒫 is said to serve request (s_i,t_i) if it contains an (s_i,t_i)-path.
The condition of vertex-disjointedness implies that each request can be served by at most one path in 𝒫.
A yes-instance is an instance admitting a solution serving all the k-requests.
Otherwise we deal with a no-instance.
(Max) is a variant of (Max) Disjoint Paths where the input digraph is assumed to be acyclic.



    Notation for trees.

For a rooted tree T and v ∈ V(T) we denote by (v) the set of direct descendants of v.
A vertex v in a rooted tree is a leaf if (v) = ∅.
We refer to 
the set of leaves of T as L(T). 
The depth of a vertex v ∈ V(T) is defined as its distance from the root, measured by the number of edges.
In particular, the depth of the root equals 0.
The set of vertices of depth i in T is called the i-th layer of T.

For v ∈ V(T) we write T^v to denote the subtree of T rooted at v.
We can additionally specify an integer ℓ≥ 1 and write T^v,ℓ for the tree comprising the first ℓ  layers of T^v.
In particular, the tree T^v,1 contains only the vertex v. 

For k,d ∈ we denote by T_k,d the full k-ary rooted tree of depth d.
We have |L(T_k,d)| = k^d.
A subset  A  L(T_k,d) is called a q-subset for q∈ if |A| ≥|L(T_k,d)| / q.



    Fixed parameter tractability.


We provide only the necessary definitions here; more information can be found in the book <cit.>.
A parameterized problem can be formalized as a subset of Σ^* ×ℕ.
 We say that a problem is fixed parameter tractable (FPT) if it admits an algorithm solving an
    instance (I, k) 
    in running time
    f(k)· |I|^(1), where f is some computable function.

    To argue that a parameterized
    problem is unlikely to be FPT, we employ FPT-reductions that run in time f(k)· |I|^(1) and transform an instance (I,k) into an equivalent one (I',k') where k' = g(k).
    A canonical parameterized problem that is believed to lie outside the class FPT is k-Clique.
    The problems that are FPT-reducible to  k-Clique form the class W[1].



    Negative association.

We introduce the following concept necessary for our probabilistic argument.
There are several definitions capturing negative dependence between random variables; intuitively it means that when one variable takes a high value then a second one is more likely to take a low value.
Negative association formalizes this idea in a strong sense.


    A collection of random variables X_1, X_2, …, X_n ∈ is said to be negatively associated if for every pair of disjoint subsets A_1, A_2  [n] and every pair of increasing functions f_1 ^|A_1|→, f_2 ^|A_2|→ it holds that

    
    f_1(X_i | i ∈ A_1)· f_2(X_i | i ∈ A_2)≤f_1(X_i | i ∈ A_1)·f_2(X_i | i ∈ A_2).



We make note of several important properties of negative association.



    Consider a collection of random variables X_1, X_2, …, X_n ∈ that is negatively associated. Then the following properties hold.
    
        
        
  * For every family of disjoint subsets A_1, …, A_k  [n] and increasing functions f_1, …, f_k, f_i ^|A_i|→, the collection of random variables

        
    f_1(X_i | i ∈ A_1),  f_2(X_i | i ∈ A_2), …, f_k(X_i | i ∈ A_k)

        is negatively associated. 

        
  * If random variables Y_1, …, Y_n are negatively associated and independent from X_1, …, X_n then the collection
        X_1, …, X_n, Y_1, …, Y_n is negatively associated. 

        
  * For every sequence (x_1, x_2, …, x_n) of real numbers we have
        
    X_i ≤ x_i | i ∈ [n]≤∏_i=1^n X_i ≤ x_i.

        
    



    Let n,k ∈.
    For i ∈ [k] let 𝒳^i = (X_1^i, …, X_n^i) be a sequence of real random variables that are negatively associated.
    Suppose that 𝒳^1, …, 𝒳^k are independent from each other.
    Then the random variables (∑_i=1^k X^i_1, …, ∑_i=1^k X^i_n) are negatively associated.


    By <Ref>(<ref>) we know that the union 𝒳^1 ∪…∪𝒳^k forms a collection of nk random variables that are negatively associated.
    We divide it into n disjoint subsets of the form ({X_j^1, …, X_j^k})_j=1^n and apply <Ref>(<ref>) for the increasing function f ^k →, f(x_1,…,x_k) = ∑_i=1^k x_i.



Negative association occurs naturally in situations like random sampling without replacement.
A scenario important for us is when an ordered sequence of numbers is being randomly permuted.
Intuitively, observing a high value at some index removes this value from the pool and decreases the chances of seeing high values at the remaining indices.



    Consider a sequence (x_1, x_2, …, x_n) of real numbers.
    Let Π [n] → [n] be a random variable representing a 
    permutation of the set [n] chosen uniformly at random.
    For i ∈ [n] we define a random variable X_i = x_Π^-1(i).
    Then the random variables X_1, X_2, …, X_n are negatively associated.

    


§ THE REDUCTION




Our main objects of interest are collections of functions associated with the nodes of the full k-ary rooted tree.
Such a function for a node v gives an ordering of leaves in the subtree of v.


    A scheme for T_k,d is a collection of functions, one for each node in T_k,d, such that the function f_v associated with v ∈ V(T_k,d) is a bijection from L(T^v_k,d) to [|L(T^v_k,d)|].
    Let (k,d) denote the family of all schemes for T_k,d.


We will now formalize the idea of connecting multiple copies of an instance.
On an intuitive level, we construct a d-layered instance 
by taking k many (d-1)-layered instances and adding a new layer comprising k^d-1 copies of the original instance I.
Then we map the sinks in the layer (d-1) to the sources in the layer d according to k bijections read from a scheme.
These mappings govern how we place the arcs towards the layer d and which vertex pairs form the new request set.
We need a scheme β∈(k,d) to arrange all the arcs between the layers.

In order to simplify the notation we introduce the following convention.
Suppose that an instance J is being build with multiple disjoint copies of an instance  I = (D,k,𝒯), referred to as I_1, I_2, ….
Then we refer to the copy of the vertex s_i ∈ V(D) (resp. t_i) in I_j as I_j[s_i] (resp. I_j[t_i]).


Given an instance I = (D,k,𝒯) of and a scheme β = (f_v)_v ∈ V(T_k,d)∈(k,d) we construct an instance J_k,d(I,β) = (D',k^d,𝒯') of . 
The elements of 𝒯' will be indexed by the leaves of T_k,d
as (s_v,t_v)_v ∈ L(T_k,d) while the elements of 𝒯 (in the instance I) are indexed by 1,…,k as (s_i,t_i)_i∈[k].

If d=1, we simply set J_k,1(I,β) = I, ignoring β.
We index 𝒯 by L(T_k,1) in an arbitrary order.

Consider d > 1. Let r be the root of T_k,d with (r) = {u_1, …, u_k}.
For i ∈ [k] let β_i be the truncation of β to the nodes in the subtree  T^u_i_k,d and J_i = (D_i, k^d-1, 𝒯_i) be the instance J_k,d-1(I, β_i).
We take a disjoint union of J_1,…,J_k and k^d-1 copies of I referred to as I_1,I_2,… (see <Ref>).
These  k^d-1 copies of I form layer d.



Recall that for i ∈ [k] the bijection f_u_i maps L(T^u_i_k,d) to [k^d-1].
For each i ∈ [k] and  v ∈ L(T^u_i_k,d) we insert an arc from J_i[t_v] to I_f_u_i(v)[s_i].


Then we add the pair (J_i[s_v], I_f_u_i(v)[t_i]) to 𝒯'.
This pair is assigned index ι(v) in 𝒯' where ι is the natural embedding L(T^u_i_k,d) → L(T_k,d).



Note that whenever D is acyclic then D' is acyclic as well so the procedure indeed outputs an instance of .
It is also clear that when I admits a solution serving all the k requests, it can be used to serve all the requests in J_k,d(I,β).


    Let k,d ∈ and β∈(k,d).
    If I = (D,k,𝒯) is a yes-instance of then J_k,d(I,β) is a yes-instance as well.


The case when I is a no-instance requires a more careful analysis.
We introduce the notion  of a collision that certifies that some subset of requests cannot be served.


    Let k,d ∈, A  L(T_k,d), and β = (f_v)_v ∈ V(T_k,d)∈(k,d).
    We say that u ∈ V(T_k,d) forms a collision with respect to (A,β) if A contains elements a_1,…,a_k
such that:

    
  * for each i ∈ [k] the node a_i is a descendant of u_i ∈(u) where u_1,…,u_k are distinct,
    
  * f_u_1(a_1) = f_u_2(a_2) = … = f_u_k(a_k).




    Let k,d ∈, A  L(T_k,d), and β = (f_v)_v ∈ V(T_k,d)∈(k,d).
    Suppose that there exists a collision with respect to (A,β).
    Let I = (D,k,𝒯) be a no-instance of .
    Then no solution to the instance (D',k^d,𝒯') = J_k,d(I,β) can simultaneously serve all the requests {(s_v,t_v)_v ∈ A}.


    We will prove the lemma by induction on d.
    In the case d=1 we have J_k,1(I,β) = I and the only possibility of a collision is when A = L(T_k,1) so {(s_v,t_v)_v ∈ A} is the set of all the requests. 
    By definition, we cannot serve all the requests in a no-instance.
    Let us assume d > 1 from now on.
    
    First suppose that the collision occurs at the root r ∈ V(T_k,d).
    Let (r) = {u_1, …, u_k}.
    Then there exists A' = {a_1,…,a_k} A such that a_i is a descendant of u_i and f_u_1(a_1) = f_u_2(a_2) = … = f_u_k(a_k).
    We refer to this common value as x = f_u_i(a_i).
    We will also utilize the notation from <Ref>.

    Observe that in order to serve the request (s_a_i,t_a_i) in D' the path P_i starting at s_a_i = J_i[s_a_i] must traverse the arc from J_i[t_a_i] to I_x[s_i] as every 
    other arc leaving D_i leads to some I_y with y  x having no connection to t_a_i = I_x[t_i].
    Furthermore, the path P_i must contain a subpath connecting I_x[s_i] to I_x[t_i] in I_x.
    Since the same argument applies to every i ∈ [k], we would have to serve all the k requests in I_x.
    But this is impossible because I_x is a copy of I which is a no-instance. 

    Now suppose that the collision does not occur at the root.
    Then it must occur in the subtree T^u_i_k,d
    for some i ∈ [k].
    For every v ∈ A being a descendant of u_i,
    any path P_v serving the request (s_v,t_v) in D' must contain a subpath P'_v in D_i from J_i[s_v] to J_i[t_v] as again it must leave D_i through the vertex J_i[t_v].
    By the inductive assumption, we know that we cannot simultaneously serve all the requests (s_v,t_v)_v ∈ A ∩ L(T^u_i_k,d) in the smaller instance J_i.
    The lemma follows.

    Consider some pair (s_i, t_i) ∈𝒯'.
    We can associate with it a collection of d triples (I_j,x_j), where I_j is a copy of I inside J_k,d(I,β) and x_j ∈ [k]. 
    
    
    If d=1 the collection contains just the triple (D, s_i, t_i).
    If d > 1 we consider the copy of I containing t_i and start with the pair (x,t_i) where x is the source corresponding to the sink 

    Let u ∈ V(T_k,d be the node forming the collision,
    with (u) = {u_1, …, u_k}.
    We know that there exist A' = {a_1,…,a_k} A such that a_i is a descendant of a_i and f_u_1(a_1) = f_u_2(a_2) = … = f_u_k(a_k).
    We will refer to the latter number as x.
    
    Let us focus on the moment in the construction process of J_k,d(I,β) when u is considered.
    We have just created instances J_1, …, J_k corresponding to the subtrees of u_1, …, u_k.
    As the next step, we insert k^d-1 copies of I.
    For each i ∈ [k] the vertex D_i[t_a_i] gets connected to I_x[s_i].
    

Alice and Bob play a game on T_k,d.
The strategy of Alice is a subset A  L(T_k,d).
We say that Alice plays a q-strategy if |A| ≥|L(T_k,d)/q = k^d/q.
The strategy of Bob is a scheme β∈(k,d).
Bob wins if there exists a collision with respect to (A,β).


We can now state our main technical theorem.
Recall that a subset  A  L(T_k,d) is called a q-subset if |A| ≥|L(T_k,d)|/q = k^d/q.

theoremthmBob

    Let k,d,q ∈ satisfy  d ≥ k · (4q)^4klog k.
    Then there exists β∈(k,d)
    such that for every q-subset A  L(T_k,d) there is a collision with respect to (A,β). 


The proof is postponed to <Ref> which abstracts from the Disjoint Paths problem and focuses on random permutations.
With <Ref> at hand, the proof of the main result is easy.

*

    We are going to give an FPT-reduction from the exact variant of k-, which is W[1]-hard <cit.>, to the variant with a sufficiently large gap.
    To this end, we present an algorithm that, given an instance I = (D,k,𝒯),
    runs in time f(k,q) · |I| and outputs an instance J = (D',k',𝒯') such that:
    
        
  * k' depends only on k and q,
        
  * if I is a yes-instance then J is a yes-instance, and
        
  * if I is a no-instance then no solution to J can simultaneously serve at least k'/q requests.
    
    Obviously, being able to separate these two cases for J (all requests vs. at most 1/q-fraction of requests) is sufficient to determine whether I is a yes-instance.
    
    We set d = k · (4q)^4klog(k) accordingly to <Ref>.
    It guarantees that there exists a scheme β∈(k,d)
    such that for every q-subset A  L(T_k,d) there is a collision with respect to (A,β).
    Observe that such a scheme can be computed in time f(k,q) because d is a function of (k,q) and the size of the family (k,d) is a function of (k,d).
    The same holds for the number of all q-subsets A  L(T_k,d).
    Therefore, we can simply iterate over all β∈(k,d) and check for each q-subset A whether there is a collision or not.

   The instance J is defined as J_k,d(I,β). A direct implementation of <Ref> takes time f(k,d) · |I|.
    <Ref> says that if I is a yes-instance, then J is as well, whereas <Ref> ensures that if I is a no-instance, then for each set of k'/q requests (corresponding to some q-subset A  L(T_k,d) which must have a collision with β) no solution can simultaneously serve all of them.
    This concludes the correctness proof of the reduction.


We remark that <Ref> works in a more general setting, where q is not necessarily a constant, but a function of k.
This enables us to rule out not only an (1)-approximation in FPT time, but also an α(k)-approximation for some slowly growing function α(k) →∞.
However, the value of the parameter k' becomes k^d for d = Ω(q^klog k)
so q ends up very small compared to the new parameter k'.
This is only sufficient to rule out approximation factors of the form α(k) = (log k)^o(1).
A detailed analysis of how to adjust such parameters is performed in <cit.>.



§ CONSTRUCTING THE SCHEME



This section is devoted to the proof of <Ref>.
Before delving into the rigorous analysis, we sketch the main ideas behind the proof.



    Outline.

We use the probabilistic method to prove the existence of a scheme having a collision with every q-subset of leaves in T_k,d.
We will show that for a sufficiently large d choosing each bijection at random yields a very high probability of a collision with any fixed q-subset.
Specifically, the probability that a collision does not occur should be less than 2^-k^d.
Since the number of all q-subsets of a k^d-size set is bounded by 2^k^d, the union bound will imply that the probability that a collision does not occur for at least one q-subset is strictly less than one, implying the existence of the desired scheme.

Let us fix a q-subset A  L(T_k,d).
Suppose there is a vertex u ∈ V(T_k,d) such that for every child y of u the fraction of leaves in T^y_k,d belonging to A is at least 1/q.
Let ℓ denote [|L(T^y_k,d)|].
For each such child we choose a random bijection from L(T^y_k,d) to [ℓ].
The probability that each of these k bijections maps an element of A to a fixed index x ∈ [ℓ] is at least q^-k.
Such events are not independent for distinct x but we will see that they are negatively associated, which still allows us to upper bound the probability of no such event happening by (1-q^-k)^ℓ (see <Ref>).

How to identify such a vertex u?
First, it is sufficient for us to relax the bound 1/q assumed above to 1/(4q). 
Observe that for each layer in   T_k,d there must be many vertices v satisfying |A ∩ L(T^v_k,d)| ≥1/2q |L(T^v_k,d)|.
Suppose that v does not meet our criterion: this means that it has a child v' with less than 1/(4q)-fraction of the A-leaves in its subtree.
But then the average fraction of the A-leaves among the remaining children is higher than the fraction for v.
Consequently, we can choose a child of v with a higher fraction and repeat this argument inductively.
We show that after (klog(q)) many steps this process must terminate so we are guaranteed to find a vertex for which every child has at least a 1/(4q)-fraction of the A-leaves. This is proven in <Ref>.

Finally, to obtain a large probability of a collision we must show that there many such vertices u with a large sum of their subtrees' sizes.
This will allows us to multiply the aforementioned bounds of the form (1-q^-k)^ℓ with a large sum of the exponents ℓ.
By applying the argument above to a single layer in T_k,d we can find such a collection with the sum of their subtrees' sizes being k^d divided by some function of k and q.
But we can also apply it to multiple layers as long as they are sufficiently far from each other (so that the vertices found by the inductive procedure are all distinct). 
Therefore, it suffices to take d large enough so that the number of available layers surpasses the factors in the denominator, which depend only on k and q.
This is analyzed in <Ref>.



    
 
We begin with a probabilistic lemma stating that randomly permuting k large subsets of a common universe yields a large chance of creating a non-empty intersection of these sets.


    Let k, z, ℓ∈ and
    X_1, …, X_k be subsets of [ℓ] of size at least ℓ / z each.
    Next, let Π_1, …, Π_k  [ℓ] → [ℓ] be independent random variables with a uniform
distribution on the family of all permutations over the set [ℓ]. Then
   
    
    Π_1(X_1) ∩Π_2(X_2) ∩…∩Π_k(X_k) = ∅≤exp(-ℓ / z^k).



    For i ∈ [k] and j ∈ [ℓ] let Y^i_j = 1
    if j ∈Π_i(X_i) and Y^i_j = 0 otherwise.
    By <Ref> the variables (Y^i_1, …, Y^i_ℓ) have negative association for each i ∈ [k].
    Note that 𝔼Y^i_j≥ 1/z.
    
    Next, let Z_j = ∑_i=1^k Y^i_j for j ∈ [ℓ].
    <Ref> ensures that the variables Z_1, …, Z_ℓ also enjoy negative association.
    Condition Π_1(X_1) ∩Π_2(X_2) ∩…∩Π_k(X_k) = ∅ is equivalent to max(Z_j)_j=1^ℓ≤ k - 1.
    We have
    
    Z_j ≤ k-1 = 1 - Z_j = k = 1 - ∏_i=1^kj ∈Π_i(X_i)≤ 1 - 1/z^k.

    
    max(Z_j)_j=1^ℓ≤ k-1≤∏_j=1^ℓZ_j ≤ k-1≤ (1 - 1/z^k)^ℓ = (1 - 1/z^k)^z^k· (ℓ / z^k)≤exp(-ℓ / z^k).

    In the first inequality we used <Ref>(<ref>).
    The last one holds because (1-1/m)^m < 1/e for all m ≥ 2.




    Notation.

We introduce some additional notation to work with the tree T_k,d.
For a vertex v ∈ V(T_k,d) let (v) denote the size of the set L(T^v_k,d).
Note that (v) = k^d-h where h is the depth of v.
Next, for a set A  L(T_k,d), we will write _A(v) = |A ∩ L(T^v_k,d)|  / (v).
When A is clear from the context, we will omit the subscript.


    Let k, d, q, τ∈ satisfy k,q≥ 2 and d ≥τ≥ 2k ·log(q).
    Next, let v ∈ V(T_k,d) be of depth at most d-τ and A  L(T_k,d)  satisfy _A(v) ≥1/q. 
    
    Then there exists a vertex u ∈ V(T^v,τ_k,d) such that for each y ∈(u) it holds that _A(y) ≥1/2q. 


    
    
    Suppose the claim does not hold.
    We will show that under this assumption for each i ∈ [τ] there exists v_i ∈ V(T^v,i_k,d) with (v_i) ≥1/q· (1 + 1/2k-2)^i-1.
    Then by substituting i = τ > (2k-2) ·log(q) and estimating (1 + 1/m)^m >2 (for all m ≥ 2) we will arrive at a contradiction: 
    (v_τ) ≥1/q·1 + 1/2k-2^(2k-2) ·log(q) > 
        1/q· 2^log(q)≥ 1.


    We now construct the promised sequence (v_i) inductively.
    For i = 1 we set v_1 = v which obviously belongs to T^v,1_k,d and satisfies (v) ≥1/q.
    To identify v_i+1 we consider (v_i) = u_1, u_2, …, u_k.
    We have (v_i) = 1/k·∑_j=1^k (u_j).
    We define v_i+1 as the child of v_i that maximizes the value of  (see <Ref>).
    By the assumption, one of the children satisfies (u_j) < 1/2q.
    Then (v_i+1) is lower bounded by the average value of  among the remaining k-1 children, which is at least
    1/k-1(v_i)· k - 1/2q.
    We have (v_i) ≥(v_1) ≥1/q so (v_i)· k - 1/2q≥(v_i)· k - (v_i)/2.
    We check that v_i+1 meets the specification:
    
    (v_i+1) ≥(v_i)/k-1·k - 1/2  = (v_i)·1 + 1/2k-2≥1/q·1 + 1/2k-2^i

    In the last inequality we have plugged in the inductive assumption. The lemma follows.


To apply <Ref> we need to identify many vertices satisfying _A(v) ≥1/2q.
To this end, we will utilize the following simple fact.


    Let a_1, a_2, …, a_ℓ∈ [0,1] be a sequence with mean at least x for some x ∈ [0,1].
    Then at least xℓ/2 elements in the sequence are lower bounded by x/2.


    Suppose that |{a_i ≥x/2| i ∈ [ℓ]}| < xℓ/2.
    This leads to a contradiction: 
    
    ∑_i=1^ℓ a_i < 1·xℓ/2 + x/2·ℓ
        
        = xℓ.





We will use the lemmas above for a fixed layer in the tree T_k,d to identify  multiple vertices v meeting the requirements of <Ref>.
For each such v we can find a close descendant u of v for which we are likely to observe a collision. 
The value ℓ in <Ref>, governing the probability of a collision, corresponds to the number of leaves in the subtree of u, i.e., (u).
Since this value appears in the exponent of the formula, we need a collection of such vertices u in which the total sum of (u) is large.




    Let k, d, q ∈ satisfy k,q ≥ 2, d ≥ 4kq. 
    If A  L(T_k,d) is a q-subset 
    then there exists a set F  V(T_k,d) with the following properties.
    
        
  * For each v ∈ F and u ∈(v) it holds that _A(u) ≥1/4q.
        
  * The sum ∑_v∈ F(v) equals at least  d · k^d· (4q)^-3k log(k).
    


    
    Let F_i  V(T_k,d) be i-th layer of T_k,d, i.e., the set of vertices of depth i; we have |F_i| = k^i and (v) = k^d-i for each v ∈ F_i.
    Since their subtrees are disjoint, we can see that 
    ∑_v∈ F_i |A ∩ L(T^v_k,d)| = |A|.
    Therefore ∑_v∈ F_i(v) / |F_i| ≥1/q.
    By <ref> at least 1/2q fraction  of the vertices in F_i must satisfy (v) ≥1/2q.
    Let us denote this subset as F^+_i.

    Let τ = ⌈ 2k ·log (2q) ⌉ and M = ⌊ d / τ⌋. 
    
    We define F^+ = F^+_0 ∪ F^+_τ∪ F^+_2τ∪…∪ F^+_(M-1)τ.
    Observe that for each pair u, v ∈ F^+ the trees T^u,τ_k,d,  T^v,τ_k,d are disjoint.
    We apply <ref> with q' = 2q to each v ∈ F^+ to obtain a vertex γ(v) ∈ V(T^v,τ_k,d) satisfying condition (1).
    The disjointedness of these subtrees ensures that the vertices γ(v)_v ∈ F^+ are distinct.
    We define F = {γ(v) | v ∈ F^+}.

    Now we take care of condition (2).
    Let us fix j ∈ [0, M-1].
    Since γ(v) ∈ V(T^v,τ_k,d) for v with the depth jτ, we infer that the depth of γ(v) is at most (j+1)τ-1 so |(γ(v))| ≥ k^d+1-(j+1)τ.
    We have established already that |F^+_jτ| ≥|F_jτ|/2q =  k^jτ/2q.
    The assumption d ≥ 4kq implies d ≥τ so we can simplify M = ⌊ d / τ⌋≥ d / (2τ).
    We estimate the sum within each layer F^+_jτ and then multiply it by M.
    
    
    ∑_v∈ F^+_jτ(γ(v)) ≥k^jτ/2q· k^d+1-(j+1)τ = k^d + 1 - τ/2q

    
    ∑_v∈ F(v) = ∑_j = 0^M-1∑_v∈ F^+_jτ(γ(v)) ≥d · k^d + 1 - τ/2τ· 2q

    To get rid of the ceiling, we estimate τ≤ 2k ·log (4q). 
    Then k^τ≤ k^2k log (4q) = (4q)^2k log(k).
    We also use a trivial bound τ≤ 4kq. 
    We can summarize the analysis by

    
    ∑_v∈ F(v) ≥d · k^d + 1 - τ/2τ· 2q = d · k^d+1/k^τ· 4qτ≥d · k^d+1/(4q)^2k log(k)· 16kq^2≥d · k^d/(4q)^3k log(k)
 


Now we combine the gathered ingredients to show that a random scheme yields a high probability of a collision with any fixed q-subset. At this point we also adjust d to be larger then the factors depending on k and q. 


    Let k,d,q ∈ satisfy d ≥ k · (4q)^4klog k.
    Consider some q-subset A  L(T_k,d).
    Suppose that we choose the scheme β = (f_v)_v ∈ V(T_k,d)∈(k,d) by picking each bijection f_v  L(T^v_k,d) → [|L(T^v_k,d)|] uniformly and independently at random.
    Then the probability that (A,β) has no collision is at most exp(-k^d).



    We apply <Ref> and use the obtained set F  V(T_k,d) to analyze the probability of getting a collision.
    Consider u ∈ F with (u) = {u_1,…,u_k} and let C_u denote the event that (A,β) has a collision at u.
    For each i ∈ [k] we have (u_i) = (u)/k and we know from <Ref>(1) that _A(u_i) ≥ 1/(4q). 
    For each i ∈ [k] a random bijection f_u_i is chosen between L(T^u_i_k,d) and [(u_i)].
    This can be interpreted as first picking an arbitrary bijection to [(u_i)] and then combining it with a random permutation over [(u_i)].
    We apply <Ref> with z = 4q to infer that the probability of getting no collision at u is upper bounded by
    
    C_u≤exp-(u_i)/z^k = exp-(u)/k·(4q)^k.

    Since the sets ((u))_u ∈ F are pairwise disjoint, the corresponding events C_u are independent.
    We can thus upper bound the probability of getting no collision at all by the product ∏_u∈ F C_u.
    
    Next, by <Ref>(2) and the assumption on d we know that
    
    ∑_u ∈ F(u) ≥ d· k^d· (4q)^-3k log k≥ k^d+1· (4q)^k .

    We combine this with the previous formula to obtain
    
    ⋃_u∈ F C_u = ⋂_u∈ F C_u = ∏_u∈ F C_u≤exp-∑_u∈ F(u)/k·(4q)^k≤exp(-k^d).



We are ready to prove <Ref> (restated below) and thus finish the proof of the reduction.

*

    We choose the scheme β by picking each bijection uniformly and independently at random.
    For a fixed q-subset A let C_A denote the event that (A,β) witnesses a collision. 
    In these terms, <Ref>
    says that C_A≤exp(-k^d). 
    Let 𝒜 be the family of all q-subsets A  L(T_k,d); we have |𝒜| ≤ 2^k^d.
    By the union bound, the probability that there exists a q-subset with no collision with β is 
    
    ⋃_A ∈𝒜 C_A≤∑_A ∈𝒜 C_A≤ 2^k^d· (1/e)^k^d < 1.

    Consequently, there is a positive probability of choosing a scheme β having a collision with every q-subset.
    In particular, this means that such a scheme exists.




§ CONCLUSION

We have shown that no FPT algorithm can achieve an (1)-approximation for Max Disjoint Paths on acyclic digraphs.
However, our reduction blows up the parameter significantly so it does not preserve a running time of the form f(k)n^o(k).
It is known that such a running time is unlikely for the exact variant of the problem <cit.>.
This leads to a question whether Max admits an (1)-approximation that is faster than n^(k).

Our proof yields an alternative technique for gap amplification in a parameterized reduction based on the probabilistic method (extending the restricted version appearing in <cit.>), compared to reductions relying on coding theory <cit.> or communication complexity <cit.>.
Can this approach come in useful for proving that Parameterized Inapproximability Hypothesis (PIH) follows from FPTW[1]?

plainurl


