<p>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.</p>

<p>Here are some details for the construction:</p>

<p>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:</p>

<ul>
<li>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\}$.</li>
<li>For every arc $(v,u)\in E'$, we introduce the undirected edge $\{v_3,u_1\}$ in graph $G$.</li>
<li>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.</li>
<li>The starting point of the desired lowest path is vertex $x_2$, and the endpoint is vertex $y_2$.</li>
</ul>

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

CC BY-SA 4.0
2018-07-13T08:33:22.743Z
2018-07-13T17:27:47.083Z
2018-07-13T17:27:47.083Z
Gamow
<p>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 <em>lowest</em> 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.</p>

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

CC BY-SA 4.0
2018-07-12T20:12:27.750Z
This problem is btw (somewhat) related to the min-average cost cycle in directed graphs, which can be solved in polynomial time.
Sariel Har-Peled
<graph-algorithms><planar-graphs>
Finding a "lowest" path in a graph
Joseph O'Rourke
# Finding a "lowest" path in a graph

(Asked by: username_0 on 2018-07-12)

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.

**Tags:** graph-algorithms, planar-graphs
> **Comments:**
> **username_1**: This problem is btw (somewhat) related to the min-average cost cycle in directed graphs, which can be solved in polynomial time.  

---

## 1 answers

### Answer by username_2 on 2018-07-13. Score: 2 | Accepted answer

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


---

