# Finding a 5-Pointed Star in polynomial time

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!

If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?
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.).
• @BrotherJack For example yes, if one can give a polynomial-time algorithm for a problem, it clearly shows that the problem is in $P$. Note that one doesn't even need to go as "low-level" as a Turing machine, a higher-level algorithm will do just as well. – Juho Apr 8 '12 at 21:20