If you want to give the clique tool a quick spin, copy and paste the data below left into the text area at the top, press the LOAD/RELOAD MATRIX button, change the TARGET CLIQUE SIZE to 6, and then press the OBTAIN CLIQUE button. The result will appear in the text areas at the bottom.

Adjacency Lists can be input as an alternative to adjacency matrices. This file (graph13.txt) is the equivalent of the matrix above. The standard form of the list has an entry for every 1 in the matrix. However, the input procedure sets a pair of ones in the the matrix for every entry so one entry per pair (an edge viewed from either vertex) is sufficient. Note that the first line states the number of vertices.

If you use the matrix form of input, the applet displays the loaded data as an adjacency list. This is to help you check the results. If the graph contains more than 100 vertices it doesn't display the list. This is because my output routine is too slow.

There are just 1716 combinations of 6 out of 13. Two of these are the cliques we want. It wouldn't be too difficult to do this without using a computer, especially with the help the diagram. But, there's enough here to get some feel for how the applet performs. Just keep pressing the obtain button. The applet finds one or the other of the 2 cliques, taking a different path each time.

If we are looking for clique of size 6 in a 100-vector graph, the number of combinations is around a billion. This is still a small enough number to contemplate examining all combinations. Most PCs today would take less than 15 minutes to do that. If we're looking for a size 7 clique, then we're up to 16 billion. That's around 4 hours processing. By the time we get to clique size 10 we have 200 days of processing. Beyond that, it really takes off! This is assuming that there's only 1 clique, and it turns up right at the end of the search. The number of cliques there are to find, depends on the degree of connectivity. The more there are, the easier they are to find.

Does anyone really care about this stuff?

Here's a file (plantedcliques.txt) that contains an adjacency matrix for a thinly connected graph of 100 vertices. The graph has too few edges for it to be likely to have cliques above size 3. I've planted a clique size 6, and a clique size 7. You can see them in the bottom right-hand corner. Don't worry, the applet's random processing doesn't see them like that. The matrix is, anyway, shuffled before the search begins. This is not a conjurer's ploy. It's done so that the random procedure has a different starting position each time. With my original music tape application I found that although the selection was generally random, now and again the selection would include a clump of tracks from the start of the library. You'll find that the applet has no problem obtaining the single clique 7. Note also that it doesn't get stuck in the local minimum associated with the clique 6. If you specify a clique 6 it will find a number of them. You'll see this if you keep pressing the obtain button.

As an example of the sort of problem that lies behind the million dollar PvsNP question, the Clay Institute describes the 400-student accommodation problem. It's not entirely clear whether the accomodation is 50 double units, or 100 single units. With the 50 doubles, the dean's list would need to contain all but a few hundred of the 79800 possible pairings before it became difficult, so the latter interpretation is probably the correct one. If so, then the problem is to extract a clique of size 100 from a graph of 400 vertices. The vertices are the students, and the edges indicate pairs that get along ok. The missing edges constitute the deans list.

Here are some files that contain 400-vertex matrices for different degrees of random connectivity. We're talking of a uniform spread here. No social misfits, nor ready-banded centuriae allowed. The crunch point seems to be when the 400 students have an average of more than 16 fellow students that they can't get along with. The antipathy is mutual. So, if the dean's list has more than 3200 unique pairings on it, he has a problem looming. That's 1 in 25....Thinking about my old classroom of 27, it's not so unrealistic. Life imitates maths?

These are all 313 KB txt files:

Dean's List of 3800 pairs
Dean's List of 3400 pairs
Dean's List of 3200 pairs
Dean's List of 2800 pairs
Dean's List of 1800 pairs
Dean's List of 800 pairs

If you click on Dean's List of 3200 pairs, the text file should open in a new window. Copy and paste it into the input text area, set iterations to 1 million, and clique size to 100, and press the obtain button. There's a good chance it will find one of the (I don't know how many) clique size 100's before a million iterations have completed. If not, press the obtain button again. If it still doesn't come up, press it again. It shouldn't take long.

Move on then to the list of 3400 pairs. I don't think it will find a clique of 100 there. I don't think there is one. If I was able to say with certainty that there is not, I'd probably be on the rich list.

The thing I like about this problem is that it simply demonstrates the difficulty that makes the PvsNP question a million dollar one. You don't get distracted as you might with the subset sum problem and the size of its integers. Such questions may be relevant to the problems themselves...but not, I think, to their NP-completeness.

This tool won't provide you with worst case answers (unless you're very lucky), but hopefully it will provide you with cliques enough for your everyday problems.

DISCLAIMER: It's not as easy to check the results of a clique problem. as it is with, say, a subset sum problem. Nonetheless, if you intend to use the results for any serious purpose, it's up to you to verify them. I don't want the dean onto me because he's got with Minnie The Minx and Paranoid Pete cooped up together, or you because you put your money on the wrong filly.