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.

  • $\begingroup$ Do you mean simple path, i.e., every vertex used once? Otherwise additional loops might be favorable. $\endgroup$ – Hendrik Jan Mar 6 '13 at 23:55
  • $\begingroup$ @Hendrik Jan, yes simple otherwise $G$ it self would indeed be an optimal solution. $\endgroup$ – user695652 Mar 7 '13 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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