Question

You are given an undirected graph A. The problem P asks, if there exists a cycle that contains more than half of the nodes in graph A? Is this problem in NP(nondeterministic polynomial time)? How is it related to the Hamiltonian cycle problem?

Construct your example in python.

Input: Graph A as either an edge list or adjacent list.
Output: Yes or No. If the output is yes, display the cycle as a sequence of nodes.

Answer 1

Please give positive ratings for my effort. Thanks.

PROGRAM

from collections import defaultdict 

class Graph: 

        def __init__(self,vert): 
                self.V = vert
                self.graph = defaultdict(list) 

        def addEdge(self,a,b): 
                self.graph[a].append(b) 
                self.graph[b].append(a) 


        def check(self,a,vis,parent): 
                vis[a] = True

                for i in self.graph[a]: 
                        if vis[i]==False : 
                                if(self.check(i,vis,a)): 
                                        return True
                        elif parent!=i: 
                                return True
                
                return False

        def iscycle(self): 
                
                vis =[False]*(self.V) 
                for i in range(self.V): 
                        if vis[i] ==False: 
                                if(self.check(i,vis,-1)) == True: 
                                        return True
                
                return False

test = Graph(5) 
test.addEdge(1, 0) 
test.addEdge(1, 2) 
test.addEdge(2, 0) 
test.addEdge(0, 3) 
test.addEdge(3, 4) 

if test.iscycle(): 
        print ("Given Graph contains cycle")
else : 
        print("Given Graph does not contain cycle ")