[Solved]: Finding a 5-Pointed Star in polynomial time

Problem Detail: 

I want to establish that this is part of my homework for a course I am currently taking. I am looking for some assistance in proceeding, NOT AN ANSWER.

This is the question in question:

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.

If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?

If there is a 5-clique, one of this subsets is a clique.

Spoilers below:

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