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

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 Now in the next unit we'll look at hardness results that may uh hint that it's not just our inability to find some algorithm but there's some underlying structure that makes this say unlikely or maybe even impossible. This is uh at the very least it will be based on the assumption that P is not NP otherwise we can solve all of these problems efficiently. uh but maybe we can say a bit more and I want to take you a bit through the journey. There's there's different notions that you can come up with and the the ultimate answer let me give that that punch line away will be this this notion called W1 hardness but it's a bit awkward the definition I think in isolation doesn't seem to make that much sense so I want to go quickly through some more sensible alternatives where you would say this is natural this is how we would um generalize the notion of NP hardness but it turns out to be not helpful. It's not that the theory is wrong or so. It's just not capturing what we want. But uh to motivate a bit why we get to this last part, I want to take this detour. So the goal of the whole unit should be to try to prove that somehow we cannot find an algorithm or in the complexity theory sense that a problem is not in FPT.

1:24 And we've seen one example missing from the list, the clique problem. And that will be kind of the uh the guiding example in in this unit. You can of course um do this this n to the k times polomial which of course is swallowed by this term. Um this is easy to do by going through all the subsets but it's not an ft runtime right. Uh so there seems this is this is the obvious brute force and um things that worked for say vertex cover this very easy first example pick any edge and one of the end points has to be part of the solution this doesn't seem to work here for clique of course you can say for every vertex it's in the solution or not but that's a there's n vertices not k so it seems not clear how to make progress on um rem removing the n from the exponential part. So maybe this is just not possible.

2:30 It certainly is possible in case all of this collapses if p is np. So it will be conditional but maybe I'm a bit stronger than just uh just we can't do it. Okay. Um as always there will be some uh property conditional on the hypothesis. We'll try to mostly work against P not equals NP because there we still have faith. I think uh is no no um real progress on proving or disproving this. Uh for some other hypothesis, there are results and maybe un uh somewhat surprising or or counter to what people expected, but maybe the expectation was just a bit too um blindsided or too optimistic on the negative side, too pessimistic.

3:25 The first notion that we need for all of this if we want some theory like NP hardartness is a notion of reductions and it should be some something similar like polomial time reductions. You take an instance for one problem in uh not too much time you turn it into an instance for the other problem and you preserve yes instances. But a general polomial time reduction may not work so well. And let me show you first an example that we've seen.

4:04 So here are um here three problems from our list of np hard problems. Vertex cover independent set and click. And uh on essentially the same graph they have a very intimate relation as is not hard to see. If you have any vertex cover like the vertices here they must cover all the edges. Okay. But that means the complement set all the other vertices must form an independent set. So this is a very very close relationship between vertex cover and independent set. But what happens to the solution size in this tiny graph? It's a bit harder to see, but this it could be just these three red vertices. And I have a gazillion little leaves here around this vertex three. That would not change the size of the vertex cover, but it blows up the graph size. But for the independent set, each of these leaves is part of the solution. So I might turn a tiny vertex cover into a humongous independent set.

5:02 That is not what we need for keeping somehow a parameterized problem. similar. I would potentially turn an instance with a small solution size for vertex cover into an equivalent problem for independent set but with a huge solution size. There's there's a problem lurking there. And then a click and independent set are of course very similar in that an independent set in a graph is a click in the complement graph where you have all edges that you don't have here. So this uh that's why the example is rather small. Drawing an example where both the graph and the complement are still looking not too crazy. You have quadratic edges means you can't have too many vertices. But here you see precisely the edges that are missing here between the independent set are there. So this has to be a click. But of course the the difference with vertex cover remains. A vertex cover here could be small whereas the click in the complement graph could be huge and vice versa.

6:06 So there is a polomial time reduction in all directions between any of these problems. They're all nplete and the reduction is easy. Right? you either flip the graph to the complement or not depending on whether click is involved and you may have to adjust the threshold for your decision problem. uh but it's easy to do a polomial time reduction and yet it seems a bit useless also thinking of the two the three problems vertx cover we know is an FPT and these two maybe not so if there is a reduction from any one to all the others in the usual sense probably our normal sense of reductions is problematic that's uh that's the whole point of um of this new definition and we should do something with the parameter obviously. Yeah. So what's the natural thing? We start with an instance for one problem which has a certain parameter. We generate a new instance for the new problem that also has a parameter. So the natural thing would be that this new parameter is bounded in terms of the old parameter but not the old input size.

7:19 And that's what what is called a parameterized reduction. So formally I have two problems both parameterized right um all of these problems let me just repeat this because um I've changed notation mid midm module a problem formally a decision problem formally is a is a set of allowable instances that I'm looking at and that is the yes instances which are a subset and this sigma will often ignore it's just the alphabet that we encode everything over an FPT reduction from this uh pi 1 to pi 2 written like this uh needs needs some algorithm to turn an instance from L1 from the first problem to an instance from the second problem and then for all problems for for all instances of the problem we have to have that the yes instances is preserved if it's a yes instance in the first problem the mapped input is a yes instance for the second problem um we can be a bit more generous in uh how long it takes to turn one input x into a of x. It doesn't need to be polomial. It's enough if it's ftt since we're chaining together um ft algorithms that's that's uh good enough is a bit weaker. Often we don't even need it.

8:38 Um and so what this means is is a can have running time some function that we already use f I guess not. So we could write f of k1 time n1 to the constant if um if n1 is the size of x and k1 is the parameter of x of x, right? But the crucial point is the last one. We want that the parameter of this new mapped instance is bounded as some function again but only in terms of the parameter of the input. Okay.

9:32 And now you see um that if we compare a vertex covered independent set that um I've shown you on the animation that it's a bit hard to find such a parameterized reduction. We can find a normal reduction independent set reduces to vertex cover. But here this this fundamentally includes the size of the input. So the new parameter would be n minus k or something like that. And that's not a function just of k. So this doesn't imply the the normal reduction doesn't imply anything about FPT reduction and so doesn't tell us anything about independent set being part or not part of FPT.

10:23 Uh we can give a a reduction between the two um more related problems independent setting click and both directions. uh you just take you just generate the complement graph that is polomial time in the input size but the crucial part is the parameter of the new mapped instance is only a function of the old parameter it's here even the same okay so a very easy example this clearly means if either of the two has an FPT algorithm then the other one has one as well uh and also vice versa if if they don't have one. Then the other one also doesn't have one.

← Video 4-10: InterleavingVideo 5-2: Nondeterministic FPT - para-NP →