2
$\begingroup$

The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain amount of time to traverse it. The reward is consumed on visiting once, so a path may visit a node multiple times but receives 0 reward for future visits.

Is there an algorithm for maximising the reward while proceeding from node A to node B (or back to A again) in a given maximum amount of time available?

Note that the times and rewards cannot be combined as a single "weight".

The data is sparse and isn't that big: a few hundred nodes which typically have less than 5 arcs each.

Any tips on modelling and/or algorithms greatly appreciated.

|cite|improve this question
$\endgroup$
1
$\begingroup$

I think this problem is NP-Complete via reduction to Knapsack Problem

An instance of the Decision Problem involves: a Graph g, time alloted, sum_reward, and two nodes s,t : Is there path from s to t with sum of rewards>=sum_reward within the alloted time period?

Reduction

Add nodes $s,t$ and an edge $s->t$ with reward,weight =0. For every item a=(value(a),weight(a)) create a node $n_{a}$ and the following two edges:

  • $e_{a}= s->n_{a}$ with $reward(e_{a})=value(a)$ and $cost(e_{a})=weight(a)$
  • $e_{b}= n_{a}->s$ with both values zero

I just noticed that rewards are on nodes instead of edges. But this does not change the reduction(just transfer reward from edge to node)

Now run the algo for input ($G',knapsack$ $size$,$sum$ $reward,s,t$)$

IFF proof

=> if knapsack is feasible, simply iterate over edges of nodes contained in the knapsack and finally hop from s to t. This will give the desired sum_reward

<= More or less, the same idea.

I hope this helps you somehow :)

Since your data is kind of special, perhaps someone can provide an exact algorithm instead of an approximation one. I cannot (yet :P)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Aren't you assuming here that there is a requirement to return to point S after collecting each reward (that we can only "carry" one of them at once)? That isn't the case. We can assume infinite carrying capacity and there is no requirement to be anywhere particular until the maximum time runs out. $\endgroup$ – Geoff Bache Oct 9 '15 at 21:02
  • $\begingroup$ I constructed the graph in such a way that picking an item is the same as traversing the two edges connecting the node of the item with s. Of course this is not true for all instances of the problem, but it suffices (or I think it does ) to show NP-Hardness. $\endgroup$ – jjohn Oct 9 '15 at 21:10
  • $\begingroup$ Ah, OK. I misunderstood what you meant by "reduction" then, I thought you were showing equivalence to a known problem, rather than showing that a much more constrained problem could still be NP-Hard. I think it's pretty clear that it is NP-Hard in the general case, the question then becomes more if good approximations/heuristics can be found and whether the sparseness of the data can be utilised in some way. I'm thinking along the lines of graph pruning using shortest paths with the times, it seems like you could possibly cut the graph size down a great deal doing that. $\endgroup$ – Geoff Bache Oct 9 '15 at 21:30
1
$\begingroup$

This problem is NP-hard by a simple reduction from the directed Hamilton cycle problem. Given a graph $G$ with $n$ nodes, simply set all edge weights to $1$ and place a positive reward on every node. Observe that $G$ has a directed Hamilton cycle if and only if it is possible to collect all rewards in $n$ time units on a round trip starting at an arbitrary node. Hence your problem is NP-hard and I would not be too hopeful to find an efficient algorithm for solving it exactly.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think this is only relevant if you're assuming that the maximum time available is such that all rewards can be collected. But that isn't going to be true in practice most of the time. There is no requirement to get all the rewards, just as many as possible in the time given, which is typically much too small to traverse the whole graph. $\endgroup$ – Geoff Bache Oct 9 '15 at 20:48
  • $\begingroup$ That doesn't make it easier. At least as long as the maximum number of rewards that can be collected is allowed to be within a polynomial ratio of the total number of nodes, a similar reduction is possible. If you are just looking at very specific instances of the problem, maybe you should specify them in more detail so we can help you better. $\endgroup$ – Dennis Kraft Oct 10 '15 at 5:47
  • $\begingroup$ I think we're agreed this is NP-hard in the general case. But I'm still hoping to get somewhere with approximate solutions and heuristics. Beyond what I've already stated about the data I don't know that there's much more to add: about 200 nodes and typically less than 5 arcs per node, with the maximum time allowing collection of maybe 20-30 rewards. As I replied to jjohn above I have a vague idea to try if nothing more promising turns up here. $\endgroup$ – Geoff Bache Oct 12 '15 at 19:26
  • $\begingroup$ Well, if your input is of fixed size, a brute force algorithm runs in constant time theoretically. However, the search space is still way too large for this to be practical. Maybe you can come up with some heuristics that work for you. Right now I don't see any obvious solution that guarantees a good approximation ratio. $\endgroup$ – Dennis Kraft Oct 12 '15 at 21:28

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.