snor.re

Constrained Shortest Path is NP-complete

Published 2020-09-05

A friend recently mentioned a graph/flow network problem consisting of finding the shortest path between two vertices such that some secondary cost of the path doesn’t exceed some set threshold.

As an example, we can think of a transportation network, where each edge has both a cost and a transportation time associated. Then the problem consist of finding a route that can move goods as cheaply as possible within a given maximum transportation time, if one exists. Or, vice versa, finding a fastest route that doesn’t exceed some transportation budget, if one exists.

We can formalize this as the following optimization problem:

Optimization problem [Constrained Shortest Path].

Input. A directed multigraph G=(V,E)G = (V,E), two vertices s,tVs,t \in V, two edge weight functions w1,w2:EZ0w_1,w_2 : E \to \mathbb{Z}_{\ge 0}, such that w1(e)w_1(e) and w2(e)w_2(e) are not both zero for each eEe \in E, and a maximum weight W2Z0W_2 \in \mathbb{Z}_{\ge 0}.

Output. A simple path π\pi from ss to tt minimizing w1(π)w_1(\pi) subject to w2(π)W2w_2(\pi) \le W_2, or, if no such path exists, \bot.

(In the above, w1(π)w_1(\pi) denotes the total w1w_1-weight of the path π\pi, that is, w1(π)=eπw1(e)w_1(\pi) = \sum_{e \in \pi} w_1(e), and similarly for w2w_2.)

My friend was in particular interested in whether the problem was solvable in polynomial time, so, having recently taken a course in NP-completeness, I decided to try to answer this question.

Decision problem

While the optimization problem is the problem we actually want to reason about, to use the concept of NP-completeness, we must first find a corresponding decision problem. A decision problem is a problem that given some input either has the answer YES or NO.

To be more precise, a corresponding decision problem is one where, given an algorithm AA that answers the decision problem, we can construct an algorithm for answering the optimization problem, and vice versa, such that the constructed algorithm invokes AA only a polynomial number of times (as a function of the input size) and only performs additional computations with polynomial time complexity.

We focus here on polynomial time complexity because it means that a polynomial-time AA leads to a polynomial-time algorithm for the optimization problem—and, conversely, that if no polynomial-time AA exists, there can exist no polynomial-time algorithm for the optimization problem.

Surprisingly, it is possible to formulate the decision problem in a way that makes the weights w1w_1 and w2w_2 symmetrical. Using this, we can group them as pairs, so that w(e)=(w1(e),w2(e))w(e) = (w_1(e),w_2(e)) for each eEe \in E. This lets us simplify our notation a bit, by saying (w1,w2)(W1,W2)(w_1,w_2) \le (W_1,W_2) if and only if w1W1w_1 \le W_1 and w2W2w_2 \le W_2.

A somewhat natural corresponding decision problem is then given by:

Decision problem [Constrained Shortest Path].

Input. A directed multigraph G=(V,E)G = (V,E), two vertices s,tVs,t \in V, a pair-valued edge weight function w:EZ02w : E \to \mathbb{Z}_{\ge 0}^2 where w(e)(0,0)w(e) \ne (0,0) for each eEe \in E, and a maximum weight pair WZ02W \in \mathbb{Z}_{\ge 0}^2.

Output. YES if there exists a path π\pi from ss to tt such that w(π)Ww(\pi) \le W, otherwise NO.

(Here, we let w(π)=(w1(π),w2(π))w(\pi) = (w_1(\pi), w_2(\pi)).)

Importantly, this problem is actually in NP. A bit informally, this means that there exists a polynomial-time non-deterministic algorithm that always answers NO for NO-instances, and is capable of answering YES for every YES-instance.

To see this, we can observe, that we can non-deterministically “guess” a simple path from ss to tt (in polynomial time), and then determine whether it satisfies the constraint w(π)Ww(\pi) \le W (in polynomial time), by simply calculating w(π)w(\pi).

We will now show that the optimization corresponds to the decision problem.

Correspondence to the optimization problem

First we need to prove that we can use a solution to the optimization to solve the decision problem. To do this, consider an instance XX of the decision problem. We can then construct an instance of the optimization problem using the same multigraph G=(V,E)G=(V,E), same vertices s,ts,t, same edge weight function ww, and same w2w_2-constraint W2W_2.

A solution to the optimization problem will then provide us with either a path π\pi minimizing w1w_1 subject to w2(π)W2w_2(\pi) \le W_2, or \bot, if no such path exists. In the first case, we know that the decision problem must have answer YES if W1w1(π)W_1 \ge w_1(\pi), as π\pi then is an example of a satisfying path, or NO if W1<w1(π)W_1 < w_1(\pi), as π\pi minimizes w1w_1. In the second case, there exists no path π\pi satisfying w2(π)W2w_2(\pi) \le W_2 at all, so clearly the answer to the decision problem is NO. This shows that we can turn an answer to the optimization problem into an answer to the decision problem.1

To see that the reverse is also the case, that is, that a solution to the decision problem helps us solve the optimization problem, let AA be an algorithm solving the decision problem. Then we can solve the optimization problem with the following algorithm:

Algorithm [Optimization problem from decision problem].

Input. A directed multigraph G=(V,E)G = (V,E), two vertices s,tVs,t \in V, two edge weight functions w1,w2:EZ0w_1,w_2 : E \to \mathbb{Z}_{\ge 0}, such that w1(e)w_1(e) and w2(e)w_2(e) are not both zero for each eEe \in E, and a maximum weight W2Z0W_2 \in \mathbb{Z}_{\ge 0}.

Output. A simple path π\pi from ss to tt minimizing w1(π)w_1(\pi) subject to w2(π)W2w_2(\pi) \le W_2, or, if no such path exists, \bot.

Steps.

  1. Let M=eEw1(e)M = \sum_{e \in E} w_1(e). If AA answers NO when given W=(M,W2)W = (M,W_2), then answer \bot and stop.
  2. Perform a binary search on the interval [0,M][0,M] to find the smallest W1[0,M]W_1 \in [0,M] such that AA answers YES when given W=(W1,W2)W = (W_1,W_2).
  3. For each edge eEe \in E, do the following:
    1. Remove ee from EE.
    2. If this causes AA to answer NO, then put ee back in EE.
  4. Return the path consisting of exactly the remaining edges in EE.

We now need to show two things: That the algorithm correctly solves the optimization problem, and that it runs in polynomial time provided that AA runs in polynomial time.

Correctness. Since every simple path contains each edge at most once, we must have w1(π)Mw_1(\pi) \le M for all simple paths π\pi. It is therefore correct to return \bot if AA answers NO in step 1 when given W=(M,W2)W = (M,W_2).

Assume now that the algorithm reaches step 2. Then there must exist at least one simple path π\pi such that w2(π)W2w_2(\pi) \le W_2. Let then W1[0,M]W_1 \in [0,M] denote the smallest w1w_1-weight of such a path, such that no simple path π\pi satisfies both w1(π)<W1w_1(\pi) < W_1 and w2(π)W2w_2(\pi) \le W_2. Clearly, AA, when given W=(W1,W2)W = (W_1',W_2), must then answer YES if W1W1W_1' \ge W_1 and NO if W1<W1W_1' < W_1. Because of this, we can conclude that the binary search in step 2 must successfully find W1W_1, and that every solution π\pi to the optimization problem we are trying to solve must have w1(π)=W1w_1(\pi) = W_1.

If we reach step 2, we thus know AA answers YES for W1=MW_1 = M. Since there is a minimal w1w_1-weight, we know that AA must answer NO for all values of W1W_1 less than this value and YES for all values greater than or equal to it. Hence, the so the binary search must successfully find a smallest satisfactory W1W_1. In other words, in order to minimize w1(π)w_1(\pi), every solution π\pi must have w1(π)=W1w_1(\pi) = W_1.

For the loop in step 3, at the start and end of each iteration, AA must answer YES. This means that we gradually remove each edge that is not part of every remaining solution to the problem. Hence, the edges remaining after step 3 are exactly those edges that are part of every remaining solution. But then they must in fact form the last and only remaining solution, so step 4 is correct.

Analysis. The only parts of the algorithm that could be problematic in terms of time complexity are the binary search in step 2 and the loop in step 3. However, since the binary search takes at most O(logM)O(\log M) iterations, it invokes AA a number of times polynomial in the input size.2 The loop in step 3 invokes AA exactly once for each edge in EE, so it requires O(E)O(|E|) calls to AA, which is also polynomial in the input size. We can thus conclude that the algorithm invokes AA a polynomial number of times and otherwise takes polynomial time.

In summary, we can conclude, that there exists a (deterministic) polynomial-time algorithm for solving the optimization problem if and only if the given decision problem is in P.

NP-completeness

Having found a corresponding decision problem, the next step is to either show it is in P or that it is NP-complete. If the problem is in P, then it can be solved by a deterministic polynomial-time algorithm. If on the other hand it is NP-complete, then it is at least as difficult to solve as all other problems in NP, and probably can’t be solved by a polynomial-time algorithm.

Failing to easily come up with a proof either way, I decided to try to look up whether the problem was well-known, hoping to find an existing proof. Doing this, I found a reference to a variant of the same problem in the book Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson:

[ND30] SHORTEST WEIGHT-CONSTRAINED PATH

INSTANCE: Graph G=(V,E)G = (V,E), length l(e)Z+l(e) \in Z^+, and weight w(e)Z+w(e) \in Z^+ for each eEe \in E, specified vertices s,tVs,t \in V, positive integers K,WK,W.

QUESTION: Is there a simple path in GG from ss to tt with total weight WW or less and total length KK or less?

Reference: [Megiddo, 1977]. Transformation from PARTITION.

Comment: Also NP-complete for directed graphs. Both problems are solvable in polynomial time if all weights are equal or all lengths are equal.

It states that the problem can be proven NP-complete by transformation from the Partition problem. Unfortunately, the reference to the proof is given as “private communication”, so no actual proof is included.

It does, however, provide a hint for the kind of problem we can use. Instead of the Partition problem, I will here provide a proof using the similar Subset Sum problem.

It should be noted, that the formulation of the Shortest Weight-Constrained Path problem differs from that of the Constrained Shortest Path problem given earlier. However, the proof presented here can, as we will see at the end, be adapted to work for the Shortest Weight-Constrained Path problem as well.

In any case, here we go.

Transformation from Subset Sum

Subset Sum is a known NP-complete problem, so if we can show that Constrained Shortest Path is at least as difficult to solve as Subset Sum, it too must be NP-complete. To show this in practice, we must show that if we can solve Constrained Shortest Path instances in polynomial time, then we can also solve Subset Sum instances in polynomial time. Somewhat counterintuitively, this means we must be able to transform the problem instances in the opposite direction, i.e., that we must be able to turn each instance of Subset Sum into an instance of Constrained Shortest Path. Additionally, this transformation must preserve the answer of the instance and must itself have polynomial time complexity.

The formulation of Subset Sum we will use here is given by:

Decision problem [Subset Sum].

Input. Positive integers s1,,sns_1,\dotsc,s_n and integer BB.

Output. YES if there exists A{1,,n}A \subseteq \{1,\dotsc,n\} such that iSsi=B\sum_{i \in S} s_i = B, otherwise NO.

For this pair of problems, there exists a relatively clean transformation:

Transformation.

Input. An instance of Subset Sum, that is, positive integers s1,,sns_1,\dotsc,s_n and integer BB.

Output. An instance of Constrained Shortest Path, that is, a directed multigraph G=(V,E)G = (V,E), two vertices s,tVs,t \in V, a pair-valued edge weight function w:EZ02w : E \to \mathbb{Z}_{\ge 0}^2 where w(e)(0,0)w(e) \ne (0,0) for each eEe \in E, and a maximum weight pair WZ02W \in \mathbb{Z}_{\ge 0}^2.

Steps.

  1. Create n+1n+1 vertices, v0v_0 through vnv_n, and let V={v0,,vn}V = \{v_0,\dotsc,v_n\}. For each i=1,,ni=1,\dotsc,n, create two parallel edges eie_i and eie_i' between vi1v_{i-1} and viv_i, and let E={ei,eii=1,,n}E = \{e_i,e_i' \mid i=1,\dotsc,n\}.
  2. Let s=v0s=v_0 and t=vnt=v_n.
  3. Let w(ei)=(si,0)w(e_i) = (s_i,0) and w(ei)=(0,si)w(e_i') = (0,s_i) for each i=1,,ni=1,\dotsc,n.
  4. Let W=(B,SB)W = (B,\: S - B), where S=i=1nsiS = \sum_{i=1}^n s_i.

The transformation has polynomial time complexity. Labeling each edge ee with w(e)w(e), we can visualize the constructed multigraph as:

This transformation has several important properties. First note, that for each i=1,,ni=1,\dotsc,n we have w1(ei)+w2(ei)=w1(ei)+w2(ei)=siw_1(e_i) + w_2(e_i) = w_1(e_i') + w_2(e_i') = s_i. Hence, since a path π\pi from ss to tt must include either eie_i or eie_i' but not both for each i=1,,ni=1,\dotsc,n, we must have w1(π)+w2(π)=s1+s2++sn=Sw_1(\pi) + w_2(\pi) = s_1 + s_2 + \dotsb + s_n = S.

Now, assume the answer to the Subset Sum instance is YES, that is, that there exists A{1,,n}A \subseteq \{1,\dotsc,n\} such that iAsi=B\sum_{i \in A} s_i = B. Then consider the path π\pi constructed by following eie_i if iAi \in A and following eie_i' if i∉Ai \not\in A for each i=1,,ni=1,\dotsc,n. Then clearly w1(π)=iAsi=Bw_1(\pi) = \sum_{i \in A} s_i = B and w2(π)=Sw1(π)=SBw_2(\pi) = S - w_1(\pi) = S - B, so π\pi satisfies w(π)Ww(\pi) \le W. The answer to the constructed Constrained Shortest Path instance is thus also YES.

Assume now instead, that the answer to the constructed Constrained Shortest Path instance is YES, that is, that there exists a path π\pi from ss to tt such that w1(π)Bw_1(\pi) \le B and w2(π)SBw_2(\pi) \le S - B. Then

w1(π)=Sw2(π)S(SB)=B.w_1(\pi) = S - w_2(\pi) \ge S - (S - B) = B.

so w1(π)=Bw_1(\pi) = B. Let now AA be defined by iAi \in A if and only if π\pi includes eie_i. Then iAsi=w1(π)=B\sum_{i \in A} s_i = w_1(\pi) = B, so the answer to the Subset Sum instance is YES.

We have in other words shown that the Subset Sum is a YES-instance if and only if the constructed Constrained Shortest Path instance is a YES-instance. Hence if there exists a polynomial-time algorithm for solving instances of Constrained Shortest Path, then we can combine that algorithm with the above transformation to get a polynomial-time algorithm for solving Subset Sum.

In conclusion, since Subset Sum is NP-complete, we see that Constrained Shortest Path also is NP-complete.

Note that since the construction happens to be acyclic, the problem is still NP-complete if we restrict it to acyclic directed multigraphs.

Adapting the proof to Shortest Weight-Constrained Path

The formulation of Shortest Weight-Constrained Path from Computers and Intractability differs from our Constrained Shortest Path formulation in two aspects:

  1. It requires G=(V,E)G=(V,E) to be an undirected graph rather than a directed multigraph.
  2. It requires both w1(e)w_1(e) and w2(e)w_2(e) to be positive for each eEe \in E.

Adapting to the first difference, we can make the edges undirected and add a dummy vertex per edge to ensure there is at most one edge between any two vertices. To satisfy the second difference, we can add (1,1)(1,1) to the weight of every edge, and, in response, increase WW by (2n,2n)(2n,2n).

We can visualize the new transformation as:

We then set W=(B+2n,SB+2n)W = (B + 2n,\: S - B + 2n).

References

  1. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co, 1990.

  1. For completeness sake, it is also important that the transformation takes at worst polynomial time.↩︎

  2. The problem encoding scheme must encode the weights, so the input size is Ω(logM)\Omega(\log M).↩︎