3
$\begingroup$

Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.

The problem is:

Find a path from $s$ to $t$ with cost $a$.

I suppose this is NP-hard.

Some questions:

  1. Would putting a bound $\max w_i < C$ make the problem easier?
  2. What are the best algorithms for this?
  3. Is the problem NP-complete?

Update What about this modification of Number: 63 Shortest Weight-Constrained Path

To each edge associate second label weight $r_i \in \mathbb{N}$. The weight of a path is the sum of $r_i$.

Assume (possibly small) bound $C$ of the costs $w_i$ and solve:

$cost = a$ and $weight < K$.

Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?

$\endgroup$
12
$\begingroup$

Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.

If you assume that $\max w_i<C$ then there's a dynamic programming algorithm with time $O(mnC)$: just process the nodes in a topological ordering, and for each node calculate the set of path lengths by which it can be reached from $s$.

$\endgroup$
  • $\begingroup$ Thank you. I suppose something close to $O(mnC)$ can be achieved by replacing $w_i$ by a chain of $w_i$ unlabelled edges and then search for path of length $a$? $\endgroup$ – jerr18 Mar 11 '11 at 8:25
  • $\begingroup$ Each set is a bitmask of nC bits and you have to propagate these bitmasks across m edges, hence the O(mnC) time bound. $\endgroup$ – David Eppstein Mar 11 '11 at 8:40
  • $\begingroup$ Since you are looking for a path with cost exactly $a$, a bitmask of $a$ bits suffices. Hence $O(nma)$ time holds also without a $\max w_i<C$ bound. $\endgroup$ – Gianluca Della Vedova Mar 11 '11 at 9:12
  • 2
    $\begingroup$ @jerr18 @Radu Yes, it's $O(n+ma)$, and it's on non-negative weights. $\endgroup$ – Gianluca Della Vedova Mar 11 '11 at 10:06
  • 1
    $\begingroup$ One additional remark is that one can implement an $O(n+ma)$ algorithm using dynamic programming even if the graph is not a DAG. $\endgroup$ – arnab Mar 12 '11 at 5:42
0
$\begingroup$

Another way to prove that it is NP-complete consist of noticing that if each label is 1 and $a = \#V$ where $V$ is the set of vertices, we obtain the hamiltonian path problem. It shows too that even if you give an upper bound C, it remains NP-complete.

EDIT: My answer is wrong because in DAG, hamiltonian path problem has a polynomial algorithm.

$\endgroup$
  • 4
    $\begingroup$ The directed Hamiltonian path problem for DAGs is polynomial-time, not NP-complete. $\endgroup$ – David Eppstein Mar 11 '11 at 15:46
  • $\begingroup$ @David Oups, I hadn't read enough carefully the question. Should I delete my answer to prevent people from being misled if they don't read comments ? $\endgroup$ – Ludovic Patey Mar 11 '11 at 23:14
  • $\begingroup$ Currently we have no policy about deleting wrong answers, so you may do anything you want. Edit the answer, as you did, is another solution. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 12 '11 at 16:44

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.