Finding a "lowest" path in a graph

Question

I have an undirected graph $G = (E,V)$, $|V|=n$, where each node $v_i$ has a natural number weight. Think of these weights as heights $h_i$. Given two nodes $s$ and $t$, I'd like to find a lowest simple path between $s$ and $t$, a path whose average height is minimal among all simple paths. If $\rho = (s{=}v_1, v_2, \ldots, v_{k-1}, v_k{=}t)$ is a path, its average height is $(h_1 + \cdots + h_k)/k$. The path $\rho$ must be simple, i.e., no vertex repeated.

I am not seeing an efficient algorithm. If it helps, assume $G$ is planar.

Answer 1

This problem is NP-complete, by reduction from Hamiltonian cycle in a graph G=(V,E). Every edge in E receives weight 0. If a vertex is traversed, there is a gadget that allows you to use an edge of weight 1. Now in order to maximize the average, you need as many weight-1 edges as possible.

Here are some details for the construction:

Consider an instance $(V',E')$ of directed Hamilton path that asks for a Hamilton path from vertex $x\in V'$ to vertex $y\in V'$. We create the following instance of the lowest path problem in an undirected graph $G=(V,E)$ from it:

• Every vertex $v\in V'$ is replaced by three new vertices $v_1,v_2,v_3$, together with the two edges $\{v_1,v_2\}$ and $\{v_2,v_3\}$.
• For every arc $(v,u)\in E'$, we introduce the undirected edge $\{v_3,u_1\}$ in graph $G$.
• All edges $\{v_2,v_3\}$ in $G$ with $v\ne x$ and $v\ne y$ have weight 1, and all the remaining edges have weight 0.
• The starting point of the desired lowest path is vertex $x_2$, and the endpoint is vertex $y_2$.

Consider a path $P$ in $G$ from $x_2$ to $y_2$, and let $k$ denote the number of weight $1$ edges on $P$.Then $P$ must also contain (at least) $3k+4$ edges of weight $0$, so that the average weight is at most $k/(4k+4)$. This expression is at most $|V'|/(4|V'|+4)$. A Hamilton cycle in $G'$ translates into a path with average weight $|V'|/(4|V'|+4)$ in $G$.