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

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 The P short Turing machine acceptance problem is the turns out natural complete problem for this W1 uh complexity class. Now that we've established that we can use that to prove hardness for more natural problems and we'll do it in two steps. First a more lengthy proof that connects it to independent set of all things and then from there um okay three steps are light. There's another intermediate problem that often makes makes life easy. But then a last example of a typical reduction for new problems that you might want to do if you if you're asking yourself for some new problem is this potentially hard to find an FPT algorithm. Okay, the first thing we'll show is that you can reduce this this pore touring machine acceptance directly to independent set. And um what that means is that we have to use independent set to simulate the execution of an arbitrary touring machine. Um we'll see how that works uh as a corollery and you'll well see exercises I think I'm not going to say much more about this. You can directly get this for some other problems.

1:18 How do we do this proof of this theorem 513? uh we'll use independent set to encode computations of these Turing machines and then there will be one that fully satisfies us meaning it is large enough if and only if the the during machine has some accepting computation that has to be the plan nothing much else works um so uh we'll make a few assumptions but let me first recap um the useful way of thinking about computations of some Turing machine. We talked about this in unit two in in uh length but it's a while ago. So think about um a large table that gives you the full computation across time. So the time ticks from row to row. We start in the first row and what the rows contain is uh the contents of the tape at this point in time and one one cell is highlighted. That's the position of the readr head. Okay. So I'll keep this as as formal as this table is. It's just by example and there's some way to encode that this is red. You can invent something. That's that's what we do.

2:31 Then um from each time step to the next the head can move somewhere. And of course the tape contents can change but only at the position of the readrite head from the previous position. So maybe here this is now x1 prime but this still has to read x2 and these are all still the same. Um maybe I should have put a concrete computation. This is what a Turing machine can do. The only freedom it has because it's nondeterministic. There may be several potential successor rows uh given the same row at the top. A single computation is one such table but there are potentially many tables possible. In general also we know the number of rows is precisely our parameter K. Okay, we're only simulating this Turing machine for that's why this short here for a fixed given number of steps and either it accepts then or we say it doesn't we give up. Now um to make life a little easier to formulate things, we assume that we we tweak our Turing machine so that after the uh it first reaches an accepting state, it just stays there and and keeps saying I'm done, I'm done, I'm done and I'm happy and I'm happy and happy. Yeah.

3:43 So we can uh restrict the problem to being to precisely check in this last row in row k are we in an accepting state. Uh this is not a restriction just an observation. The time k means we can only walk as much to the left and right as we have k. So uh the table here is is bounded in width. I can only really visit k + one different uh positions.

4:14 Um okay so roughly k squared cells in this table that's um what we what we need for now which you may note is only a function of the parameter not of the size of the touring machine right the input here is the um encoding of the machine so unlike usually you think of the touring machine being fixed and then the input is large here it's the opposite in a way we have uh the machine can only run for k steps. So also it only reads k parts of the input. So the big thing is the machine it might encode a lot of cleverness in its states. Um and k is the the time. Okay.

5:10 Now, how do we encode this computation as an independent set? The key idea is all in this picture and then the rest, the next couple of slides, we're going to puzzle it together so that it it works in all cases. Uh the idea is to have one of these cells. We're zooming into one of these little boxes here. And inside these boxes, we have vertices of a graph. And the vertices have um there's only six drawn here is is a a lot wider in general. We have vertices that signal that um this cell contains a certain letter. That's the subscript. But also it encodes that the Turing machine's read write head is not at this position at this point in time. So each of each of these cells has a certain time, right? Um it also has a certain position J and so the the states the the top vertices say at time t and index j in the read write tape um I have this uh sigma. So what I mean by is if you include this state in your independent set this vertex in your independent set it's supposed to encode this semantics that there is this certain character at this point in time but the readr head is not at this position of the tape and then the other vertex is kind of kind of the same you hold a certain value but then the uh read write head is here um you also encode the state that the machine has at this point in time. So you have many many copies of these B's many more than the A's because you have one copy of of B for every combination of these parameters quite a lot. Uh in particular the state space could be huge. This is depending on the input size N. So the graph that we construct will be large not FPT bounded. It's not a kernel.

7:15 Um right. So uh the size of the states could be uh let's equal is maybe we need to encode the entire machine but this can be much much larger than K. So we have potentially many of these states B also I think the alphabet is also maybe large um okay we'll be fine not notwithstanding we also encode in this vertex what is the next transition we take from uh this point in time forward. Okay. So some um the transition of course again is uh containing the current state and then the new state the new simple rewrite and the direction we move the read write head. So this is a lot in this lower part. How many really um I mean we we'll count it later but uh it's the the cartisian product of all these sets but each of these is bounded in terms of the input size. So it's some horrendous large polomial but it's not more than polomial in the input size.

8:30 Okay. Uh we also will make this a click so that out of each cell every independent set can pick at most one vertex. So it's kind of really a decision which uh any any uh encoding must must pick one of those choices. So it's a unique uh encoding. Uh a few corner cases. Um at the very beginning of time we have some constraints and at the end we have some constraints. So we just get rid of some vertices that we don't want. For example um all the vertices that don't encode that we have the appropriate position of the input in the tape at this point we get rid of because we know what the initial input of the tape is. Um also we know where the initial read write head is it's supposed to be in position one. So uh all the other B vertices we just delete from the graph. Um second yeah same for the tape contents. I think this is um rather easy to see what you would have to delete in the first row. You make it mirror or only keep the vertices that correspond to the initial configuration.

9:40 And for the last row, we delete all the states that encode states that are all the vertices that encode states that are not accepting. Okay? So there's just no choice to pick those. So if if you in the end pick a single vertex from each cell, the meaning should be this is a valid and accepting computation. Uh here's an estimate for the size of the graph. We have that many cells, rows and columns. And for each cell uh you have to have one for each symbol here. That's the ace. And then we have um the size of the transition table roughly gives you this this delta. Uh and that already is subsumes all the parameters because a a single this is one one arc in the transition diagram or one one entry in the transition relation. So uh it has the the first the state it starts from this target state and this old symbol new symbol and movement this is all supposed to be encoded in this this kab delta again importantly this is polomial in the input size so all of this is polomial so I also assume it's not hard to produce these and so far I guess that's true uh the parameter the size of the independent set we want in the end is the number of cells we want to pick precisely one vertex from each cell and that is a function only of the parameter okay so we're on on route to showing a proper FPT reduction let me also point out from just these these clicks within the cells I can never ever have an independent set with more than kvert k prime vertices so it'll be as often with these reduction questions a question is there any independent set where I can pick a vertex in each cell and if not nothing will work I'll not reach the size k prime okay so far we have independent cells and that doesn't form a computation yet right so far I can easily pick one vertex in each cell and they don't have this proper meaning we have to enforce this to do that um here's some abbreviations that will be used uh these are just sets of vertices that summarize or take take the union over a whole range of vertices. Uh all the A vertices and all the B vertices in a cell that's these two where I keep fixed the index of the cell but then anything else just is lumped together.

12:21 And for the B vertices, um, I distinguish a bit more. There's the B vertices that keep the cell and the target the the start start state and the old symbol fixed and sum up over the or take the union over the rest. And similar um, if I only fix one of the two components. I hope um, the notation is is intuitive enough that you don't have to memorize it. I'll come back to it. Okay. Now this is what I already said. Um we'll make sure that each cell within is a click so that I can only pick one vertex.

13:02 Second will also form clicks among the elements of the row namely for all the B vertices. And this is encoding that the read write head has to be at one position only. It cannot be uh in several places.

13:22 That's the first part. That's I think the easy rules, right? This is um rather clear what they do. The next thing is we need to encode that we do a a proper transition. We already encoded in these B vertices what the next transition should be, but so far we've not enforced that the next row respects that choice. So, uh that's what we have to do next. Um, okay. The the first one is a different part. Let me maybe explain the the head part first. This is maybe the most complicated. Let's do that first. If I'm currently in one Bvertex in the row above that tells me what state I'm in and what symbol I read here. So, I know what kind of transitions are possible and the state fixes which one I take. So there's a a unique successor state Q prime for the Turing machine and a unique symbol that is written into this cell of the tape.

14:23 So um I put these these green edges the the the dashed ones are non-edges. These are not edges of the graph. They're just shown to emphasize that there's no edge. Nothing to see here. um and the green edge is is such that in the same cell I'm writing this new symbol uh sigma prime. So here this is an example. Okay, this is one specific transition where I move the right head to the right. So in the same cell I can no longer have the right head after this. So um I put an edge between this B delta and A sigma prime to show um sorry the other way around. The arrows are the compatible choices. These are the non-edges and the red ones are the forbidden ones. These are the edges of the graph. We're doing independent sets is the other way around. um I want that I can if I'm in this state last time step I want to pick this a for the independent set because this green arrow is essentially saying this is what happens in real the real computation so I want at that position the to see the new symbol that's written at this point and because I know I'm following this transition where the head moves right it is no longer in this column J it has moved to the So in the in the cell one to the right I go to a Bvertex to signal the read right head is now here and I do this this here I have uh several options of non-edges that I can pick from because the next transition isn't fixed yet. I go to all possible ones. I only go to all those that have the right state Q prime though that um comes from my uh transition here.

16:15 So I think this is um conceptually not that hard but is very annoying to write down fully formally. You know everything about the machine in the previous time step. You know where you currently are, what you've read and what you want to do as a transition. All that's left is to put non-edges to all the sensible success successor uh vertices and put forbidden edges to everything else. So we'll have a lot of edges across the levels but not more than polomial. Okay, formally written it is just this um but I think it's a bit hard to digest.

16:56 Um another thing we have to enforce because otherwise it would be lost in the graph is that among cells where the read write head is not in the previous step the symbol doesn't change. So you need to forbid going from a vertex up here and picking a vertex down there that are inconsistent.

17:19 So you make the a vertices up here adjacent to all vertices in the next time step um that have uh a different symbol. So you you make it adjacent to all others except for those where the same symbol sigma here is encoded. Right? for these it's allowed to pick them because nothing has changed here. Okay.

17:59 Okay. Uh so after after doing this um the B vertices is joined with all the A vertices in in the next row. You have to choose a new bvertex in the row below one left one right or strictly below and at most one uh uh t and there must be uh exactly one vertex where where you pick the right successor states. Okay, that's all the edges that we put in. So again, the arrows, these are non- edges like it's written for the dash ones, but maybe be explicit. This is all the construction. Okay, so for each of the cells we have this large collection of vertices and we put edges whenever something is forbidden to be combined and then an independent set cannot combine them. What's left to show is that this works. So we have to show that if this Turing machine within keps accepts the input we're given, then the graph has an independent set of the pres of the prescribed size and vice versa.

19:26 So it's always uh two implications best to show a separate uh but it's actually rather easy here. So with the the long setup if we have an accepting computation then um there's some configurations that we go through with the Turing machine again the computation is nondeterministic so it's only existential there may be many but if if there is one that is accepting then we have these configurations from the configurations we can select for each cell the corresponding vertex that describes it in this case we can really appeal to the semantic picks of the vertices in every in every row T. I can pick maybe write this down a bit.

20:24 We pick this vertex T J with our delta of the head in this configuration CT. Uh back in unit 2, we encoded these as words. So that you you could be more formal about this. Maybe it's not not helpful to do that. Uh here there was the configuration is this the string, right? Where the tape content left to the of the head comes first and the state and then the rest. So you could say it's the the length of the prefix up to the state. Um, and we know what the next configuration is. So we can work out what the delta is. So we can pick the right vertex.

21:31 And uh we also pick for all the other cells in this row. Uh let's call this uh okay whatever j prime we pick the vertex a t j prime sigma where sigma is the tape content and claim is that this is an independent that and this is essentially by following our construction. We always pick vertices where we specifically had this green edge of having no edge in the graph. So it forms an independent set also because the final state has to be an accepting one. It's one of the vertices that we did not delete. So it's still there. So this hopefully all checks out.

22:42 for the other direction. Um suppose we have an independent set in this graph that we constructed and it has the right size k prime. Then uh we have to go through um our our uh properties here by this property I inside clicks I can have at most one vertex in each of the cells.

23:10 So uh because K prime is the number of cells, it's exactly one vertex per cell. With the boundary deletions, these vertices cannot be selected because they're gone. So row zero is the initial configuration and row K has an accepting state, right? And then by induction, if you want, you can show row T corresponds then to some configuration that the machine could have could have assumed at this point in time. And for the inductive step, you use the other uh properties. Um the row clicks imply that the tape head has a uniquely determined position. So this is well defined. And then for the state and transitions, uh this is a a valid way. Uh if there's a an independent set, it has to follow one of those green edges, the non- edges. So you can pick a corresponding transition and make uh simulate what the machine would have done or that the transition and get a configuration CT + one that is valid. And so if you do that all the way through, you end up with some accepting state again because we deleted the other vertices. So the machine accepts.

24:30 Uh overall this is a polomial time construction even though this graph is um rather large polomial polomial in input size and the new parameter that's the crucial bit depends only on K the input parameter namely the number of steps to simulate so it is an FPT reduction we've reduced from a W1 complete problem to our new problem P independent set hence uh P independent set is W1 hard and completeness is easy to show. If you take a step back and look at this um lovely construction with the graph over this this cells of things, you could ask yourself how specific that even is to this FPT. And so uh a simple yes no question in this case. But the point is to prompt you to think a bit about this construction again or maybe also feedback if it was understandable to follow this construction.

25:39 Yeah. So you you should see the question. Um I can go over to the to the proof slides maybe more useful. Um, I think this is maybe the overall most useful page because it has the visual cues for all the relevant definitions. I think again worth worth to take a minute to think about this.

28:30 And given that we're a small group, we can also discuss a bit. And the point will be either it just works or there's something some reason why it wouldn't work. Yeah.

29:15 So maybe um uh more generally speaking if I have a reduction from a problem A to a problem B that's an FPT reduction is that also a polomial time reduction from A to B. We've seen examples for the other direction where the answer was no because we could have like for um for vertex cover an independent set. Uh maybe the reduction is easy to describe in polomial time but the parameter is in the final result is is n minus k or something not just depending on the input parameter. That's one thing for the other direction how it can fail. How about um from an FPT reduction to poly time reduction? That's kind of the question we ask here. Although um yeah, let let me let me show the one vote. I guess you can guess. Uh I would guess that's that's your vote. Um I think in general the answer has to be no. An FPT reduction is not necessarily poly time because it has FPT time. It might take time exponential in the parameter and the parameter could be large in general. So then it's it's incomparable as a notion between reductions.

30:34 Um now in this specific case it's actually true there is no no exponential part in K. It's um it's polomial in the input size. we create this this rather large graph with all its its edges and so on. Fine. Um and uh the the Turing machine is part of the input. So the alphabet and the state space all of this is essentially linear in the input size. Um so the graph can be a high degree polomial in n but not more and the rest just works.

31:12 So uh if you want we can we can treat this this proof uh sorry I didn't even show the result on the screen. Uh you could see it on the phone if you had it open. Um this is an alternative to proving SAT as the mother of all hard problems. Right? You could also have picked independent set out of all random graph problems if you wish. Now this shouldn't surprise you at all of course because we know that by chaining polytime reductions you could have picked any nplete problem and it would have eventually worked to encode a Turing machine has to but I think this construction is not even that crazy it's um somewhat somewhat intuitive and you can maybe debate whether the original cook levian construction is even better than this or not encoding the computation as formula Uh well I I think it's unclear which is more natural. This is um up to taste eventually.

32:20 I found that kind of cute that you have this loop back and an alternative proof for cook leaven. I mentioned I managed to smuggle in you know the little choice.

32:36 Let's have a look at a different problem. Um this independent set is one sensible quest problem where you could ask yourself the question if it is NP if it is in FPT and the answer is probably not. We don't know for sure because W1 could still be the same as P but we don't think or FPT sorry but we don't think that's the case um for some other problems and uh the kind of goal for today will be to look at dominating set somewhat of a relative of vertex cover right instead of covering the edges with vertices you have to cover the vertices with vertices feels not so different and you can probably wrap your head around some other way but uh dominating set is a typical example for W1 hardness reduction where it's not so convenient to start just with independent set uh you'll show okay maybe this is um in the exercises you'll do the very hard proof uh that click is W1 And so independent set and click both are W1 hard.

33:58 So we can try to uh use these as as basis for reductions. Um for further reductions, it turns out that uh an artificial intermediate problem is much more natural or much much easier to work with. And that's this multicolored click problem. that's defined here. It's just a graph where each of the vertices has a color, one of one of k colors and uh the parameter is the number of of colors here. And you're looking for a click that picks a vertex from each color class. So it's still asking for clicks, but it's restricted to have one vertex each from each class. So like in this illustration, the vertices are grouped by their color and you have to find some some uh click that combines one vertex each. Okay. Uh you'll see um in a bit why this is convenient to start a reduction from this. First we have to show that this multicolored click is also W1 hard to be able to use that.

35:06 Uh so that's that's the next little reduction that we do. Um first let's show it's actually W1 complete even. So the in W1 part is the only place where you need these nams again um at the level of abstraction that we discussed these constructions maybe not that bad. What an N RAM can do is make f ofk guesses or g of k guesses. Here we just pick K and uh what it can guess is some polomial choices. Here in particular it can guess a subset of vertices and then you can uh check whether that's a click that's the same as in the standard click problem. Here we restricted to the guess restrict the guess to be one vertex from each set. Right? This is the only difference. So of course the same kind of trick gives us an tail non-deterministic kapa restricted n RAM.

36:10 Let's uh write this again. So that that suffices to prove that it's in W1. The hardness is more interesting. And here we'll use that you've already done your work in the exercises to show that P click is W1 hard. And we'll do a reduction from there. And the reduction is rather simple. you just take K copies of your graph. More specifically, um given a graph and a threshold K, we make K copies. So we have uh for every vertex K copies just as the the cartisian product. So we have pairs of vertices and numbers. And then the edge set of our new graph is edges in the original graph, but we only connect between color classes. Vertices in the same color class just don't get an edge. So unsurprisingly, a click in this new graph will be multicolored because there's just no edge between vertices of the same colors. This is a very simple reduction.

37:13 Uh, nevertheless, let's convince ourselves that this works. So if you have a multicolored click in the resulting graph, it has to look like this. Some vertex from color one, some vertx from color k. Uh so I I just assign them so that the second component gives me this this color class and then uh there's some some vertex from each class. I just call these vi uh and these are all pair wise adjacent. So in particular um because we assume here I guess standard assumption if it's not written different then that the graph a graph is simple. So if they have an edge then these vertices are all different just because we don't put an edge between uh there's no ui vi edge. No uh ui uj edge.

38:20 This is never in our edge edge set. And specifically if the graph has no edges then from this construction it follows uh which means I have k vertices each of them has an edge in the original graph otherwise it wouldn't be connected in my multicolored graph hence the same collection of vertices v1 up to vk is a k click in the original graph uh for the other direction assume you have a kclick in the original graph well just form the multicolored version where for each vertex X here this is give me these vertices in some arbitrary order I don't care this graph is entirely symmetric uh order the vertices from one to K and for vertex I pick the color I version then this has to form a multicolored click these had all edges present here I never pick the same color twice so I have the corresponding edges in E prime also the construction is polomial time I'm I'm blowing up my graph by a factor at most n that grows a bit but it's polomial and the new parameter is the old parameter so clearly an FPT reduction okay so this is not a hard proof the reason why it's convenient is that many many reductions essentially do the same first step they start from click or independent set and then do this construction let's factor it out as a as a lema first and Then you can use it and kind of also use this this trick as a a standard um standard technique.

← Video 5-3: Tail-Nondeterminism - W[1]Video 5-4: W[1]-hardness reductions →