Cycles on graphs

Alessandro · Post by **Alessandro** » Mon Aug 09, 2004 9:44 pm

I propose you a problem about cycles on graphs.

Given an undirected unweighted graph and two nodes A and B, I've got to find a path from A to B and then a path from B to A. I can't visit a node more than once (with the exception of node A, that must be visited at the beginning and at the end). I have to determine the maximum number of nodes that can be visited with such paths.

In other words, I have to find a cycle that contains A and B and touches the maximum number of nodes.

Any hint?

Ciao
Alessandro

Larry · Post by **Larry** » Mon Aug 09, 2004 10:32 pm

You can reduce Hamiltonian cycle to this. (Is there a cycle in which max = N?)

Therefore, it's NP-complete.

Alessandro · Post by **Alessandro** » Tue Aug 10, 2004 12:48 am

Oh, yes... For my high school final exam I presented a work about NP-completeness, and now I remember Hamiltonian cycle is NP-complete of course!

F**k (the problem, not you Larry

)