<p>Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function <span class="math-container">$f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$</span>.</p>
<p>Define the following decision problem:
<span class="math-container">$$ \bbox[5px,border:2px solid black]
{
\begin{align*}
&amp;\text{Weighted path}_f \\
&amp;\text{INPUT}: \text{A grid graph $G = (V, E)$ and a bound $K &gt; 0$.} \\
&amp;\text{QUESTION}: \text{Is there a path $\pi$ in $G$ that visits each vertex such that cost$(\pi) \le K$?}
\end{align*} 
}
$$</span></p>
<p>How could one show that this problem is <span class="math-container">$NP$</span>-complete? Membership to <span class="math-container">$NP$</span> is clear, <span class="math-container">$NP$</span>-hardness is not.</p>
<p>If <span class="math-container">$f \equiv n$</span> for some <span class="math-container">$n$</span> then the problem is clearly <span class="math-container">$NP$</span>-hard because we may choose <span class="math-container">$K = (|V|-1) \cdot n$</span> and the problem can be solved iff <span class="math-container">$G$</span> has a Hamiltonian path. But what about a non-uniform definition of <span class="math-container">$f$</span>?</p>
<p>Note: By a grid graph I mean a finite, vertex induced subgraph of the integer lattice <span class="math-container">$(\mathbb Z^2, E)$</span> where <span class="math-container">$(u, v) \in E \iff d_{\ell_2}(u,v) = 1$</span>.</p>

CC BY-SA 4.0
2023-09-19T20:12:23.943Z
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 [edit]ing your post to summarize what you've found.
D.W.
CC BY-SA 4.0
2023-09-22T23:30:14.183Z
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$?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-09-23T06:58:14.230Z
The latter. I.e. find all $f$ for which the problem is NP-hard.
TRP
<cc.complexity-theory><graph-theory><np-hardness>
Generalization of the Hamiltonian path problem on Grid Graphs
TRP
# Generalization of the Hamiltonian path problem on Grid Graphs

(Asked by: username_0 on 2023-09-19)

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

**Tags:** cc.complexity-theory, graph-theory, np-hardness

> **Comments:**
> **username_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 [edit]ing your post to summarize what you've found.  
> **username_2**: 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$?  
> **username_0**: The latter. I.e. find all $f$ for which the problem is NP-hard.  

---

## 0 answers

