patternModerate
Finding a 5-Pointed Star in polynomial time
Viewed 0 times
pointedstarpolynomialtimefinding
Problem
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$ 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!
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$ 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!
Solution
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.).
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.).
Context
StackExchange Computer Science Q#1143, answer score: 11
Revisions (0)
No revisions yet.