1
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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