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)?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
13
$\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$.

Improve this answer
$\endgroup$
9
  • $\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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 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.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ The directed Hamiltonian path problem for DAGs is polynomial-time, not NP-complete. $\endgroup$
    – David Eppstein
    Mar 11, 2011 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, 2011 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, 2011 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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