Figure: Subgraph: maximize the number of reds.
The weakness of previous solution synthesis algorithms is that they do not directly decrease problem complexity. Constraint satisfaction methods used in combination with solution synthesis indirectly aid in decreasing complexity, and variable ordering techniques such as MBO try to direct this aid, but complexity is still driven by the number of exhaustive solutions available at each synthesis. In effect, solution synthesis has been used simply as a way to maximize the disambiguating power of constraint satisfaction for optimization problems.
Instead of concentrating on constraints, HG focuses on the optimization aspect and uses that to guide solution synthesis. The key technique used for optimization is branch-and-bound. Consider the subgraph of a coloring problem in Figure 2 . In this subgraph, only vertex A has constraints outside the subgraph. What this tells us is that by examining only this subgraph, we cannot determine the correct value for vertex A, since there are constraints we are not taking into account. However, given a value for vertex A, we can optimize each of the other vertices with respect to that value.
Figure: Three steps for subgraph optimization.
The optimization is done in three steps. First, exhaustively determine all of the combinations of values for the vertices in the subgraph. Next, use constraint satisfaction to eliminate impossible combinations. Finally, for each possible value of the vertex with constraints outside the subgraph, determine the optimal assignments for the other vertices. Figure 3 illustrates this process. Note that step 3 retains a combination for each possible value of vertex A, each optimized so that the maximum number of reds appear.
Figure: Subgraph: maximize the number of reds.
Consider what happens if, instead of having a single vertex constrained outside the subgraph, two vertices are constrained outside the subgraph, as in Figure 4 . In this case, the assignment of correct values for both Vertices A and D must be deferred until later. In the branch-and-bound reduction phase, all possible combinations of values for vertices A and D must be retained, each of which can be optimized with respect to the other vertices. Phase three for this subgraph would yield 4*4=16 combinations.
Solution synthesis is used to combine results from subgraphs or to add individual vertices onto subgraphs. Figure 5 shows an example of combining the subgraph from Figure 4 with two additional vertices, E and F. Step 1 in the combination process is to take all of the outputs from the input subgraph, 16 in this case, and combine them exhaustively with all the possible values of the input vertices, or 4 each. This gives a total complexity for step 1 of 16 * 4 * 4 = 256. Constraint satisfaction can then be applied as usual. In the resulting synthesized subgraph, only vertex A has constraints outside the subgraph (assuming vertices E and F have no other constraints, as shown). The output of step 3, therefore, will contain 4 optimized answers, one for each of the possible values of A.
Synthesis of two (or more) sub-graphs into one proceeds similarly. All of the step 3 outputs of each input subgraph are exhaustively combined. After constraint satisfaction, step 3 reduction occurs, yielding the output of the synthesis.
Note that the complexity of the processing described up to this point is dominated by the exhaustive listing of combinations in step 1. With this in mind, subgraphs are constructed to minimize this complexity (see below for a discussion of how this is accomplished in non-exponential time). For this reason, our solution synthesis will be directed at combining subgraphs created to minimize the total effect of all the step 1's. This involves limiting the number of inputs to the subgraph as well as maximizing the branch-and-bound reductions (which in turn will help minimize the inputs to the next higher subgraph). This outlook is the central difference between this methodology and previous efforts at solution synthesis, all of which attempted to maximize the effects of early constraint disambiguation. The pruning driven by this branch-and-bound method typically overwhelms the contribution of constraint satisfaction (see below for actual results).
HG Algorithm
A simple algorithm for HG is shown in Figure 6 . It accepts a list of Subgraphs, ordered from smallest to largest, so that all input subgraphs are guaranteed to have been processed when needed in PROCESS-SUB-GRAPH. Each subgraph is identified by a list of input vertices, a list of input subgraphs, and a list of vertices that are constrained outside the subgraph.
The COMBINE-INPUTS procedure (line 7) simply produces all combinations of
value assignments for the input vertices and subgraphs. This
procedure has complexity
O(
), where x is the number of
vertices in In-Vertices, a is the maximum
number of values for a vertex, and 
is the complexity of the
input subgraph (which was already processed and reduced to a minimum
by a previous call to PROCESS-SUBGRAPH). In the worst case, x
will be n, the number of vertices; this is
the case when the initial subgraph contains all the vertices and no
subgraphs. Of course, this is simply an exhaustive search, not
Solution Synthesis. In practice, the subgraphs usually contain no more
than two or three vertices not involved in the input subgraphs. In
short, the complexity of Step 1 is the product of the complexity of
the reduced outputs for the input subgraphs times the number
of exhaustive combinations of input vertices. This complexity
dominates the algorithm and will be what we seek to minimize below in
the discussion of creating the input sub-graphs.
Lines 8-10 will obviously be executed the same number of times as the
complexity for line 7. An arc consistency (line 9) routine similar to
AC-4 (see Tsang, 1993) is used. It has complexity
O(
), where e is the number of edges in the graph.
In the worst case, when the graph is a clique, e equals
n! because every vertex affects every other vertex.
Fortunately, SS-HG is aimed at problems of lesser dimensionality.
Cliques are going to have exponential complexity no matter how they
are processed. For us, the only vertices that will have edges outside
the subgraph are those in Constrained-Vertices. Propagation of
constraint failures by the AC-4 algorithm is limited to these
vertices, and, indirectly, beyond them by the degree of
inter-connectedness of the graph. In practice, for the
lower-dimensional graphs we attack, the processing time associated
with line 9 is negligible. (It's effects, however, are not, as
constraint satisfaction can help prune the search space.)
The REDUCE-PLANS procedure in line 11 simply goes through each Plan
that passed arc consistency, and keeps track of the best one for each
combination of values of Constrained-Vertices. If there are two
Constrained-Vertices, each of which has four possible values,
REDUCE-PLANS should return 16 plans (unless one or more combinations
are impossible due to constraints), one for each of the possible
combination of values of Constrained-Vertices, each optimized with respect to
every other vertex in the subgraph. The complexity of line 12 is
therefore the same as the complexity of COMBINE-INPUTS. We refer to
this complexity as the ``input complexity'' for the subgraph, whereas
the ``output complexity'' is the number of plans returned by
REDUCE-PLANS, which is equal to O(
), where c is the
number of vertices in Constrained-Vertices.
With this in mind, we can refigure the complexity of COMBINE-INPUTS.
The output complexity of a subgraph is O(
), which becomes a
factor in the input complexity of the next higher subgraph. The input
complexity of COMBINE-INPUTS is the product of O(
) times
the complexity of the input subgraphs. Taken together, the complete
input complexity of COMBINE-INPUTS, and thus the overall complexity of
PROCESS-SUBGRAPH, is O(
), where 
is the
total number of Constrained-Vertices in all of the input subgraphs.
In simple terms, the exponent is the number of vertices in In-Vertices
plus the total number of Constrained-Vertices in each of the input
subgraphs. To simplify matters later, we will refer to input
complexity as the exponent value 
and the output
complexity as the number of vertices in Constrained-Vertices.
The complexity of SS-HG will be dominated by the PROCESS-SUBGRAPH
procedure call with the highest input complexity. Thus, when creating
the progression of subgraphs (details below) input to SS-HG, we will
seek to minimize the highest input complexity, which we will refer to
as Maximum-Input-Complexity. To be precise,
Maximum-Input-Complexity = 
for the subgraph with
highest input complexity. As will be shown, some
fairly simple heuristics can simplify this subgraph creation process.
For completion, it should be noted that PROCESS-SUBGRAPH is called X
times in SS-HG, where X is the number of subgraphs in Subgraphs.
A Subgraph with input complexity less than Maximum-Input-Complexity
will run in time negligible compared to those with
Maximum-Input-Complexity. Thus, Number-At-Maximum-Input-Complexity is
an important measure, and the overall complexity of SS-HG will be:
O(Number-At-Maximum-Input-Complexity *
)
Theoretically, one could create
Subgraphs in such a way that there would be an exponential number of
subgraphs. However, our algorithm below guarantees that there will be n
or less subgraphs. Typically, only a portion of these have
Maximum-Input-Complexity, thus the overall complexity is less than
O(n * 
).
Space complexity is actually more limiting than time complexity for
solution synthesis approaches. Although one can theoretically wait
ten years for an answer, no answer is possible if the computer runs out
of memory. The space complexity of SS-HG is dominated by the need to
store results for subgraphs that will be used as inputs later. This
need is minimized by carefully deleting all information once it is no
longer needed; however, the storage requirements can still be quite
high. The significant measurement in this area is the maximum output
complexity, because it determines the amount of output combinations
stored by the subgraph with the highest output complexity. The
highest output complexity is bounded by the highest input complexity,
and thus is proportional to O(n * 
).
Again, it must be noted that this approach attempts to directly
minimize the space complexity. Previous solution synthesis methods
only reduced space (and time) complexity as an accidental by-product
of the constraint satisfaction process. As will be shown below, their
space complexity becomes unmanageable even for relatively small
problems.
