Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$.

Define the following decision problem: $$ \bbox[5px,border:2px solid black] { \begin{align*} &\text{Weighted path}_f \\ &\text{INPUT}: \text{A grid graph $G = (V, E)$ and a bound $K > 0$.} \\ &\text{QUESTION}: \text{Is there a path $\pi$ in $G$ that visits each vertex such that cost$(\pi) \le K$?} \end{align*} } $$

How could one show that this problem is $NP$-complete? Membership to $NP$ is clear, $NP$-hardness is not.

If $f \equiv n$ for some $n$ then the problem is clearly $NP$-hard because we may choose $K = (|V|-1) \cdot n$ and the problem can be solved iff $G$ has a Hamiltonian path. But what about a non-uniform definition of $f$?

Note: By a grid graph I mean a finite, vertex induced subgraph of the integer lattice $(\mathbb Z^2, E)$ where $(u, v) \in E \iff d_{\ell_2}(u,v) = 1$.

  • $\begingroup$ You might start by reviewing the proof that "Hamiltonian path in a grid graph" is NP-hard, checking what are the challenges or barriers to applying those techniques to your problem, and editing your post to summarize what you've found. $\endgroup$
    – D.W.
    Sep 19, 2023 at 20:12
  • $\begingroup$ I'm not sure I understand the question. The problem can be NP-hard if $f$ is constant. Is your question whether there exist non-constant functions $f$ such that this is NP-hard? Or whether this is NP-hard for all functions $f$? $\endgroup$
    – a3nm
    Sep 22, 2023 at 23:30
  • $\begingroup$ The latter. I.e. find all $f$ for which the problem is NP-hard. $\endgroup$
    – TRP
    Sep 23, 2023 at 6:58


Your Answer

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