title: What is the difference between divide and conquer, and branch and reduce?
body: <p>What is the difference between divide and conquer, and branch and reduce.</p>
  
  <p>From Exact Exponential Algorithms by Fomin and Kratsch, branch and reduce algorithms uses two types of rules:</p>
  
  <blockquote>
    <ul>
    <li>A reduction rule is used to simplify a problem instance or halt the algorithm</li>
    <li>A branching rule is used to solve a problem instance by recursively solving smaller instances of a problem.</li>
    </ul>
  </blockquote>
  
  <p>To me this sounds a lot like the definition of divide and conquer given on Wikipedia:</p>
  
  <blockquote>
    <p>divide and conquer (D&amp;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.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>So is there a difference between divide and conquer, and branch and reduce? If so, what characteristic makes them different. </p>