Showing a problem is NP complete? Reducing CLIQUE to KITE.

Question

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc.

The problem is, there doesn't seem to be anyone available in my department to help me until after the test. I really struggle to understand it and get confused all too often when looking at it. So I was wondering if my wonderful chums of the internet could work through a problem with me! (Problem is below if you wanna skip my waffle) I apologise if there is an awful lot of it, I hope this will be useful for me or future lurkers though. Feel free to only answer part of it.

I get that $X \leq_p Y$ means that given an oracle for Y, we can solve X using a polynomial number of standard computational operations plus a polynomial number of calls to that oracle for Y. I also get that to show a problem Y is NP complete we show:

There exists a polynomial time certifier for problem Y.

We give a reduction $X \leq_p Y$ from a known NP problem X. Ie: Showing that X is no harder than Y.

But in practise, I really struggle to do both of these things. It all seems a bit hand wavy at times and the slides used by my course don't really help me, they seem to be used all over the place, here's a copy: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf

So, I thought we'd look at a problem that was included on an earlier test for my own module.

Given that CLIQUE is NP-complete, show that KITE is NP-complete

The CLIQUE decision problem is given a graph G and integer k; decide whether there is an induced complete subgraph of size k. The KITE decision problem is to decide whether there is a kite subgraph of size 2k, which consists of a clique of size k with a k-size tail.

Creating the certifier

So, how exactly should I write a certifier for KITE? I don't really understand what my certificates should be to be honest. I assume I want an input graph $G=(V,E)$ and then maybe a graph $H=(V',E')$ with an integer $k$ such that $H$ is a kite of $2k$. And then check if G contains H as an induced subgraph? But that seems way too easy considering it was worth 20% of the example paper.

algo kiteCertifier(Graph G, Graph H, int k) {
  for each v in V'
    if v not in V
      return no

   for each (u,v) in E'
      if (u,v) not in E
          return no

   return yes
}

I suppose what really confuses me is that I don't get how to pick a certificate for problems, perhaps I don't really get what a certificate is or what a certifier should actually be doing.

Showing $CLIQUE \leq_p KITE$

This is where I often get confused I think. I've seen different reduction examples showing an implication in one direction, then the other, and many just show iff.

Again, it can't just be as simple as saying every kite has a clique in it can it? That's almost axiomic! I wondered if perhaps I should show a graph contains a clique iff it contains a kite.

Given a clique C of size $2k$ or $2k+1$ (i.e.: odd or even clique) we show there always exists a kite of size $2k$ within it. Consider any k nodes $\{v_1,v_2,...,v_k\}$ in the clique. These nodes also form a clique because every node v in the clique is connected to every other node w by an edge. Now consider the nodes $\{v_{k+1},v_{k+2},...,v_{2k}\}$. Each node $v_j$ in this set is connected by an edge to $v_{j+1}$ since C is a clique. We also have that $v_k$ is connected to $v_{k+1}$ and so we now have a kite of size 2k.

Now suppose we have a kite of size 2k, by definition, it contains a clique of size k.

But again, I really don't feel confident enough on this, am I even doing anything vaguely correct? :p Any help would be greatly appreciated.

Thanks very much!

Answer 1

With regards to the reduction, you need to show that given an oracle for Kite, you can solve Clique in polynomial time. It doesn't really help that every Kite has a Clique in it: we're interested in solving Clique, but a graph that has a Clique doesn't necessarily have a Kite (if it has a Kite, then it certainly has a Clique - but that's not enough). You need to modify the graph so that if(f) it has a Clique, then it also has a Kite and pass that modified graph as an input to the oracle.

We don't ordinarily believe that an NP-complete problem can be solved in polynomial time. The point of a verifier/certifiate is that with help, we can solve it in polynomial time. The certificate is the "help", and you can define the certificate to be almost anything you like. For instance, for Clique, we can ask that the certificate be a list of the vertices that make up the Clique. Verifying then becomes easy: we can check we've indeed been given $k$ vertices, and that there are edges between all of these vertices. If you like, you can think of the certificate as a solution to the problem, and the verifier's job is to check that the solution is correct.