Video 4-8: Correctness for Closest String FPT

0:02 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. 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.

1:19 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 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 out of luck with this branch. Because even if we make these steps towards this string as I, we're still and this is strictly greater, so we still have k + 1 mismatches, then we're also out of luck. Uh this is uh when we succeed, when everything has distance at most k, then we're happy.

2:21 And the remaining case is we're not yet completely doomed, um but we're also not happy yet, so there will be some string that has distance at least k + 1. And say this p is all the positions where they differ. Now I may I may try to uh fix more of these positions, but um the reason why it's enough to pick k + 1 is that any subset of k + 1 positions where I'm currently not matching as I, I will have to match one of those k + 1 positions in any in any positive solution. If I don't match all of those, well, then I have k + 1 mismatches, and then it's not a solution. So it might be that the distance to this this string is larger than k + 1 at the moment, then maybe I'm out of luck anyways. Who knows? But uh if I'm at more more than at distance k, I have to fix some positions, and any subset of k + 1 positions where I currently have a mismatch, one of them needs to be fixed.

3:29 That's the argument we need here. And that's why um it's enough to branch out on these k + 1 positions. Any solution must fix one of those for sure. And so we just try all of them. Which of these uh guesses we set the consensus string, the new one to try so that it matches as I on this position. And then we recursively call suppose I walk there and have d - 1 further steps, can I make it work? If so, I return this, otherwise uh this branch doesn't work. And if all of the branches don't work, and clearly there's no way for me to walk towards SI enough to make S as I happy. [snorts] Uh we already did the analysis of the running time of the um the size of this of this search space. We branch out in K + 1 um different directions each time. And we do that for depth K, so we have this this search space otherwise known as K to the K if you ignore constant factors.

4:37 So this is um an example where it's not just singly exponential but a bit worse. Okay, that's what we've what we've shown with this algorithm. Uh if you're a bit more careful then you can implement it fast. I don't think that's that interesting, so um I'll I'll leave it with what's on the slide. Uh you can Essentially the idea is to keep uh keep the distances stored and maintain them instead of just recomputing them each time you ask about them. Even if you did, that's uh it's not going to be the main factor. If K is not tiny then this K to the K is where you uh where this approach will die.