3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This problem is btw (somewhat) related to the min-average cost cycle in directed graphs, which can be solved in polynomial time. $\endgroup$ – Sariel Har-Peled Jul 12 '18 at 20:12
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.