$st$-path with fewest leaving edges

Given an undirected unweighted multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized.

Does anybody have any idea how to solve this? I first thought about replacing edges by two arcs and weight them according to some node degrees but the edges staying in $P$ make life difficult.

• Do you mean simple path, i.e., every vertex used once? Otherwise additional loops might be favorable. Commented Mar 6, 2013 at 23:55
• @Hendrik Jan, yes simple otherwise $G$ it self would indeed be an optimal solution. Commented Mar 7, 2013 at 1:35

Suppose input graph is simple (without parallel edges), now, If you solve your problem, you can check existence of Hamiltonian path, actually if s-t path of cost zero for some pair exists means there is Hamiltonian path and you can check this for all pair of vertices as (s,t), so you are unlucky to have polynomial time algorithm except $P=NP$.