What is the difference between divide and conquer, and branch and reduce?

Question

What is the difference between divide and conquer, and branch and reduce.

From Exact Exponential Algorithms by Fomin and Kratsch, branch and reduce algorithms uses two types of rules:

• A reduction rule is used to simplify a problem instance or halt the algorithm
• A branching rule is used to solve a problem instance by recursively solving smaller instances of a problem.

To me this sounds a lot like the definition of divide and conquer given on Wikipedia:

divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

However when comparing branch and reduce algorithms, like k-satisfiability or computing a maximum independent set, to divide and conquer algorithms, like quicksort and merge sort, they do not feel the same to me.

So is there a difference between divide and conquer, and branch and reduce? If so, what characteristic makes them different.

Cribbs

Answer 1

Divide and conquer algorithms divide the input. Branch and reduce algorithms divide the solution space.

Whorled

Answer 2

Branch and Bound (or Branch and Reduce) is a method that uses Divide and Conquer paradigm at its core to solve problems.

In other words, B&B is a D&C method.

Chiseler

This disagrees with my understanding of the two techniques. In D&C, the solution is an aggregation of the results in all subtrees, so the solution tree has to be evaluated down to all leaves, with no exceptions. In B&B the solution is found at one of the leaves, and as soon as you can find that a subtree is infeasible or dominated by results from other subtrees, you exclude that subtree (including unexplored portions) and reduce the size of the search. The accepted answer states the difference very succinctly. – Olericulture

@Olericulture Branch and bound explicitly incorporates divide and conquer strategy. Your definition of D&C is incorrect. Aggregation of what results? DnC is a strategy to break a problem in to smaller problems to solve. – Chiseler