CS 627 – Advanced Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-09, 9:39

Click any sentence to play from there.

The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.

0:03 So in the next section we'll look at the corresponding hardness notion and complexity class that you get if you use these parameterized reductions. Uh that's known as as par np par I guess for parameter. It's the that's the natural definition. Um I will I will say already this is not going to be the final answer. I I gave that away at the beginning. But again, if you listen carefully to the definition, I think it sounds so sensible that it's a bit surprising that it doesn't work to the um in the way we want it. Uh first of all, we can um we can ask about what's the the correspond the corresponding class for NP if we allow FPT algorithms. I think it's very natural to say same we have allow FPT running time but now a non-deterministic algorithm right same as with going from P to NP and um these properties are satisfied by par NP it's closed under FPT reduction so if you have a problem in par NP and an FPT reduction to some other problem then that other problem is in FP in in par NP uh also if the two coincide if FPT equals par NP that's the same as asking whether P is equal NP and there is some way of generalizing this kernelization that we've discussed um so these these properties are not completely trivial and I'm just noting this because you're not expected to know or like immediately say yes obvious facts that I wanted to state the the problem is or the reason why I'm I'm not going into the proof here is that the notion will turn out useless in a way mostly useless and so I'm I'm just stating them as that's not the problem why the theory there isn't sound okay okay we can define hardness um a problem is is par np hard parameterized problem if every other par np problem reduces to it with an parameterized reduction. So it's the whole sentence um as you would define NP hardness, you just insert parameters everywhere.

2:30 And so that that that sounds like the right notion. And um the problem is essentially uh this theorem which says suppose I have some parameterized problem that is par nplete then that necessarily means there is a constant d so that if I take this problem and restrict it to only the instances that have um parameter bounded by d by this fixed constant d then that problem that I'm left with is already an NP hard decision problem.

3:09 And this is a problem in the following sense that it defeats the purpose of FPT algorithms because uh if a problem is NP hard even if the parameter is fixed by a constant well then I can never have these problems included that have an N to the K running time.

3:33 So I'll this will come up on the slide later but again um it means that our problems such as K click P click are are par and P hard because they do allow an algorithm of the running time N to the K which is polomial if K is bounded by some fixed global constant.

4:20 And so there's going to be no hope that this theory tells us why we seem not to be able to find an FT algorithm for PC click. It's too uh coarse. Let's still go through the proof because okay I ran through this at a pace that you couldn't have probably uh made a a good opinion about this class from first principles but um if you play with the definitions for a while you you off you rather quickly come to the conclusion of some something like this so still I think it's it's insightful to go through the proof for this uh what we'll have to show is somehow this hardness, right? So, um it's going to be a classical NP hardness reduction. I try to have pick a problem and show that my new problem is hard via normal reduction. But, uh what I have at my disposal is this this weirdo parameterized problem that's par nplete where um that's all I know about it.

5:24 Okay, we'll start with a different problem. um any NPcomplete problem, I will eventually want that this this pi prime poly time reduces to our pi k lesser equals d. Okay, if I'm able to show that then um I can show that I've reduced an nplete problem to my new problem. So that new problem is also NP hard. Okay. So um let that be any such problem. This is standard NP hardness. So I don't have a parameter. I just invent one which is just always one. And um that gives me a non-deterministic polomial time algorithm for this pi prime. That is a non-deterministic FPT algorithm. Well, it's a nondeterministic poly time algorithm. It's just an NP problem. I can call it FPT if I want by inserting f of one. Okay. Uh the point here is to show that this this problem with this useless parameter of just equal one is par is in par NP. Okay.

6:39 Because here's the algorithm that satisfies the parnp completion uh definition. It's a nondeterministic algorithm. It has FPT running time for this parameterized problem. Of course the parameter is a bit of a cheat. That's the point why this fails. Now what does that mean? It is one problem in par NP. Our problem pi is par np complete. So there has to be some reduction, right? Uh so there's a there's a reduction in our parameterized reduction sense. So an algorithm a well that for every instance gives me another yes instance. But yes instance gives me another yes instance. It is computable in FPT time. But really here anything with FPT involving this this constant one parameter is just poly time. And also the new parameter of this mapped instance can only be a function of the old parameter. So it is bounded by some constant. And that's where this d comes from. It's just this this uh function from the reduction g of k. But k is always one.

7:47 Okay. And so we've we've reduced uh our arbitrary npmplete problem to via a poly time reduction to this problem where all the instances I produce happen to have a parameter less than d and d is some some fixed constant that's coming from this one arbitrary choice. But I'm doing this for one concrete nplete problem. Pick your favorite. And I'm doing it for this one one chosen par np uh complete problem.

8:22 So there there's one reduction. I don't know what this g looks like in general but it's one concrete function. So this d is one concrete number for your choice of problems. And then that implies that this is np heart. So again it means p click cannot be one of those par and pmplete problems. So the whole theory doesn't tell us whether uh any of our problems here for which we haven't found an FPT algorithm is somehow in the it doesn't tell us anything about these problems. It they cannot be parplete.

9:09 Okay. So we need uh a better theory. this seems to not have been the solution and um luckily there is uh alternatives that are a bit more fine grained. It will be a two-step story. We'll do another little detour in preparation of the real thing. And this again will fail, but again I think it's insightful to go through this little detour um because it fails for an entirely different reason.

← Video 5-1: Parameterized ReductionsVideo 5-3: Bounded Nondeterminism - W[P] →