Abstract 1 Introduction 2 Overview of our techniques 3 Definitions and preliminaries 4 Hardness results 5 Algorithmic results 6 Future research References Appendix A Flaw in the NP-completeness proof of Bang-Jensen and Thomassen

Revisiting Directed Disjoint Paths on Tournaments (And Relatives)

Guilherme de C. M. Gomes ORCID LIRMM, Université de Montpellier, CNRS, Montpellier, France
Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
Raul Lopes ORCID LIRMM, Université de Montpellier, CNRS, Montpellier, France
Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany
Ignasi Sau ORCID LIRMM, Université de Montpellier, CNRS, Montpellier, France
Abstract

In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when ck/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is 𝖶[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.

Keywords and phrases:
directed graphs, tournaments, semicomplete digraphs, directed disjoint paths, congestion, parameterized complexity, directed pathwidth
Category:
Track A: Algorithms, Complexity and Games
Funding:
Guilherme de C. M. Gomes: Funded by the European Union, project PACKENUM, grant number 101109317. Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them.
Raul Lopes: French project ELIT (ANR-20-CE48-0008-01) and HIDSS-0002 DASHH (Data Science in Hamburg - Helmholtz Graduate School for the Structure of Matter).
Ignasi Sau: French project ELIT (ANR-20-CE48-0008-01).
Copyright and License:
[Uncaptioned image] © Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Fixed parameter tractability
; Mathematics of computing Combinatorics
Related Version:
arXiv version: https://arxiv.org/abs/2504.19957 [31]
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

The Disjoint Paths problem is one of the most well-studied classical NP-complete graph problems [29]. It consists in, given an undirected graph G and k requests, which are pairs of vertices (s1,t1),,(sk,tk) known as terminals, deciding whether G contains k pairwise vertex-disjoint paths connecting each si to ti, for each i[k]. As a crucial ingredient of their Graph Minors project, Robertson and Seymour [40] proved that Disjoint Paths is fixed-parameter tractable (FPT) parameterized by k, that is, it can be solved in time f(k)n𝒪(1) on n-vertex graphs for some computable f. In this article, we focus on its directed counterpart, defined analogously for an input digraph D and called Directed Disjoint Paths, which is known to be much harder from a computational point of view: it is already NP-complete for k=2 terminals [25]. We abbreviate this problem by k-DDP, even when k is not fixed.

A number of approaches have been proposed to cope with this intractability, ranging from approximation algorithms[12, 43], heuristics [7, 38], parameterized algorithms [23, 41], restricting the input digraph D [25, 3, 16, 27, 26], or relaxing the problem by allowing congestion on vertices [10, 20, 30, 33, 34, 1, 37]. In this work we consider and combine the latter three approaches, which we proceed to discuss.

Let us start by restricting the graph class to which the input graph of k-DDP belongs. Two relevant classes of digraphs are typically considered when one seeks to improve the tractability of a problem: directed acyclic graphs (DAGs) and tournaments (that is, digraphs that can be obtained from a complete graph by orienting each edge). For the former, the (parameterized) complexity of k-DDP is well understood: the problem is NP-complete and solvable in time n𝒪(k) (hence, in the class XP[25], and 𝖶[1]-hard [41] (even to approximate within a constant factor [43]), thus unlikely to be FPT. For the latter, the landscape is more murky, and the goal of this article is to contribute to understanding it a bit better.

Bang-Jensen and Thomassen [3] claimed that k-DDP is NP-complete on tournaments when k is part of the input, and this result triggered a long line of research. In the same paper, Bang-Jensen and Thomassen [3] showed that the problem can be solved in polynomial time for k=2. In fact, their algorithm works on the larger class of semicomplete digraphs, where each pair of distinct vertices has least one arc between them, instead of exactly one as in tournaments; we note this class by 𝒮. Chudnovsky, Scott, and Seymour [16] showed that the problem can be solved in polynomial time for every fixed k on semicomplete digraphs, by providing an XP algorithm. Fradkin and Seymour [27] proved that the edge-disjoint version of the problem, for which all the results discussed above also apply, is also polynomial-time solvable on semicomplete digraphs for fixed k. It is worth mentioning that Seymour et al. [13, 16, 15, 27, 26, 35] built a containment theory on semicomplete digraphs for the study of minor-related problems, such as k-DDP (see also the work of Barbero, Paul, and Pilipczuk [5]). One of the key notions in this theory is a width measure of digraphs called directed pathwidth – a generalization of undirected pathwidth – that also plays a role in the current article.

Back to the k-DDP problem, the XP algorithm on tournaments [16] has been generalized by Chudnovsky, Scott, and Seymour [14] to the class 𝒞h of digraphs whose vertex set can be partitioned into a bounded number h of semicomplete digraphs (thus, 𝒮=𝒞1). More precisely, the running time of their algorithm is n𝒪((hk)5). The authors asked whether the result can be further generalized to the class 𝒜h of digraphs whose underlying graph has independence number at most h, and this is still open. For the edge-disjoint version of the problem, an affirmative answer was given by Fradkin and Seymour [27].

Concerning the fixed-parameter tractability of the problem, it is open whether k-DDP on tournaments (or semicomplete digraphs) is FPT parameterized by k. Interestingly, the edge-disjoint version of the problem was shown to be FPT on semicomplete digraphs by Fomin and Pilipczuk [23], by solving a more general problem called Rooted Immersion. In a nutshell (more details are given below when discussing our techniques in Section 2), theirs is a win/win approach based on the directed pathwidth of the input digraph. If the pathwidth is small (as a function of k), then a dynamic programming algorithm is used to solve the problem. Otherwise, it is shown that the digraph must contain a large obstruction to directed pathwidth called a triple [26], which is used to find an irrelevant vertex in the instance, i.e, a vertex whose removal does not affect the existence of a solution.

Note that the above win/win approach needs, as a first step, to compute the directed pathwidth of the input digraph in FPT-time. While this problem is open on general digraphs, an FPT algorithm on semicomplete digraphs is given in the same article [23]. This FPT algorithm to compute directed pathwidth was generalized by Kitsunai, Kobayashi, and Tamaki [36] to another superclass of semicomplete digraphs called h-semicomplete digraphs and denoted by 𝒮h for some fixed integer h0. Digraphs in this class satisfy the property that each vertex has at most h non-neighbors (in any direction). If we denote by 𝒯 and 𝒮 the classes of tournaments and semicomplete digraphs, respectively, it holds that 𝒮=𝒮0, and for every h0 (see the discussion in the beginning of Subsection 3.1),

𝒯𝒮𝒮h𝒞h+1𝒜h+1. (1)

Another transversal strategy to try to overcome the inherent hardness of k-DDP is to relax the problem by allowing every vertex of D to be used by at most c of the k paths of the solution, for some integer c1 that is also part of the input and is called the congestion; we call the corresponding problem Directed Disjoint Paths with Congestion, abbreviated by (k,c)-DDP. Note that if ck the problem is trivial, so we may assume that ck1. It is open whether the case k=3 and c=2 (which is the first non-trivial one with congestion greater than one) can be solved in polynomial time on general digraphs. There are, however, some positive results. For instance, Edwards, Muzi, and Wollan [20] showed that the problem for c=2 can be solved in polynomial time if the input graph is sufficiently connected as a function of k, which is not the case for the truly disjoint version [42]. See [10] for recent improvements of this result. A popular variant of the congested problem is an asymmetric version, where the goal is to either find a congested solution or to provide a no-answer for the disjoint version. This problem has been proved to be XP parameterized by k on general digraphs for some small values of c [30, 33, 34], usually exploiting the celebrated Directed Grid Theorem [9, 34, 32]. On the other hand, other articles [1, 37] study the parameterized complexity of (k,c)-DDP by considering parameters stronger than k.

Finally, it is worth mentioning that Cavallaro, Kawarabayashi, and Kreutzer [11] recently proved that the edge-disjoint version of k-DDP is FPT on Eulerian digraphs parameterized by k; this is one of the rare examples where (some variant of) the problem is FPT. We refer to the book of Bang-Jensen and Gutin [4] for a thorough introduction to algorithms on digraphs, in particular on tournaments and related superclasses.

Our contributions.

Due to space limitations, statements marked with “()” only have their full proofs in the full version. As mentioned above, the NP-completeness proof of Bang-Jensen and Thomassen [3] of k-DDP on tournaments triggered intensive research in this area [23, 14, 16]. Unfortunately, we realized that their proof has a flaw that does not seem to be easily fixable, as acknowledged by the authors [2]; see Appendix A for an explanation of this flaw. Our first contribution is to provide a new (correct) proof of this result.

Theorem 1 ().

Directed Disjoint Paths on tournaments is NP-complete.

As mentioned above, it is open whether k-DDP on tournaments is FPT parameterized by k. Recall that the win/win approach of Fomin and Pilipczuk [23] for the edge-disjoint version has two main ingredients (other than computing the directed pathwidth): a dynamic programming algorithm and an irrelevant vertex argument. While the former is claimed to exist for the vertex-disjoint version [23], the latter one is doomed to fail: Fomin and Pilipczuk [23] provide a counterexample even for k=2 consisting of a family of tournaments containing arbitrarily large triples (that are the structures where irrelevant vertices are found), but in which each vertex is relevant. Our next contribution is to prove that this obstacle disappears if we allow for a large congestion.

Theorem 2 ().

(k,c)-DDP on semicomplete digraphs is FPT parameterized by k restricted to instances satisfying c>k/2.

Note that since we can assume that ck1, the result of Theorem 2 covers roughly “half” of the range of values of the congestion c. It is natural to ask whether the problem remains NP-complete for this range of values of c, that is, when the congestion is lower-bounded by a linear function of k. This question is still open, but we provide the following hardness result, where the congestion c is almost linear in k (as ε approaches one).

Theorem 3 ().

(k,c)-DDP remains NP-complete on tournaments even restricted to instances satisfying c=kε, for every ε[0,1).

As discussed before, Chudnovsky, Scott, and Seymour [14] showed that k-DDP on the class 𝒞h can be solved in time n𝒪((hk)5). Our next result is to show that this algorithm is somehow optimal, in the sense that it is unlikely to get rid of both parameters in the exponent of n, even restricted to digraphs of bounded directed pathwidth.

Theorem 4 ().

The k-DDP problem on 𝒞h is 𝖶[1]-hard when parameterized by k+h, even if restricted to input digraphs of directed pathwidth two.

Moreover, Theorem 4 can be generalized to show hardness for (k,c)-DDP when c>k/2 (cf. Theorem 12, which, alongside Equation 1, implies that the win/win strategy cannot be extended beyond h-semicomplete graphs). We summarize our main contributions in Table 1.

Organization.

In Section 2 we give an overview of the techniques used to obtain our results. In Section 3 we provide preliminaries about general digraphs, tournaments, and related classes. In Section 4 (resp. Section 5) we present our negative (resp. positive) results. We conclude with some directions for further research in Section 6.

2 Overview of our techniques

The reduction that we use to prove Theorem 1 is novel and versatile enough so that we can build upon it and modify it appropriately to prove the NP-completeness of several variants of the problem. Intuitively, in the proof of Theorem 1 we reduce from a variant of 3-SAT where each variable has a bounded number of occurrences (namely, exactly three positive and one negative). This allows us to build an instance of k-DDP where a variable’s truth value is determined by two requests (cf. Figure 2), while the satisfaction of the clauses is encoded using one additional request per clause; interestingly, the paths that fulfill the requests have length at most five. By extending this construction using a single long path, named the critical path (cf. the black path in Figure 3), which is the unique way to fulfill several additional requests, we show how to prove NP-hardness for (k,c)-DDP for tournaments even if c=kε for ε[0,1) (cf. Theorem 3). With this approach, however, we are unable to prove hardness for (k,c)-DDP instances where c=εk and D is a tournament.

For the FPT algorithm given in Theorem 2, the challenge is that now we deal with vertex-disjoint paths, instead of edge-disjoint paths as in the original work by Fomin and Pilipczuk [23]. Much like theirs, our proof is a win/win approach that makes extensive use of k-triples (cf. 5), an obstacle for directed pathwidth on semicomplete digraphs introduced by Fradkin and Seymour [26], and has two steps: (i) show that, in a minimum solution, almost all vertices (in their case, arcs) of a sufficiently large (i.e., with more than f(k) vertices) triple can be used by other paths, and (ii) identify a vertex in the triple that can be safely removed from the instance. In the edge-disjoint setting, it was extensively used that, in a large enough triple, vertices had large in- or out-degree; consequently, finding available arcs to either shortcut (step i) or reroute (step ii) a solution was relatively simple. In the vertex-disjoint case, this does not happen; in fact, Fomin and Pilipczuk [23] present an infinite family of tournaments that have no irrelevant vertex for k-DDP. It is not hard to show that their counterexamples are also valid when ck/2 but, when c>k/2, we are able to easily find alternative paths, freeing up several vertices and thus making them irrelevant. In particular, we are able to implement step i using the pigeonhole principle: any two fully congested vertices have at least one path in common. This is not enough by itself, and we must carefully construct two shortcuts simultaneously, instead of only one, to show that vertices occupied by exactly c paths only amount to 𝒪((kc)) (see 18) elements of the triple. Step ii also offers additional challenges; in particular, when dealing with the exterior neighborhood of the triple, we must find large matchings entering and leaving the triple to properly reroute the paths using it. As such, instead of the polynomial on k used by Fomin and Pilipczuk, we now require the triple to have size of the order of 2𝒪(klogk).

Given the success of the win/win algorithms based on directed pathwidth, it is natural to see how far one can push this approach. The results of Kitsunai, Kobayashi, and Tamaki [36] that triples are also directed pathwidth obstacles for h-semicomplete digraphs is a further step in this direction. By Theorem 4 and Equation 1 however, the class of h-semicomplete digraphs is essentially as far as it goes, even if we allow for congestion (cf. Theorem 12). To prove Theorem 4, we take inspiration from Slivkins’ [41] proof that Directed Edge-Disjoint Paths is 𝖶[1]-hard parameterized by k on DAGs. In his reduction from the Clique instance (G,), a DAG in a matrix-like format is built in a way that each row corresponds to a copy of G and each column to a vertex. Moreover, only one cell may be available in each row, and this must correspond to a vertex of G in the clique; this accomplished with several requests in a way that of them are used to enforce the uniqueness, while (2) are used to encode the edges of the clique (cf. Figure 4). We adapt Slivkins’ proof by replacing parts of his gadgets with tournaments. This, however, opens us to cheating: an edge-encoding path could randomly walk along the newly introduced arcs and break the proof. To overcome this, we introduce several structures and requests in order to enforce a synchronous behavior in each row of the matrix (cf. Figure 5), which in turn cause the occupation of the important tournaments, except for the cell that encodes the clique vertex. Using a long path strategy, similar to the one used in Theorem 3, we are able to force that every vertex participates in the fulfillment of several requests while keeping both the congestion high (c=k/d for some constant 1<dk) and the directed pathwidth equal to two, proving that a statement analogous to Theorem 4 (i.e., Theorem 12) also holds for (k,c)-DDP.

3 Definitions and preliminaries

For basic background on graph theory and parameterized complexity, we refer the reader to [6] and [17, 39, 21, 19, 22], respectively. Given a digraph D, we adopt the classical notations degD(v),degD+(v), ND(v), and ND+(v) for the in-degree, out-degree, in-neighborhood, and out-neighborhood of a vertex vV(D), respectively, and by D[X] the subgraph induced by XV(D). Given X,YV(D), we say that X is complete to Y if (u,v)E(D) whenever uX and vY. We denote the directed pathwidth of D by dpw(D). We refer the reader to the appended full version for a complete set of preliminaries and definitions.

Definition 5 (k-triple).

Let D be a digraph. For an integer k1, a k-triple 𝒦 of D is formed by an ordered triple (A,B,C) of disjoint subsets of V(D) of size k with A={a1,,ak} complete to B, B complete to C={c1,,ck}, and with a perfect matching {(ci,ai)|i[k]} from C to A.

When working with a k-triple (A,B,C), it is useful to have an easy way to refer the associated endpoints of the matching from C to A. Thus we sometimes refer to this matching as a bijective mapping 𝖬 from C to A. That is, for i[k] we have 𝖬(ci)=ai and 𝖬1(ai)=ci. In addition, we extend graph-theoretical notation to k-triples in the following way. If 𝒦 is a k-triple, we denote by V(𝒦) the set ABC and by E(𝒦) the set of all arcs between pairs of vertices of V(𝒦). See Figure 1 for an example of a 4-triple.

Figure 1: A 4-triple (A,B,C).

3.1 Tournaments and relatives

As mentioned in the introduction, we denote by 𝒯 and 𝒮 the classes of tournaments and semicomplete digraphs, respectively. For every non-negative integer h, we consider three classes of digraphs. The class 𝒮h contains every digraph D such that every vV(D) has at most h non-neighbors. The class 𝒞h contains every digraph whose vertex set can be partitioned into at most h cliques. The class 𝒜h contains every digraph D with independence number at most h. Let D𝒮h; by applying Brook’s Theorem [8] to the complement of the underlying graph of D, we conclude that V(D) can be partitioned into h+1 cliques and thus 𝒮h𝒞h+1. Since every independent set of a digraph intersects any clique in at most one vertex, it also holds that 𝒞h𝒜h. In Table 1 we give a summary of our main results.

Table 1: Summary of our main results.
𝒯 𝒮 𝒞h
k-DDP NP-c. [Theorem 1]
(k,c)-DDP NP-c. for c=kε, ε[0,1) [Theorem 3] FPT by k+h when 2c>k [Theorem 2] 𝖶[1]-h. by k+h with dpw(T)2 [Theorem 4]

4 Hardness results

It has been assumed for a long time that Directed Disjoint Paths was an NP-hard problem on tournaments [14, 41, 33, 1], but there is a flaw in the proof given in [3]. Its authors have confirmed the flaw in their proof [2]. We provide a direct NP-hardness proof for tournaments and a parameterized lower bound for digraphs in Ch in this section.

4.1 Tournaments

Fortunately, as we show in the following theorem, k-DDP is indeed NP-hard on tournaments. We highlight that our reduction is completely different from the approach in [3]. In particular, we reduce from (3,1)-3-SAT, an NP-complete [18] variant of 3-SAT where each variable appears exactly four times, once negated and three times unnegated.

Construction.

Let (X,𝒞) be the input instance to (3,1)-3-SAT, where X is the set of variables and 𝒞 is the set of clauses, and (T,K) be the k-DDP instance we are going to build, with T denoting the digraph, and K denoting the set of requests. We begin by picking an arbitrary but fixed order x1,,xn of X. Now, for each variable xiX, add a copy of the directed butterfly gadget shown in Figure 2 to T, while (si,ti) and (s¯i,t¯i) are added to K; we denote this gadget by Bi. Intuitively, the paths between the white vertices of Bi must be contained in it and, since the gadget has only once center (namely, αi in Figure 2), at most one of them may avoid the “wings”, as shown in 6. This allows us to encode the assignment of a variable and only satisfy clauses for which the appropriate literal is true, i.e., adding si,αi,ti to the solution is equivalent to setting xi=𝗍𝗋𝗎𝖾.

(a) Structural arcs.
(b) Right-to-left arcs.
(c) Top-to-bottom arcs.
Figure 2: Directed butterfly gadget for variable xi, occurring negated in clause Cd and unnegated in clauses Ca,Cb, and Cc. White vertices represent terminals. The given orientations of the gray arcs will be important when talking about congested versions of the problem. Vertex αi is the center of Bi, while the two disjoint paths from the s vertices to the t vertices that do not use αi are its wings.

After building all n butterflies, add an arc from every uBj to every vBi whenever j>i. To encode our clauses, take each Ca𝒞, add new vertices pa,qa to T, the pair (pa,qa) to K, and the arc (qa,pa); arcs between each pa and qb, for ab, can be added arbitrarily. Now, take a{1,,m} as an example, and suppose that the a-th clause of 𝒞 is Ca=(x1x2x¯3); in this case, we add arcs from pa to the vertices x1a,x2a, and x¯3a, and from these to qa. For simplicity, the superscript j of each xij and x¯ij is the same as the subscript of the corresponding clause Cj. At this point, the only missing arcs to ensure we have a tournament are between vertices of butterfly gadgets and clause gadgets; we add them such that pa has no other outgoing arc and qa has no other incoming arc. This concludes the construction of (T,K), with K={(si,ti),(s¯i,t¯i)|xiX}{(pa,qa)|Ca𝒞}. For the above example, our goal is to witness the satisfiability of Ca with a path pa,y,qa, where y{x1a,x2a,x¯3a}, which will have to be the case as N+(pa)=N(qa)={x1a,x2a,x¯3a}.

Observation 6.

Let Bi be one of the butterfly gadgets of (T,K). If (T,K) admits a solution 𝒫, then (i) the paths that connecting (s¯i,t¯i) and (si,ti) are internal to Bi, and (ii) at least one of the wings of Bi is entirely occupied by such a path.

Proof.

Let P¯i,Pi𝒫 be the paths connecting (s¯i,t¯i) and (si,ti), respectively. Suppose that 𝒫 is minimal, i.e., none of its paths has an internal shortcut; for example, si,αi,t¯i,ti𝒫 because arc (αi,ti) has both endpoints contained in the path and could be used to shorten it. Let us first show that P¯iBi. Recall that N(t¯i){x¯id,αi}{v|vBj,j>i} and that no terminal of V(K) can be used as an intermediate vertex of a path, as they must be saturated by their own paths, so the only arcs incident to t¯i that may be used to reach it are the ones we have just listed. As such, the penultimate vertex of P¯i is either one of {x¯id,αi}, in which case we are done as {x¯id,αi}N+(s¯i) and 𝒫 is minimal, or it is in some Bj with j>i, but this is impossible as there is no path from s¯i to such a vertex in GV(K) by design. A symmetric analysis can be performed to show that PiBi: if αiPi, we are done as αiN+(si)N(ti), so suppose αiPi. Note that Bj, with j>i is unreachable from si in GV(K), and so we have that PiBj=. Moreover, for <i, ti is unreachable from any vertex of B in GV(K). Finally, every path between si and the right wing of Bi in GV(K) passes through αi, which is not in Pi, so the right wing of Bi does not intersect Pi. Consequently, if αiPi, then PiBi{αi,s¯i,x¯id,ti¯}, which is precisely the left wing of Bi, completing the proof of (i). Towards proving (ii), if Pi=si,xia,xib,xic,ti we are done, so suppose that Pi=si,αi,ti; by (i), this implies that P¯i=s¯i,x¯id,t¯i. A completely symmetric analysis can be performed if P¯i=s¯i,αi,t¯i to conclude that Pi=si,xia,xib,xic.

See 1

4.2 Tournaments with congestion

We now focus on (k,c)-DDP and show one way to extend Theorem 1.

Meta-construction.

We reduce from the instance (T,K) of k-DDP built in the proof of Theorem 1 to construct the instance (T,K,c) of (k,c)-DDP. Let B1,,Bn be the ordering of the butterfly gadgets, that is, Bj is complete to Bi when j>i. We perform the following modification to T: for each i[n1], reverse the arc (xi+1a,x¯id), where xi+1a is the unique out-neighbor of si+1 in the left wing of Bi+1. To conclude the construction of T, we add two vertices s,t and arcs such that x1a is the unique out-neighbor of s and x¯nd is the unique in-neighbor of t. We illustrate the resulting tournament T in Figure 3. To obtain K, we add two families of requests: for each (u,v)K, we have one copy of (u,v) and c1 copies of (𝒖,𝒗); in the second, we have c1 requests (s,t) and one request (t,s). As such, k=k+(c1)k+c=(k+1)c, so it follows that, if c is a fixed power of (k+1), say c=(k+1)γ we have k=cγ+1/γ=c1/ε. This concludes the construction of (T,K,c).

Figure 3: Queuing of the butterfly gadgets performed for the construction of T. Gray arcs do not participate in the critical path of T, while black arcs do. Again, within the butterfly gadgets, we add the missing arcs from top-to-bottom, right-to-left. All other arcs are also right-to-left.

First, note that the terminals in each Bi cannot be used as internal vertices of any path as they each participate in c requests. Now, observe that the other vertices of the butterflies are the only elements of V(T) that are not in request in K. Moreover, by construction, they all participate in the unique s-t path of TV(K{(s,t)}) in the same order specified by B1,,Bn. We call this path the critical path of T, and in any solution to (T,K,c), all of its inner vertices participate in at least c1 paths; cf. the black arcs in Figure 3. Considering this and that all butterfly gadgets are occupied by c1 paths that are single arcs, all that remains to be solved is (T,K), and Theorem 3 follows. Moreover, if we allow larger congestion values, we can prove a weak NP-hardness result (cf. Theorem 7).

See 3

Theorem 7 ().

(k,c)-DDP is weakly NP-hard on tournaments if the congestion is of the form |K|logε|K|, for every ε>0.

Overcoming the kε barrier has proved extremely challenging, and seems to require a very different approach to the one we employed, which demanded 𝒪(|V(T)|c) requests. We can adapt our proofs to other cases and avoid this. For the Restricted (k,c)-DDP problem, where terminals may only be used as endpoints of paths, we prove Theorem 8. If we do not add this restriction, we obtain Theorem 9, but for digraphs in 𝒞2 instead of tournaments.

Theorem 8 ().

Restricted (k,c)-DDP remains NP-complete even when restricted to tournaments and when c=εk for every ε(0,1).

Theorem 9 ().

(k,c)-DDP is NP-complete on 𝒞2 and when c=k/d, for d(0,k].

4.3 𝗪[𝟏]-hardness on 𝒌 + 𝒉 on graphs of directed pathwidth two

Recall that G𝒞h if and only if its vertices can be partitioned in h sets that induce tournaments in G. We show that the XP algorithm given in [14] cannot be significantly improved, as we prove that k-DDP remains 𝖶[1]-hard when parameterized by k+h on graphs of bounded directed pathwidth. As in Section 4.1, we first deal k-DDP and then show how to extend to (k,c)-DDP. We heavily simplify the construction as it is very technical. Our reduction is heavily inspired by, but requires significant increments to, the proof of Slivkins [41] of the 𝖶[1]-hardness of Directed Edge-Disjoint Paths on DAGs.

Construction.

Let (G,𝒱) be the input instance of Multicolored Clique parameterized by q=|𝒱| where 𝒱={V1,,Vq} are the color classes and (D,K) denote the k-DDP instance we are going to build. A solution to the former is a clique of size at least q that contains a vertex of every color class. For simplicity, assume that every Vi𝒱 has the same size n. The vertices of D are partitioned in a q×(2+n) matrix-like fashion, with Di,jV(D) corresponding to the j-th vertex of Vi𝒱 and Di,0,Di,n+1 with no correspondence. For every i[q], let us define and add the following sets of vertices to G, where each Di,j is a set of 2q+3 vertices that will be specified later: Di={αi,s,αi,t,ai,s,ai,t,bi,s,bi,t}{gi,s1,gi,t1,gi,s2,gi,t2}j{0}[n+1]Di,j. We keep to the convention that vertices with an s/t subscript are sources/targets of a request of K.

Each Di,j is broken down into four tournaments, namely Di,jα={αi,j}, Di,jβ={βi,j1,βi,j2}, and, for x{a,b}, Di,jx={xi,j0,xi,j1,,xi,jq}; intuitively, xi,j is the only vertex that will connect Di,j to vertices of D, while xi,j0 is used to synchronize the internal behavior of Di. Each of these tournaments has a single Hamiltonian path, with all other arcs going in the opposite direction. Moreover, there is a perfect matching from Di,ja{ai,j0} to Di,jb{bi,j0} with ai,j matched to bi,j (cf. Figure 4). Now, for each x{α,a,β,b}, we concatenate the endpoints of the Di,jx’s in order to form a long, unique, Hamiltonian path, with the other arcs again going backwards. We connect the Di,j’s with arcs as (partially) shown in Figure 5: an α vertex connects to β2 one column to the left and to a0 two columns to the right, bi,jq to the next column’s β1, ai,j0 to the β1 one column to the left, and aq)i,j to the b0 to columns to the right. Minus the matching, these arcs encode that only one cell of Di may be unoccupied by paths internal to Di; this corresponds to one vertex of Vi being picked to the solution.

We now must encode that these vertices indeed form a clique of G. As such, if uvE(G), uVi, vV, add the arc (bi,u,a,vi); this encodes the adjacencies of G. Our final set of vertices are obtained by adding the following requests and their corresponding vertices (δi,,s,δi,,t), where i[q] and [q][i1]; this implies that |K|=5q+(q2)+q. We connect δi,,s to each ai,h and each b,ri to δi,,t, as in Figure 4. Note that, if we can guarantee that each i[q] has exactly one Di,j unoccupied by the paths discussed in Step (ii), then the paths used to satisfy each δi, pair must, necessarily, go through arcs of D that encode adjacency in G, and all such arcs must be incident to the same vertex of Vi.

Figure 4: Partial representation of Di,h and D,r. The shaded path encodes one edge of the multicolored clique of G. Differently shaped/colored vertices correspond to different requests of K.
Figure 5: Paths used to satisfy the interior requests of a gadget Di if j=2; the i subscript is omitted for readability. Shaded contiguous paths represent the appropriate paths in the solution of (D,K). Differently shaped/colored vertices correspond to different requests of K.
Observation 10.

Instance (D,K) of k-DDP has |K|=6q+(q2), D can be partitioned into 6q+2(q2) tournaments and has directed pathwidth equal to 2.

Breaking the Θ(q2) bound for either |K| or h seems very hard with this approach, so we do not further trim down either parameter. For the converse direction, we can show that minimal solutions in (D,K) must adhere to a specific format: the jumps between the x-paths of each Di happen synchronously as in Figure 5: all jumps in Di happen simultaneously around the same index j. This synchronicity allows us to prove the key ingredient of our proof and the main complication to generalize Slivkins’ result: both the a- and b-paths of Di must be completely used by the internal paths of Di, except for Di,j, which is essentially untouched by them. We need this to avoid cheating by the δ paths: without it, we could have a δ path hitting an a vertex at some index u, going to an a vertex of index v using an arc added to force the appearance of a tournament, moving to its matched b vertex and then moving on to any Dj, completely breaking down the desired behavior. With these bizarre paths safely ruled out, proving the converse becomes quite direct, and we have our theorem.

See 4

Into the congestionverse.

As with Theorem 3, we employ the critical path trick. Essentially, we introduce a path that is almost Hamiltonian, missing only the δ vertices of Theorem 4. It is also possible to include them in this new path, but for simplicity’s sake we do not. Formally: let (D,K) be the instance of k-DDP built in the proof of Theorem 4 and c>1 be an integer; to obtain (D,K,c), we add c1 requests of the form (zs,zt) to K and the corresponding vertices to D. Now, add the arcs (zs,gq,t1) and (g1,s2,zt) to D. Then, for each i[q], we add the arcs (bi,t,bi,s), (ai,t,ai,s), (gi,s1,αi,s) and, if i>1, (gi,s2,gi1,t1). This completes the construction of (D,K); note that |K|=|K|+(c1) and that dpw(D)=2.

Observation 11.

There exists a unique path Pz that can satisfy (zs,zt) and, for every i[q], this path is obtained by concatenating the β-, b-, a- and α-paths, in this order.

We are now free to choose c to get the fraction of k we desire and, consequently, Theorem 12

Theorem 12 ().

(k,c)-DDP jointly parameterized by the number of requests |K| and the minimum clique cover of the host graph is 𝖶[1]-hard even if the input instance has directed pathwidth 2 and the congestion c is a fraction of, but not equal to, |K|.

5 Algorithmic results

In this section we prove our main algorithmic result and discuss its applications.

Theorem 13 ().

For all integers k1, h0, there exists a computable function f(k,h) such that every instance of (k,c)-DDP with 2c>k on an h-semicomplete digraph D containing a f(k,h)-triple has an irrelevant vertex which can be found in 𝒪(f2(k)n2) time. In particular, f(k,0)=𝒪(2klogk).

Fomin and Pilipzcuk [23, Theorem 6.3] showed that Directed Edge-Disjoint Paths is FPT on tournaments parameterized by the number of paths. They solve the problem with a win-win approach. First they show that the problem is FPT parameterized by the directed pathwidth dpw(T) of the input semicomplete digraph T plus the number k of paths. Then, through a series of results and constructions, they show that there is a computable function g(k) such that every semicomplete digraph T with dpw(T)g(k) contains a k-triple, and that every such triple contains a vertex v that is irrelevant for the given instance. This second proof essentially shows that only the instances with dpw(T) bounded by some function of k need to be solved. Although they leave open whether k-DDP is FPT on semicomplete digraphs, they mention that an FPT dynamic programming algorithm, parameterized by the number of paths, can be done for k-DDP to obtain a result analogous to [23, Theorem 6.3].

Another approach to obtain such an FPT algorithm relies on directed cliquewidth, which is bounded from above by dpw(T)+2 on every semicomplete digraph T [23, Lemma 2.14]. Then one can apply [23, Theorem 2.16] which states that, given an MSO1 formula ϕ and a semicomplete digraph T, there is an algorithm which checks whether ϕ is satisfied by T in FPT time parameterized by the order of ϕ and dpw(T). This implies the existence of an FPT algorithm on semicomplete digraphs for Directed Disjoint Paths parameterized by the number of paths, since this problem can be modeled by MSO1 (see, for instance, [28, Proposition 4.7]). In any case, the following is obtained.

Proposition 14 (Fomin and Pilipzcuk [23]).

k-DDP on semicomplete digraphs parameterized by the number of paths and the directed pathwidth is in FPT.

Applying classical techniques, one can show easily show that 14 also implies an FPT algorithm for (k,c)-DDP. Indeed, given an instance of this problem on a semicomplete digraph T, it suffices to add copies v2,,vc of each vV(T) with the same in- and out-neighborhood as v. Then, we add arcs among vertices in {v,v2,,vc} in order to ensure that this set induces an acyclic tournament. This procedure easily implies that the directed pathwidth of T increases by at most a factor of c. Hence we can apply 14 to solve k-DDP in the newly constructed digraph and transport any solution, whether positive or negative, to the original instance. This implies that (k,c)-DDP is also FPT parameterized by k and the directed pathwidth of the input digraph. When applying their irrelevant vertex rule, Fomin and Pilipzcuk [23] use a series of results ([23, Theorem 4.12, Lemmas 3.6, 3.9, and 3.12, proof of Theorem 9.9]) to construct in FPT time a triple of large order on semicomplete digraphs of sufficiently large directed pathwidth, obtaining the following.

Proposition 15 (Fomin and Pilipzcuk [23]).

Let T be a semicomplete digraph. There is a computable function g(t) and an FPT algorithm parameterized by t that either outputs a directed path decomposition of T with width at most g(t) or finds a t-triple in T.

In light of Propositions 15 and 14, it is now easy to apply Theorem 13 to obtain an FPT algorithm for (k,c)-DDP when 2c>k, proving Theorem 2.

See 2

5.1 Irrelevant vertices in 𝒌-triples

This section is dedicated to the proof of Theorem 13. We first prove the version of Theorem 13 restricted to semicomplete digraphs. Our algorithm relies on the existence of arcs between every pair of vertices in two of its parts. First, when performing reroutings inside the f(k)-triple; and secondly, when discussing how the triple interacts with its in- and out-neighbors outside the triple. In this case, we partition the in- or out-neighborhood of the triple into the large and small vertices, that have many and few neighbors, respectively, in the triple. Informally, the goal is to show that vertices with large in- or out-neighborhood in the triple (depending on the case of the analysis) can be used to reroute paths in a desirable way. At this step, it suffices to increase the thresholds that define the large and small sets by a factor of h in order to extend the analysis to the class 𝒮h. By doing so, we ensure that at each of those steps the number of non-neighbors of the observed vertex is taken into account in the underlying pigeonhole argument, and thus the same ideas work for h1.

We abbreviate f(k,0) by f(k) and assume that an f(k)-triple is given. The choice of f(k) is discussed later. Let =(T,K,c) be an instance of (k,c)-DDP on a semicomplete digraph T with 2c>|K|=k. For the remainder of this section, as well as in Subsection 5.2 and Subsection 5.3, we assume that 𝒦 is an f(k)-triple (A,B,C) of T and that 𝒫 is a set of paths satisfying 16.

Property 16.

𝒫 is a solution {P1,,Pk} for minimizing i[k]|V(Pi)|.

As congestion is allowed, a vertex is counted in the summation as many times as it is used by a path. This per-path measure is necessary as we often shortcut (formally defined later in this section) a path P𝒫 through a vertex that is used by other paths in the solution 𝒫.

To avoid some technicalities, we make two assumptions about 𝒦. First, by discarding at most 2k vertices of each set A,B, and C, we assume that no terminal of appears in V(𝒦). Second, by deleting parallel arcs of T if necessary, we assume that there are no arcs in E(𝒦) from C to B and no arcs from B to A. Removing these arcs poses no issues for the irrelevant vertex argument since an irrelevant vertex of TT is also irrelevant in T.

The set B plays as distinguished role in this proof since it concentrates the heads of all arcs of 𝒦 between A and B and the tails of all arcs of 𝒦 between B and C. The goal is to show that there is room to reroute paths in 𝒦 in order to show that if is a yes-instance, then there is a vertex bB and a solution 𝒬 for such that every Q𝒬 accessing b does so from a vertex in A and to a vertex in C.

We follow the blueprint of the proof for Directed Edge Disjoint Paths on semicomplete digraphs by Fomin and Pilipzcuk [23]. A fundamental property in their case is that any vertex with out-degree (resp. in-degree) at least k+1 in the given triple has at least one arc leaving (resp. entering) it that is not used by any solution 𝒬 minimizing the sum of the lengths of its paths. This property allows them to prove that every such solution cannot use more than two arcs of the matching from C to A. This, in turn, is used to show that every path in 𝒬 uses at most 2k+4 vertices from A and from C, and at most 4k vertices of B. The hard part of their proof is about how to apply these results to prove that an irrelevant vertex is guaranteed to exist in a large enough triple, and how to find it in polynomial-time.

In our case, the existence of a vertex vV(𝒦) with large out-degree or in-degree in the triple does not guarantee that we can find a vertex in N+(v)N(v) that is not used by a path of 𝒫. In fact, in many places of our proof we do not guarantee that at all, since we produce shortcuts for paths in 𝒫 through vertices that have been used by other paths of 𝒫 while but at most c1 of them, hence being careful not to exceed the allowed congestion on each vertex. The fundamental property that we use comes from the assumption that 2c>k: if u,v are both used by c paths, then by the pigeonhole principle there is a path that uses both u and v. Reliance on this property makes our analysis significantly harder than the one in [23]. For example, in order to show that a few vertices of A and C are used by paths of 𝒫 (19), we first need to show that some vertices of B can be used for shortcuts (18) and these two proofs are already much harder than their counterparts in [23].

We also adopt the following notation. Let 𝖬 denote the arcs of the matching from C to A; recall that 𝖬 may be seen as a bijective mapping from C to A according to the matching arcs defining 𝒦. Additionally, for CC (resp. AA) we call the set 𝖬(C)={𝖬(v)|vC} (resp. 𝖬1(A)={𝖬1(u)|uA}) the mirror of C (resp. of A) in 𝒦.

For Pi𝒫 we denote by i the order in which V(Pi) appears in Pi. A shortcut for Pi is a walk R such that there is some subpath RPi where |V(R)|<|V(R)| and R starts and ends in the same vertices as R. We may refer to a shortcut R as the sequence v1vm of vertices of R as they appear in the walk. The existence of a shortcut for a path of 𝒫 respecting the congestion bound contradicts 16, and the goal of the first part of the proof of Theorem 13 is to exploit this fact to prove useful properties on how the paths of 𝒫 interact with the triple. We refrain from stating that these shortcuts lead to contradictions in the proofs of this section for conciseness. Simply replacing R with R may not lead to a minimal solution: there could be forward arcs that further shorten the resulting object, or cycles could be introduced, depending on the visiting order of the involved vertices.

For every vV(𝒦), we assign to v a list of indices 𝖫(v)2[k] representing which paths of 𝒫 are using v. Thus |𝖫(v)|c holds for any vertex v since 𝒫 is a solution for . For i[k], we say that v is i-free if i𝖫(v) or if |𝖫(v)|c1, and that v is i-saturated otherwise. Intuitively, an i-free vertex can be used to construct shortcuts for path Pi since either Pi is already using v and thus the route may be replaced with a shorter one without increasing the congestion of v, or the congestion of v is not yet saturated and can be increased by one to generate a better solution. We denote by the set of all possible lists of indices that can be assigned to a vertex by a solution. More precisely, ={L2[k]||L|c}. For L we denote by V(L) the set {vV(𝒦)|𝖫(v)=L} of vertices of 𝒦 which are assigned indices in L. Finally, we say that {u,v}V(T) is an i-free pair if both u and v are i-free.

5.2 Freeing 𝑨,𝑩, and 𝑪

In this section, we show that only a bounded number of vertices bB have |𝖫(b)|=c, and how to use this result to bound the number of vertices that each Pi𝒫 can use in A and C.

Lemma 17 ().

For all Pi𝒫, if |V(Pi)B|5 then there are no i-free pairs.

Lemma 18 ().

For all L with |L|=c, it holds that |V(L)B|4.

Sketch of the proof.

By contradiction, assume that there is L such that |L|=c and |V(L)B|5. For all iL, let Ai=V(Pi)A and Ci=𝖬1(Ai). If all iL satisfy |Ai|4c, then |V(L)A|4c2 and thus there are many i-free vertices in A=AAi and a shortcut for Pi can be found by applying 17 and observing the mirror of A.

Assume now that there is an iL such that |Ai|4c+1 and notice that every uCi has |𝖫(u)|=c, as otherwise {u,𝖬(u)} would be an i-free pair, contradicting 17 as |V(Pi)B||V(L)B|5. The goal now is to group all pairs of the form {u,𝖬(u)} with uCi according to which indices appear in 𝖫(u)𝖫(𝖬(u)). The size of |Ai| guarantees that at least one index appears in the lists of the endpoints of many of these pairs and we use it to shortcut two paths. First, we shortcut P through some bV(L)B. By doing this, we no longer have a solution for our instance since a vertex of this set is used by c+1 paths. However, the shortcut for P frees some vertices of C, which are now used by at most c1 paths. Thus we can shortcut Pi in a way that avoids b to generate a new solution contradicting 16. Formally, we proceed as follows. For j[k]L, let Xj be the set of pairs {u,𝖬(u)} such that j𝖫(u)𝖫(𝖬(u)) with uCi. Notice that these sets are not necessarily pairwise disjoint and that the exclusion of L is natural as the occurrence of any of its indices in 𝖫(u)𝖫(𝖬(u)) would contradict 17. In addition, the pigeonhole principle implies that at least one set X satisfies |X|5 as |Ai|4c+1.

Let A be the subset of vertices of A appearing in pairs of X and C=𝖬1(A), and let b1,,bq be the first q5 vertices of V(L)B ordered i. We consider two cases. In the first case, P uses a vertex of A before any vertex of C. If v1 is the first vertex of A used by P, then we shortcut P through v1b3u, where u the last vertex of C used by P, to build P and set 𝒫=(𝒫{P}){P}. Notice that b3 is by c+1 paths of 𝒫. However, P avoids at least three vertices of C{𝖬1(v1)}. If u is one of them, we can shortcut Pi through b1u𝖬(u)bq to avoid b3, thus reducing the congestion of this vertex back to c and finding a solution that contradicts 16. Figure 6 illustrates this shortcut. In the second case, P uses a vertex of C before any vertex of A, but the proof is analogous. We remark that |A|5 is needed only in this case due to the size of the shortcut for P.

Figure 6: Shortcuts built in the first case of the proof of 18. The blue path starting in v1 is the shortcut for P. The red path starting in b1 is the shortcut for Pi.

18 implies that at least f(k)4(kc) vertices of B are used by at most c1 paths of 𝒫. Thus, all such vertices are i-free for any i[k] and can be used to build shortcuts for any path in 𝒫. We now show that only a few vertices of A and C are used by paths of 𝒫.

Lemma 19 ().

If there is bB such that |𝖫(b)|c1, then for all 𝒫i𝒫 it holds that |V(Pi)A|8c+4; and |V(Pi)C|8c+4.

5.3 Finding the irrelevant vertex in polynomial time

With 19, we can show 20, a tighter bound on |V(𝒫)B| that is critical to our proof of Theorem 13; in particular, this allows us to reroute all paths that touch an irrelevant vertex candidate through only one other vertex of B.

Corollary 20 ().

For all i[k], |V(Pi)B|4.

We are now ready to prove Theorem 13 restricted to semicomplete digraphs. The goal is to give a polynomial-time algorithm that finds a vertex bB such that if there is a solution for , then there is another solution whose paths all avoid b. We follow the blueprint of the proof by Fomin and Pilipzcuk [24, Theorem 9.1]. The goal is to first find a large set XB such that every path of a solution entering some bX from outside 𝒦 can be rerouted to access b from a vertex in A. Then, we must show that there is a bX such that every path of the solution leaving b to a vertex not in C can be rerouted to leave b to a vertex in C. As these reroutings do not use too many extra vertices in the triple, by 20, and our hypothesis that the triple is large, we can then argue that b can be replaced with another bB, that is unused by the solution, and thus b can be safely removed from the graph.

Thus, at some point in the proof, we need to analyze how a path of a solution for can enter and leave B, and show how to reroute paths not respecting the desired behavior using vertices outside of the triple. In Fomin and Pilipczuk’s proof, the fact that they consider collisions in arcs plays a major role here in this step. Informally, in a particular case of their analysis and using our notation, if a path Pi accesses bB through a vertex vV(T)A and v has “sufficiently many” out-neighbors in V(T)A which are in-neighbors of distinct vertices of B, then at least one of those out-neighbors, say v, can be used to reroute Pi through vvu𝖬(u)b. This holds due to three main properties: (i) at most k arcs leaving a vertex are used by any solution, and thus any vertex of out-degree at least k+1 has one arc leaving it that is free, (ii) their versions of Lemmas 18 and 19, and (iii) a clever analysis on the behavior of the arcs between in-neighbors of vertices in B outside of A.

In our case, an analogous to the first of those three points requires more work since, a priori, it may seem that we have little control on how a solution intersects the in-neighborhood of B outside of A. We prove that this is not the case by applying another shortcutting argument which allows us to bound how many vertices a path Pi𝒫 can use in a particular subset of in-neighbors of B. In addition, after the first rerouting round, we can no longer rely on 16, as we do increase the length of each path by an 𝒪(1) factor. Thus a small trick is needed to apply a similar shortcutting argument as the one used in the in-neighbors of B, this time to the out-neighbors of B; this happens when we want to find a vertex of B that, when used by a path, is always followed by a vertex of C.

6 Future research

This work touched on several common strategies used to cope with the hardness of the Directed Disjoint Paths problem. We investigated its (parameterized) complexity on tournaments and some of its superclasses, both with and without the typical relaxation of allowing congestion in the vertices. One of our key contributions is a fix (Theorem 1) for a gap in the literature originating in a flaw in the NP-hardness proof for k-DDP on tournaments given in [3]; we also as adapt a win/win approach based on directed pathwidth first used in an FPT algorithm for Directed Edge-Disjoint Paths parameterized by the number of paths on tournaments [23] to (k,c)-DDP when 2c>k. We note, however, that this latter problem is not known to be NP-complete; while we are able to show that (k,kε)-DDP is hard for every ε[0,1), we are unable to extend this to c=εk, or even c=k/2+1. Alongside the already challenging problems listed in Section 1, we consider this the main open question related to our work. We do not provide all the details for the proof of Theorem 13 in its full generality, only for the case of semicomplete graphs. Extending our arguments to h>0 is just a matter of technicalities: we must increase the size of the triple taking h into account and, when discussing the exterior neighborhood of the triple, increase the thresholds to classify the in- and out-neighbors of B as having “too many” neighbors in B or not. This extension, however, is not enough to give an FPT algorithm for (k,c)-DDP on h-semicomplete graphs when 2c>k. In particular, two challenges remain: (i) computing a triple for elements of this class in FPT-time, as the only known algorithm being an XP one introduced by Kitsunai, Kobayashi, and Tamaki [36]; and (ii) devising an FPT algorithm for the joint parameterization by k, h, and the directed pathwidth, which would also improve upon the XP algorithm shown in [36]. We recall that, among the classes studied in our work, an FPT algorithm for h-semicomplete digraphs is the best we can hope for, as we have shown that k-DDP and (k,c)-DDP are 𝖶[1]-hard when parameterized by k and the number of covering tournaments on digraphs of directed pathwidth two (Theorem 4 and Theorem 12).

References

  • [1] Saeed A. Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. Information Processing Letters, 151:105836, 2019. doi:10.1016/j.ipl.2019.105836.
  • [2] Jørgen Bang-Jensen and Caresten Thomassen. Personal communication. Personal Communication, 2024.
  • [3] Jørgen Bang-Jensen and Carsten Thomassen. A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM Journal on Discrete Mathematics, 5(3):366–376, 1992. doi:10.1137/0405027.
  • [4] Jørgen Bang-Jensen and Gregory Gutin. Classes of Directed Graphs. Springer Monographs in Mathematics, 2018. doi:10.1007/978-3-319-71840-8.
  • [5] Florian Barbero, Christophe Paul, and Michal Pilipczuk. Strong immersion is a well-quasi-ordering for semicomplete digraphs. Journal of Graph Theory, 90(4):484–496, 2019. doi:10.1002/JGT.22408.
  • [6] Adrian Bondy and U.S.R. Murty. Graph Theory. Springer-Verlag London, 2008.
  • [7] Ulrik Brandes, Wolfram Schlickenrieder, Gabriele Neyer, Dorothea Wagner, and Karsten Weihe. A software package of algorithms and heuristics for disjoint paths in planar networks. Discrete Applied Mathematics, 92(2-3):91–110, 1999. doi:10.1016/S0166-218X(99)00048-7.
  • [8] Rowland Leonard Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194–197, 1941. doi:10.1017/S030500410002168X.
  • [9] Victor Campos, Raul Lopes, Ana Karolinna Maia, and Ignasi Sau. Adapting the Directed Grid Theorem into an FPT Algorithm. SIAM Journal on Discrete Mathematics, 36(3):1887–1917, 2022. doi:10.1137/21M1452664.
  • [10] Victor A. Campos, Jonas Costa, Raul Lopes, and Ignasi Sau. New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages. In Proc. of the 31st Annual European Symposium on Algorithms (ESA), volume 274 of LIPIcs, pages 30:1–30:18, 2023. doi:10.4230/LIPICS.ESA.2023.30.
  • [11] Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Edge-Disjoint Paths in Eulerian Digraphs. In Proc. of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 704–715, 2024. doi:10.1145/3618260.3649758.
  • [12] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An o(n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146, 2006. doi:10.4086/TOC.2006.V002A007.
  • [13] Maria Chudnovsky, Alexandra O. Fradkin, and Paul D. Seymour. Tournament immersion and cutwidth. Journal of Combinatorial Theory, Series B, 102(1):93–101, 2012. doi:10.1016/J.JCTB.2011.05.001.
  • [14] Maria Chudnovsky, Alex Scott, and Paul Seymour. Disjoint paths in unions of tournaments. Journal of Combinatorial Theory, Series B, 135:238–255, 2019. doi:10.1016/j.jctb.2018.08.007.
  • [15] Maria Chudnovsky and Paul D. Seymour. A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B, 101(1):47–53, 2011. doi:10.1016/J.JCTB.2010.10.003.
  • [16] Maria Chudnovsky, Paul D. Seymour, and Alex Scott. Disjoint paths in tournaments. Advances in Mathematics, 270:582–597, 2015. doi:10.1016/j.aim.2014.11.011.
  • [17] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
  • [18] Andreas Darmann and Janosch Döcker. On simplified np-complete variants of monotone 3 -sat. Discrete Applied Mathematics, 292:45–58, 2021. doi:10.1016/j.dam.2020.12.010.
  • [19] Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
  • [20] Katherine Edwards, Irene Muzi, and Paul Wollan. Half-Integral Linkages in Highly Connected Directed Graphs. In Proc. of the 25th Annual European Symposium on Algorithms (ESA), volume 87 of LIPIcs, pages 36:1–36:12, 2017. Full version available in https://arxiv.org/abs/1611.01004. doi:10.4230/LIPIcs.ESA.2017.36.
  • [21] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006. doi:10.1007/3-540-29953-X.
  • [22] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. doi:10.1017/9781107415157.
  • [23] Fedor V. Fomin and Michal Pilipczuk. On width measures and topological problems on semi-complete digraphs. Journal of Combinatorial Theory, Series B, 138:78–165, 2019. doi:10.1016/J.JCTB.2019.01.006.
  • [24] Fedor V. Fomin and Michał Pilipczuk. On width measures and topological problems on semi-complete digraphs. Journal of Combinatorial Theory, Series B, 138:78–165, 2019. doi:10.1016/j.jctb.2019.01.006.
  • [25] Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111–121, 1980. doi:10.1016/0304-3975(80)90009-2.
  • [26] Alexandra O. Fradkin and Paul D. Seymour. Tournament pathwidth and topological containment. Journal of Combinatorial Theory, Series B, 103(3):374–384, 2013. doi:10.1016/J.JCTB.2013.03.001.
  • [27] Alexandra O. Fradkin and Paul D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. Journal of Combinatorial Theory, Series B, 110:19–46, 2015. doi:10.1016/J.JCTB.2014.07.002.
  • [28] Robert Ganian, Petr Hliněný, Joachim Kneis, Alexander Langer, Jan Obdržálek, and Peter Rossmanith. Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics, 168:88–107, 2014. doi:10.1016/j.dam.2013.10.038.
  • [29] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. URL: https://dl.acm.org/doi/10.5555/574848.
  • [30] Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon. The canonical directed tree decomposition and its applications to the directed disjoint paths problem, 2020. arXiv:2009.13184.
  • [31] Guilherme C. M. Gomes, Raul Lopes, and Ignasi Sau. Revisiting directed disjoint paths on tournaments (and relatives), 2025. arXiv:2504.19957.
  • [32] Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, and Irene Muzi. Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem. In Proc. of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1–20, 2024. doi:10.1109/FOCS61266.2024.00011.
  • [33] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In Proc. of the 46th Annual ACM on Symposium on Theory of Computing (STOC), pages 70–78, 2014. doi:10.1145/2591796.2591876.
  • [34] Ken-ichi Kawarabayashi and Stephan Kreutzer. The Directed Grid Theorem. In Proc. of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 655–664. ACM, 2015. doi:10.1145/2746539.2746586.
  • [35] Ilhee Kim and Paul D. Seymour. Tournament minors. Journal of Combinatorial Theory, Series B, 112:138–153, 2015. doi:10.1016/J.JCTB.2014.12.005.
  • [36] Kenta Kitsunai, Yasuaki Kobayashi, and Hisao Tamaki. On the pathwidth of almost semicomplete digraphs. In Nikhil Bansal and Irene Finocchi, editors, Proc. of the 23rd Annual European Symposium on Algorithms (ESA), volume 9294 of LNCS, pages 816–827, 2015. doi:10.1007/978-3-662-48350-3_68.
  • [37] Raul Lopes and Ignasi Sau. A relaxation of the Directed Disjoint Paths problem: A global congestion metric helps. Theoretical Computer Science, 898:75–91, 2022. doi:10.1016/j.tcs.2021.10.023.
  • [38] Lúcia Martins, Teresa Gomes, and David Tipper. Efficient heuristics for determining node-disjoint path pairs visiting specified nodes. Networks, 70(4):292–307, 2017. doi:10.1002/NET.21778.
  • [39] Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. doi:10.1093/acprof:oso/9780198566076.001.0001.
  • [40] Neil Robertson and Paul D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.
  • [41] Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM Journal on Discrete Mathematics, 24(1):146–157, 2010. doi:10.1137/070697781.
  • [42] Carsten Thomassen. Highly connected non-2-linked digraphs. Combinatorica, 11(4):393–395, 1991. doi:10.1007/BF01275674.
  • [43] Michal Wlodarczyk. Constant Approximating Disjoint Paths on Acyclic Digraphs Is W[1]-Hard. In Proc. of the 35th International Symposium on Algorithms and Computation (ISAAC), volume 322 of LIPIcs, pages 57:1–57:16, 2024. doi:10.4230/LIPICS.ISAAC.2024.57.

Appendix A Flaw in the NP-completeness proof of Bang-Jensen and Thomassen

In this appendix we sketch the flaw in the proof of Bang-Jensen and Thomassen claiming that Directed Disjoint Paths is NP-complete on tournaments when k is part of the input.

Their approach is to first prove the NP-completeness of a related problem on tournaments, and then reduce from this problem to Directed Disjoint Paths. Namely, it is proved in [3, Theorem 6.1] that the following problem Q is NP-complete on tournaments: given a tournament T and a set of arcs AE(T), decide whether T contains a directed cycle visiting all the arcs in A (in any order). The proof of [3, Theorem 6.1] is correct, and consists in a simple reduction from Hamiltonian Cycle on general digraphs to Q on tournaments.

The problem comes later: right after the proof of [3, Theorem 6.1], it is claimed that “This proves that, if k is not fixed, then the k-DDP problem is NP-complete on tournaments”. This statement is not clear at all, the main issue being that in problem Q the set of arcs A to be visited by the cycle is unordered. Indeed, in order to construct an instance of k-DDP starting from an instance (T,A) of problem Q, the natural strategy would be to consider an arbitrary ordering σ=(e0,,ek1) of the arcs in A, and construct a set K of k requests in T as follows. For every i{0,,k1}, add to K a request from the head of ei to the tail of ei+1, where indices are taken modulo k. One may hope that the desired cycle C in T visiting all the arcs in A would translate to the existence of k pairwise vertex-disjoint paths in T satisfying all the requests in K. But this is not true, as C may exist in T, but may yield a visiting ordering of the arcs in A that is different from the ordering σ that we have fixed arbitrarily. One could try to fix this issue by guessing all the possible orderings σ of the arcs in A, but this would result in k! choices, which is not allowed in a polynomial-time reduction since k is considered as part of the input.

We have shared the above issue with the authors of [3] and they have confirmed to us [2] that it does not seem to be easily fixable.