Revisiting Directed Disjoint Paths on Tournaments (And Relatives)
Abstract
In the Directed Disjoint Paths problem (-DDP), we are given a digraph and pairs of terminals, and the goal is to find pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that -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 -DDP where we allow congestion on the vertices is FPT on semicomplete digraphs provided that is greater than . This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of is best possible for this technique, with a counterexample with no irrelevant vertices when . We also prove that -DDP on digraphs that can be partitioned into semicomplete digraphs is -hard parameterized by , 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 pathwidthCategory:
Track A: Algorithms, Complexity and GamesFunding:
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.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Fixed parameter tractability ; Mathematics of computing CombinatoricsEditors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

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 and requests, which are pairs of vertices known as terminals, deciding whether contains pairwise vertex-disjoint paths connecting each to , for each . As a crucial ingredient of their Graph Minors project, Robertson and Seymour [40] proved that Disjoint Paths is fixed-parameter tractable (FPT) parameterized by , that is, it can be solved in time on -vertex graphs for some computable . In this article, we focus on its directed counterpart, defined analogously for an input digraph and called Directed Disjoint Paths, which is known to be much harder from a computational point of view: it is already NP-complete for terminals [25]. We abbreviate this problem by -DDP, even when 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 [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 -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 -DDP is well understood: the problem is NP-complete and solvable in time (hence, in the class XP) [25], and -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 -DDP is NP-complete on tournaments when 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 . 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 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 . 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 -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 -DDP problem, the XP algorithm on tournaments [16] has been generalized by Chudnovsky, Scott, and Seymour [14] to the class of digraphs whose vertex set can be partitioned into a bounded number of semicomplete digraphs (thus, ). More precisely, the running time of their algorithm is . The authors asked whether the result can be further generalized to the class of digraphs whose underlying graph has independence number at most , 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 -DDP on tournaments (or semicomplete digraphs) is FPT parameterized by . 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 ), 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 -semicomplete digraphs and denoted by for some fixed integer . Digraphs in this class satisfy the property that each vertex has at most non-neighbors (in any direction). If we denote by and the classes of tournaments and semicomplete digraphs, respectively, it holds that , and for every (see the discussion in the beginning of Subsection 3.1),
(1) |
Another transversal strategy to try to overcome the inherent hardness of -DDP is to relax the problem by allowing every vertex of to be used by at most of the paths of the solution, for some integer that is also part of the input and is called the congestion; we call the corresponding problem Directed Disjoint Paths with Congestion, abbreviated by -DDP. Note that if the problem is trivial, so we may assume that . It is open whether the case and (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 can be solved in polynomial time if the input graph is sufficiently connected as a function of , 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 on general digraphs for some small values of [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 -DDP by considering parameters stronger than .
Finally, it is worth mentioning that Cavallaro, Kawarabayashi, and Kreutzer [11] recently proved that the edge-disjoint version of -DDP is FPT on Eulerian digraphs parameterized by ; 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 -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 -DDP on tournaments is FPT parameterized by . 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 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 ().
-DDP on semicomplete digraphs is FPT parameterized by restricted to instances satisfying .
Note that since we can assume that , the result of Theorem 2 covers roughly “half” of the range of values of the congestion . It is natural to ask whether the problem remains NP-complete for this range of values of , that is, when the congestion is lower-bounded by a linear function of . This question is still open, but we provide the following hardness result, where the congestion is almost linear in (as approaches one).
Theorem 3 ().
-DDP remains NP-complete on tournaments even restricted to instances satisfying , for every .
As discussed before, Chudnovsky, Scott, and Seymour [14] showed that -DDP on the class can be solved in time . 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 , even restricted to digraphs of bounded directed pathwidth.
Theorem 4 ().
The -DDP problem on is -hard when parameterized by , even if restricted to input digraphs of directed pathwidth two.
Moreover, Theorem 4 can be generalized to show hardness for -DDP when (cf. Theorem 12, which, alongside Equation 1, implies that the win/win strategy cannot be extended beyond -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 -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 -DDP for tournaments even if for (cf. Theorem 3). With this approach, however, we are unable to prove hardness for -DDP instances where and 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 -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 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 -DDP. It is not hard to show that their counterexamples are also valid when but, when , 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 paths only amount to (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 used by Fomin and Pilipczuk, we now require the triple to have size of the order of .
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 -semicomplete digraphs is a further step in this direction. By Theorem 4 and Equation 1 however, the class of -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 on DAGs. In his reduction from the Clique instance , a DAG in a matrix-like format is built in a way that each row corresponds to a copy of and each column to a vertex. Moreover, only one cell may be available in each row, and this must correspond to a vertex of in the clique; this accomplished with several requests in a way that of them are used to enforce the uniqueness, while 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 ( for some constant ) and the directed pathwidth equal to two, proving that a statement analogous to Theorem 4 (i.e., Theorem 12) also holds for -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 , we adopt the classical notations , , and for the in-degree, out-degree, in-neighborhood, and out-neighborhood of a vertex , respectively, and by the subgraph induced by . Given , we say that is complete to if whenever and . We denote the directed pathwidth of by . We refer the reader to the appended full version for a complete set of preliminaries and definitions.
Definition 5 (-triple).
Let be a digraph. For an integer , a -triple of is formed by an ordered triple of disjoint subsets of of size with complete to , complete to , and with a perfect matching from to .
When working with a -triple , it is useful to have an easy way to refer the associated endpoints of the matching from to . Thus we sometimes refer to this matching as a bijective mapping from to . That is, for we have and . In addition, we extend graph-theoretical notation to -triples in the following way. If is a -triple, we denote by the set and by the set of all arcs between pairs of vertices of . See Figure 1 for an example of a -triple.
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 , we consider three classes of digraphs. The class contains every digraph such that every has at most non-neighbors. The class contains every digraph whose vertex set can be partitioned into at most cliques. The class contains every digraph with independence number at most . Let ; by applying Brook’s Theorem [8] to the complement of the underlying graph of , we conclude that can be partitioned into cliques and thus . Since every independent set of a digraph intersects any clique in at most one vertex, it also holds that . In Table 1 we give a summary of our main results.
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 in this section.
4.1 Tournaments
Fortunately, as we show in the following theorem, -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 be the input instance to (3,1)-3-SAT, where is the set of variables and is the set of clauses, and be the -DDP instance we are going to build, with denoting the digraph, and denoting the set of requests. We begin by picking an arbitrary but fixed order of . Now, for each variable , add a copy of the directed butterfly gadget shown in Figure 2 to , while and are added to ; we denote this gadget by . Intuitively, the paths between the white vertices of must be contained in it and, since the gadget has only once center (namely, 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 to the solution is equivalent to setting .
After building all butterflies, add an arc from every to every whenever . To encode our clauses, take each , add new vertices to , the pair to , and the arc ; arcs between each and , for , can be added arbitrarily. Now, take as an example, and suppose that the -th clause of is ; in this case, we add arcs from to the vertices , and , and from these to . For simplicity, the superscript of each and is the same as the subscript of the corresponding clause . 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 has no other outgoing arc and has no other incoming arc. This concludes the construction of , with . For the above example, our goal is to witness the satisfiability of with a path , where , which will have to be the case as .
Observation 6.
Let be one of the butterfly gadgets of . If admits a solution , then (i) the paths that connecting and are internal to , and (ii) at least one of the wings of is entirely occupied by such a path.
Proof.
Let be the paths connecting and , respectively. Suppose that is minimal, i.e., none of its paths has an internal shortcut; for example, because arc has both endpoints contained in the path and could be used to shorten it. Let us first show that . Recall that and that no terminal of 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 that may be used to reach it are the ones we have just listed. As such, the penultimate vertex of is either one of , in which case we are done as and is minimal, or it is in some with , but this is impossible as there is no path from to such a vertex in by design. A symmetric analysis can be performed to show that : if , we are done as , so suppose . Note that , with is unreachable from in , and so we have that . Moreover, for , is unreachable from any vertex of in . Finally, every path between and the right wing of in passes through , which is not in , so the right wing of does not intersect . Consequently, if , then , which is precisely the left wing of , completing the proof of (i). Towards proving (ii), if we are done, so suppose that ; by (i), this implies that . A completely symmetric analysis can be performed if to conclude that .
See 1
4.2 Tournaments with congestion
We now focus on -DDP and show one way to extend Theorem 1.
Meta-construction.
We reduce from the instance of -DDP built in the proof of Theorem 1 to construct the instance of -DDP. Let be the ordering of the butterfly gadgets, that is, is complete to when . We perform the following modification to : for each , reverse the arc , where is the unique out-neighbor of in the left wing of . To conclude the construction of , we add two vertices and arcs such that is the unique out-neighbor of and is the unique in-neighbor of . We illustrate the resulting tournament in Figure 3. To obtain , we add two families of requests: for each , we have one copy of and copies of ; in the second, we have requests and one request . As such, , so it follows that, if is a fixed power of , say we have . This concludes the construction of .
First, note that the terminals in each cannot be used as internal vertices of any path as they each participate in requests. Now, observe that the other vertices of the butterflies are the only elements of that are not in request in . Moreover, by construction, they all participate in the unique - path of in the same order specified by . We call this path the critical path of , and in any solution to , all of its inner vertices participate in at least paths; cf. the black arcs in Figure 3. Considering this and that all butterfly gadgets are occupied by paths that are single arcs, all that remains to be solved is , 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 ().
-DDP is weakly NP-hard on tournaments if the congestion is of the form , for every .
Overcoming the barrier has proved extremely challenging, and seems to require a very different approach to the one we employed, which demanded requests. We can adapt our proofs to other cases and avoid this. For the Restricted -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 instead of tournaments.
Theorem 8 ().
Restricted -DDP remains NP-complete even when restricted to tournaments and when for every .
Theorem 9 ().
-DDP is NP-complete on and when , for .
4.3 -hardness on + on graphs of directed pathwidth two
Recall that if and only if its vertices can be partitioned in sets that induce tournaments in . We show that the XP algorithm given in [14] cannot be significantly improved, as we prove that -DDP remains -hard when parameterized by on graphs of bounded directed pathwidth. As in Section 4.1, we first deal -DDP and then show how to extend to -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 -hardness of Directed Edge-Disjoint Paths on DAGs.
Construction.
Let be the input instance of Multicolored Clique parameterized by where are the color classes and denote the -DDP instance we are going to build. A solution to the former is a clique of size at least that contains a vertex of every color class. For simplicity, assume that every has the same size . The vertices of are partitioned in a matrix-like fashion, with corresponding to the -th vertex of and with no correspondence. For every , let us define and add the following sets of vertices to , where each is a set of vertices that will be specified later: . We keep to the convention that vertices with an subscript are sources/targets of a request of .
Each is broken down into four tournaments, namely , , and, for , ; intuitively, is the only vertex that will connect to vertices of , while is used to synchronize the internal behavior of . 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 to with matched to (cf. Figure 4). Now, for each , we concatenate the endpoints of the ’s in order to form a long, unique, Hamiltonian path, with the other arcs again going backwards. We connect the ’s with arcs as (partially) shown in Figure 5: an vertex connects to one column to the left and to two columns to the right, to the next column’s , to the one column to the left, and to the to columns to the right. Minus the matching, these arcs encode that only one cell of may be unoccupied by paths internal to ; this corresponds to one vertex of being picked to the solution.
We now must encode that these vertices indeed form a clique of . As such, if , , , add the arc ; this encodes the adjacencies of . Our final set of vertices are obtained by adding the following requests and their corresponding vertices , where and ; this implies that . We connect to each and each to , as in Figure 4. Note that, if we can guarantee that each has exactly one unoccupied by the paths discussed in Step (ii), then the paths used to satisfy each pair must, necessarily, go through arcs of that encode adjacency in , and all such arcs must be incident to the same vertex of .
Observation 10.
Instance of -DDP has , can be partitioned into tournaments and has directed pathwidth equal to 2.
Breaking the bound for either or 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 must adhere to a specific format: the jumps between the -paths of each happen synchronously as in Figure 5: all jumps in happen simultaneously around the same index . This synchronicity allows us to prove the key ingredient of our proof and the main complication to generalize Slivkins’ result: both the - and -paths of must be completely used by the internal paths of , except for , which is essentially untouched by them. We need this to avoid cheating by the paths: without it, we could have a path hitting an vertex at some index , going to an vertex of index using an arc added to force the appearance of a tournament, moving to its matched vertex and then moving on to any , 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 be the instance of -DDP built in the proof of Theorem 4 and be an integer; to obtain , we add requests of the form to and the corresponding vertices to . Now, add the arcs and to . Then, for each , we add the arcs , , and, if , . This completes the construction of ; note that and that .
Observation 11.
There exists a unique path that can satisfy and, for every , this path is obtained by concatenating the -, -, - and -paths, in this order.
We are now free to choose to get the fraction of we desire and, consequently, Theorem 12
Theorem 12 ().
-DDP jointly parameterized by the number of requests and the minimum clique cover of the host graph is [1]-hard even if the input instance has directed pathwidth 2 and the congestion is a fraction of, but not equal to, .
5 Algorithmic results
In this section we prove our main algorithmic result and discuss its applications.
Theorem 13 ().
For all integers , , there exists a computable function such that every instance of -DDP with on an -semicomplete digraph containing a -triple has an irrelevant vertex which can be found in time. In particular, .
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 of the input semicomplete digraph plus the number of paths. Then, through a series of results and constructions, they show that there is a computable function such that every semicomplete digraph with contains a -triple, and that every such triple contains a vertex that is irrelevant for the given instance. This second proof essentially shows that only the instances with bounded by some function of need to be solved. Although they leave open whether -DDP is FPT on semicomplete digraphs, they mention that an FPT dynamic programming algorithm, parameterized by the number of paths, can be done for -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 on every semicomplete digraph [23, Lemma 2.14]. Then one can apply [23, Theorem 2.16] which states that, given an MSO1 formula and a semicomplete digraph , there is an algorithm which checks whether is satisfied by in FPT time parameterized by the order of and . 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]).
-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 -DDP. Indeed, given an instance of this problem on a semicomplete digraph , it suffices to add copies of each with the same in- and out-neighborhood as . Then, we add arcs among vertices in in order to ensure that this set induces an acyclic tournament. This procedure easily implies that the directed pathwidth of increases by at most a factor of . Hence we can apply 14 to solve -DDP in the newly constructed digraph and transport any solution, whether positive or negative, to the original instance. This implies that -DDP is also FPT parameterized by 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 be a semicomplete digraph. There is a computable function and an FPT algorithm parameterized by that either outputs a directed path decomposition of with width at most or finds a -triple in .
In light of Propositions 15 and 14, it is now easy to apply Theorem 13 to obtain an FPT algorithm for -DDP when , 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 -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 in order to extend the analysis to the class . 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 .
We abbreviate by and assume that an -triple is given. The choice of is discussed later. Let be an instance of -DDP on a semicomplete digraph with . For the remainder of this section, as well as in Subsection 5.2 and Subsection 5.3, we assume that is an -triple of and that is a set of paths satisfying 16.
Property 16.
is a solution for minimizing .
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 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 vertices of each set , and , we assume that no terminal of appears in . Second, by deleting parallel arcs of if necessary, we assume that there are no arcs in from to and no arcs from to . Removing these arcs poses no issues for the irrelevant vertex argument since an irrelevant vertex of is also irrelevant in .
The set plays as distinguished role in this proof since it concentrates the heads of all arcs of between and and the tails of all arcs of between and . 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 and a solution for such that every accessing does so from a vertex in and to a vertex in .
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 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 to . This, in turn, is used to show that every path in uses at most vertices from and from , and at most vertices of . 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 with large out-degree or in-degree in the triple does not guarantee that we can find a vertex in 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 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 : if are both used by paths, then by the pigeonhole principle there is a path that uses both and . 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 and are used by paths of (19), we first need to show that some vertices of 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 to ; recall that may be seen as a bijective mapping from to according to the matching arcs defining . Additionally, for (resp. ) we call the set (resp. ) the mirror of (resp. of ) in .
For we denote by the order in which appears in . A shortcut for is a walk such that there is some subpath where and starts and ends in the same vertices as . We may refer to a shortcut as the sequence of vertices of 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 with 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 , we assign to a list of indices representing which paths of are using . Thus holds for any vertex since is a solution for . For , we say that is -free if or if , and that is -saturated otherwise. Intuitively, an -free vertex can be used to construct shortcuts for path since either is already using and thus the route may be replaced with a shorter one without increasing the congestion of , or the congestion of 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, . For we denote by the set of vertices of which are assigned indices in . Finally, we say that is an -free pair if both and are -free.
5.2 Freeing , and
In this section, we show that only a bounded number of vertices have , and how to use this result to bound the number of vertices that each can use in and .
Lemma 17 ().
For all , if then there are no -free pairs.
Lemma 18 ().
For all with , it holds that .
Sketch of the proof.
By contradiction, assume that there is such that and . For all , let and . If all satisfy , then and thus there are many -free vertices in and a shortcut for can be found by applying 17 and observing the mirror of .
Assume now that there is an such that and notice that every has , as otherwise would be an -free pair, contradicting 17 as . The goal now is to group all pairs of the form with according to which indices appear in . The size of 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 through some . By doing this, we no longer have a solution for our instance since a vertex of this set is used by paths. However, the shortcut for frees some vertices of , which are now used by at most paths. Thus we can shortcut in a way that avoids to generate a new solution contradicting 16. Formally, we proceed as follows. For , let be the set of pairs such that with . Notice that these sets are not necessarily pairwise disjoint and that the exclusion of is natural as the occurrence of any of its indices in would contradict 17. In addition, the pigeonhole principle implies that at least one set satisfies as .
Let be the subset of vertices of appearing in pairs of and , and let be the first vertices of ordered . We consider two cases. In the first case, uses a vertex of before any vertex of . If is the first vertex of used by , then we shortcut through , where the last vertex of used by , to build and set . Notice that is by paths of . However, avoids at least three vertices of . If is one of them, we can shortcut through to avoid , thus reducing the congestion of this vertex back to and finding a solution that contradicts 16. Figure 6 illustrates this shortcut. In the second case, uses a vertex of before any vertex of , but the proof is analogous. We remark that is needed only in this case due to the size of the shortcut for .
18 implies that at least vertices of are used by at most paths of . Thus, all such vertices are -free for any and can be used to build shortcuts for any path in . We now show that only a few vertices of and are used by paths of .
Lemma 19 ().
If there is such that , then for all it holds that ; and .
5.3 Finding the irrelevant vertex in polynomial time
With 19, we can show 20, a tighter bound on 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 .
Corollary 20 ().
For all , .
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 such that if there is a solution for , then there is another solution whose paths all avoid . We follow the blueprint of the proof by Fomin and Pilipzcuk [24, Theorem 9.1]. The goal is to first find a large set such that every path of a solution entering some from outside can be rerouted to access from a vertex in . Then, we must show that there is a such that every path of the solution leaving to a vertex not in can be rerouted to leave to a vertex in . 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 can be replaced with another , that is unused by the solution, and thus 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 , 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 accesses through a vertex and has “sufficiently many” out-neighbors in which are in-neighbors of distinct vertices of , then at least one of those out-neighbors, say , can be used to reroute through . This holds due to three main properties: (i) at most arcs leaving a vertex are used by any solution, and thus any vertex of out-degree at least 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 outside of .
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 outside of . We prove that this is not the case by applying another shortcutting argument which allows us to bound how many vertices a path can use in a particular subset of in-neighbors of . 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 factor. Thus a small trick is needed to apply a similar shortcutting argument as the one used in the in-neighbors of , this time to the out-neighbors of ; this happens when we want to find a vertex of that, when used by a path, is always followed by a vertex of .
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 -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 -DDP when . We note, however, that this latter problem is not known to be NP-complete; while we are able to show that -DDP is hard for every , we are unable to extend this to , or even . 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 is just a matter of technicalities: we must increase the size of the triple taking into account and, when discussing the exterior neighborhood of the triple, increase the thresholds to classify the in- and out-neighbors of as having “too many” neighbors in or not. This extension, however, is not enough to give an FPT algorithm for -DDP on -semicomplete graphs when . 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 , , 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 -semicomplete digraphs is the best we can hope for, as we have shown that -DDP and -DDP are [1]-hard when parameterized by 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 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 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 is NP-complete on tournaments: given a tournament and a set of arcs , decide whether contains a directed cycle visiting all the arcs in (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 on tournaments.
The problem comes later: right after the proof of [3, Theorem 6.1], it is claimed that “This proves that, if is not fixed, then the -DDP problem is NP-complete on tournaments”. This statement is not clear at all, the main issue being that in problem the set of arcs to be visited by the cycle is unordered. Indeed, in order to construct an instance of -DDP starting from an instance of problem , the natural strategy would be to consider an arbitrary ordering of the arcs in , and construct a set of requests in as follows. For every , add to a request from the head of to the tail of , where indices are taken modulo . One may hope that the desired cycle in visiting all the arcs in would translate to the existence of pairwise vertex-disjoint paths in satisfying all the requests in . But this is not true, as may exist in , but may yield a visiting ordering of the arcs in 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 , but this would result in choices, which is not allowed in a polynomial-time reduction since 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.