The optimization version of the Hamiltonian Cycle Partition Problem is to partit
ID: 3770851 • Letter: T
Question
The optimization version of the Hamiltonian Cycle Partition Problem is to partition the edges of a graph into as many Hamiltonian Cycles as possible (with possibly some edges left over).
1. Solve the optimization version of the Hamiltonian Cycle Partition Problem for complete graphs. Your answer should be a function of the number of vertices n. Justify your answers.
1a. For complete, directed graphs. (For n = 0 there are no Hamiltonian cycles. for n = 1, 2 there is one Hamiltonian cycle. For n = 3 there are two Hamiltonian cycles.)
1b. For complete, undirected graphs. (For n = 0, 1, 2 there are no Hamiltonian cycles. For n = 3 there is one Hamiltonian cycle, which is the graph itself.)
2. Show that the decision version of the Hamiltonian Cycle Partition Problem for undirected graphs is in NP.
Explanation / Answer
Hamiltonian Cycle covers all the node of the graph exactly once.
Or
Hamiltonian Cycle is set of consecutive edges which covers all the nodes of a graph completely.
1.
OptimizedHamiltonian(n)
(
If all the neighbours of `n` are visited
return `n`
Partition the set at a mid vertex into L & R
l = OptimizedHamiltonian(nodes in L)
r = OptimizedHamiltonian(nodes in R)
Merge(l,r)
)
1a. Complete Directed Graphs :-
n=3 :: there are two Hamiltonian cycle. A->B->C and C->B->A
1b. Complete Undirected Graphs :-
n=3 :: there is one Hamiltonian cycle. A->B->C
2.
Decision :
Find hamiltonian cycle of weight <= k
The problem of Hamiltonian Cycle can be solved in a Non-Deterministic Machine in polynomial time; i.e, the solution can be guessed. But it is not confirmed that the exact solution will be obtained.
So, decision version is NP.