1
$\begingroup$

In Team Orienteering Problem (TOP) we have a graph $G=(V,E)$ and $K$ participants, We are supposed to find $K$ paths with total edge cost less than a threshold while maximising total vertex rewards. The constraint on reward collecting is once a reward has been collected by some participant the it can not be collected again by another participant. e.g. each vertex have only one piece of reward.

enter image description here

But given a graph like this, and two participants, where $s,t$ are the start and terminating points. I want to have two pieces of reward in $d$ but only one piece of reward in $b$ and $c$.

Does this problem has a name ? Is that proven to be NP-Complete ?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't know if it has a name but it's NP-hard. Just take $K=1$, give every edge and vertex weight $1$ and ask if there's a solution with vertex reward $|V|$ and edge cost at most $|V|-1$. This happens if, and only if, there's an $s$–$t$ Hamiltonian path. The decision version "Can I get reward at least $R$ with cost at most $C$" is NP-complete.

$\endgroup$
10
  • $\begingroup$ I understand if $n=\vert V \vert$ it will end up creating a hamiltonian path. But having more than 2 reward points in the same vertex doesn't play any role with one participant only. if $K\geq 1$ we cannot use all $\vert V \vert$ vertices because of the vertex sharing coefficient (limited number of rewards in each vertex). $\endgroup$
    – Neel Basu
    Jan 15, 2018 at 20:41
  • 1
    $\begingroup$ @NeelBasu Setting $K=1$ allows us to solve an NP-hard problem, so this problem is NP-hard. It doesn't matter what happens when $K=2$, because $K=1$ on its own has that power. $\endgroup$ Jan 15, 2018 at 20:48
  • $\begingroup$ Thanks, understood. However if I asked for miximizing (total rewards - total edge cost) with limited rewards on vertices would that still be NP-complete with $K\geq 2$ ? I think in that case $K$ matters. $\endgroup$
    – Neel Basu
    Jan 15, 2018 at 20:52
  • $\begingroup$ Well, you can even ask if the original problem is still NP-hard if restricted to $K>1$. My guess is that it probably is, but a reduction doesn't immediately come to mind. Maybe you could do something with max-cut? Reward-minus-cost shouldn't make much difference, since you can always give every vertex weight 2 and every edge weight 1 and you're in the same situation of having to construct a Hamilton path when $K=1$. $\endgroup$ Jan 15, 2018 at 21:17
  • $\begingroup$ Yes I was trying to reduce it for two days. I am afraid that people may think reward-cost is solvable by shortest path, but that sharing makes it hard. Now I think TOP is not the best problem to reduce, I was thinking Graph partitioning is something to start with. I will try with Max cut. Here is the question I posted for that cs.stackexchange.com/questions/86785/… $\endgroup$
    – Neel Basu
    Jan 15, 2018 at 21:19

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.