title: Clique problem algorithm design
body: <p>One of the assignments in my algorithms class is to design an exhaustive search algorithm to solve the clique problem.  That is, given a graph of size <em>n</em>, the algorithm is supposed to determine if there is a complete sub-graph of size <em>k</em>.  I think I've gotten the answer, but I can't help but think it could be improved.  Here's what I have:</p>
  
  <h1>Version 1</h1>
  
  <p><strong>input</strong>:  A graph represented by an array A[0,...<em>n</em>-1], the size <em>k</em> of the subgraph to find.</p>
  
  <p><strong>output</strong>:  True if a subgraph exists, False otherwise</p>
  
  <p><strong>Algorithm</strong> (in python-like pseudocode):</p>
  
  <pre><code>def clique(A, k):
      P = A x A x A //Cartesian product
      for tuple in P:
          if connected(tuple):
              return true
      return false
  
  def connected(tuple):
      unconnected = tuple
      for vertex in tuple:
          for test_vertex in unconnected:
              if vertex is linked to test_vertex:
                  remove test_vertex from unconnected
      if unconnected is empty:
          return true
      else:
          return false
  </code></pre>
  
  <h1>Version 2</h1>
  
  <p><strong>input</strong>:  An adjacency matrix of size n by n, and k the size of the subgraph to find</p>
  
  <p><strong>output</strong>:  All complete subgraphs in A of size k.</p>
  
  <p><strong>Algorithm</strong> (this time in functional/Python pseudocode):</p>
  
  <pre><code>//Base case:  return all vertices in a list since each
  //one is a 1-clique
  def clique(A, 1):
      S = new list
      for i in range(0 to n-1):
          add i to S
      return S
  
  //Get a tuple representing all the cliques where
  //k = k - 1, then find any cliques for k
  def clique(A,k):
      C = clique(A, k-1)
      S = new list
      for tuple in C:
          for i in range(0 to n-1):
              //make sure the ith vertex is linked to each
              //vertex in tuple
              for j in tuple:
                  if A[i,j] != 1:
                      break
              //This means that vertex i makes a clique
              if j is the last element:
                  newtuple = (i | tuple) //make a new tuple with i added
                  add newtuple to S
      //Return the list of k-cliques
      return S
  </code></pre>
  
  <p>Does anybody have any thoughts, comments, or suggestions?  This includes bugs I might have missed as well as ways to make this more readable (I'm not used to using much pseudocode).</p>
  
  <h1>Version 3</h1>
  
  <p>Fortunately, I talked to my professor before submitting the assignment.  When I showed him the pseudo-code I had written, he smiled and told me that I did <em>way</em> too much work.  For one, I didn't have to submit pseudo-code; I just had to demonstrate that I understood the problem.  And two, he <em>was</em> wanting the brute force solution.  So what I turned in looked something like this:</p>
  
  <p><strong>input</strong>:  A graph G = (V,E), the size of the clique to find <em>k</em></p>
  
  <p><strong>output</strong>:  True if a clique does exist, false otherwise</p>
  
  <p><strong>Algorithm</strong>:</p>
  
  <ol>
  <li>Find the Cartesian Product V<sup>k</sup>.</li>
  <li>For each tuple in the result, test whether each vertex is connected to every other.  If all are connected, return true and exit.</li>
  <li>Return false and exit.</li>
  </ol>
  
  <p><strong>UPDATE</strong>:  Added second version.  I think this is getting better although I haven't added any fancy dynamic programming (that I know of).</p>
  
  <p><strong>UPDATE 2</strong>:  Added some more commenting and documentation to make version 2 more readable.  This will probably be the version I turn in today.  Thanks for everyone's help!  I wish I could accept more than one answer, but I accepted the answer by the person that's helped me out the most.  I'll let you guys know what my professor thinks.</p>