Progress in Random Graphs and its Application to NP Complete Problems

Abstract. Most NP- Complete problems have linear solutions when restricted to random graphs [2]. Random graph models provide probabilistic setting for studying such problems. Finding a Hamiltonian cycle in a graph is a NP- hard problem. In this paper, we give a polynomial time solution by suitably selecting random graphs, even though it may be hard to solve in general