On the Complexity of Detecting k-Length Negative Cost
Cycles

arXiv:1603.01925v3 [cs.CC] 20 May 2017

Longkun Guoa,∗, Peng Lib
a College

of Mathematics and Computer Science, Fuzhou University, China
b Amazon Web Services, Amazon.com, Unite States

Abstract
Given a positive integer k and a directed graph with a cost on each edge, the
k-length negative cost cycle (kLNCC ) problem is to determine whether there
exists a negative cost cycle with at least k edges, and the fixed-point k-length
negative cost cycle trail (FPkLNCCT) problem is to determine whether there
exists a negative trail enrouting a given vertex (as the fixed point) and containing
only cycles with at least k edges. The kLNCC problem first emerged in deadlock avoidance in synchronized streaming computing network [10], generalizing
two famous problems: negative cycle detection and the k-cycle problem. As a
warmup by-production, the paper first shows that FPkLNCCT is N P-complete
in multigraph even for k = 3 by reducing from the 3SAT problem. Then as the
main result, we prove the N P-completeness of kLNCC by giving a sophisticated
reduction from the 3 Occurrence 3-Satisfiability (3O3SAT ) problem, a known
N P-complete special case of 3SAT in which a variable occurs at most three
times. The complexity result is interesting, since polynomial time algorithms
are known for both 2LNCC (essentially no restriction on the value of k) and
the k-cycle problem of fixed k. This paper closes the open problem proposed by
Li et al. in [10] whether kLNCC admits polynomial-time algorithms.
Keywords: k-length negative cost cycle, N P-complete, 3 occurrence
3-satisfiability, 3-satisfiability.

∗ Corresponding

author
Email addresses: lkguo@fzu.edu.cn (Longkun Guo), lipeng.net@gmail.com (Peng Li)

Preprint submitted to arXiv.org

May 23, 2017

1. Introduction
We define the following k-length negative cost cycle problem (kLNCC):
Definition 1. Given a fixed integer k and a directed graph G = (V, E), in
which each edge e ∈ E is with a cost c(e) → R and a length l(e) = 1, kLNCC is to
P
determine whether there exists a cycle O with total length l(O) = e∈O l(e) ≥ k
and total cost c(O) < 0.
The kLNCC problem arises in deadlock avoidance for streaming computing,
which is widely used in realtime analytics, machine learning, robotics, and computational biology, etc. A streaming computing system consists of networked
nodes communicating through finite first-in first-out (FIFO) channels, and a
data stream referring to data transmitted through a channel. In streaming
computing, a compute node might need to synchronize different incoming data
streams. If the synchronized streams have different rates (e.g. due to filtering
[10]), the computing network might deadlock. Several deadlock avoidance algorithms have been proposed in [10], which rely on inserting heartbeat messages
into data streams. When to insert those heartbeat messages, however, depends
on the network topology and buffer size configurations. An open problem is
deciding whether a given heartbeat message schedule can guarantee deadlock
freedom, which raises the negative-cost cycle detection problem. Further, we
are only interested in the negative-cost cycle with length at least k ≥ 3, as
deadlocks of few nodes can be easily eliminated. This raises the above kLNCC
problem. Besides, in many cases, we are also interested in whether a particular
node in a streaming computing system is involved in a deadlock or not, which
brings the k-length negative-cost fixed-point cycle trail problem (FPkLNCCT):
Definition 2. Given a graph G = (V, E) in which each edge e ∈ E is with
a cost c(e) → R and a length l(e) = 1, a fixed integer k, and a fixed point
p ∈ G, the FPkLNCCT problem is to determine whether there exists a trail T
P
containing p, such that c(T ) < 0 and l(O) = e∈O l(e) ≥ k for every O ⊆ T
(with c(O) < 0).
2

Note that c(O) < 0 makes no difference for the above definition, as a negative
cost trail must contain at least a negative cost cycle. Further, if G contains a
vertex p as a fixed point such that the FPkLNCCT problem is feasible, then
P
G must contain at least a cycle O with c(O) < 0 and e∈O l(e) ≥ k, and vice
versa. So if FP kLNCCT admits a polynomial-time algorithm, then kLNCC
is also polynomially solvable. That is because we can run the polynomialtime algorithm as a subroutine to verify whether G contains a vertex p wrt
which FP kLNCCT is feasible, and then to verify whether kLNCC is feasible.
Conversely, if the N P-completeness of kLNCC is proven, it can be immediately
concluded that FP kLNCCT is also N P-complete.
Throughout this paper, by walk we mean an alternating sequence of vertices
and connecting edges; by trail we mean a walk that does not pass over the same
edge twice; by path we mean a trail that does not include any vertex twice; and
by cycle we mean a path that begins and ends on the same vertex.
1.1. Related works
The kLNCC problem generalizes two well known problems: the negative
cycle detection problem of determining whether there exist negative cycles in a
given graph, and the k-cycle problem (or namely the long directed cycle problem
[2]) of determining whether there exists a cycle with at least k edges. The former
problem is known polynomially solvable via the Bellman-Ford algorithm [1, 5]
and is actually kLNCC of k = 2. The latter problem, to determine whether a
given graph contains a cycle O with l(O) ≥ k, is kLNCC when c(e) = −1 for
every e ∈ E. It is shown fixed parameter tractable in [7], where an algorithm
with a time complexity k O(k) nO(1) is proposed. The runtime is then improved
to O(ck nO(1) ) for a constant c > 0 by using representative sets [4], and later to
6.75k nO(1) independently by [3] and [11]. Compared to the two above results, i.e.
negative cycle detection and the k-cycle problem of fixed k are both polynomially
solvable, it is interesting that 3LNCC is N P-complete as 3LNCC is exactly a
combination of the two problems belonging to P.

3

1.2. Our results
The main result of this paper is proving the N P-completeness of kLNCC
in a simple directed graph. Since the proof is constructive and complicated,
we will first accomplish a much easier task of proving the N P-completeness
of the FP kLNCCT problem in multigraphs by simply reducing from the 3Satisfiability (3SAT ) problem, where a multigraph is a graph that allows multiple edges between two nodes.
Lemma 3. For any fixed integer k ≥ 3, FPkLNCCT is N P-complete in a
multigraph.
Then following a similar main idea of the proof of Lemma 3 but with more
sophisticated details, we will prove the N P-completeness of kLNCC (and hence
also FP kLNCCT ) in a simple directed graph.
Theorem 4. For any fixed integer k ≥ 3, kLNCC is N P-complete in a simple
graph.

2. The N P-completeness of FPkLNCCT in Multigraphs
In this section, we will prove Lemma 3 by reducing from 3SAT that is
known to be N P-complete [8]. In an instance of 3SAT , we are given n variables
{x1 , . . . , xn } and m clauses {C1 , . . . , Cm }, where Ci is the OR of at most three
literals, and each literal is an occurrence of the variable xj or its negation. The
3SAT problem is to determine whether there is an assignment satisfying all the
m clauses.
For any given instance of 3SAT, the key idea of our reduction is to construct
a digraph G, such that G contains a negative cost trail with only cycles of length
at least 3 and enrouting a given vertex iff the instance of 3SAT is satisfiable.
The construction is composed with the following three parts. First, for each
variable xi with ai occurrences of xi and bi occurrences of xi in the clauses, we

4

x1
y1

u1

x2
z1

v1

Cost −1 edge

y2

x3
z2

y3

u2

v2

Cost 0 edge

x4
z3

y4

z4

u3

v3

Cost m − 1 edge

Figure 1: The construction of G for an 3SAT instance (x1 ∨ x3 )∧ (x1 ∨ x2 ∨ x4 )∧ (x1 ∨ x2 ∨ x4 ).

construct a lobe 2 which contains two vertices, denoted as yi and zi , and ai + bi
edges of cost −1 between the two vertices, i.e. ai copies of edge (yi , zi ) and bi
copies of (zi , yi ) ( A lobe is depicted as in the dashed circles in Figure 1). For
briefness, we say an edge in the lobes is a lobe-edge. Then, for each clause Cj ,
add two vertices ui and vi , as well as edge (vi , ui+1 ), 1 ≤ i ≤ m − 1, with cost 0
and edge (vm , u1 ) with cost m − 1. Last but not the least, for the relationship
between the variables and the clauses, say variable xj occurs in clause Ci , we
add two edges with cost 0 to connect the lobes and the vertices of clauses:
• If Ci contains xj , then add two edges (ui , yj ), (zj , vi );
• If Ci contains xj , then add two edges (ui , zj ), (yj , vi ).
An example of the construction for a 3SAT instance is depicted in Figure 1.
Then since FPkLNCCT is clearly in N P, the correctness of Lemma 3 can
be immediately obtained from the following lemma:

2 The

term lobe was used to denote an unit of the auxiliary graph constructed for an instance

of SAT, as in [9] and many others [13, 6].

5

Lemma 5. An instance of 3SAT is satisfiable iff in its corresponding auxiliary
graph G there exists a negative-cost trail containing u1 but no length-2 cycles.
Proof. Suppose there exists a negative-cost trail T , which contains u1 but NO
negative cost length-2 cycle. Then let τ be a true assignment for the 3SAT
instance according to T : if T goes through (yi , zi ), then set τ (xi ) = true;
Otherwise, set τ (xi ) = f alse. It remains to show such an assignment will
satisfy all the clauses. Firstly, we show that the path P = T \ {vm , u1 } must
go through all vertices of {vi |i = 1, . . . , m}. Since T contains u1 , T has to go
through edge (vm , u1 ), as the edge is the only one entering u1 . Then because
T is with negative cost and the cost of edge (vm , u1 ) is m − 1, P has to go
through at least m edges within the n lobes, as only the edges of lobes has a
negative cost −1. According to the construction of G, between two lobe-edges
on P , there must exist at least an edge of {vi , ui+1 |i = 1, . . . , m − 1}, since
vi has only one out-going edge (vi , ui+1 ) while every edge leaving a lobe must
enter a vertex of {vi |i = 1, . . . , , m − 1}. So P = T \ {vm , u1 } has to go
through all the m − 1 edges of {vi , ui+1 |i = 1, . . . , m − 1}, and hence through
all vertices of {vi |i = 1, . . . , m}. Secondly, assume vj and vj ′ are two vertices of
{vi |i = 1, . . . , m}, such that P (vj , vj ′ ) ∩ {vi |i = 1, . . . , m} = {vj , vj ′ }. Again,
because there must be at least an edge of {vi , ui+1 |i = 1, . . . , m−1} between two
lobe-edges, there must be at least a lobe-edge appearing on P (vj , vj ′ ), otherwise
there will be at most m − 1 lobe-edges on T . That is, there must be exactly
a lobe edge, say (yi , zi ), on P (vj , vj ′ ). Then according to the construction of
graph G, xi appears in Cj , and hence τ (xi ) = true satisfies Cj . The case for
(zi , yi ) appears on P (vj , vj ′ ) is similar. Therefore, the 3SAT instance is feasible
as it can be satisfied by τ .
Conversely, suppose the instance of 3SAT is satisfiable, and a true assignment is τ : x → {true, f alse}. Then for clause Ck , there must exist a literal,
say wk , such that τ (wk ) = true. If wk is an occurrence of xi , then set the corresponding subpath as Pk = uk − yi − zi − vk ; otherwise set Pk = uk − zi − yi − vk .
Then clearly, P = {Pk |k = 1, . . . , m} ∪ {(vh , uh+1 )|h = 1, . . . , m − 1} exactly

6

composes a path from u1 to vm with a cost of −m, as it contains m lobe-edge
and other edges of cost 0. So T = P ∪ {vm , u1 } is a negative cost trail of
length at least 3. Besides, since τ (xi ) must be either true or false, there exist
no length-2 cycles on P . This completes the proof.



However, the above proof can not be immediately extended to prove the N Pcompleteness of kLNCC, since there are two tricky obstacles. First, in the
above proof, there might exist negative cycles with length at least three but
without going through u1 . Thus, in Lemma 5, containing u1 is mandatory. we
Second, Lemma 5 holds only for multigraphs as some of the lobes are already
multigraphs. Thus, to extend the proof to kLNCC, we need to eliminate negative
cycles bypassing u1 and to transform the (multigraph) lobes to simple graphs.
3. The N P-completeness Proof of kLNCC
In this section, to avoid the two obstacles as analyzed in the last section,
we will prove Theorem 4 by reducing from the 3 occurrence 3SAT (3O3SAT )
problem that is known N P-complete [12]. Similar to 3SAT, in an instance of
3O3SAT we are also given m clauses {C1 , . . . , Cm } and n variables {x1 , . . . , xn },
and the task is to determine whether there is an assignment satisfying all the
m clauses. The only difference is, however, each variable xi (including both
literal xi and xi ) appears at most 3 times in all the m clauses. To simplify the
reduction, we assume that the possible occurrences of a variable x in an instance
of 3O3SAT fall in the following three cases:
• Case 1: All occurrences of x are all positive literal x;
• Case 2: The occurrences of x are exactly one positive literal and one
negative literal;
• Case 3: The occurrences of x are exactly two positive literals and one
negative literal.
The above assumption is without loss of generality. We note that there are still
two other cases:
7

• Case 4: All occurrences of x are negative literals;
• Case 5: Exactly two occurrences of negative literals and one positive
literal.
However, Case 4 and Case 5 can be respectively reduced to Case 1 and Case 3,
by replacing occurrences of x and x respectively with y and y. Therefore, we
need only to consider 3O3SAT instances with variables satisfying Case 1-3.
The key idea of the proof is, for any given instance of 3O3SAT, to construct
a graph G, such that there exists a cycle O with c(O) < 0 and l(O) ≥ 3 in G if
and only if the instance is satisfiable. An important fact used in the construction
is that every variable appears at most 3 times in a 3O3SAT instance. In the
following, we will show how to construct G according to clauses, variables, and
the relation between clauses and variables.
1. For each Ck :
Add to G two vertices uk and vk , as well as edge (vk , uk+1 ), 1 ≤ k ≤ m − 1
with cost 0, and edge (vm , u1 ) with cost −1.
2. For each variable xi , construct a lobe according to the occurrences of xi
and xi (The construction a lobe is as depicted in a dashed circle as in
Figure 2):
• Case 1: All occurrences of xi in are positive literal xi , such as x4 in
Figure 2.
For the jth occurrence of xi , add a directed edge (yij , zij ) and assign
cost −2m to it.
• Case 2: Exactly one occurrence for each of positive literal xi and
negation xi , such as x2 in Figure 2.
(a) Add two vertices zij2 = yij1 and yij2 = zij1 , and connect them with
directed edges (yij1 , zij1 ) and (yij2 , zij2 ).
(b) Assign edge (yij1 , zij1 ) with cost −2m and (yij2 , zij2 ) with cost
1
m+1 ;

8

x1
y11 (z13 )

z11

y12

u1

x2

x3

z12 (y13 ) y (z )

z21 (y22 )

v1

u2

1
2

2
2

x4
z31

y31

y41

u3

v2

1
m+1

Cost −2m edge

Cost

Cost m edge

Cost 0 edge

edge

z41

z42

y42

v3

Cost

1
2m+2

edge

Cost −1 edge

Figure 2: The construction of G for an 3O3SAT instance (x1 ∨x3 )∧(x1 ∨x2 ∨x4 )∧(x1 ∨x2 ∨x4 ).

• Case 3: Exactly 2 occurrences of xi and one occurrence xi , such as
x1 in Figure 2.
(a) For the two positive literals of xi , say the j1 th and j2 th occurrence of xi , j1 < j2 , add four vertices yij1 , zij1 , yij2 , zij2 , and
two directed edges (yij1 , zij1 ), (yij2 , zij2 ) connecting them with cost
−2m;
(b) For the negation xi , say the j3 th occurrence, set zij3 = yij1 and
yij3 = zij2 , and add three directed edges (yij3 , yij2 ), (yij2 , zij1 ), (zij1 , zij3 )
with costs

1
2m+2 ,

0 and

1
2m+2 ,

respectively.

3. For the relation between the variables and the clauses, say Ck is the clause
containing the jth occurrence of xi , i.e. Ck is the jth clause xi appears
in, add directed edges (uk , yij ) and (zij , vk ). If the occurrence of xi in Ck
is a positive literal, assign the newly added edges with cost m; Otherwise,
assign them with cost 0. Note that no edges will be added between lobes
and uk , vk if xi does not appear in Ck .
An example of the construction of G according to F = (x1 ∨ x3 )(x1 ∨ x2 ∨
x4 )(x1 ∨ x2 ∨ x4 ) is as depicted in Figure 2.
As kLNCC is apparently in N P, it remains only to prove the following
9

lemma to complete the proof of Theorem 4.
Lemma 6. An instance of 3O3SAT is feasible iff the corresponding graph G
contains a cycle O with l(O) ≥ 3 and c(O) < 0.
Let U = {ui , vi |i = 1, . . . , m} be the set of vertices that correspond to the
clauses. We first prove a proposition that if a path from uh to vl (h 6= l) does
not enroute any other u ∈ U , the cost of the path is at least m.
Proposition 7. Let P (u, v) be a path from u to v. For any path P (uh , vl ) that
satisfiesP (uh , vl ) ∩ U = {uh , vl }, if h 6= l, then c(p(uh , vl )) ≥ m.
Proof. For every edge (y, z) with cost −2m, clearly there exists only one edge
e1 entering y, and only one edge e2 leaving z. Furthermore, e1 = (uh′ , y) and
e2 = (z, vh′ ). So P (uh , vl ), h 6= l, as in the proposition can not go through any
cost −2m edge. That is, P (uh , vl ), h 6= l, can only go through the non-negative
cost edges. It remains to show P (uh , vl ), h 6= l, must go through at least one
cost m edge.
Suppose P (uh , vl ), h 6= l does not go through any cost m edges.

Let

(uh , yij1 ), (zij2 , vl )∈ P (uh , vl ) be the two edges leaving uh and entering vl , respectively. Then yij1 and zij2 must incident to two edges that corresponds to
the negation of two variables. Further, the two variable must be identical, since
vertices of two distinct lobes will be separated by U , and hence for P (yij1 , zij2 ) ⊂
P (uh , vl ), P (yij1 , zij2 ) ∩ U 6= ∅. This contradicts with P (uh , vl ) ∩ U = {uh , vl }.

Proposition 8. In graph G \ e(vm , u1 ), every path P (u, v), u, v ∈ U , has a
non-negative cost.
Proof. Apparently, in G \ e(vm , u1 ), every edge with negative cost is exactly
with cost −2m. Let (yij , zij ) be such an edge with cost −2m. From the structure
of G, there exists exactly one edge entering yij , and exactly one leaving zij , each
of which is with exactly cost m. So for every path P (u, v), u, v ∈ U , if it
contains edge (yij , zij ), then it must also go through both the edge entering yij
10

and the edge leaving zij . That is, the three edges must all present or all absent
in P (u, v), and contribute a total cost 0. Therefore, c(P (u, v)) ≥ 0 must hold.

Now the proof of Lemma 6 is as below:
Proof. Suppose that there exists an assignment τ : x → {true, f alse} satisfying all the m clauses. Since c(vm , u1 ) = −1, we need only to show there exists a
u1 vm -path with cost smaller than 1 by construction such one path. For a satisfied clause Ck , there must exist a literal, say wk with τ (wk ) = true. If wk is the
jth occurrence of xi , then set the corresponding subpath as Pk = uk −yij −zij −vk .
We need only to show P = {Pk |k = 1, . . . , m} ∪ {(vh , uh+1 )|h = 1, . . . , m − 1}
exactly composes a path from u1 to vm with cost smaller than 1. For the first,
P is a path. Because τ is an assignment, τ (xi ) = true and τ (xi ) = true can
not both hold, and hence P contains no length-2 cycle. For the cost, according
to the construction, if τ (wk ) = τ (xi ) = true then the subpath Pk is with cost
exactly equal to 0; otherwise, i.e. τ (wk ) = τ (xi ) = true, the subpath Pk is with
cost exactly equal to

1
m+1 .

fore, the total cost c(P ) ≤

Meanwhile, c(e(vh , uh+1 )) = 0 for each h. Therem
m+1

< 1, where the maximum is attained when all

clauses are all satisfied by negative of the variables.
Conversely, assume that there exists a negative-cost cycle O, which contains
NO negative cost length-2 cycle. According to Proposition 8, e(vm , u1 ) must
appears on O, so that c(O) < 0 can hold. Let P = O \ e(vm , u1 ) and τ be a true
assignment according to P : if P goes through literal xi , set τ (xi ) = f alse and
set τ (xi ) = true otherwise. It remains to show such the assignment according
to P satisfies all the clauses. To do this, we shall firstly show P will go through
all the vertices of U in the order u1 ≺ v1 ≺ · · · ≺ ui ≺ vi ≺ · · · ≺ um ≺ vm ; and
secondly show that P (uh , vh ) has to go through exactly a subpath corresponding
to a literal, say w, for which if τ (w) = true, then Ch is satisfied. Then from the
fact that P contains no negative cost length-2 cycle, τ is a feasible assignment
satisfying all the clauses.
For the first, according to Proposition 7, if P (ui , vj ) ∩ U = {ui , vj }, then
11

j = i (i.e. vj = vi ) must hold. Since otherwise, according to Proposition 7
c(P (ui , vj )) ≥ m must hold; while according to Proposition 8, the other parts
of P is with c(P (u1 , ui )) ≥ 0 and c(P (vj , vm )) ≥ 0. That is, c(P ) ≥ m. On
the other hand, since c(e(vm , u1 )) = −1 and c(O) < 0, we have c(P ) < 1,
a contradiction. Furthermore, since there exists only one edge leaving vi , i.e.
(vi , ui+1 ), P must go through every edge e(vi , ui+1 ) incrementally on i, i.e. in
the order of u1 ≺ v1 ≺ · · · ≺ ui ≺ vi ≺ · · · ≺ um ≺ vm . For the second,
according to the structure of G and c(P ) < 1, c(P (uh , vh )) ≤

1
m+1

must hold.

Then c(P (uh , vh )) has to go through exactly a subpath corresponding to a
literal.



Note that, a simple undirected graph does not allow length-2 cycles. Anyhow, by
replacing length-2 cycles with length-3 cycles in the above proof, i.e. replacing
every edge (yj , zj ) with two edges (yj , wj ) and (wj , zj ) of the same cost, and
ignoring the direction of the edges, we immediately have the correctness of
Corollary 9.
Corollary 9. For any fixed integer k ≥ 4, kLNCC is N P-complete in a simple
undirected graph.

4. Conclusion
In this paper, we have shown the N P-completeness for both the k-length negative cost cycle (kLNCC ) problem in a simple directed graph and the fixed-point
k-length negative cost cycle (FPkLNCCT) problem in a directed multigraph,
which have wide applications in parallel computing, particularly in deadlock
avoidance for streaming computing systems. Consequently, it can be concluded
that kLNCC is N P-complete in a simple undirected graph and that FPkLNCCT
is also N P-complete in a simple directed graph. In future, we will investigate
approximation algorithms for these two problems.

12

References
[1] Richard Bellman. On a routing problem. Technical report, DTIC Document, 1956.
[2] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel
Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms, volume 4. Springer, 2015.
[3] Fedor V Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.
Representative sets of product families. In Algorithms-ESA 2014, pages
443–454. Springer, 2014.
[4] Fedor V Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact
algorithms. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 142–151. SIAM, 2014.
[5] Lester Randolph Ford. Network flow theory. 1956.
[6] S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem* 1. Theoretical Computer Science, 10(2):111–121, 1980.
[7] Harold N Gabow and Shuxin Nie. Finding a long directed cycle. ACM
Transactions on Algorithms (TALG), 4(1):7, 2008.
[8] Michael R Garey and David S Johnson. Computers and intractability: A
guide to the theory of np-completeness, 1979.
[9] Longkun Guo and Hong Shen. On finding min-min disjoint paths. Algorithmica, 66(3):641–653, 2013.
[10] Peng Li, Kunal Agrawal, Jeremy Buhler, and Roger D. Chamberlain. Deadlock avoidance for streaming computations with filtering. In Proc. 22nd
ACM Symp. on Parallelism in Algorithms and Architectures, pages 243–
252, 2010.

13

[11] Hadas Shachnai and Meirav Zehavi. Faster computation of representative
families for uniform matroids with applications. CoRR, abs/1402.3547,
2014.
[12] Craig A Tovey. A simplified np-complete satisfiability problem. Discrete
Applied Mathematics, 8(1):85–89, 1984.
[13] D. Xu, Y. Chen, Y. Xiong, C. Qiao, and X. He. On the complexity of
and algorithms for finding the shortest path with a disjoint counterpart.
IEEE/ACM Transactions on Networking, 14(1):147–158, 2006.

14

