Problem Detail: 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.
Asked By : Wuschelbeutel Kartoffelhuhn
Answered By : Luke Mathieson
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22080 Ask a Question Download Related Notes/Documents
