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)

• Mark Byers: Homework? If so, use the homework tag.
• R. Martinho Fernandes: Is this copy-pasted directly from the homework question? What's your doubt? How far can you go without help?
• Mark Byers: What exactly is your question? Do you have a specific question or do you just want us to send the codez? Also, what language? How far have you got with solving the problem yourself? If you have some non-working code, can you post it and tells us what error you get?
• Alon: if you'll press on the clique-problem tag above, you'll probably get instant help.
• Cristo: In any programming language Mark. Let's say it's some kind of homework. Martinho, some code would give me a huge boost. Thanks. ;)

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.

• Cristo: Thanks very very much Alex. Though, I don't know Python. I am gonna try to make it in C/C++ or Java. Any idea?
• Alex Martelli: @Cristo, should be exactly the same algorithm -- e.g., in C++, use std::set where in the Python code above I use set, use std::map to represent the mappings instead of Python dicts, do combinations e.g. w. code from codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117 , etc. Python is "executable pseudocode", after all, so it shouldn't be hard to understand the above pseudocode and translate it into c++!-) Do ask specific questions if you have trouble understanding any of the above pseudocode, of course.
• Cristo: Thanks a lot Alex. If I have trouble understanding, I'm gonna ask specifically asap. Cheers. ;)

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.

• Cristo: This makes sence. Could you post me the code for "sub-square"?
• Hamish Grubijan: Sorry, Cristo, you are asking for too much.
• Cristo: Edit: What do you mean with sub-square? Mother tongue: not english
• R. Martinho Fernandes: A subsquare is a set of lines and columns from the adjacency matrix. as stated in the answer, they don't need to be adjacent.
• Cristo: Good, thanks a lot folks. One more: How can I generate the different subsquare from the matrix?