I read that determining the size of the maximum independent set (and also a cliq
ID: 653463 • Letter: I
Question
I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard.
With respect to finding clique size, you can sort the node degrees, decrement i from |V| to 0, and each time check if you have i elements of node degree i, pick the power set of those ?i elements and verify the clique. However, picking the power set is exponential, and this algorithm would give you the solution itself. I have a hard time figuring out how you can construct an algorithm that decides the presence of a clique (or independent set) of a certain size in polytime, but doesn't give you the solution.
Explanation / Answer
I would be interested to see what you read, but determining the size of the maximum independent set is NP-hard (of course clique is equivalent, so I'll just talk about independent set). Recall that the decision problem "Does the graph G contain an indepedent set of size at least k?" is NP-complete. If we could determine the size of the maximum independent set (?(G)) in polynomial time, we could answer this decision problem in polynomial time by taking G, getting ?(G) from our polynomial time algorithm, then if k??(G), we say Yes, if k>?(G) we say no. Hence a polynomial time algorithm for determining the maximum would immediately give us P=NP.
Perhaps you read that determining the size of a maximal independent set is poynomial time solvable. A maximal set is just one that cannot be made larger, so we can (typically, and certainly for independent sets) compute these greedily.