Introduction

Given any of the following problems:

Determine the optimal graph coloring of a randomly generated 80 node planar graph with the average node connected to 6 arcs such that at most four colors are used and:

1. red is used as frequently as possible.
2. the first forty nodes use red as frequently as possible, and the second forty nodes use blue as frequently as possible.
3. node 23 is green, and as many as possible of the nodes surrounding it are blue, with all of the rest of the nodes using red as frequently as possible.

there is not a computer in existence that could examine the approximately exhaustive combinations of colorings available. Unfortunately, there are no non-exhaustive algorithms using techniques such as constraint satisfaction and/or solution synthesis that can be of much help either.

The key words in the problem statement are optimal, 80 and 6:

• Optimality requires either psychic ability or some sort of (possibly optimized) exhaustive search. Computers are short on the former, and therefore must rely on the latter. If problem 1 was restated to require only a solution containing at least 20 red nodes, some sort of best-first search with constraint satisfaction might yield a result in a reasonable time, although in the worst case it still requires an exhaustive search.

  The problem with requiring optimality is, of course, that one can never be sure that the best answer has been discovered until all other possible answers are compared to it. Branch-and-bound algorithms (Lawler, 1966) can reduce this complexity somewhat by ruling out solution paths that can be guaranteed to be sub-optimal. For instance, a sub-solution of 41 nodes with no reds can be eliminated from further consideration when a solution with 40 reds has already been found. However, it is clear that enormous amounts of processing still need to be invested just to find all sub-solutions of length 40.

  The other problem with requiring optimality is that most real-world problems do. Very rarely does one hear a traveler say, ``Find me a flight path from here to Los Angeles.'' Usually, the weary vacationer asks for the shortest or cheapest path. Occasionally, a wealthy businessman might ask for any itinerary under X amount of dollars, but all too often these requirements result in near exhaustive searches anyway.

• 80 is a significant word in the problem statement because it is well above the kind of exponents we like to see in exponential problems. A planar graph coloring requires a maximum of four colors (Appel & Haken, 1976), thus each vertex can take on four values. An exhaustive search therefore requires combinations, which yields the extremely large number mentioned before. A traveling salesperson might not have as many ``vertices'' to travel to, but probably has quite a few more choices at each node (including different airlines, days and time of the next flight, etc.). If the trip is limited to 10 cities, but the number of possible ``values'' at each city number 10, there will be combinations to sift through, which still requires several hours to compute (more if you are waiting in line behind this person). Natural language semantic analysis is another application that produces exponential complexity. Numbers in the trillions have been observed for sentence-level analysis which require several days of processing to complete.

• 6 is also significant because it gives some measure of the inter-connectedness of the problem. A problem with 80 vertices, with the average vertex connected by 6 edges sets up a relatively local problem space. It may be possible to break such a problem up into manageable sub-problems. Natural language processing, which generally has tree-shaped graphs (Beale, et al, 1996), has a low average inter-connectivity. The N-Queens problem, where every decision affects every other decision, is an example of a clique with high inter-connectivity. The traveling salesperson problem can probably be reduced to one with relatively small inter-connectivity with a little common sense reasoning (eliminating paths from Chicago to New York through Los Angeles).

  Fortunately, many real world problems do have low inter-connectivity. It is not often that you find potential plans where every decision directly impacts every other decision. And sometimes, like the traveling salesperson, an application of common sense reasoning can reduce an otherwise globally interacting problem to a more local one.

Below, we present a computational strategy which attacks problems of this kind. We integrate three related AI search techniques -- constraint satisfaction, branch-and-bound and solution synthesis -- and direct each at minimally interacting sub-problems. The methodology called HUNTER-GATHERER (HG) was introduced in (Beale, et al, 1996) and can be summarized as follows:

• branch-and-bound and constraint satisfaction allow us to ``hunt down'' non-optimal and impossible solutions and prune them from the search space.
• novel solution synthesis methods then ``gather'' all optimal solutions.

Below, we briefly review some of the earlier work on each of the component computing techniques. Next, we discuss the HG algorithm and apply it to the graph coloring problem mentioned above. An important prerequisite of HG is the ability to break a large problem into sub-problems which are relatively local. In general, this problem is NP-complete in itself, but we show how we can use properties of the HG algorithm to efficiently guide such a decomposition. This decomposition is based on graph topology, which in turn can be linked to a measure of the problem's inter-connectedness, or complexity. We examine these relationships and show how a problem's topology affects HG's efficiency. Finally, we discuss practical applications of this methodology to the field of natural language semantic analysis.