Exploiting Graph Topology for Optimization Problems

  
Figure 50: 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 49 gave the complexity information for problems of three different dimensions: 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 50. 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 from 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 51: Topology of a Tree.

Trees are basically one-dimensional objects, as shown in Figure 51. 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 52: Graph Topology.

Figure 52 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 53: 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. Figure 53 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 (if their input complexity is prohibitive).
• 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.

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 use the maximum-input-complexity. This gives a direct indication of how long it will take to solve a given problem. Functions are available that can determine this measure quickly. In addition, the topology of a problem can be analyzed using this complexity measure, with the most difficult subsections identified. Sections with maximum-input-complexity over a given value can be treated with heuristic search methods.