Advanced Algorithms (Winter 2026-27) - 04-09 Linear Recurrences
Watch on YouTube →
Overview
Sebastian Wild improves the vertex-cover search bound by solving degree-at-most-two components directly, then branching on a maximum-degree vertex to obtain the recurrence T(k) = T(k-1) + T(k-3). He uses generating functions, partial fractions, and characteristic roots to show a search-space growth rate of about 1.4656^k and presents a general method for analyzing similar recurrences.
Key takeaways
- In vertex cover, any remaining graph of maximum degree two can be solved exactly as paths and cycles, avoiding unnecessary recursive branching.
- Branching on a maximum-degree vertex after excluding the degree-at-most-two case gives T(k) = T(k-1) + T(k-3), because the neighbor branch removes at least three vertices from the budget.
- The recurrence T(k) = T(k-1) + T(k-3) has characteristic polynomial x^3 - x^2 - 1 and search-tree growth of approximately 1.4656^k, rather than 2^k.
- Generating functions convert constant-shift linear recurrences into rational functions; partial fractions then express their coefficients as sums of exponential terms.
- For a recurrence with parameter reductions D1 through Di, the polynomial x^D - sum(x^(D-Dj)) provides a systematic way to estimate the exponential search-tree growth from its largest-magnitude root.
Chapters
- The basic edge-based branching algorithm tries either endpoint and has a search space of 2^K for budget K.
- A graph whose vertices all have degree at most two is a disjoint union of isolated vertices, paths, and cycles.
- Each component has an optimal vertex cover computable directly: alternate vertices on paths, and use roughly half the vertices on cycles.
- The algorithm first handles an empty edge set and an exhausted budget, then solves the entire remaining graph exactly if its maximum degree is at most two.
- For other graphs, choose a maximum-degree vertex and branch on including it or including all its neighbors.
- After the low-degree case has been excluded, the chosen vertex has degree at least three, so the neighbor branch reduces K by at least three.
- For an upper bound, assume both branches are always needed and the neighbor branch reduces the parameter by exactly three.
- Counting leaves gives B(k) = B(k-1) + B(k-3), with small parameter values handled as base cases.
- The recursion tree is binary, so its total number of calls is within a constant factor of its leaves; a quadratic graph scan per call gives an overall polynomial overhead.
- Define B(z) = sum of B(k)z^k to encode the entire sequence of search-tree leaf counts.
- Substitute B(k) = B(k-1) + B(k-3) into the series, shifting indices and accounting for the initial values B(0), B(1), and B(2).
- The resulting generating function is rational, with denominator 1 - z - z^3.
- Factor the generating-function denominator into linear factors over the complex numbers, corresponding to its roots.
- Partial fractions express the rational function as a sum of terms associated with individual roots; each coefficient can be isolated by multiplying by its factor and substituting the root.
- Each fraction expands as a geometric series, converting the generating function back into a sum of exponential terms.
- The coefficient of z^k in B(z) is B(k), so the partial-fraction expansion gives a closed form as a sum of exponentials.
- For asymptotic growth, the root with the largest relevant exponential magnitude dominates the other terms.
- The recurrence's dominant growth rate is about 1.4656^k, improving on the original 2^k vertex-cover search bound.
- For a recurrence with reductions D1 through Di and maximum reduction D, use the characteristic polynomial x^D - sum(x^(D-Dj)).
- The largest absolute value among the polynomial's roots determines the exponential growth rate.
- The recurrence T(k) = T(k-1) + T(k-3) yields x^3 - x^2 - 1, whose dominant root produces the approximately 1.4656^k bound.
- A hypothetical recurrence with reductions (1, 2) has dominant growth about 1.61^k, worse than the vertex-cover recurrence.
- Reductions (1, 4) give about 1.38^k, while (2, 2) gives sqrt(2)^k, or about 1.414^k.
- Sebastian Wild demonstrates using SymPy to solve characteristic polynomials and compare candidate branching vectors; the smallest dominant root gives the best search-space bound.
Transcript excerpt
0:00 Now back to our famous famous vertex cover problem where we've already had some FPT algorithm where the kernel was two to the K where we again remember the branching that we've seen so far was pick a any arbitrary edge one of the end point end points has to be in the vertex cover try both options. If you do that for depth K if K is the budget then um you get this two to the K search space for vertex cover. Can we do better? Uh there's several answers to this nowadays but let's um do the um immediate one. One idea is that we can try to do better on the base cases because so far the algorithm
0:47 didn't do anything smart at the base case it gave up when there was no hope at all. So if I'm out of budget I can no no longer pick any extra vertex then I give up and if I've covered all edges then I'm happy and I succeed. We can do a bit better namely um if we look at uh graphs with only small degree vertices. What do graphs look like that have vertices where the largest degree is two? Well they can have some isolated vertices not super exciting. They can have stuff like this individual edges. They can also have paths. Uh maybe of of odd length or of even length both can happen. And they can have cycles. That's degree two.
1:40 I cannot do much more I cannot even build a tree sadly right that already needs uh a vertex of degree three. So really this is all and this this means the graph is a disjoint union oops disjoint union of paths and cycles. Well, that's um probably not a very interesting class to
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).