Say you are given an undirected unweighted graph, where s and t are nodes from the graph. d(s,t) means the distance between s and t which outputs the number of edges.

How do I find the the maximum distance between s and t , max{d(s,t)}, where the edges between s and t are minimal? Also, how can this problem can be related/reduced to the hamiltonian problem?

Any advice would be really helpful.


closed as unclear what you're asking by D.W., Juho, David Richerby, Rick Decker, Luke Mathieson Dec 5 '14 at 1:27

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Where does $s$ come from? Please specify your problem more carefully. What is given and what exactly are you looking for? Also, what have you tried and where did you get stuck? $\endgroup$ – Raphael Dec 2 '14 at 18:20
  • $\begingroup$ @Raphael sorry, I will re-define my question as it seems to be confusing. $\endgroup$ – Stella Dec 2 '14 at 18:27
  • $\begingroup$ Do you only consider simple paths? If so, it is certainly related to the hamiltonian path problem: a hamiltonian path exists if for some $s,t$ the maximum distance between $s$ and $t$ is $n-1$. $\endgroup$ – Yuval Filmus Dec 2 '14 at 18:48
  • $\begingroup$ @YuvalFilmus Yes, I am considering simple paths. I am also trying to understand how the shortest-path can be reduced to the hamiltonian-path problem. hamiltonian-path<=shortest-path. $\endgroup$ – Stella Dec 2 '14 at 18:55
  • 1
    $\begingroup$ Sorry, I still can't understand your question. What is given (what are the inputs), and what is the desired output? max{d(s,t)} doesn't make sense if s,t are two given vertices: d(s,t) is a single integer, so why are you taking a max of a set with one element? And why do you think this is related to the Hamiltonian path problem? I think you need to spend more time thinking about this more carefully and figuring out how to explain your problem and articulate it more precisely. $\endgroup$ – D.W. Dec 4 '14 at 1:15

Hint: Given a graph $G$, add two new vertices $s,t$, each connected to all vertices in the original graph. When does there exist a path from $s$ to $t$ of length $n+1$?


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