2
$\begingroup$

Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible fuel tanks). A path from A to B is a series of contiguous edges starting at A and finishing at B. The net cost of a path is the sum of the weights of edges (including multiplicity) on the path minus the sum of the benefits of the distinct nodes (ignoring multiplicity) on the path.

In principle paths are permitted to visit a node more than once, but the node's benefit is only ever collected once (i.e. you can't pick up the same fuel can twice).

Is there an efficient algorithm to find a minimum cost path from A to B in this situation? What if you're promised that the input contains no paths from A to B with net negative cost? What if you're happy with heuristics that perform well when nodes containing 'fuel' are scarce?

Improve this question
$\endgroup$
5
  • $\begingroup$ How much have you tried finding cases when this problem might be NP-hard? $\endgroup$
    – John L.
    Dec 24, 2018 at 21:19
  • $\begingroup$ Why would you consider paths that enter a node twice? You will not gain any extra benefit. $\endgroup$
    – Hendrik Jan
    Dec 24, 2018 at 21:22
  • 1
    $\begingroup$ @HendrikJan Imagine a path with only one entrance/exit with a big "fuel tank" at the end. Then the nodes alone the way will need to be entered twice (once on entrance, once on exit) $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Dec 24, 2018 at 21:28
  • $\begingroup$ @BlueRaja-DannyPflughoeft Of course, a small detour to get a bonus. Thanks. $\endgroup$
    – Hendrik Jan
    Dec 24, 2018 at 21:45
  • $\begingroup$ @Apass.Jack I have not tried much at all. Partially because I have a more specialized case in mind where the fuel would be relatively scarce, and I expect a reduction would involve a lot of fuel cans lying around. I would consider an answer containing a reduction to be a valid answer and accept it. $\endgroup$
    – Craig Gidney
    Dec 25, 2018 at 0:53

1 Answer 1

Reset to default
1
$\begingroup$

This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP. Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish. Now running a solver for your problem will give the solution to the TSP.

I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier. If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Doesn't the TSP have a stricter condition about revisiting? In this problem you're allowed to backtrack. For the heuristic argument, subtracting the fuel at a node from the incoming edges may give those edges negative cost which violates the conditions of the usual shortest path problem. $\endgroup$
    – Craig Gidney
    Dec 25, 2018 at 3:29

Your Answer

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

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