<p>A class of typical examples of this arises in branching algorithms, where one branches into several cases until some condition is met that allows for a polynomial-time algorithm.</p>
<p>A well-known example for this is the branching algorithm for the <em>Vertex Cover</em> problem, where the input is a graph <span class="math-container">$G$</span> and a number <span class="math-container">$k$</span> and the task is to find a vertex set of size at most <span class="math-container">$k$</span> whose deletion makes the graph edgeless.</p>
<p>The easiest branching algorithm for this has running time <span class="math-container">$O(2^k\cdot |G|)$</span>: as long as the graph has at least one edge <span class="math-container">$uv$</span> and <span class="math-container">$k &gt; 0$</span> branch into the two cases to delete either <span class="math-container">$u$</span> or <span class="math-container">$v$</span>. The running time bound comes from the fact that in each case the deletion budget <span class="math-container">$k$</span> is decreased by one.</p>
<p>Now the interesting observation is that this can be improved by solving some special cases in polynomial time. The easiest such special case is to consider graphs with maximum degree 1. These consist of isolated edges and vertices and can be easily solved in polynomial time. Now with the polynomial-time algorithm for that case at hand, we can use the following branching:</p>
<p>While <span class="math-container">$G$</span> contains a vertex <span class="math-container">$u$</span> of degree at least 2 and <span class="math-container">$k&gt; 0$</span>, branch into the cases to delete <span class="math-container">$u$</span> or to delete all neighbors of <span class="math-container">$u$</span>. If the condition is not met, then we can solve the instance in polynomial time (since either <span class="math-container">$G$</span> has maximum degree 1 or <span class="math-container">$k\le 0$</span>).</p>
<p>Since in the second branch one always removes at least two vertices, the total size of the branching tree is <span class="math-container">$O(1.62^k)$</span> and thus much smaller than for the <span class="math-container">$2^k$</span>-branching.</p>
<p>Many improved exact exponential-time algorithms and FPT-algorithms use this approach. The final instances that are solved in polynomial-time can become much more interesting / complicated than in the example above. The proof for such algorithms that an instance to which branching is no longer applied can be solved in polynomial time is sometimes called <em>termination lemma</em>.</p>

CC BY-SA 4.0
2024-11-29T15:40:48.687Z
2024-11-29T15:40:48.687Z
Christian Komusiewicz
<p>The <a href="https://en.wikipedia.org/wiki/Cutting-plane_method" rel="noreferrer">cutting plane method</a> for integer programming is such an example - it works by repeatedly using some algorithm to solve linear programming (with real variables), which can be done in polynomial time, and whenever the obtained solution isn't integral it finds a linear inequality which all integer points satisfy but the current solution doesn't and adds it.</p>

CC BY-SA 4.0
2024-11-27T13:37:55.410Z
This is a good example but I was hoping for something more combinatorial in nature.
GEP
CC BY-SA 4.0
2024-11-29T19:24:24.350Z
@GEP - Given the ubiquity of integer programming, there is almost surely an algorithm for some combinatorial problem that is actually the cutting plane method applied to the combinatorial problem written as an integer program.
Alexander Woo
CC BY-SA 4.0
2024-11-30T17:32:34.813Z
@AlexanderWoo that is probably true but I wouldn't call such an algorithm combinatorial in nature.
GEP
CC BY-SA 4.0
2024-11-30T18:13:33.570Z
@GEP - I wouldn't be so sure - for example the Ford-Fulkerson algorithm for min-cut/max-flow is actually the dual simplex method for a particular pivot rule.  The point is that, if you translate the cutting plane method back into the combinatorial formulation, you might get a very combinatorial looking algorithm.  For example, SAT solving methods that involve adding implied terms probably are cutting plane algorithms.
Alexander Woo
CC BY-SA 4.0
2024-11-27T12:20:20.190Z
2024-11-27T12:20:20.190Z
Command Master
<p>The usual algorithm for integer powering <span class="math-container">$a^b$</span> by repeated squaring is an exponential-time algorithm that works by iterating a polynomial-time algorithm just <em>polynomially</em> many times.</p>
<hr />
<p>The real answer here is that <em>every</em> exponential-time algorithm computed by a Turing machine <span class="math-container">$M$</span> is an exponential iteration of the polynomial-time algorithm “simulate one step of <span class="math-container">$M$</span>”. This can be seen as a “special case” of the original problem if you understand it as “simulate <span class="math-container">$M$</span> for a given number of steps”.</p>

CC BY-SA 4.0
2024-11-27T16:13:41.380Z
2024-11-28T08:01:45.100Z
2024-11-28T08:01:45.100Z
Emil Jeřábek
<p>Linear programming. (actually not programming, but name predates computer programming.) This is a matrix operation.</p>
<p>The standard simplex method is very simple, but has exponential worst case complexity. The worst case is not that common.</p>
<p>There are proven to be polynomical worst case algorithms, but those are very complex, so they do not outperform the simplex in many common scenarios.</p>

CC BY-SA 4.0
2024-11-29T09:46:53.740Z
2024-11-29T09:46:53.740Z
user1389698
<p>Dynamic programming. The Held–Karp algorithm is a classic example that finds the exact solution to the Traveling Salesman Problem (TSP), and to several related problems including Hamiltonian Cycle Problem, in exponential time.</p>
<pre><code>TSP(graph, source, target) {
  if source == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, source, target) {
    tour_length = TSP(remove(graph, source), neighbor, target)
                  + distance(graph, source, neighbor);
    if tour_length &lt; min {
      min = tour_length;
    }
  }
  return min;
}
</code></pre>
<p>Note: (neighbors only returns target as a viable neighbor if no other choice is available)</p>
<p>This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. The time complexity of this algorithm is as follows:</p>
<p>There are <span class="math-container">$n$</span> possible start vertices and <span class="math-container">$2^n$</span> possible subgraphs. So this function will be called on at most <span class="math-container">$n.2^n$</span> distinct arguments (the target never changes). Each call runs linearly in <span class="math-container">$O(n)$</span> (as there are at most <span class="math-container">$n$</span> neighbors). Hence the time complexity is: <span class="math-container">$n^2.2^n$</span>.</p>

CC BY-SA 4.0
2024-12-02T19:07:49.000Z
2024-12-02T19:24:29.620Z
2024-12-02T19:24:29.620Z
Vidyadhar Rao
<p>There are many examples of exponential algorithms that use polynomial algorithms for special cases as subroutines. Still, I was hoping to see one that uses a well-known polynomial algorithm for a special case <em>exponentially many times as the <strong>primary method</strong></em> of solving the general problem.
This is not just for the verification of a subsolution but also for the construction of the solution.</p>
<blockquote>
<p>Are there any examples of exponential algorithms that use a
polynomial-time algorithm for a special case as a subroutine
(exponentially many times)?</p>
</blockquote>

CC BY-SA 4.0
2024-11-29T15:58:11.547Z
To compute $e^x$, you add 1 (polynomial) $e^x$ times?
Peter - Reinstate Monica
<ds.algorithms><graph-algorithms>
Are there any examples of exponential algorithms that use a polynomial-time algorithm for a special case as a subroutine (exponentially many times)?
GEP
# Are there any examples of exponential algorithms that use a polynomial-time algorithm for a special case as a subroutine (exponentially many times)?

(Asked by: username_0 on 2024-11-27)

There are many examples of exponential algorithms that use polynomial algorithms for special cases as subroutines. Still, I was hoping to see one that uses a well-known polynomial algorithm for a special case *exponentially many times as the **primary method*** of solving the general problem.
This is not just for the verification of a subsolution but also for the construction of the solution.

> Are there any examples of exponential algorithms that use a
> polynomial-time algorithm for a special case as a subroutine
> (exponentially many times)?

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: To compute $e^x$, you add 1 (polynomial) $e^x$ times?  

---

## 5 answers

### Answer by username_2 on 2024-11-29. Score: 5 | Accepted answer

A class of typical examples of this arises in branching algorithms, where one branches into several cases until some condition is met that allows for a polynomial-time algorithm.

A well-known example for this is the branching algorithm for the *Vertex Cover* problem, where the input is a graph $G$ and a number $k$ and the task is to find a vertex set of size at most $k$ whose deletion makes the graph edgeless.

The easiest branching algorithm for this has running time $O(2^k\cdot |G|)$: as long as the graph has at least one edge $uv$ and $k > 0$ branch into the two cases to delete either $u$ or $v$. The running time bound comes from the fact that in each case the deletion budget $k$ is decreased by one.

Now the interesting observation is that this can be improved by solving some special cases in polynomial time. The easiest such special case is to consider graphs with maximum degree 1. These consist of isolated edges and vertices and can be easily solved in polynomial time. Now with the polynomial-time algorithm for that case at hand, we can use the following branching:

While $G$ contains a vertex $u$ of degree at least 2 and $k> 0$, branch into the cases to delete $u$ or to delete all neighbors of $u$. If the condition is not met, then we can solve the instance in polynomial time (since either $G$ has maximum degree 1 or $k\le 0$).

Since in the second branch one always removes at least two vertices, the total size of the branching tree is $O(1.62^k)$ and thus much smaller than for the $2^k$-branching.

Many improved exact exponential-time algorithms and FPT-algorithms use this approach. The final instances that are solved in polynomial-time can become much more interesting / complicated than in the example above. The proof for such algorithms that an instance to which branching is no longer applied can be solved in polynomial time is sometimes called *termination lemma*.


---

### Answer by username_3 on 2024-11-27. Score: 12

The [cutting plane method](https://en.wikipedia.org/wiki/Cutting-plane_method) for integer programming is such an example - it works by repeatedly using some algorithm to solve linear programming (with real variables), which can be done in polynomial time, and whenever the obtained solution isn't integral it finds a linear inequality which all integer points satisfy but the current solution doesn't and adds it.

> **Comments:**
> **username_0**: This is a good example but I was hoping for something more combinatorial in nature.  
> **username_4**: @GEP - Given the ubiquity of integer programming, there is almost surely an algorithm for some combinatorial problem that is actually the cutting plane method applied to the combinatorial problem written as an integer program.  
> **username_0**: @AlexanderWoo that is probably true but I wouldn't call such an algorithm combinatorial in nature.  
> **username_4**: @GEP - I wouldn't be so sure - for example the Ford-Fulkerson algorithm for min-cut/max-flow is actually the dual simplex method for a particular pivot rule.  The point is that, if you translate the cutting plane method back into the combinatorial formulation, you might get a very combinatorial looking algorithm.  For example, SAT solving methods that involve adding implied terms probably are cutting plane algorithms.  

---

### Answer by username_5 on 2024-11-27. Score: 11

The usual algorithm for integer powering $a^b$ by repeated squaring is an exponential-time algorithm that works by iterating a polynomial-time algorithm just *polynomially* many times.

---

The real answer here is that *every* exponential-time algorithm computed by a Turing machine $M$ is an exponential iteration of the polynomial-time algorithm “simulate one step of $M$”. This can be seen as a “special case” of the original problem if you understand it as “simulate $M$ for a given number of steps”.


---

### Answer by username_6 on 2024-11-29. Score: 3

Linear programming. (actually not programming, but name predates computer programming.) This is a matrix operation.

The standard simplex method is very simple, but has exponential worst case complexity. The worst case is not that common.

There are proven to be polynomical worst case algorithms, but those are very complex, so they do not outperform the simplex in many common scenarios.


---

### Answer by username_7 on 2024-12-02. Score: 1

Dynamic programming. The Held–Karp algorithm is a classic example that finds the exact solution to the Traveling Salesman Problem (TSP), and to several related problems including Hamiltonian Cycle Problem, in exponential time.
TSP(graph, source, target) {
  if source == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, source, target) {
    tour_length = TSP(remove(graph, source), neighbor, target)
                  + distance(graph, source, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

Note: (neighbors only returns target as a viable neighbor if no other choice is available)
This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. The time complexity of this algorithm is as follows:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n.2^n$ distinct arguments (the target never changes). Each call runs linearly in $O(n)$ (as there are at most $n$ neighbors). Hence the time complexity is: $n^2.2^n$.


---

