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!