Seven rules for reducing the text of D or resolving whether a k-clique exists have been mentioned. In order to progress beyond this point, we need to consider the adjacency relationships between the nodes of H. Rules for text reduction and resolution will be discussed at length.

The following is a sketch of the KCliqueExistsSearch algorithm:

This algorithm has three major parameter algorithms:

My current algorithm for ConstructMap will be presented later - it is lengthy and complex. It is quite effective but can most certainly can be improved upon.

I have been investigating several algorithms for text reduction. One of these, TightenText, will be presented in this paper as a stand-in for ReduceText. Many rules that may be used in the design of text-reduction algorithms will also be presented. The design of algorithms for text reduction will be a very fruitful area of research.

A fairly straightforward SearchForKClique algorithm will be presented.

The KCliqueExistsSearch algorithm shows promise as a framework in which to design algorithms for solving the k-Clique Exists problem. Further investigation of this framework and the design of improved algorithms for its parameters are among my active research interests.

Search space construction

The search space of algorithm SearchForKClique

While we could treat the directed acyclic graph D as the search space through which SearchForKClique searches for a k-clique, it is rather coarse - D can only be reduced by the elimination of a directed edge or a node. D doesn't represent everything that we may know about which nodes of D can occupy which positions in a search sequence of D.

Constructing the text of D, reducing it rather than D, and treating the reduced text of D as the search space for SearchForKClique is both more effective and more efficient than working with D directly. The text of D can reduced to reflect the deletion of a directed edge of D and the deletion of a node of D, but it can also be reduced by the deletion of a cell-edge and the deletion of a cell (by marking it as Impossible).

Reduction of the search space by relabelling nodes

A directed edge from X to Y is a transition of length (Y-X). Each search sequence of D contains (k-1) transitions having a combined length of less than N. In general, the longer a transition, the fewer search sequences of D contain it. Some transitions are too long to participate in any search sequence of D.

The more short transitions that can be 'occupied' by a non-edge of D, the fewer the number of search sequences that D will have.

The construction of the map M from V(G) onto V(H) is a valuable opportunity to reduce the number of search sequences of D. The major goal of map construction is maximize the number of short transitions, especially transitions of length 1, that are occupied by the non-edges of D and thereby forbidden to the edges of D. The algorithm ConstructMap is one of the parameters of this algorithm.

The adjacency set of node X of G is the set of all nodes in G that have an edge with X and is denoted by AS(X) The augmented adjacency set of a node X in G consists of AS(X) ? {X}, and is denoted by AAS(X).

A node X of G is complete iff |AAS(X)| = N.

One requirement that we will place on ConstructMap is that, if there are P complete nodes in G, the map that it constructs will map the labels of all of the complete nodes of G onto the nodes labelled 0 .. P-1 in H.

Constructing a map that reduces the search space

My current algorithm for constructing M does so in two phases. The following is an example summary of its operation on a randomly generated graph (N = 50, k = 27, edgeProbability = 0.96):

            Number of transitions occupied by non-edges

Transition              After       After
Length      Originally  Phase 1     Phase 2

   1          2          26          32
   2          1           1           1
   3          3           2           3
   4          1           3           1
   5          4           2           2
   6          3           1           2
   7          1           2           1
   8          3           1	
   9          5           1           2
  10          2           2	
  11                      2	
  12          2           2           1
  13                      1	
  14          3           1           1
  15			    	
  16          2   	
  17          1           1           2
  18          2
  19
  20          2                       1
  21          1           1	
  22          3		
  23					
  24                      2	
  25          4           1	
  26					
  27                                  1
  28          3           1           1
  29          1           1           2
  30                                  1
  31					
  32          1           1	
  33          1		
  34                      1           1
  35                                  1
  36				
  37          1	
  38				
  39          1	
  40          2	
  41				
  42          1	

This algorithm is quite effective at constructing a map that minimizes the number of 1-transitions that are occupied by edges of H, which is all that it attempts.

It is worth noting that the relative unavailability of 1-transitions to edges that results from the construction and application of map M is responsible for the efficacy of the constraint-propagation algorithm at carving away at the edges of the Possible text, resulting in much steeper top and bottom edges. This can be seen in the following pair of images:

    (Random graph: N = 50, k = 30, edgeProbability = 0.96)

After Initialization	After constraint propagation

To be continued...

          Next in thread

Two Identities from the Structure of the N-th Power of Integers

Twenty-five years ago I was captured by Fermat's Last Theorem and spent a lot of time exploring the levels of differences between n-th powers of integers.

Several identities came out of this exploration, two of which I found very suggestive as a pair. I hoped that they would provide constraints that would make a proof of Fermat's Last Theorem approachable, but I didn't know how to use them in that way. Nonetheless, I think they are beautiful.