Figure 45: Graph Coloring Example
Graph coloring is an interesting application to look at for several reasons. First, it is in the class of problems known as NP-Complete, even for planar graphs (see for example, (Even, 1979)). In addition, a large number of practical problems can be formulated in terms of coloring a graph, including many scheduling problems (Gondran & Minoux, 1984). Quite a bit of research has been extended in this area, including the well-known theorem that every planar graph can be 4-colored (Appel & Haken, 1976). Finally, it is quite easy to make up a large range of problems, from simple to complex, single dimensional to multi-dimensional.
Figure 45 is a simple variant (with solution) of the
first graph coloring problem in the introduction: find a graph
coloring that uses four colors such that red is used as often as
possible. It should be noted that even this ``simple'' problem produces
exhaustive combinations, or over 4 million.
Figure 46: HG Subgraph Processing
Figure 47: Subgraph A Processing
Figure 46 shows the list of input subgraphs given to SS-HG and follows the processing. The subgraphs input to SS-HG along with their composition are given in the first three columns. The vertices covered by the subgraph are in column 4. The vertices constrained outside of the subgraph are listed in column 5, and the input and output complexities of processing are given in the last two columns. Figure 47 shows steps 1, 2 and 3 for subgraph A.
The most important column in Figure 46
is the input complexity. The largest value
in this column, 5 for subgraph E, defines the complexity for the whole
problem. Because there is only one subgraph with the maximum input
complexity, this problem will be solved in time proportional
to 1 * 
, where 4 is the number of values possible for each
vertex (red, yellow, green and blue), and 5 is the maximum input
complexity. This complexity compares very favorably to an exhaustive
search, and to other types of algorithms, as shown below.
It must be noted again that the partitioning algorithm presented
earlier
is not guaranteed
to give the optimal set of subgraphs. It is designed to give
near-optimal results quickly (near optimal with respect to
the eventual complexity of SS-HG. SS-HG is guaranteed to give the
optimal result no matter what the subgraphs are, as long as they
legally combine to cover the whole input problem). In this example,
if subgraph E had added only vertices 8 and 9, it would have had input
complexity 4 and output complexity 3. We could have then created an
intermediate subgraph to which vertex 11 was added to E, with an input
complexity of 4 and an output complexity of 3, from which the final
subgraph
could be created by adding vertex 10, with an input complexity of 4.
In that case, the maximum input complexity would be 4.
Since there would be 5 subgraphs with that complexity, the total complexity
would be to 5 * 
, which happens to be
greater than the complexity of the solution actually used. The fact that it
turns out like that in this case is irrelevant; the algorithm for
creating the input subgraphs can lead to slightly higher
complexities than theoretically possible. This tradeoff was chosen to
simplify the subgraph creation (which is not the focus of this
research), ensuring that the subgraph creation complexity doesn't
overwhelm the complexity of SS-HG, yet still providing SS-HG with
reasonable inputs.
Figure 48: HG Processing Results
It is interesting to experiment with SS-HG using several different-sized (and different dimensionality - see below) problems and compare the results to other approaches. Figure 48 presents the results of such experiments. Six different problems are solved. The last two, the 100-tree and the 36-square, are included in anticipation of the discussion below on graph topology. Each of the six problems are run (when possible) using four different algorithms:
A number of comments are in order. The numbers given in the graph represent the number of intermediate combinations produced by the algorithms. This measure is consistent with that used by Tsang and Foster (1990) when they report that their algorithm outperforms several others, including backtracking, full and partial lookahead and forward checking. ``DNF'' is listed for those instances when the program was not able to run to completion because of memory limitations (more than 100MB were available).
The first fact, although obvious, is worth stating. HG was able to process all of the problems. This, in itself, is a significant step forward, as problems of such complexity have been intractable up until now. HG performed significantly better than Tsang's algorithm for every problem considered. Especially noteworthy is the 100-tree problem (a binary tree with 100 nodes). HG's branch-and-bound optimization rendered this problem (as all trees) simple, while Tsang's technique was unable to solve it.
Comparing HG without constraint satisfaction to HG without branch-and-bound is significant. Removing constraint satisfaction degrades performance fairly severely, especially in the higher complexity problems. Disabling branch-and-bound, though, has a much worse effect. Problem complexity soars without branch-and-bound. This confirms that our approach, aimed at optimization rather than constraints, is effective.
HG without branch-and-bound is very similar to previous solution synthesis algorithms, including Tsang. Tsang (as well as Freuder (1978)) require a linear ordering of vertices which are then combined into two-vertex solutions, then three, etc.. HG, on the other hand, uses the subgraphs to guide the synthesis process, an extension to the minimal bandwidth ordering principle used by Tsang. We expected this extension to benefit even without branch-and-bound, and our expectations were confirmed. Tsang's algorithm outperformed HG without branch-and-bound only for the simplest problem, for which an MBO ordering turned out to be a superior way to partition the problem. When the number of vertices was raised even a small amount, the subgraph approach became better. We therefore propose that a subgraph decomposition approach such as used in HG is superior to any linear ordering approach, such as used by Tsang or Freuder.
Figure 49: Actual vs. Predicted Complexity
We can also compare the actual performance of these algorithms with the predicted behavior. Figure 49 shows the actual number of combinations built by HG without constraint satisfaction. Obviously the actual behavior aligns closely with the complexity predicted by max-input-complexity, as described above. The relatively small differences are due almost entirely to subgraphs with input complexity one less than the maximum input complexity. For example, the 83 vertex problem had 34 subgraphs with input complexity of 7. If added to the combinations for only subgraphs of input complexity 8, the total is within 3% of the actual total. Programs are available that can give the exact number of combinations that will be required (without constraint satisfaction) for any problem.
We have added a seventh problem to the chart in Figure 49 - a cube with 64 vertices. The subgraph construction algorithm described below was able to suggest input subgraphs with a maximum input complexity of 15. The HG algorithm was unable to solve this problem, since over a billion combinations would need to be computed (and stored). This underlines the point that, although HG can substantially reduce complexity, higher dimensional problems are still intractable. Nevertheless, we expect that many practical problems will become solvable using these techniques. Furthermore, we can easily estimate a problem's dimensionality, as discussed in section 9.4. This can lead us to a new measure of complexity which can be used evaluate problems before solutions are sought and may help in formulating the problem in the first place.