===========================================================================
CSC 363H                Tutorial Notes for Week 12              Summer 2007
===========================================================================

Example 1:  CLIQUE-SEARCH
    Input:  Undirected graph G, positive integer k.
    Output:  A clique of size k in G, if one exists; special value NIL if
    there is no such clique in G.

 -  Idea:  For each vertex in turn, remove it iff resulting graph still
    contains a k-clique.

 -  Details:  Assume we have an algorithm CL(G,k) that returns true iff G
    contains a clique of size k.  We construct an algorithm to solve
    CLIQUE-SEARCH as follows.

    CLS(G,k):
        if not CL(G,k):  return NIL  # no k-clique in G
        for each vertex v in V:
            # remove v and its incident edges
            V' = V - {v};  E' = E - { (u,v) : u in V }
            # check if there is still a k-clique
            if CL(G'=(V',E'),k):
                # v not required for k-clique, leave it out
                V = V';  E = E'
        return V

 -  Correctness:  CL(G=(V,E),k) remains true at every step so at the end,
    V contains every vertex in a k-clique of G.  At the same time, every
    other vertex will be taken out because it is not required, so V will
    contain no other vertex.  Hence, the value returned is a k-clique of G.

 -  Runtime:  Each vertex of G examined once, and one call to CL for each
    one, plus linear amount of additional work (removing edges).  Total is
    O((n+1)*t(n,m) + n*(n+m)) where t(n,m) is runtime of CL on graphs with
    n vertices and m edges; this is polytime if t(n,m) is polytime.

 -  Exercise:  What happens if G contains more than one k-clique?