Advanced Algorithms (Winter 2026-27) - 04-03 Depth-Bounded Search I

Overview

Sebastian Wild introduces depth-bounded exhaustive search through Vertex Cover: repeatedly choose an uncovered edge and branch on selecting one of its two endpoints, reducing the budget by one per step. The resulting search tree has depth at most K and at most 2^K leaves, giving an FPT algorithm; the same search can find a minimum cover even when K is unknown by trying budgets in increasing order.

Key takeaways

Every Vertex Cover must choose at least one endpoint of any uncovered edge, making the two-way branch exhaustive and preserving correctness.
The search tree has depth at most K and at most 2^K leaves, yielding fixed-parameter running time when the graph-processing work per call is polynomial.
The algorithm can return a minimum cover by comparing successful branch results, rather than stopping at the first cover that fits the threshold.
When the target cover size is unknown, increasing K one at a time avoids the excessive parameter values that make binary or exponential search expensive.
An exponential-time parameterized search can still be practical when K is small, even though brute force over all size-K vertex subsets has a much larger dependence on graph size.

Chapters

0:00 Vertex Cover Search Branches on an Uncovered Edge

For a graph and threshold K, Vertex Cover asks whether at most K vertices cover every edge.
Choose any uncovered edge {u,v}: every valid cover must include u or v, so recurse once for each endpoint.
Each recursive choice removes the selected vertex's incident edges and decreases the remaining budget by one.
The search depth is at most K, so branching on two endpoints creates at most 2^K leaves.

6:00 Recursive Correctness, Induced Subgraphs, and Running Time

The recursive procedure succeeds when no edges remain, returns failure when K is zero but edges remain, and otherwise explores both endpoints of a selected edge.
Deleting vertex u leaves the induced subgraph G[V\{u}], which represents the remaining edges after choosing u.
If both branches produce covers, choosing the smaller returned set also solves the optimization version, not only the decision problem.
With two recursive calls per budget decrement and polynomial work per call, the search runs in O(2^K · poly(n,m)), improving on checking all size-K subsets.

12:00 Finding the Minimum Cover Without Knowing K

Binary search over K can make an early call cost 2^(n/2), while exponential doubling can require a call near 2^(2K).
Instead, test budgets in increasing order from zero; the first feasible budget gives a minimum Vertex Cover.
Because exponential running time is dominated by the largest call, summing the linear-search calls costs roughly twice the final call.
For Vertex Cover, feasibility changes from false to true as K increases, so the first successful threshold is the optimum.

Transcript excerpt

0:00 Let's stop just juggling definitions around and instead um come up with some algorithmic techniques that use this uh notion of parameters. And the first and and simplest, I guess, um is a kind of exhaustive search that uses the parameter to make it not arbitrarily expensive. Uh I think on an on an example this is easiest to see what that means. We've actually seen an example, even though a not interesting one, with this brute-force algorithm for satisfiability. It kind of had, if you pick as parameter the number of variables, naturally a search tree that was bounded in depth by the parameter. And that led to an FPT algorithm.

0:48 It was for a parameter that isn't usually small, but the same kind of trick does work for other problems. And uh the first one we'll look at is our uh lamplighter problem, the vertex cover problem. And we'll use the canonical parameterization. Okay, so I give you a graph and um a threshold K and ask you, "Can you cover all the edges with at most K vertices?" And you're allowed to take a function that depends horribly on K, but not uh more than polynomial in the in the graph size. Um you can do something similar as for the satisfiability problem by picking an arbitrary edge and saying, "Okay, I mean, I have to cover this eventually. I can pick one of the endpoints.

1:37 If I pick one of the endpoints not, then I have to pick the other one." And so you have a a natural bisection over any edge. You have to pick either one endpoint or the other endpoint, maybe both, but not none. And that gives you a simple um algorithm that you can can execute. Maybe let me show you an

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).