Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 8:03
    
The premise is indeed unknown and probably incorrect. I misread the section. –  Wuschelbeutel Kartoffelhuhn Feb 27 at 15:30

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks for confirming. I just looked back and realized that I misread the section –  Wuschelbeutel Kartoffelhuhn Feb 27 at 7:08
    
@WuschelbeutelKartoffelhuhn no problem, a very easy mistake to make. –  Luke Mathieson Feb 27 at 7:26
    
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 3 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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