Graph Topology

  
Figure: Partitioning a Square.

One of the most interesting aspects of this work is the topological view it gives to problem spaces. The dimension of a problem becomes very important when determining its complexity. The last three columns of Figure 11 give the complexity information for problems of three different dimension: a one dimensional tree, a two dimensional square, and a three dimensional cube. The maximum input complexity of these problems in terms of the number of vertices, n, is (at worst):

• a constant for the tree. Any tree can be partitioned with a maximum input complexity of 2 (our simplified subgraph creation algorithm uses 3). A 1000 node binary tree would still have a maximum input complexity of 2. Furthermore, any tree of arbitrary branching factor can be partitioned such that it will have a maximum input complexity of 2.
• approximately +1 for squares.
• approximately +1 for cubes.
• approximately +1 for perfect 4-dimensional problems, etc..

To understand why this is true, refer to Figure 13 . This Figure shows a very simple way to partition a square for input to HG (The subgraph creation algorithm above actually does a much better job, reducing the number of subgraphs with maximum input complexity of 5 to a minimum.). The first step is to create a subgraph using all of the vertices in the top row. This has input complexity 4 and output complexity 4. The next subgraph will be a combination of that subgraph and the first vertex in the second row. The input complexity of this subgraph is 5 (the output complexity of the last subgraph plus one vertex), and the output complexity is 4, because the top-left-hand vertex no longer has an edge outside this subgraph. Subgraph creation continues, adding one vertex each time while maintaining a maximum input complexity of 5, until the entire graph is covered.

Thus, to solve this problem, HG will require complexity proportional to O(). In essence, the problem was reduced to a 4-by-4 square with exhaustive complexity of 16 to a ``line'' of length 4 (plus a constant 1). A 100-by-100 square would be reduced to a line of length 10. The input complexity is the square root of the number of vertices. There will be (n-) such subgraphs giving a total HG complexity of (n-)* (for this simplified method; our results are better).

Cubes perform similarly. The first step in the decomposition of a 3-by-3-by-3 cube is to make a subgraph of the first 3-by-3 square, giving an input complexity of 9. Then larger subgraphs can be constructed by adding a single vertex. The input complexity of a x-by-x-by-x cube is x-by-x (plus a constant 1), or , since n=. There will be (n-) of these subgraphs (for this simplified method), yielding a total complexity of (n-)*.

  
Figure: Topology of a Tree.

Trees are basically one-dimensional objects, as shown in Figure 14 . By starting at the ends, subgraphs can always be created by joining a leaf with its parent, giving an input complexity of 2 and output complexity 1. At each branching point, these subgraphs can be combined one at a time, each time with input complexity 2 and output complexity 1. This continues from the endpoints in until the whole graph is covered. There will be n-1 such subgraphs, giving the HG complexity for any tree to be (n-1)*.

  
Figure: Graph Topology.

Figure 15 summarizes these results. HG can be seen as a process that ``squeezes'' down the dimensionality of a problem. Trees are squeezed into a point, squares into a line and cubes into a square.

  
Figure: Problem Instance Topology.

Typically, real problems do not present as perfect trees, squares or cubes (or higher-dimensional objects). Natural language semantic analysis, for instance, is tree-shaped for the most part with scattered two-dimensional portions (see below for more details). Figure 16 represents a problem with one, two and three dimensional aspects. Using HG's ``window'', we can reduce the complexity to zero, one and two dimensions. Unless they are very small, the overall complexity, even with HG, will be dominated by the higher dimensional subproblems. This suggests the following approach to generalized problem solving:

• Analyze the problem topology.
• Solve higher dimensional portions heuristically.
• Use HG to combine the heuristic answers for the higher dimensionality portions with the rest of the problem. This relegates possibly non-optimal heuristic processing only to the most difficult sections of the problem, while allowing efficient, yet optimal, processing of the rest.

  
Figure: A New Measure of Complexity.

This discussion raises the possibility of a new measure of complexity that might be useful. Theoretically, the exponents 0, 1/2 and 2/3 for the tree, square and cube, up to 1 for a clique, would be good measures. Unfortunately, these are hard to calculate for problems with different dimensionalities. An easy alternative measure would be to take the ratio of maximum input complexity to total number of vertices. The subgraph creation algorithm described above can be used to quickly give an estimate of this quotient. Figure 17 displays this complexity for the problems discussed in this paper.