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.
Divide and conquer algorithms divide the input. Branch and reduce algorithms divide the solution space.