Maximal Average Path Assume that we have a graph $(V,E)$ where $V$ is a finite list of vertices, $E\subset V^2$, and $(a,b)\in E$ implies $(b,a)\in E$.  Further assume that we have a value function $f:V\rightarrow \mathbb R^+$ where $\mathbb R^+$ denotes the non-negative reals.  
Define a non-repeating path from $v_0$ to $v_\infty$ as a sequence of verticies $v_1, v_2, \ldots v_n$ such that $n$ is a positive integer, $(v_i, v_{i+1})\in E$ for $i=0,1, \ldots, n-1$, $(v_n, v_\infty)\in E$, and $v_i=v_j$ if and only if $i=j$.    
Define the average value of a non-repeating path $v_1, v_2, \ldots, v_n$ to be $\frac1n \sum_{i=1}^n f(v_i)$.  
Given $\{v_0, v_\infty\}\in V$, is there a polynomial time algorithm for finding a non-repeating path with the maximal average value? (i.e. The running time is bounded by a $p(k)$ where $k$ is the number of points in $V$ and $p$ is a polynomial.)
Also, does it help if the graph is planar?    
 A: This problem is NP-complete, which is bad news.
To see that it's NP-hard, reduce from the Hamiltonian path problem; specifically, the version where we have two vertices $s,t$, and we want to find a path that starts at $s$, ends at $t$, and visits all other vertices exactly once.
Given an instance of this problem in a graph $G$, add a new vertex $v_0$ adjacent only to $s$ and a new vertex $v_\infty$ adjacent only to $t$. Define $f(s) = f(t) = 0$ and $f(v) = 1$ for all other $v \in V(G)$. (The values of $f(v_0)$ and $f(v_\infty)$ don't matter; they don't contribute to the average value.)
Then any path $v_1, v_2, \dots, v_n$ has $v_1 = s$ and $v_n = t$ since these are the only vertices adjacent to $v_0$ and $v_\infty$, and so we have $$\frac1n \sum_{i=1}^n f(v_i) = \frac{n-2}{n},$$ which gets closer to $1$ the larger $n$ is. An average value of $\frac{|V(G)|-2}{|V(G)|}$ is only achievable by a path that visits all vertices in $V(G)$: a Hamiltonian path.
If we could find a maximum average path, then we could see if the average value of $\frac{|V(G)|-2}{|V(G)|}$ is achievable, and so we'd know if a Hamiltonian path exists in $G$.
By the way, the Wikipedia article for the Hamiltonian path problem mentions several classes of graphs for which that problem (and therefore also the maximum average path problem) remains NP-complete, and these include planar graphs, so that assumption won't help you.
