2
$\begingroup$

Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$.

Does there exists a path in $G$ with total weight $W$ that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

$\endgroup$
4
$\begingroup$

So this is a simple solution to this question. Given an instance of Hamiltonian path problem $G(V, E)$. Just set $w$ and $\mathrm{max-visit}$ to be equal to $1$ everywhere and $W=|V|$. A path in $G$ satisfies the requirements in our problem now corresponds to a Hamiltonian path in the original instance, and vice versa.

$\endgroup$

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.