algorithm problem

Question

A graph is a subgraph of the graph in which any vertex is connected with the rest of vertexes.

In the k- problem, the input is an undirected graph and a number k, and the output is a clof size k if one exists (or, sometimes, all cl of size k)

Answer 1

Suppose without loss of generality that the graph's nodes are identified by the integers between 0 and N-1 (no loss of generality because if each node needs to carry other information you can have an array / vector / list of the N node objects, and take those integers as being indexes into the array in question). The graph's connectivity may be indicated, for example, with a mapping from each node to a set which is the node's immediate neighbors.

To check connection, rather than immediate adjacency, you'll rather need a different mapping -- the transitive closure of the immediate-neighbors mapping. There are of course good algorithms for that (see for example the Python source code for the networkx package), but a brute-force one would simply start by copying the immediate adjacency mapping to the connection mapping, then iteratively expand the sets until one iteration doesn't expand any set any longer.

E.g., a Python 2.6 brute-force example:

import copy

def transitive_closure(immediate_neighbors):
  result = copy.deepcopy(immediate_neighbors)
  changes = True
  while changes:
    changes = False
    for node in result:
      newset = set(result[node])
      for neighbor in result[node]:
        newset.update(result[neighbor])
      if newset != result[node]:
        changes = True
        result[node] = newset
  return result

immediate = {0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3]}
connections = transitive_closure(immediate)
for node in sorted(connections):
  print node, sorted(connections[node])

prints:

0 [0, 1, 2]
1 [0, 1, 2]
2 [0, 1, 2]
3 [3, 4]
4 [3, 4]

With the connections dictionary at hand, all we have to do is examine every combination of k nodes (for example, in Python 2.6 or better, itertools.combinations(range(N), k) gives us those combinations): it's going to be a clique if it's a subset (not necessarily a proper subset of course) of the set of items connected to any one of its members.

So for example the above code could continue, to show all 2-cliques:

import itertools
cliques = set()
for somenodes in itertools.combinations(range(5), 2):
  if set(somenodes) <= connections[somenodes[0]]:
    cliques.add(somenodes)
print '%d cliques:' % len(cliques)
for c in sorted(cliques): print ' ', c

which prints, with the data used in the previous example:

4 cliques:
  (0, 1)
  (0, 2)
  (1, 2)
  (3, 4)

For non-brute force approaches, I recommend again studying the networkx source code to which I pointed earlier.

Answer 2

Ok, number vertices 1 ... n and convert the graph to a boolean adjacency matrix - 1 at (i,j) meaning that i and j are connected. In an undirected graph the matrix should be symmetric. Now your task reduces to finding a "sub-square" of size k x k with all 1s. A "sub-square" is funny in that rows and column need not be adjacent to each other. To get some sub-square, you start with n rows, n column, eliminate (n-k) of rows and columns - and voila! you got it.

Now, every unique sub-square of all 1s will correspond to a clique. To check for uniqueness, represent the subsquare as an immutable tuple ((i1,j1), (i2, j2) ... (ik,jk)) (Python notation).

In Python you can add tuples to an unordered set, and ask the set if it already contains an element that we seek.