NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs

2008/09/15 by Panda, B. S., Pradhan, D.
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0809.2443

Abstract

The Hamiltonian cycle problem is to decide whether a given graph has a Hamiltonian cycle. Bertossi and Bonuccelli (1986, Information Processing Letters, 23, 195-200) proved that the Hamiltonian Cycle Problem is NP-Complete even for undirected path graphs and left the Hamiltonian cycle problem open for directed path graphs. Narasimhan (1989, Information Processing Letters, 32, 167-170) proved that the Hamiltonian Cycle Problem is NP-Complete even for directed path graphs and left the Hamiltonian cycle problem open for rooted directed path graphs. In this paper we resolve this open problem by proving that the Hamiltonian Cycle Problem is also NP-Complete for rooted directed path graphs.

Related

• Hamiltonian Cycle Problem is in P
• On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path
• Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
• The Complexity of Determining Existence a Hamiltonian Cycle is O(n³)
• Polynomial solvability of NP-complete problems