Finding Two Edge-Disjoint Paths with Length
Constraints

arXiv:1509.05559v1 [cs.DS] 18 Sep 2015

Leizhen CAI⋆ and Junjie YE
Department of Computer Science and Engineering, The Chinese University of Hong
Kong, Shatin, Hong Kong SAR, China
{lcai,jjye}@cse.cuhk.edu.hk

Abstract. We consider the problem of finding, for two pairs (s1 , t1 ) and
(s2 , t2 ) of vertices in an undirected graphs, an (s1 , t1 )-path P1 and an
(s2 , t2 )-path P2 such that P1 and P2 share no edges and the length of
each Pi satisfies Li , where Li ∈ {≤ ki , = ki , ≥ ki , ≤ ∞}.
We regard k1 and k2 as parameters and investigate the parameterized
complexity of the above problem when at least one of P1 and P2 has a
length constraint (note that Li = “ ≤ ∞” indicates that Pi has no length
constraint). For the nine different cases of (L1 , L2 ), we obtain FPT algorithms for seven of them. Our algorithms uses random partition backed
by some structural results. On the other hand, we prove that the problem
admits no polynomial kernel for all nine cases unless N P ⊆ coN P/poly.
Keywords: Edge-disjoint paths, random partition, parameterized complexity, kernelization.

1

Introduction

Disjoint paths in graphs are fundamental and have been studied extensively in
the literature. Given k pairs of terminal vertices (si , ti ) for 1 ≤ i ≤ k in an
undirected graph G, the classical Edge-Disjoint Paths problem asks whether
G contains k pairwise edge-disjoint paths Pi between si and ti for all 1 ≤ i ≤
k. The problem is NP-complete as shown by Itai et al. [12], but is solvable
in time O(mn) by network flow [15] if all vertices si (resp., ti ) are the same
vertex s (resp., t). When we regard k as a parameter, a celebrated result of
Robertson and Seymour [16] on vertex-disjoint paths can be used to obtain an
FPT algorithm for Edge-Disjoint Paths. On the other hand, Bodlaender et
al. [4] have shown that Edge-Disjoint Paths admits no polynomial kernel
unless N P ⊆ coN P/poly.
In this paper, we study Edge-Disjoint Paths with length constraints Li
on (si , ti )-paths Pi and focus on the problem for two pairs of terminal vertices.
The length constraints Li ∈ {≤ ki , = ki , ≥ ki , ≤ ∞} indicate that the length
of Pi need to satisfy Li . We regard k1 and k2 as parameters, and study the
parameterized complexity of the following problem.
⋆

Partially supported by GRF grant CUHK410212 of the Research Grants Council of
Hong Kong.

2

Edge-Disjoint (L1 , L2 )-Paths
Instance: Graph G = (V, E), two pairs (s1 , t1 ) and (s2 , t2 ) of vertices.
Question: Does G contain (si , ti )-paths Pi for i = 1, 2 such that P1 and
P2 share no edge and the length of Pi satisfies Li ?
There are nine different length constraints on two paths (note that EdgeDisjoint (≤ ∞, ≤ ∞)-Paths puts no length constraint on two paths). For
instance, Edge-Disjoint (= k1 , ≤ ∞)-Paths requires that |P1 | = k1 but P2
has no length constraint, and Edge-Disjoint (= k1 , ≥ k2 )-Paths requires that
|P1 | = k1 and |P2 | ≥ k2 .
Related Work. Edge-Disjoint (L1 , L2 )-Paths has been studied under the
framework of classical complexity. Ohtsuki [14], Seymour [17], Shiloah [18],
and Thomasssen [19] independently gave polynomial-time algorithms for EdgeDisjoint (≤ ∞, ≤ ∞)-Paths. Tragoudas and Varol [20] proved the NP-completeness
of Edge-Disjoint (≤ k1 , ≤ k2 )-Paths, and Eilam-Tzoreff [7] showed the NPcompleteness of Edge-Disjoint (≤ k1 , ≤ ∞)-Paths even when k1 equals the
(s1 , t1 )-distance. For Edge-Disjoint (L1 , L2 )-Paths with L1 = k1 or ≥ k1
(same for L2 = k2 or ≥ k2 ), we can easily establish its NP-completeness by
reductions from the classical Hamiltonian Path problem.
As for the parameterized complexity, there are a few results in connection
with our Edge Disjoint (L1 , L2 )-Paths. Golovach and Thilikos [11] obtained
an 2O(kl) m log n-time algorithm for Edge Disjoint Paths when every path
has length at most l. For a single pair (s, t) of vertices, Fomin et al. [8] gave the
currently fastest O(2.851l m log2 n)-time algorithm for finding an (s, t)-path of
length exactly l, if it exists. For the problem of finding an (s, t)-path of length
at least l, Bodlaender [1] derived an O(22l (2l)!n + m)-time algorithm, Gabow
and Nie [10] designed an ll 2O(l) mn log n-time algorithm, and a recent FPT algorithm of Fomin et al. [8] for cycles can be adapted to yield a 8l+o(l) m log2 n-time
algorithm.
Our Contributions. In this paper, we investigate the parameterized complexity
of Edge-Disjoint (L1 , L2 )-Paths for the nine different length constraints and
have obtained FPT algorithms for seven of them (see Table 1 for a summary).
In particular, we use random partition in an interesting way to obtain FPT
algorithms for Edge-Disjoint (= k1 , ≤ ∞)-Paths and Edge-Disjoint (=
k1 , ≥ k2 )-Paths. This is achieved by bounding the number of some special edges,
called “nearby-edges”, in the two paths P1 and P2 by a function of k1 and k2
alone. We also consider polynomial kernels and prove that all nines cases admit
no polynomial kernel unless N P ⊆ coN P/poly.
Notation and Definitions. All graphs in the paper are simple undirected
connected graphs. For a graph G, we use V (G) and E(G) to denote its vertex
set and edge set respectively, and n and m, respectively, are numbers of vertices
and edges of G. For two vertices s and t, the distance between s and t is denoted
by d(s, t).

3
Constraints

|P2 | ≤ k2

|P2 | = k2

|P2 | ≥ k2

≤∞
2

r1

|P1 | ≤ k1 O(2.01 m log n)
|P1 | = k1

O(5.71r1 m log3 n)

|P1 | ≥ k1

O(2.01r3 m log3 n)

O(2.01r2 m log3 n)

O(2.01k1 m log n)
2
k1

O(2.01 m log3 n)

Open

Table 1. Running times of FPT algorithms for Edge-Disjoint (L1 , L2 )-Paths with
length constraints Li ∈ {≤ ki , = ki , ≥ ki , ≤ ∞} for i = 1, 2. Note that r1 = k1 + k2 ,
r2 = k12 + 5k2 , and r3 = k22 + 5k1 .

An instance (I, k) of a parameterized problem Π consists of two parts: an
input I and a parameter k. We say that a parameterized problem Π is fixedparameter tractable (FPT) if there is an algorithm solving every instance (I, k)
in time f (k)|I|O(1) for some computable function f . A kernelization algorithm
for a parameterized problem Π maps an instance (I, k) in time polynomial in
|I| + k into a smaller instance (I ′ , k ′ ) such that (I, k) is a yes-instance iff (I ′ , k ′ )
is a yes-instance and |I ′ | + k ′ ≤ g(k) for some computable function g. Problem
Π has a polynomial kernel if g(k) is a polynomial function.
For simplicity, we write O(2.01f (k) ) for 2f (k)+o(f (k)) as the latter is O((2 +
f (k)
ǫ)
) for any constant ǫ > 0 and we choose ǫ = 0.01. In particular, 2k k O(log k) =
k+O(log2 k)
2
= O(2.01k ).
In the rest of the paper, we present FPT algorithms for seven cases in Section
2, and show the nonexistence of polynomial kernels in Section 3. We conclude
with some open problems in Section 4.

2

FPT algorithms

Random partition provides a natural tool for finding edge-disjoint (L1 , L2 )-paths
in a graph G: We randomly partition edges of G to form two graphs G1 and G2 ,
and then independently find paths P1 in G1 (resp., P2 in G2 ) whose lengths
satisfy L1 (resp., L2 ).
When our problem satisfies the following two conditions, the above approach
yields a randomized FPT algorithm and can typically be derandomized by universal sets.
1. Whenever G has a solution, the probability of “G1 contains required P1 and
G2 contains required P2 ” is bounded above by a function of k1 and k2 alone.
2. It takes FPT time to find required paths P1 in G1 and P2 in G2 .
Indeed, straightforward applications of the above method yield FPT algorithms for Edge-Disjoint (L1 , L2 )-Paths when Li ∈ {≤ ki , = ki } for i = 1, 2.
Theorem 1. Edge-Disjoint (L1 , L2 )-Paths can be solved in O(2.01k1 +k2 m log n)
time for (L1 , L2 ) = (≤ k1 , ≤ k2 ), and O(5.71k1 +k2 m log3 n) time for (L1 , L2 ) =
(≤ k1 , = k2 ) or (= k1 , = k2 ).

4

Proof. Let r = k1 + k2 . We randomly color each edge by color 1 or 2 with
probability 1/2 to define a random partition of edges. Denote by Gi , i = 1, 2,
the graph consisting of edges of color i. Then for all three cases of (L1 , L2 ), the
probability that both G1 and G2 contain required paths is at least 1/2r when
Edge-Disjoint (L1 , L2 )-Paths has a solution.
We can use BFS starting from si to determine whether Gi contains an (si , ti )path of length at most ki in time O(m), and an algorithm of Fomin et al. [8]
to determine whether Gi contains an (si , ti )-path of length exactly l in time
O(2.851l m log2 n). Furthermore, we use a family of (m, r)-universal sets of size
2r rO(log r) log m [13] for derandomization. Therefore Edge-Disjoint (L1 , L2 )Paths can be solved in time
2r rO(log r) log m ∗ m = 2r rO(log r) m log n = O(2.01r m log n)
for (L1 , L2 ) = (≤ k1 , ≤ k2 ), and time
2r rO(log r) log m ∗ (2.851k1 + 2.851k2 )m log2 n = O(5.71r m log3 n)
for (L1 , L2 ) = (≤ k1 , = k2 ) or (= k1 , = k2 ).
For other cases of (L1 , L2 ), a random edge partition of G does not, unfortunately, gurantee condition (1) because of the possible existence of a long path in
a solution. To handle such cases, we will compute some special edges and then
use random partition on such edges to ensure condition (1). For this purpose,
we call a vertex v a nearby-vertex if d(s1 , v) + d(v, t1 ) ≤ k1 , and call an edge
a nearby-edge if its two endpoints are both nearby-vertices. We will show that
there exists a solution where the number of nearby-edges is bounded above by
a polynomial in k1 and k2 alone, which enables us to apply random partition
to nearby-edges to ensure condition (1) and hence to obtain FPT algorithms.
We note that such a clever way of applying random partition has been used by
Cygan et. al [6] in obtaining an Eulerian graph by deleting at most k edges.
In the next two subsections, we rely on random partition of nearby-edges to
obtain FPT algorithms to solve Edge-Disjoint (L1 , L2 )-Paths for the following four cases of (L1 , L2 ): (≤ k1 , ≤ ∞), (= k1 , ≤ ∞), (≤ k1 , ≥ k2 ) and
(= k1 , ≥ k2 ).
2.1

One short and one unconstrained

In this subsection, we use random partition on nearby-edges to obtain FPT
algorithms for Edge-Disjoint (L1 , L2 )-Paths when (L1 , L2 ) is (≤ k1 , ≤ ∞) or
(= k1 , ≤ ∞). To lay the foundation of our FPT algorithms, we first present the
following crucial property on the number of nearby-edges in a special solution.
Recall that a nearby-vertex v satisfies d(s1 , v)+ d(v, t1 ) ≤ k1 and both endpoints
of a nearby-edge are nearby-vertices.
Lemma 1. Let (s1 , t1 ) and (s2 , t2 ) be two pairs of vertices in a graph G =
(V, E), P1 an (s1 , t1 )-path of length at most k1 , and P2 a minimum-length
(s2 , t2 )-path edge-disjoint from P1 . Then

5

1. all edges in P1 are nearby-edges, and
2. P2 contains at most (k1 + 1)2 nearby-edges.
Proof. Statement 1 is obvious and we focus on Statement 2.
For a vertex v in P2 , we say that v is a P1 -near vertex if there is a vertex u in
P1 such that G contains a (u, v)-path of length at most k1 /2 that is edge-disjoint
from P1 . We call v a u-near vertex when we want to emphasize the endpoint u,
and refer to such a (u, v)-path as a P1 -near (u, v)-path.
Let v ∗ be a nearby-vertex in P2 . Since d(s1 , v ∗ ) + d(v ∗ , t1 ) ≤ k1 , there is an
(s1 , v ∗ )-path or a (t1 , v ∗ )-path of length at most k1 /2. As s1 and t1 are vertices of
P1 , v ∗ must be a P1 -near vertex. Therefore each nearby-vertex in P2 is a P1 -near
vertex, and we bound the number of P1 -near vertices to prove this lemma.
Suppose to the contrary that P2 contains at least (k1 + 1)2 + 1 P1 -near vertices. Then by pigeonhole principle, there exists a vertex u in P1 that has at
least k1 + 2 u-near vertices. Sort these vertices along P2 from s2 to t2 . Let v1
and v2 be the first and last vertex respectively. Then the (v1 , v2 )-section of P2
has length at least k1 + 1. Let W be the (v1 , v2 )-walk concatenating the P1 -near
(u, v1 )-path and the P1 -near (u, v2 )-path. Then W contains at most k1 edges
and is edge-disjoint from P1 by the definition of P1 -near path. So we can replace
the (v1 , v2 )-section by W to obtain an (s2 , t2 )-walk that contains an (s2 , t2 )-path
shorter than P2 , contradicting to the minimality of P2 . Therefore P2 contains at
most (k1 + 1)2 P1 -near vertices and thus nearby-vertices, which implies that P2
contains at most (k1 + 1)2 nearby-edges.
The above lemma lays the ground for an FPT algorithm based on random
partition. Let {E1 , E2 } be a random partition of nearby-edges, and construct
G1 = G[E1 ] and G2 = G−E(G1 ). Note that whenever G admits a solution, it has
a solution (P1 , P2 ) such that P2 is a minimum-length (s2 , t2 )-path edge disjoint
from P1 . Lemma 1 implies that P1 is inside G1 with probability ≥ 1/2k1 , and P2
2
is inside G2 with probability ≥ 1/2(k1 +1) . This ensures that, with probability
≥ 1/2k1 , G1 contains an (s1 , t1 )-path of length at most k1 and, with probabil2
ity at least 1/2(k1 +1) , G2 contains an (s2 , t2 )-path. Therefore with probability
2
≥ 1/2k1 +(k1 +1) , we will be able to find a solution for G by finding an (s1 , t1 )-path
of length at most k1 in G1 and an (s2 , t2 )-path in G2 . This paves the way for the
following randomized FPT algorithm for Edge-Disjoint (≤ k1 , ≤ ∞)-Paths.
Note that the algorithm also works for Edge-Disjoint (= k1 , ≤ ∞)-Paths
once we change “length ≤ k1 ” to “length k1 ” in Step 3.
Algorithm 1:
1. Find all nearby-edges in O(m) time by two rounds of BFS, one from s1 and
the other from t1 .
2. Randomly color each nearby-edge by color 1 or 2 with probability 1/2, and
color all remaining edges of G by color 2. Let Gi (i = 1, 2) be the graph
consisting of edges of color i.

6

3. Find an (s1 , t1 )-path P1 of length ≤ k1 in G1 , and an (s2 , t2 )-path P2 in
G2 . Return (P1 , P2 ) as a solution if both P1 and P2 exist, and return “No”
otherwise.
Algorithm 1 solves Edge-Disjoint (≤ k1 , ≤ ∞)-Paths with probability
2
≥ 1/2k1 +(k1 +1) and runs in O(m) time, as the two tasks in Step 3 for G1 and G2
also take O(m) time. Let m′ be the number of nearby-edges and r = k1 +(k1 +1)2 .
We can use (m′ , r)-universal sets to derandomize our algorithm, and obtain a
deterministic FPT algorithm running in time
2

2r rO(log r) log n ∗ m′ = O(2.01k1 m log n).
For Edge-Disjoint (= k1 , ≤ ∞)-Paths, Step 3 takes more time as it takes
O(2.851k1 m log2 n) time to find an (s1 , t1 )-path P1 of length k1 . Therefore our
deterministic FPT algorithm for the problem takes time
2

2r rO(log r) log m′ ∗ 2.851k1 m log2 n = O(2.01k1 m log3 n).
Theorem 2. Edge-Disjoint (≤ k1 , ≤ ∞)-Paths and Edge-Disjoint (=
2
2
k1 , ≤ ∞)-Paths can be solved in time O(2.01k1 m log n) and O(2.01k1 m log3 n)
respectively.
2.2

One short and one long

Now we consider Edge-Disjoint (L1 , L2 )-Paths when (L1 , L2 ) is (≤ k1 , ≥
k2 ) or (= k1 , ≥ k2 ). The main difficulty lies in the possibility that one path
may be long, and we overcome this obstacle by the following lemma similar
to Lemma 1 to upper bound the number of nearby-edges in a special solution.
Again, the lemma enables us to use random partition on nearby-edges to obtain
FPT algorithms for both cases.
For an (s1 , t1 )-path P , a P -valid (s2 , t2 )-path is an (s2 , t2 )-path that is edgedisjoint from P and has length at least k2 .
Lemma 2. Let (s1 , t1 ) and (s2 , t2 ) be two pairs of vertices in a graph G =
(V, E), P an (s1 , t1 )-path of length at most k1 , and Q a P -valid (s2 , t2 )-path of
minimum length. Then
1. all edges in P are nearby-edges, and
2. at most k12 + 3k1 + 2k2 edges of Q are nearby-edges.
Proof. Statement (1) is obvious and we focus on Statement (2).
For path Q, let Q[s2 ] denote the section containing the first k2 + 1 vertices,
and Q[t2 ] the section containing the remaining vertices. We show that Q[t2 ]
contains at most k12 + 3k1 + k2 nearby-edges, which implies Statement (2) as the
remaining part of Q, i.e., Q[s2 ], has k2 edges.
Let v be a vertex in Q[t2 ]. We say that v is a P -near vertex (resp., Q[s2 ]-near
vertex) if there is a vertex u in P (resp., Q[s2 ]) such that G contains a (u, v)path of length at most k1 /2 that is edge disjoint from P and vertex-disjoint from

7

Q[s2 ] (except u). We refer to such a (u, v)-path as a P -near (u, v)-path (resp.,
Q[s2 ]-near (u, v)-path).
Consider a nearby-vertex v in Q[t2 ]. Since d(s1 , v) + d(v, t1 ) ≤ k1 , G contains
either an (s1 , v)-path or a (t1 , v)-path of length at most k1 /2. If this path contains
a vertex v ∗ of Q[s2 ] such that the (v, v ∗ )-section is edge-disjoint from P and
vertex-disjoint from Q[s2 ] except v, then v is a Q[s2 ]-near vertex, and otherwise
v is a P -near vertex. Therefore all nearby-vertices in Q[t2 ] are P -near or Q[s2 ]near vertices, and we will put an upper bound on the number of nearby-vertices
in Q[t2 ] by limiting the numbers of P -near and Q[s2 ]-near vertices.
We can use the proof of Lemma 1 to show that Q[t2 ] contains at most (k1 +1)2
P -near vertices, and we now prove that Q[t2 ] contains at most k1 + k2 − 1 Q[s2 ]near vertices.
Suppose to the contrary that Q[t2 ] contains at least k1 + k2 Q[s2 ]-near vertices. Let vi denote the i-th Q[s2 ]-near vertex in Q[t2 ] when we travel along Q[t2 ]
from its other endpoint to t2 . Let h = ⌈k1 /2⌉ + 1, and denote by Ph a Q[s2 ]near (uh , vh )-path for some vertex uh in Q[s2 ]. Denote by vq the first Q[s2 ]-near
vertex in Q[t2 ] when we travel along Ph from uh to vh .
Since all internal vertices of the (uh , vq )-section S1 of Ph is vertex-disjoint
from Q, we can replace Q[uh , vq ] by S1 to obtain an (s2 , t2 )-path Q∗ (see Figure
1 for illustration). Clearly, Q∗ is edge-disjoint from P as both Q and S1 are
edge-disjoint from P . We show in two cases that k2 ≤ |Q∗ | < |Q| to contradict
the minimality of Q.
Note that the (vq , vh )-section S2 of Ph is vertex-disjoint from Q[s2 ] and edgedisjoint from P . It follows that if the (vq , vh )-section S2′ of Q[t2 ] is longer than S2 ,
we can replace S2′ in Q by S2 to obtain an (s2 , t2 )-walk W that is edge-disjoint
from P and shorter than Q. Since the first k2 vertices of W are distinct vertices,
we can obtain from W a P -valid (s2 , t2 )-path shorter than Q. Therefore we may
assume that |S2 | ≥ |S2′ | by the minimality of Q.

s2

uh

S1

vq

vh

t2

q≤h

S2

Q[s2 ]
s2

S2′

uh

vh

S2
S2′

vq

t2
q>h

S1
Fig. 1. Two cases for the intersections of Q and Q∗ . Note that S2 may share internal
vertices with Q[t2 ].

8

Case 1: q ≤ h. Clearly |Q∗ | ≥ k2 as Q[vq , t2 ] contains more than k2 Q[s2 ]near vertices. On the other hand, |Q[uh , vh ]| ≥ h > |Ph | and |S2 | ≥ |S2′ |. Therefore
|S1 | = |Ph | − |S2 | < |Q[uh , vh ]| − |S2′ | = |Q[uh , vq ]|
and hence |Q∗ | < |Q|.
Case 2: q > h. Clearly |Q∗ | < |Q| as |S1 | ≤ k1 /2 < |Q[uh , vq ]|, and we show
that |Q∗ | ≥ k2 . Since |S2′ | ≤ |S2 | ≤ k1 /2 − 1, S2′ contains at most k1 /2 Q[s2 ]-near
vertices. Therefore q ≤ k1 and Q[vq , t2 ] contains at least k2 Q[s2 ]-near vertices,
implying |Q∗ | ≥ k2 .
Therefore Q[t2 ] has at most k1 + k2 − 1 Q[s2 ]-near vertices. Together with at
most (k1 + 1)2 P -near vertices in Q[t2 ] and k2 vertices in Q[s2 ], we conclude that
Q contains at most k12 + 3k1 + 2k2 P -near and Q[s2 ]-near vertices, and hence at
most k12 + 3k1 + 2k2 nearby-vertices/edges.
The above lemma enables us to obtain a randomized FPT for Edge-Disjoint
(≤ k1 , ≥ k2 ) by replacing Step 3 of Algorithm 1 as follows:
Step 3: Find an (s1 , t1 )-path P1 of length ≤ k1 in G1 , and an (s2 , t2 )-path P2
of length ≥ k2 in G2 . Return (P1 , P2 ) as a solution if both P1 and P2 exist, and
return “No” otherwise.
By Lemma 2, the randomized algorithm solves Edge-Disjoint (≤ k1 , ≥
2
k2 )-Paths with probability ≥ 1/2k1 +4k1 +2k2 . Since an (s2 , t2 )-path P2 of length
≥ k2 can be found in time 8k2 +o(k2 ) m log2 n [8] as mentioned earlier in the
introduction, the two tasks in Step 3 takes 8k2 +o(k2 ) m log2 n time and thus the
randomized algorithm runs in the same time. Let m′ be the number of nearbyedges and r = k12 + 4k1 + 2k2 . We can use (m′ , r)-universal sets to derandomize
our algorithm, and obtain a deterministic FPT algorithm for Edge-Disjoint
(≤ k1 , ≥ k2 )-Paths running in time
2

2r rO(log r) log m′ ∗ 8k2 +o(k2 ) m log2 n = O(2.01k1 +5k2 m log3 n).
For Edge-Disjoint (= k1 , ≥ k2 )-Paths, Step 3 needs to find an (s1 , t1 )path P1 of length k1 which takes O(2.851k1 m log2 n) time. Therefore our deterministic FPT algorithm for the problem takes time
2

2r rO(log r) log m′ ∗O(2.851k1 m log2 n+8k2 +o(k2 ) m log2 n) = O(2.01k1 +5k2 m log3 n).
Theorem 3. Both Edge-Disjoint (≤ k1 , ≥ k2 )-Paths and Edge-Disjoint
2
(= k1 , ≥ k2 )-Paths can be solved in time O(2.01k1 +5k2 m log3 n).

3

Incompressibility

Having obtained FPT algorithms, we are impelled to investigate the existence of
polynomial kernels for Edge-Disjoint (L1 , L2 )-Paths. Our findings are negative as we will show that, unless N P ⊆ coN P/poly, the problem admits no
polynomial kernel for all nine different cases of length constraints (L1 , L2 ).

9

We start with relaxed-composition algorithms defined by Cai and Cai [5],
which is a relaxation of composition algorithms introduced by Bodlaender et
al. [2] in their pioneer work on the nonexistence of polynomial kernels.
Definition 1 (relaxed-composition [5]). A relaxed-composition algorithm for
a parameterized problem Π P
takes w instances (I1 , k), . . . , (Iw , k) ∈ Π as input
and, in time polynomial in w
i=1 |Ii | + k, outputs an instance (I, k) ∈ Π such
that
1. (I, k ′ ) is a yes-instance of Π iff some (Ii , k) is a yes-instance of Π, and
2. k ′ is polynomial in maxw
i=1 |Ii | + log w.
Note that relaxed-composition algorithms relax the requirement in composition algorithms [2] for parameter k ′ from polynomial in k to polynomial in
maxw
i=1 |Ii | + log w. As observed by Cai and Cai [5], the following important
result is implicitly established in Bodlaender et al. [2].
Theorem 4 ([2,9,3]). If an NP-complete parameterized problem admits a relaxedcomposition algorithm, then it has no polynomial kernel, unless N P ⊆ coN P/poly.
We also need the following polynomial parameter transformation (ppt-reduction
in short).
Definition 2 (ppt-reduction [4,5]). A ppt-reduction from a parameterized
problem Π to another parameterized problem Π ′ is an algorithm that, for input
(I, k) ∈ Π, takes time polynomial in |I| + k and outputs an instance (I ′ , k) ∈ Π ′
such that
1. (I, k) is a yes-instance of Π iff (I ′ , k ′ ) is a yes-instance of Π ′ , and
2. parameter k ′ is bounded above by a polynomial of k.
Theorem 5 ([4]). If there is a ppt-reduction from a parameterized problem Π to
another parameterized problem Π ′ , then Π ′ admits no polynomial kernel whenever Π admits no polynomial kernel.
Now we show the nonexistence of polynomial kernels for seven easy cases.
We first use relaxed-composition to show the nonexistence of polynomial kernels
of (s, t)-k-Path (resp., Long (s, t)-Path) that are NP-complete problems of
finding an (s, t)-path of length k (resp., ≥ k). Then we present ppt-reductions
from these two problems to Edge-Disjoint (L1 , L2 )-Paths problems.
Lemma 3. Both (s, t)-k-Path and Long (s, t)-Path admit no polynomial kernel unless N P ⊆ coN P/poly.
Proof. Given w instances of (s, t)-k-Path with si and ti being the two terminal
vertices of the i-th instance for 1 ≤ i ≤ w, we can relaxed-composite these
w instances into one instance by identifying si (resp., ti ) as one vertex for all
1 ≤ i ≤ w. Then, by Theorem 4, (s, t)-k-Path admits no polynomial kernel
unless N P ⊆ coN P/poly. By the same relaxed-composition, we can deduce that
Long (s, t)-Path admits no polynomial kernel unless N P ⊆ coN P/poly.

10

Theorem 6. Edge-Disjoint (L1 , L2 )-Paths for (L1 , L2 ) being (≤ k1 , = k2 ),
(≤ k1 , ≥ k2 ), (= k1 , = k2 ), (= k1 , ≤ ∞), (= k1 , ≥ k2 ), (≥ k1 , ≤ ∞) or (≥ k1 , ≥
k2 ), admits no polynomial kernel unless N P ⊆ coN P/poly.
Proof. Given an instance of (s, t)-k-Path, we construct an instance of EdgeDisjoint (= k1 , ≤ ∞)-Paths as following:
1. Set s1 = s and t1 = t, and k1 = k,
2. add new vertices s2 and t2 , and edge s2 t2 .
The above reduction is clearly a ppt-reduction, and thus Edge-Disjoint
(= k1 , ≤ ∞)-Paths admits no polynomial kernel unless N P ⊆ coN P/poly. For
the other six cases, similar ppt-reductions from (s, t)-k-Path or Long (s, t)Path will work.
Now we consider the remaining two cases of length constraints (≤ k1 , ≤ k2 )
and (≤ k1 , ≤ ∞). Following our argument for the other cases, we can easily
construct ppt-reductions from the problem of determining whether G contains
an (s, t)-path of length at most k. Unfortunately, this short path problem is
solvable in polynomial time and thus admits a polynomial kernel, which makes
such ppt-reductions meaningless for the purpose of proving the nonexistence of
polynomial kernels. In fact, these two cases are difficult to deal with, and we will
design delicate relaxed-composition algorithms to establish the nonexistence of
their polynomial kernels.
Theorem 7. Both Edge-Disjoint (≤ k1 , ≤ k2 )-Paths and Edge-Disjoint
(≤ k1 , ≤ ∞)-Paths admit no polynomial kernel unless N P ⊆ coN P/poly.
Proof. Let (G1 , ≤ k1 , ≤ k2 ), . . . , (Gw , ≤ k1 , ≤ k2 ) be w instances of Edgei i
i i
Disjoint (≤ k1 , ≤ k2 )-Paths, and n = maxw
i=1 |V (Gi )|. Let (s1 , t1 ) and (s2 , t2 )
be the two pairs of vertices of the i-th instance for 1 ≤ i ≤ w. Assume that w is
a power of two, say w = 2d . Otherwise we can add some redundant no-instances
to make w a power of two.
We first show how to composite two instances into one instance, which is
the crucial step of our relaxed-composition. Given the i-th instance and j-th
instance, we construct a new instance (G′ , ≤ k1′ , ≤ k2′ ) as following (See Figure 2
for an illustration.):
1. Create two pairs of vertices (s′1 , t′1 ) and (s′2 , t′2 ), and four vertices u1 , u2 , v1
and v2 .
2. Connect these new vertices with graph Gi and Gj as showed in Figure 2,
where each dashed/dotted edge is a short-path of length one, and each normal
edge is a long-path of length k1 + 4.
3. Denote by G′ the new graph and set k1′ = k1 + 4, k2′ = k2 + 3(k1 + 4) + 1.
We claim that (G′ , ≤ k1′ , ≤ k2′ ) is a yes-instance iff one of these two instances
is a yes-instance.
Suppose that one of these two instances has a solution. Without loss of
generality, assume that (Gi , ≤ k1 , ≤ k2 ) has a solution (P1 , P2 ). Let P1′ be the

11

ti2

si2

s′2

t′2

Gi
si1
u1

ti1

u2

v1

v2

tj2

sj2
Gj
s′1

sj1

tj1

t′1

Fig. 2. The relaxed-composition for two instances. Here a dashed/dotted edge is a
short-path of length one, and a normal edge is a long-path of length k1′ = k1 + 4.

(s′1 , t′1 )-path concatenated by P1 and the four dashed short-paths, and P2′ be the
(s′2 , t′2 )-path going through u1 , u2 , si2 and ti2 , whose (si2 , ti2 )-section is P2 . By the
edge-disjointness between P1 and P2 , P1′ and P2′ are edge-disjoint. Furthermore,
we have |P1′ | ≤ k1′ and |P2′ | ≤ k2′ as |P1′ | ≤ k1 and |P2′ | ≤ k2 . Then (P1′ , P2′ ) is a
solution of (G′ , ≤ k1′ , ≤ k2′ ).
Conversely, suppose that (P1′ , P2′ ) is a solution of (G′ , ≤ k1′ , ≤ k2′ ). Since P1′
has length at most k1′ = k1 + 4, and each long-path has length k1 + 4, P1′ contains
either all dotted short-paths or dashed short-paths. Assume that P1′ contains all
dotted short-paths. (The argument is similar when P1′ contains all dashed shortpaths.) Then the (sj1 , tj1 )-section P1 of P1′ is an (sj1 , tj1 )-path in Gj of length at
most k1 . Moreover, P2′ must be an (s′2 , t′2 )-path going through the (s′2 , sj2 )-longpath Ps and the (tj2 , v1 )-long-path Pt . Since d(v1 , t′2 ) = k1 + 5, the (sj2 , tj2 )-section
P2 ∈ Gj of P2′ has length at most
|P2′ | − |Ps | − |Pt | − d(v1 , t2 ) ≤ (k2 + 3k1 + 13) − 2(k1 + 4) − (k1 + 5) ≤ k2 .
Then (P1 , P2 ) is a solution of (Gj , ≤ k1 , ≤ k2 ).
Now we are ready to present our relaxed-composition that contains d = log w
iterations. In the i-th iteration, there are 2d−i+1 instances and we group these
instances into 2d−i pairs for 1 ≤ i ≤ d. For each pair, we composite them into
one instance as presented above. Finally, there remains only one instance which
completes the relaxed-composition. Let (≤ k1i , ≤ k2i ) be the length constraints
after the i-th iteration for 0 ≤ i ≤ d. Note that k10 = k1 and k20 = k2 . The
recursion relation for k1i and k2i is
k1i+1 = k1i + 4 and k2i+1 = k2i + 3k1i+1 + 1,

12

as short-path and long-path respectively have length 1 and k1i+1 in the i-th
iteration. We have k1i = k1 + 4i and k2i = k2 + (3k1 + 1)i + 6i(i + 1) for 0 ≤ i ≤ d.
Let (G′′ , ≤ k1′′ , ≤ k2′′ ) be the final instance, where k1′′ = k1d = k1 + 4d and
′′
k2 = k1d = k2 + (3k1 + 1)d + 6d(d + 1). By above proof for the composition
of two instances, we can deduce that (G′′ , ≤ k1′′ , ≤ k2′′ ) has a solution iff one of
these w instances has a solution. Both k1′′ and k2′′ are polynomially bounded in
n + log w as d = log w. This composition is a valid relaxed-composition. Since
Edge-Disjoint (≤ k1 , ≤ k2 )-Paths is NP-complete, by Theorem 4, it admits
no polynomial kernel unless N P ⊆ coN P/poly.
The relaxed-composition also holds if we discard the length constraint for
the second path, i.e. discard the length constraints “ ≤ k2 ” and “ ≤ k2′ ”, which
yields that Edge-Disjoint (≤ k1 , ≤ ∞)-Paths admits no polynomial kernel
unless N P ⊆ coN P/poly.

4

Concluding Remarks

We have obtained FPT algorithms to solve Edge-Disjoint (L1 , L2 )-Paths for
seven of the nine different cases of length constraints (L1 , L2 ), and also established the nonexistence of polynomial kernels for all nine cases, assuming
N P 6⊆ coN P/poly. However parameterized complexities of the remaining two
cases are open.
Problem 1. Determine the parameterized complexities of Edge-Disjoint (≥
k1 , ≤ ∞)-Paths and Edge-Disjoint (≥ k1 , ≥ k2 )-Paths.
It is interesting to note that an FPT algorithm for Edge-Disjoint (≥ k1 , ≥
k2 )-Paths will actually yield a new polynomial-time algorithm to solve EdgeDisjoint Paths for two pairs of terminal vertices (i.e., Edge-Disjoint (≤
∞, ≤ ∞)-Paths).
We can consider vertex-disjoint paths, instead of edge-disjoint paths, and
form Vertex-Disjoint (L1 , L2 )-Paths problems for nine different length constraints (L1 , L2 ). We note that it is straightforward to obtain FPT algorithms by
color-coding or random partition for the three cases of (L1 , L2 ) being (≤ k1 , ≤
k2 ), (= k1 , ≤ k2 ) or (= k1 , = k2 ), but the remaining six cases seem much harder
than their corresponding edge-disjoint counterparts.
Problem 2. Determine the parameterized complexity of Vertex-Disjoint (L1 , L2 )Paths for the following six cases of (L1 , L2 ):
(≤ k1 , ≤ ∞), (≤ k1 , ≥ k2 ), (= k1 , ≤ ∞), (= k1 , ≥ k2 ), (≥ k1 , ≤ ∞) and (≥ k1 , ≥
k2 ).
We note that structural properties similar to Lemma 1 and Lemma 2 seem
not hold for vertex-disjoint paths with length constraints. On the other hand, our
proofs for the nonexistence of polynomial kernels for Edge-Disjoint (L1 , L2 )Paths also work for Vertex-Disjoint (L1 , L2 )-Paths, and hence VertexDisjoint (L1 , L2 )-Paths admits no polynomial kernel unless N P ⊆ coN P/poly
for all nine different cases of length constraints (L1 , L2 ).

13

Finally, we can consider both edge-disjoint and vertex-disjoint paths with
length constraints for digraphs, which appear to be much harder than these
problems on undirected graphs.
Problem 3. For digraphs, determine the parameterized complexity of EdgeDisjoint (L1 , L2 )-Paths and Vertex-Disjoint (L1 , L2 )-Paths for various
length constraints (L1 , L2 ).

References
1. Bodlaender, H.L.: On linear time minor tests with depth-first search. Journal of
Algorithms 14(1), 1–23 (1993)
2. Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences 75(8), 423–434
(2009)
3. Bodlaender, H.L., Jansen, B.M., Kratsch, S.: Kernelization lower bounds by crosscomposition. SIAM Journal on Discrete Mathematics 28(1), 277–305 (2014)
4. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and
disjoint paths. Theoretical Computer Science 412, 4570–4578 (2011)
5. Cai, L., Cai, Y.: Incompressibility of H-free edge modification problems. Algorithmica 71(3), 731–757 (2014)
6. Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized
complexity of Eulerian deletion problems. Algorithmica 68(1), 41–61 (2014)
7. Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discrete Applied Mathematics 85(2), 113–138 (1998)
8. Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative
sets with applications in parameterized and exact algorithms. In: Proceedings of
the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 142–151.
SIAM (2014)
9. Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct
PCPs for NP. Journal of Computer and System Sciences 77(1), 91–106 (2011)
10. Gabow, H.N., Nie, S.: Finding long paths, cycles and circuits. In: Algorithms and
Computation, pp. 752–763. Springer (2008)
11. Golovach, P.A., Thilikos, D.M.: Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization 8(1), 72–86 (2011)
12. Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths
with length constraints. Networks 12(3), 277–286 (1982)
13. Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer
Science. pp. 182–191. IEEE (1995)
14. Ohtsuki, T.: The two disjoint path problem and wire routing design. In: Proceedings of the 17th Symposium of Research Institute of Electric Communication on
Graph Theory and Algorithms. pp. 207–216. Springer-Verlag (1980)
15. Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceedings of the forty-fifth
annual ACM Symposium on Theory of Computing. pp. 765–774. ACM (2013)
16. Robertson, N., Seymour, P.D.: Graph minors. XIII. the disjoint paths problem.
Journal of Combinatorial Theory, Series B 63(1), 65–110 (1995)
17. Seymour, P.D.: Disjoint paths in graphs. Discrete Mathematics 29(3), 293–309
(1980)

14
18. Shiloach, Y.: A polynomial solution to the undirected two paths problem. Journal
of the ACM 27(3), 445–456 (1980)
19. Thomassen, C.: 2-linked graphs. European Journal of Combinatorics 1(4), 371–378
(1980)
20. Tragoudas, S., Varol, Y.L.: Computing disjoint paths with length constraints. In:
Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in
Computer Science. pp. 375–389. Springer (1997)

