A 5-pointed-star in an undirected graph is a 5-clique. Show that 5-POINTED-STAR $in P$, where 5-POINTED-STAR = ${ <G>$ $: G$ contains a 5-pointed-star as a subgraph $}$.
Where a clique is CLIQUE = ${(G, k) : G$ is an undirected graph $G$ with a $k$-clique $}$. Now my problem is that this appears to be solving the CLIQUE problem, determining whether a graph contains a clique with the additional constraint of having to determine that the CLIQUE forms a 5-pointed star. This seems to involve some geometric calculation based on knowledge of a 5-pointed star. However, in Michael Sipser’s Theory of Computation, pg 268, there is a proof showing that CLIQUE is in $NP$ and on page 270 notes that,
We have presented examples of languages, such as HAMPATH and CLIQUE, that are members of NP but that are not known to be in $P$. [emphasis added]
If CLIQUE is not in $P$, why five pointed star be in $P$? Is there something I’m not seeing? Remember, this is a HOMEWORK PROBLEM and A DIRECT ANSWER WOULD NOT BE APPRECIATED. Thanks!
Asked By : BrotherJack
Answered By : Ran G.
There are ${|V| choose 5}$ possible subsets to check, that is, at most $|V|^5$ options, which is polynomial in the input. This is NOT the case for an arbitrary $k$, since $|V|^k$ might be exponential in the input, and this is why $text{CLIQUE} notin P$ (unless P=NP, agghh.).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1143
