3
$\begingroup$

I have the following shortest path problem.

Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a starting node that is connected to all nodes at level $1$ (the first level).

Each edge is labelled by a pair of non-negative integer weights. Each level $i$ has a single non-negative integer label which we call $L_i$.

The goal is to minimize the shortest path with respect to the first weight in each edge weight pair from the starting node to the last level while ensuring that the weight of the path from the starting node with respect to the second weight in each edge weight pair is no more than $L_i$ at each level $i$.

Has this problem been studied? Is it known to be NP-hard?

$\endgroup$
  • $\begingroup$ This problem is actually sort of constrained shortest path problem, which is NP-complete on DAGs (For your DAG is also NP-complete except if weight functions are not arbitrary functions). $\endgroup$ – Saeed Jan 29 '15 at 12:30
  • $\begingroup$ @Saeed This is very interesting. Do you have a suitable reference for the NP-hardness result by any chance? My weights are all non-negative integers. I am not sure what you meant precisely by " except if weight functions are not arbitrary functions". $\endgroup$ – Lembik Jan 29 '15 at 14:03
  • $\begingroup$ In the Gary and Johnson's book is written the proof is by personal communication but I have my own proof which maybe be the same as others but if you want to have a reference to something you may use this paper which also has a nice and quite simple (to implement) FPTAS, but it's not exactly what are you searching for but you can modify it (But just referred to the book for NP-hardness and if you look at the book you will see what I said). sciencedirect.com/science/article/pii/S0020019002002053. $\endgroup$ – Saeed Jan 29 '15 at 14:35
  • $\begingroup$ By my except I mean if for example weight functions are not polynomially bounded by size of the graph. e.g if biggest weight is $n$ where $n$ is the number of nodes in the graph then we can solve the problem by dynamic programming in O(n^3). $\endgroup$ – Saeed Jan 29 '15 at 14:39
  • $\begingroup$ @Saeed I can see a pseudo poly time dynamic programming solution but mine is $O(nm^2 L)$ where $L$ is the largest $L_i$. How do you get it down to your complexity? $\endgroup$ – Lembik Jan 29 '15 at 15:01
6
+50
$\begingroup$

It is NP-hard by reduction from Partition.

Let $x_1,\dots,x_n$ be the partition instance.

Create a graph on levels $0,1,\dots,n$ with level $0$ containing the start vertex $s$, and level $i$ containing two vertices, $a_i$ and $b_i$.

Every path from $s$ to a vertex in the last level corresponds to a partition of $x_1,\dots,x_n$ into two blocks, $A$ and $B$, as follows: If the path goes through $a_i$, then $x_i$ is placed in $A$, otherwise the path must go through $b_i$, and $x_i$ is placed in $B$. Conversely, every partition is realized by some path in this way.

For every edge to $a_i$ from the level below, let the cost be $(x_i,0)$, and for every edge to $b_i$ from the level below, set the cost to $(0,x_i)$. Finally, set $L_i = \sum_{i=1}^n x_i/2$. Now the partition instance has a balanced partition if and only if there is a solution to the path problem with cost $\le \sum_{i=1}^n x_i/2$.

(Edit: I originally gave a reduction from the shortest weight-constrained path problem, and then to answer a comment; a reduction from partition to the shortest weight-constrained path problem. However, the last reduction is enough by itself.)

$\endgroup$
  • $\begingroup$ Thank you. Very nice and simple in the end. I notice the Knapsack reduction (in the now deleted answer) was similarly simple as well. $\endgroup$ – Lembik Feb 7 '15 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.