Advanced Algorithms (Winter 2026-27) - 04-10 Interleaving

Overview

Sebastian Wild explains interleaving, applying kernelization inside each recursive call of a bounded search tree, rather than only once before search. A lollipop-flower vertex-cover instance shows how this can cut an apparent 2^k search to a few steps, while recurrence and generating-function analysis show that the worst-case gain depends on the kernelization overhead and its growth rate relative to the branching recurrence.

Key takeaways

Applying kernelization before every branching step can expose forced choices after the parameter decreases, allowing a search to terminate before exploring most of its tree.
On the lollipop-flower vertex-cover instance, the sequential algorithm explores about 2^k branches, while interleaving triggers the high-degree rule after two branch choices and detects infeasibility.
If a kernel has size polynomial in k, interleaving makes the per-call reduction cost shrink with the parameter, but that cost must be represented as an inhomogeneous term in the recurrence.
A recurrence's dominant exponential rate remains unchanged when its forcing term grows more slowly than the rate from its characteristic roots; a faster-growing term such as 2^k can instead dominate.
The interleaved vertex-cover analysis replaces a multiplicative dependence on the original graph size with an additive size-dependent term, a modest worst-case gain despite potentially large instance-specific savings.

Chapters

0:00 Interleaving Kernelization with Bounded Search

The sequential approach kernelizes once, then runs a depth-bounded exhaustive search; interleaving reapplies reductions before branching in each recursive call.
Per-call reductions add work, but may shrink the parameter early and eliminate many later search-tree calls.
The motivating example uses vertex cover, where a high-degree rule forces a vertex into the cover when its degree reaches the current budget.

3:25 Lollipop-Flower Graphs Expose the Benefit of Early Reductions

The constructed graph has k - 2 star-shaped petals attached to a head and a tail path of 3k + 1 vertices, for a total of k² + 4 vertices.
With k = 5, the initial high-degree rule does not apply, so the non-interleaved algorithm explores essentially 2^k branches before discovering infeasibility.
After two branch choices, the budget drops to k - 2; the interleaved rule then forces high-degree petal vertices and detects that the budget cannot suffice.
The example demonstrates a dramatic instance-specific improvement, but both the algorithms and graph family are deliberately constructed.

8:10 Modeling Interleaved Search Costs with Recurrences

The general setup assumes a polynomial-size kernel of size Q(k), a polynomial-time kernelization, and a branching rule with parameter reductions described by branching vectors.
Without interleaving, the kernelization costs P(n) once, followed by roughly α^k search calls, each operating on an instance of size Q(k).
With interleaving, kernelization is repeated when an instance exceeds the kernel-size bound, so the per-call work decreases as the parameter and instance shrink.
This makes the recurrence inhomogeneous: besides recursive-call terms, it includes a parameter-dependent cost for reductions and branching.

12:04 Generating Functions Handle Parameter-Dependent Overhead

For vertex cover, the interleaved algorithm applies the Buss kernel before checking the base case and branching; degree-zero, degree-one, and sufficiently high-degree rules yield a kernel quadratic in k.
The recurrence therefore includes a polynomial-in-k overhead term as well as recursive calls, unlike the homogeneous recurrence analyzed earlier.
Generating functions convert the recurrence into a functional equation; differentiating the geometric series derives the needed sums involving k²z^k.
The resulting generating function gains a factor such as 1 - z cubed in its denominator, whose root at 1 does not change the dominant exponential growth root in this example.

19:28 When the Forcing Term Changes the Growth Rate

An inhomogeneous term does not alter the recurrence's dominant exponential rate when its own growth is strictly smaller than the rate determined by the characteristic roots.
The condition matters: a recurrence with an added 2^k cost can be dominated by that term, even if its recursive-call structure has a smaller growth rate.
The lollipop example's rapid pruning should not be confused with a guaranteed large worst-case improvement; the forcing cost must be included in the analysis.

24:21 Analytic Combinatorics and the Overall Worst-Case Result

Generating functions connect recurrence counting to function analysis; singularities and transfer theorems can translate behavior near a denominator root into asymptotic coefficient estimates.
For the interleaved vertex-cover algorithm, the stated worst-case bound is the search-space term plus a term depending on the original graph size, rather than a multiplicative dependence on that size.
Wild characterizes the general worst-case improvement as modest despite the lollipop graph's dramatic speedup, and notes that lowering exponential constants such as 1.27 to 1.25 may be less significant if subexponential algorithms are available under recent claims about ETH.
The unit closes by recapping fixed-parameter tractability, kernelization, and bounded search trees, then previews impossibility results for FPT algorithms.

Transcript excerpt

0:01 The last chapter here um ties together a few little tricks that um maybe if you've spend enough time on thinking about how to lower this this exponential base get lost easily. This is just a kind of little trick that helps sometimes uh but I think it's it's useful to keep that in mind. It's called injured leaving and the idea is that um so far what we thought about for these uh these two techniques of kernelization and then depth bounded search was kind of one after the other. First you take your input and you do some pre-processing to reduce it to some small kernel and then you apply this depth bounded exhaustive search and because this takes polynomial time it kind of didn't matter too much what you do there. This is really what what

0:49 costs a lot. But um why not if that's expensive anyways uh try to do this reduction in each recursive call because the parameter gets smaller that might actually help. And uh yes it increases the cost you do per step here but the number of steps was the the big deal anyways. If we can get the number of steps down that would be useful. Okay so as an example again uh we'll look at vertex cover and just to make the case that this can sometimes have an tremendous effect uh let me create an artificial setup here. Suppose we do this uh comparison with this straw man algorithm where we only do the large degree rule

1:39 if there if the graph contains some vertex of degree at least k then we we have to include that one because taking all its neighbors is already too costly. So we do only this um reduction rule for the kernelization whereas of course we could have used

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Sebastian Wild (Lectures).