0 votes 0 votes All the places where I have read the Ham-Cycle problem, the graph used is directed. Is the problem of finding Ham-Cycle on an undirected graph also NP-Complete or not? Graph Theory graph-theory hamiltonian-cycle p-np-npc-nph + – gmrishikumar asked Nov 30, 2018 • recategorized Jul 6, 2022 by Lakshman Bhaiya gmrishikumar 876 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply kumar.dilip commented Nov 30, 2018 reply Follow Share directed or undirected graph, It is NP-complete. 0 votes 0 votes gmrishikumar commented Nov 30, 2018 reply Follow Share Got it. 0 votes 0 votes Please log in or register to add a comment.
Best answer 0 votes 0 votes Got it. Both problems are stated differently, but both are NP-Complete. The mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. Source: https://en.wikipedia.org/wiki/Hamiltonian_path_problem gmrishikumar answered Nov 30, 2018 • edited Dec 1, 2018 by gmrishikumar gmrishikumar comment Share Follow See all 0 reply Please log in or register to add a comment.
