14
$\begingroup$

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!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
11
$\begingroup$

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.).

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's what is tripping me up I think. I was under the impression that the CLIQUE problem was worded that way to simply mean that it could apply to any size clique, and that size was given as part of the problem. Whereas in that problem it appears that the CLIQUE size is unknown (yet in the hw one it is 5). Now if I were to construct a deterministic single tape Turing machine which decided an answer to this problem in polynomial time, that would constitute an answer (given the proof is solid of course), yes? $\endgroup$
    – BrotherJack
    Apr 8, 2012 at 20:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – Juho
    Apr 8, 2012 at 21:20
  • $\begingroup$ It may be interesting to relate this effect with parameterised complexity. $\endgroup$
    – Raphael ♦
    Apr 9, 2012 at 10:58
  • 1
    $\begingroup$ I didn't know you could do the spoilers effect. Nice hint. $\endgroup$
    – Joe
    Apr 9, 2012 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.