Advanced Algorithms (Winter 2026-27) - 04-08 Correctness for Closest String FPT

Overview

Sebastian Wild explains the correctness of a fixed-parameter algorithm for the p-closest string problem, which asks whether a consensus string lies within Hamming distance k of every input string. Starting from the first input string, the algorithm branches on k + 1 mismatching positions because every valid solution must fix at least one; with depth k, this yields a search space of (k + 1)^k, or roughly k^k.

Key takeaways

For p-Closest String, a candidate is feasible only if its Hamming distance from every input string is at most k.
More than m * k dirty columns make the instance impossible, since some input string must incur at least k + 1 mismatches.
When an input string has at least k + 1 mismatches against the current candidate, every feasible solution must fix one position from any chosen subset of k + 1 mismatches.
Branching on those k + 1 positions is complete: the search explores a necessary move for every possible solution.
With at most k changes from the starting string and k + 1 choices per step, the algorithm explores at most (k + 1)^k branches up to constant factors.
Updating stored Hamming distances can reduce per-node work, but it does not remove the dominant roughly k^k growth in the search space.

Chapters

0:00 p-Closest String Setup and the Dirty-Column Bound

The p-closest string problem asks for a consensus string at Hamming distance at most k from every input string.
A column is dirty when the input strings contain more than one letter in that position.
More than m * k dirty columns rule out a solution: at least one input string must be at distance k + 1 or greater from any proposed consensus.

1:19 Why Correct Branches Need Only k + 1 Mismatching Positions

The search starts from the first string, s1, and allows at most k changes from it.
If some input string still differs from the current candidate in at least k + 1 positions, select any k + 1 of those mismatches.
Every valid solution must change at least one selected position; leaving all k + 1 unmatched would violate the distance-k constraint.
The algorithm tries each selected position by changing the candidate to match the input string there, then recurses with one fewer step.

4:12 Search-Tree Cost and Maintaining Distances

Each search node branches into k + 1 choices, with recursion depth at most k.
The resulting search space is (k + 1)^k, commonly described as roughly k^k when ignoring constant factors.
An implementation can store and update distances rather than recomputing them, but the k^k search-space growth is the main cost.

Transcript excerpt

0:01 The problem we were looking at is the p-closest string problem in the parameterized setting. So we have strings of the same length and a threshold and the question is can you find some consensus string that's at most at Hamming distance k from all of them. And we had some supporting lemmas that if you have too many dirty columns where there's more than one letter then you're out of luck. Specifically if you have more than m * k then one string definitely has distance k + 1 to some um well any string you pick one of the strings in your input has distance k + 1 to uh your chosen consensus string. Um then I jumped straight to the the final solution for our FPT algorithm.

0:51 Um written down here maybe um just intuitively you start walking away from the first string as one potential guess of what this consensus string could be. And you give yourself a budget of k steps that you can okay mismatches to s 1 you're allowed to introduce. More than that would certainly not be a consensus string with respect to s 1 so that's no no point in trying. And the one step we left open correctness wise last time was uh why it's okay to just look at k + 1 positions here. So a simple argument but uh let's let's revisit that. Um first of all if we're even in this

1:38 position then we already ruled out that we're in a completely hopeless situation. If we've arrived somewhere where we have negative budget then we're in trouble. And also if we have the budget to still walk away uh to still walk and the distance we may at the end have if that is more than distance to any string, then we're also

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