You have to prove that given a set of vertices, you can check in polynomial time if those vertices form a clique or not. If you have k vertices in a set, all that you have to do is check every pair for the presence of an edge between them in the graph G. These can be done in O(kC2) time = O(k^2)
it look me a while to realize this was not fully english
puri ip university chalane wale sir ko dandwat pranaam..
How did we prove that the clique problem belong to NP ? (before doing the NP-Complete part)
You have to prove that given a set of vertices, you can check in polynomial time if those vertices form a clique or not. If you have k vertices in a set, all that you have to do is check every pair for the presence of an edge between them in the graph G. These can be done in O(kC2) time = O(k^2)
Bahut badhiyan se explain kiya hai.
ha bhai
you have proved it's NP-Hard, not NP-complete!
is a np problem? yes
is a np-hard problem? also, yes
congrats, it IS a np-complete problem.
You earlier said there should not be poly time solver, but in this example you too poly time solver
Sir you are legend
i was concentrating on that pen..LMAO..
Can u give me link of 3 CNF is np complete Problem proof
this is proof for clique is np hard. not np complete
Sir iski plalist kha hai
Bakwaas... Sir, clique problem me hamen K nshi find karana hota hai....
aakhir kaar koi dhang ka explanation