# Why is determining the size of a maximum independent set or a clique in P?

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 $\geq 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.

• Where did you read that? I suggest you provide a source for the claim in the first sentence. That claim is wrong, assuming $P \ne NP$, so I suspect you might be misremembering it. – D.W. Feb 27 '14 at 8:03
• The premise is indeed unknown and probably incorrect. I misread the section. – Wuschelbeutel Kartoffelhuhn Feb 27 '14 at 15:30

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 ($\alpha(G)$) in polynomial time, we could answer this decision problem in polynomial time by taking $G$, getting $\alpha(G)$ from our polynomial time algorithm, then if $k \leq \alpha(G)$, we say $Yes$, if $k > \alpha(G)$ we say no. Hence a polynomial time algorithm for determining the maximum would immediately give us $P=NP$.
• is there a polynomial time algorithm when $G$ is actually a comparability graph? I believe that is equivalent to finding the width of a given poset. – seteropere Oct 25 '14 at 23:15