Advanced Algorithms (Winter 2026-27) - 04-06 Depth-Bounded Search for Planar Independent Set

Overview

Sebastian Wild derives a fixed-parameter algorithm for finding an independent set of size K in planar graphs, using planar graph edge bounds to establish 5-degeneracy. Branching on a vertex of degree at most 5 and its neighbors gives at most 6 recursive calls per solution vertex, for a straightforward O(6^K n) running time.

Key takeaways

Every simple planar graph with at least three vertices has at most 3n - 6 edges, which implies average degree below 6.
Planarity is inherited by induced subgraphs, so the average-degree argument guarantees a degree-at-most-5 vertex in every induced subgraph; planar graphs are therefore 5-degenerate.
Branching on v and its at most five neighbors is correct because every maximal independent set contains at least one vertex from that closed neighborhood.
The planar independent-set search has at most 6 branches per level and depth at most K, yielding an O(6^K n) implementation.
The algorithmic benefit comes from degeneracy rather than planarity itself: the same bounded-branching strategy applies to other graph classes with bounded degeneracy.

Chapters

0:00 Independent Set: Hardness and the Planar Restriction

An independent set is a vertex subset whose induced subgraph has no edges; the goal is to find one of size at least K.
Independent Set remains NP-complete even on planar graphs with maximum degree 3.
The lecture focuses on the parameterized problem for planar graphs, where K is the requested independent-set size.

4:00 Planar Embeddings and the K5, K3,3 Minor Characterization

A graph is planar if its vertices and edges can be drawn in the plane without edge crossings.
Kuratowski and Wagner results characterize planarity through the two obstructions K5 and K3,3; the minor formulation uses edge deletion, vertex deletion, and edge contraction.
Each of those minor operations preserves planarity, so a graph containing K5 or K3,3 as a minor cannot be planar.

12:27 Euler’s Formula for Connected Planar Maps

For a connected planar map, the numbers of vertices, edges, and faces satisfy n - m + f = 2.
Faces are the regions formed by the embedding, including the unbounded outer face.
The proof idea inducts on the number of faces: trees provide the one-face base case, and adding a face adds one edge, preserving the formula.

21:11 Deriving the 3n - 6 Planar Edge Bound

In a simple planar graph, each face has at least three edge incidences, while each edge is counted twice across face incidences.
Combining 3f ≤ 2m with Euler’s formula yields m ≤ 3n - 6 for simple planar graphs with n at least 3.
Since the sum of vertex degrees is 2m, the average degree is less than 6.

28:20 From Average Degree to 5-Degenerate Graphs

An average degree below 6 guarantees at least one vertex of degree at most 5.
Deleting vertices preserves planarity, so every induced subgraph also has a vertex of degree at most 5.
This property defines 5-degeneracy and supplies a low-degree vertex at every stage of the search.

32:10 Branching on a Vertex and Its Neighbors

Choose a vertex v of degree at most 5, giving at most six candidates in its closed neighborhood: v and its neighbors.
For each candidate x, include x, remove x and its neighbors, and recursively search for an independent set of size K - 1.
The branching is complete because any maximal independent set must contain a vertex in the closed neighborhood of v.

36:10 Search Runtime and the Planar Independent Set Result

Each recursive step reduces K by 1 and creates at most 6 branches, so the search tree has O(6^K) nodes.
With O(n) work per node on a planar graph, a straightforward implementation runs in O(6^K n) time.
The method is FPT for planar Independent Set, even though the unrestricted problem is NP-hard and is expected not to be FPT when parameterized by solution size.

Transcript excerpt

0:01 We next want to look at the independent set problem in a specific restriction and again see some depth bounded search tree algorithms based on that. Um what I briefly recalled uh for the vertex cover problem is that we've not done so much algorithmic intelligence in our algorithms for these for these problems so far. Uh they're essentially a brute force method which just observed that if the parameter that you care about happens to bound this this depth then there's already a a result in the style that we ask about here. And the next problem I want to look at is this the independent set problem. So again to briefly remind uh everyone what the independent set problem is, you

0:47 have a graph with various edges. I'm just making some arbitrary example. And now with the question is how many vertices can you pick where none of the picked vertices have an edge in between. So here it looks like you want to pick these two. And maybe three is the best you can do. At least that is a independent set. The vertices have mutually no edges in between. Or in other words, the uh subgraph induced by the red vertices is the empty graph. That's the independent set problem or interested in finding a large such set. Now unfortunately this is a hard problem

1:35 in several ways. First of all, it is NP-hard NP-complete even if you restrict the graphs a lot. If you restrict them to planar graphs and where the vertices only have three edges. So these are uh essentially um collections of such glued together triangles if you think about it and maybe some trees attached to it. Maybe with a bit more more of a um such triangles or I could also of course

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