2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Feb 27 '14 at 8:03
  • $\begingroup$ The premise is indeed unknown and probably incorrect. I misread the section. $\endgroup$ – Wuschelbeutel Kartoffelhuhn Feb 27 '14 at 15:30
4
$\begingroup$

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

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for confirming. I just looked back and realized that I misread the section $\endgroup$ – Wuschelbeutel Kartoffelhuhn Feb 27 '14 at 7:08
  • $\begingroup$ @WuschelbeutelKartoffelhuhn no problem, a very easy mistake to make. $\endgroup$ – Luke Mathieson Feb 27 '14 at 7:26
  • $\begingroup$ 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. $\endgroup$ – seteropere Oct 25 '14 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.