CS 627 – Advanced Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-12, 14:34

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:02 We'll now finally apply our new problem, the multi-click multi-colored click problem that we found that is W one hard, W one complete even, um to show some some new problems that are also hard uh where maybe the direct reduction is is a little less obvious. And as a as an example, we'll pick the dominating set problem. And again, dominating set means pick a subset of vertices so that every vertex is either picked itself or one of their neighbors is picked.

0:36 Why would it help to do this multi-colored click problem instead of just some unrestricted click or independent set? Uh the point is that we we can now build gadgets for each of the classes and maybe even pairs because we know we know the the solution is forced to have a specific shape that gives us a bit more leverage to work. And we can pick the parameter K which here in this in this multi-colored click problem is reused for two things, right? K is the number of color classes and also the size of the click. And so both of the number of these gadgets is is a function of K only. I I think that's that's my interpretation for why this is often um easier a bit. Okay, let's see what we can do with this uh dominating set problem. Um let me mention it's actually not complete for W one, but rather it is in an even slightly more general class that we didn't discuss. I didn't even define what it is.

1:37 And it's you have to look very closely at the definition to see why where the difference lies and I think this is not interesting really. There is a hierarchy of these W classes, but I'm not even I'm not sure how strongly we believe that they're even distinct and so on. And W one hard already implies likely no FPT algorithm. That's what I care about So, um, this kind of just for us a side remark, we only proved W hard not complete here for a reason. So let's reduce our multi-colored click problem to this dominating set problem. So we're given some some graph with our color classes. And now we try to build a new graph H for which the dominating set problem can solve this this click problem. Um, and the idea is to have uh these gadgets.

2:34 Let me see. This somehow not copy. If if that's not there, that would be uh a big shame. So then give me one sec.

3:08 Okay. I'm jumping ahead of myself. The picture is later. Um, we um we make these V I's, the vertices that come from the same color class, we'll make those a click. So in a way they're easy to dominate by some vertex and we'll add two new vertices that are not connected to anything only to these two. Like Okay, forget about it. This is uh this the slides are duplicated. This is what I that's why I'm confused. I was looking for the color. Um, so let's just ignore the slide. So same same thing again but with picture this time. Um, here's the picture I was looking for. Uh, we have for each of the color classes, we build a clique. So we copy the vertices into our graph H. But uh I think important we entirely throw away the edges the original graph had and we built entirely different edges in our graph H. That's fine for us to do, right?

4:24 It just so happens that the vertices of the original color classes we do copy. And so each of these form um one of these classes here. And we make that a clique. These edges are are not shown, but uh in principle these edge uh one color these edges all are present.

4:48 Let's not clutter the picture all that much. Let's um assume this is the the blue background. And we have these new extra vertices X I Y I that we add for each vertex class that are connected to everything within the clique, but not to themselves. Okay? So you can pick any vertex either from the color class or this X I Y I. And all the others would be dominated, but X I and Y I not. So these are the dominate if you want to dominate all these vertices, you have to pick one of the vertices from the original color classes. If you pick one of these, the other one is not yet dominated. So you had to you would have to pick both. On the other hand, you can also not pick any of the blue vertices in V I because that would leave X I Y I un- dominated. So these are our kind of uh force or that we pick a vertex from the class.

5:50 Uh the second the pair gadgets are a bit uh less intuitive maybe. Um for every ordered pair of of classes if there's a non-edge in the original graph so um UV here were not an in in my um multicolored graph.

6:10 Then we make a new vertex for specifically this pair of vertices that's connected to everything in in these clicks here and let me get rid of the blue edges for that. So this is clearly showing uh connected to everything except the two vertices that they represent.

6:31 Okay. This will essentially force when we pick a dominating set it to pick these two because then this green one would be leftover. Okay, that's that's the construction. That's the graph we generate our graph H. And the the target size is the same as the click size. The size of the graph is polynomial. You can even do the counting if you want. Uh what's important now is to show that this preserves the yes instances.

7:05 So we want to show the original graph has a multicolored click even only if uh H has a dominating set of size uh K. Now for the one direction, suppose we have a multicolored click. So this is some selection of vertices, one here one here and so on. Uh now we have to show that everything is dominated. So clearly the blue parts are fine. These are clicks, so they're all mutually connected. So all of this here is dominated.

7:39 Uh green is maybe not good. Let me use this. Horrible white uh yellow. This is a light green. Also these are dominated because they're connected with V as well. So all of these are fine. The only things that might be leftover are the green vertices.

8:01 And so um if uh we have some some edge UV that uh a non-edge in the original graph, then it cannot be a UI U J these these two that we selected. So they cannot be some of the red vertices that okay this is gone like here which did I use these two okay.

8:39 So here this would be my VI UI this would be my U J the pick vertices from the click. So it cannot be that these are both my selected vertices because I have to select a click and these have a non-edge in the original graph. That means one of those two like in this case UI is not the U from the screen vertex and so that one dominates this.

9:12 All right? So again if I have a a click all pairs between these two vertices that I selected have to be edges in the original graph. So they cannot be the two endpoints of a non-edge for which we have such a green vertex that would not be connected to either of these. At least one of the vertices is one of the others and this has an edge to the green one so the green is dominated.

9:42 And so all vertices are dominated because that's all the graph has right they're all either blue or green or original. That's the one direction. For the other direction we assume we have some arbitrary dominating set and now we'll we'll use our gadgets to show that this dominating set has a specific structure. And in particular if you look at these two vertices in part I gave this argument earlier already. Uh, their neighborhoods is this guy and all of the I, and for this guy, it's this guy and all of the I, but I cannot pick either of those and dominate the other of these external vertices.

10:28 Um, and because I'm starting from multi-colored clique, I know I pick exactly one vertex from the V I's um in my in my I need to pick This is the other way around. My dominating set has size K prime. So I have to pick some vertex in this V I part plus X I X J to to dominate X I and Y I. I have to pick either one of these or here someone. I cannot pick nothing. And I only have K vertices for K color classes, so they only get one each. And that means I cannot ever pick one of these in my dominating set. Then I would not have enough budget to cover everything. So that's that's uh what this says. The D I are unique. Each V I has one D I that might in principle be one of the blue vertices, but it can't actually be one of the X I Y I. It has to be one of the original vertices.

11:31 And if you pick these D I D J, it's not possible that they are in the original graph not connected because then there would be this green vertex. And if you pick this and this as the only vertices from these sets, the green vertices aren't dominated.

11:53 And so that's a contradiction. Hence these are all pairwise adjacent in the original graph and hence form a multi-colored clique. Okay, so that that can finishes the proof. We've now shown also dominating set sadly doesn't have an FPT algorithm.

12:13 And that's um a lot of classes collapse. You can continue with such reductions and build a network or hierarchy of of other problems, some of which we've seen. This is the the short Turing machine acceptance and independent set we've seen and then multi-color click dominating set. And you see there's a few others that you can connect with this and this is of course only a snapshot. The the book is linked on the website where this is from where all of the arcs are also discussed. I'll I'll leave it with that at this point.

12:58 Again, I think if you look at problems like vertex cover or dominating set, it isn't so obvious sometimes whether this problem is in FPT or not. I think superficially it might well be mistaken that they are the same complexity and here that couldn't be further from the truth. And for that really the reductions help you. If you're running out of ideas for finding FPT algorithms, the reductions help you to show why that might be the case.

13:28 Okay. Some care is needed to lift complexity theory. The reductions we had to use need to preserve parameters. That was the main one. And then there was a bit of a um trickiness to get to the right definition.

13:45 I should say it's it's still believed that this W1 class isn't the same as FPT. So it's a strict inclusion. And that's still open. There used to be stronger support for this because the exponential time hypothesis essentially implies that this inclusion is strict. Now this support is gone because the exponential time hypothesis has been refuted. It doesn't imply anything for this inclusion except that there's one argument that doesn't support it anymore. Okay.

14:24 Like all all the all the rest I already mentioned so that's all on the complexity part of fixed parameter algorithms that I want to show.

← Video 5-4: p-IndependentSet is W[1]-completeVideo 6-1: Linear Programs Example →