Approximation algorithms used in exact algorithms Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.

However, constant factors are ignored in time complexity.

So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:


Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.


This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.
An example from the parameterized complexity is a kernelization for the vertex cover problem using a theorem of Nemhauser and Trotter.

In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size.  A vertex cover of an undirected graph is a vertex subset that touches all edges.

Here is an exact algorithm that uses an approximation at the first phase.

Phase 1: Set up the integer linear programming formulation of the minimum vertex cover problem.  It's known (or easy to show) that a basic optimal solution of the linear programming relaxation is half-integral (i.e., every coordinate is either 0, 1, or 1/2).  Such a basic optimal solution can be found by a usual polynomial-time algorithm for linear programming (or in this special case, we can formulate it as a network flow problem, so we can solve it combinatorially in polynomial time).  Having such a basic optimal solution, we round it up to obtain a feasible solution to the original integer linear programming problem.  Let S be the corresponding vertex subset.  It's good to note that S is a 2-approximation of the given minimum vertex cover instance.

Phase 2: Find a minimum vertex cover in the subgraph induced by S (for example by an exhaustive search).  A theorem by Nemhauser and Trotter states that this subgraph contains an optimal solution of the original input graph.  So, the correctness of this approach follows.

You may consult a book by Niedermeier on fixed-parameter algorithms for this algorithm.