# Flexible Team Orienteering Problem

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.

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 ?

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.
• 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). Jan 15, 2018 at 20:41
• @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. Jan 15, 2018 at 20:48
• 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. Jan 15, 2018 at 20:52
• 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$. Jan 15, 2018 at 21:17