# Generalization of the Hamiltonian path problem on Grid Graphs

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$$.

• 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.
– D.W.
Sep 19, 2023 at 20:12
• 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$?
– a3nm
Sep 22, 2023 at 23:30
• The latter. I.e. find all $f$ for which the problem is NP-hard.
– TRP
Sep 23, 2023 at 6:58