# What is the difference between exhaustive search & combinatorial search?

I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper!

What is the difference between exhaustive search & combinatorial search ?

My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, in general exhaustive search is in the worst case linear in the size of the search space to be explored.

On the other hand, combinatorial search instead is a smarter kind of search, which usually exploits one or more pruning strategies to avoid testing all of the possible candidate solutions. In this case, you can safely discard some candidates (depending on the particular algorithm of course) and therefore you can save precious time. An example of combinatorial search is, for instance, branch and bound. Here, you may safely skip some subtrees since, depending on your particular optimization problem, you know in advance that no node within a certain subtree can yeld a better solution than the current one during the execution of your algorithm.

Exhaustive search is used mainly in two different context:

• When trying to find some $x \in X$ that satisfies a property $P$, the exhaustive search algorithm tries all $x \in X$ until it finds one satisfying property $P$.

• When trying to optimize some function $f$ over some domain $X$, the exhaustive search algorithm computes the value on $f$ on all of $X$, and then finds the optimum.

Combinatorial search isn't a standard term, so I don't know what your paper meant by it, but at any rate it encompasses a wider class of algorithms. For example, greedy and local search heuristics might be considered combinatorial search. A good example is the simplex algorithm for linear programming. What makes these algorithms combinatorial is that they operate with combinatorial - that is, discrete - objects. In contrast, interior-point algorithms for linear programming work with a continuous relaxation of the problem, and so they aren't considered to be combinatorial search.

An essential component of combinatorial algorithms is that a combinatorial structure is utilized to speed up the search. What does this mean?

• "combinatorial" -- it's discrete, and usually efficiently enumerable. In CS terms, think of any data structure.
• "structure" -- as opposed to just a set of things. Graphs, for instance, specify relations between elements of a flat set. This additional information may be useful for algorithms.

In this sense, you could say that exhaustive/brute-force search is the dumbest combinatorial search possible.

For example, you can improve the brute-force algorithm for Vertex Cover by noting that there is always an optimal vertex cover without nodes of degree one (for connected graphs with more than two nodes) -- we use both the structure of graphs and the problem for achieving the speedup.

See, for instance, Vertex Cover: Further Observations and Further Improvements by Chen et al. (2001); they give an exact algorithm for Vertex Cover that runs in time $O(kn + 1.3^n)$ (free copy) which is a huge improvement over the brute-force $O(2^n)$-time algorithm.