k-Clique Exists - Participants::Intersection approach 1

Introduction

Much of my graduate study at Northwestern centered upon automated theorem proving using resolution-based algorithms. I've wanted to find an approach to the k-Clique Exists problem that is resonant with and informed by resolution-based automated theorem proving. The closest I've come is what I refer to as the Participants::Intersection approach. I'll begin to discuss this approach in this post and discuss some of the issues that are raised in future posts.

A k-clique is a subgraph induced by a set of nodes P of cardinality k, such that the intersection I of the augmented adjacency sets of the nodes in P is a superset of P. 'P' stands for 'participants' and 'I' stands for 'intersection'.

Resolution-based theorem proving is built upon the idea of a clause; this approach is built upon the idea of a P::I pair of sets - for example, { 3, 7, 8, 11, 15 } :: { 1, 3, 7, 8, 11, 13, 15 }.

A P::I pair consists of a set of participant nodes P and the intersection I of the augmented adjacency sets of the nodes in P. If P is a subset of I, then P is a clique.

Basic operations

We'll build up a collection of P::I pairs in search of a pair for which P is a clique and has cardinality of at least k. Since the goal of this approach is to determine whether a k-clique exists, we will not want to retain a pair whose P is not a clique in the collection.

We'll start out with a list of N P::I pairs, one for each node in the graph. If the augmented adjacency set for node 11 is { 2, 5, 8, 11, 17 }, then the P::I pair from that node is { 13 } :: { 2, 5, 8, 11, 17 }.

There are four basic operations that we'll be concerned with: merger, extension, subsumption, and retention. For a pair X, X.P denotes the P set of X and X.I denotes the I set of X.

We'll merge two pairs X and Y by forming the union of the P sets and the intersection of the I sets, resulting in the pair Z where Z.P = X.P union Y.P and Z.I = X.I intersection Y.I. Pairs X and Y should be merged only if X.P is a subset of Y.I and Y.P is a subset of X.P, otherwise the resulting P set will not be a clique. For example,

   { 1, 3 } :: { 1, 2, 3, 4 } merged with { 2 } :: { 1, 2, 3, 4, 5 } yields { 1, 2, 3 } :: { 1, 2, 3, 4 }

It is possible that, for pair X, nodes not in X.P have augmented adjacency sets that have X.I as a subset. Such nodes can and should be added to X.P. The only nodes that should be examined for addition to X.P are in X.I - X.P. This process will be referred to as 'extension' and it should be performed prior to retention, i.e. prior to adding the pair to the collection. Extension should be performed on all initial pairs and upon every pair that results from merger whose P set is a clique. For example, depending upon the graph,

   { 1, 3 } :: { 0, 1, 2, 3, 4 } might be extended to { 0, 1, 3, 4 } :: { 0, 1, 2, 3, 4 }

Pair X subsumes pair Y if and only if Y.P is a subset of X.P and Y.I is a subset of X.I. For example,

   { 1, 3 } :: { 1, 2, 3, 4 } subsumes { 1 } :: { 1, 2, 3, 4 }

   { 1, 3 } :: { 1, 2, 3, 4 } subsumes { 1, 3 } :: { 1, 2, 3 }

   { 1, 3 } :: { 1, 2, 3, 4 } subsumes { 1 } :: { 1, 2, 3 }

   { 1, 3 } :: { 1, 2, 3, 4 } subsumes { 1, 3 } :: { 1, 2, 3, 4 }

If pair X subsumes pair Y, then Y is a consequence of X, and pair Y can safely be deleted or discarded.

If pair X is in a collection of pairs, pair Y is a newly expanded pair, and X subsumes Y, Y is said to be 'forward subsumed' by X and Y should be discarded.

If pair X is in a collection of pairs, pair Y is a newly expanded pair, and Y subsumes X, X is said to be 'backward subsumed' by Y and X should be deleted from the collection.

Retention is the addition of a P::I pair to the collection. A pair X should be retained if and only if X.P is a clique, X has been extended, and X is not forward subsumed by any pair in the collection.

As pair Y is added to a collection, every pair already in the collection that is backward subsumed by Y should be deleted from the collection.

An example

In this example, we determine whether a graph contains a 9-clique by using the I::P approach. This example was worked out by hand and I already knew that the graph has a 9-clique. Subsumption does not play a signficant role in this example.

Augmented Adjacency Sets for Graph0

0  : { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
13 : { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
14 : { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

add pair for AAS(0)
    extend { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
        no change
    retain { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
        added as pair 0

add pair for AAS(1)
    extend { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        added as pair 1

add pair for AAS(2)
    extend { 2 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
        added 12 to P
    retain { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
        added as pair 2

add pair for AAS(3)
    extend { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
        added as pair 3

add pair for AAS(4)
    extend { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
        no change
    retain { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
        added as pair 4

add pair for AAS(5)
    extend { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
        no change
    retain { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
        added as pair 5

add pair for AAS(6)
    extend { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        added as pair 6

add pair for AAS(7)
    extend { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
        no change
    retain { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
        added as pair 7

add pair for AAS(8)
    extend { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
        no change
    retain { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
        added as pair 8

add pair for AAS(9)
    extend { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
        added as pair 9

add pair for AAS(10)
    extend { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
        no change
    retain { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
        added as pair 10

add pair for AAS(11)
    extend { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
        no change
    retain { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
        added as pair 11

do not add pair for AAS(12) - it would be subsumed by pair 2

add pair for AAS(13)
    extend { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
        added as pair 12

add pair for AAS(14)
    extend { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        no change
    retain { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
        added as pair 13

List of P::I pairs from the Augmented Adjacency Sets of Graph0

0  : { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
13 : { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

merge 2 and 1
    { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
    extend
        no change
    retain { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
        added as pair 14

List of P::I pairs

0  : { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
13 : { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
14 : { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }

merge 14 and 6
    { 1, 2, 6, 12 } :: { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
    extend
        added 11 to P
    retain { 1, 2, 6, 11, 12 } :: { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
        added as pair 15

List of P::I pairs

0  : { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
13 : { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
14 : { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
15 : { 1, 2, 6, 11, 12 } :: { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }

merge 15 and 13
    { 1, 2, 6, 11, 12, 14 } :: { 1, 2, 3, 6, 8, 9, 11, 12, 13, 14 }
    extend
        no change
    retain { 1, 2, 6, 11, 12, 14 } :: { 1, 2, 3, 6, 8, 9, 11, 12, 13, 14 }
        added as pair 16

List of P::I pairs

0  : { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
13 : { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
14 : { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
15 : { 1, 2, 6, 11, 12 } :: { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
16 : { 1, 2, 6, 11, 12, 14 } :: { 1, 2, 3, 6, 8, 9, 11, 12, 13, 14 }

merge 16 and 3
    { 1, 2, 3, 6, 11, 12, 14 } :: { 1, 2, 3, 6, 9, 11, 12, 13, 14 }
    extend
        added 9 and 13 to P
    retain { 1, 2, 3, 6, 9, 11, 12, 13, 14 } :: { 1, 2, 3, 6, 9, 11, 12, 13, 14 }
        added as pair 17

List of P::I pairs

0  : { 0 } :: { 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13 }
1  : { 1 } :: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
2  : { 2, 12 } :: { 0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
3  : { 3 } :: { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14 }
4  : { 4 } :: { 0, 1, 2, 3, 4, 5, 7, 10, 12, 14 }
5  : { 5 } :: { 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
6  : { 6 } :: { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
7  : { 7 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14 }
8  : { 8 } :: { 0, 1, 2, 5, 6, 7, 8, 10, 11, 12, 14 }
9  : { 9 } :: { 1, 2, 3, 5, 6, 9, 10, 11, 12, 13, 14 }
10 : { 10 } :: { 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14 }
11 : { 11 } :: { 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
12 : { 13 } :: { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
13 : { 14 } :: { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
14 : { 1, 2, 12 } :: { 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14 }
15 : { 1, 2, 6, 11, 12 } :: { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14 }
16 : { 1, 2, 6, 11, 12, 14 } :: { 1, 2, 3, 6, 8, 9, 11, 12, 13, 14 }
17 : { 1, 2, 3, 6, 9, 11, 12, 13, 14 } :: { 1, 2, 3, 6, 9, 11, 12, 13, 14 }

a 9-clique exists : { 1, 2, 3, 6, 9, 11, 12, 13, 14 }

Coming up

My next post in this thread will discuss some issues that arise, some similarities to automated theorem proving, and some candidates for heuristics.

All Rights Reserved.