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.