Video 5-5: Recap & W[1]-hardness

0:03 So a very brief recap of the parameterized hardness part that we've seen. Um we went through a bit of a detour to find the right definition. And basically I wanted to give you uh some some reasons for why the definition may be um not not the most natural one that you could come up with for this uh class W1. But really the uh the end of the story is that W1 is the class that you want to show reductions against.

0:33 Um there's a very easy way to show that a problem is in W1 using either the kstep halting problem or just from the definition that we used with this tail non-deterministic kappa restricted non-deterministic random access machine which is a long term but all it says is you do the usual kind of RAM program and you're allowed a little bit of non-determinism but only in the last f of case steps and if you can solve your problem with such a machine non-determinism only at the end and only for some amount of time that is bounded by the parameter then the problem is in W1 equivalently you can uh reduce it to this uh holding problem for for a touring machine I think the other is is a bit more natural and then we've seen there are further complete problems for this and uh independent set is one of them as well uh which followed from this uh the specific weighted satisfiability problem. Now the uh slightly uh annoying part here is that we couldn't do the full proof because it uh I looked into this again and it it just gets um into a a lecture on logic and um I felt this is not not where we want to go. Uh there's more direct ways to prove this.

2:02 [Music] um which um you can find in um in seed al in this uh book that uh is referenced on the website as one example. What else you could you could have as problems that uh might or might not have in fixed parameter tractable algorithm was this partial vertex cover problem where it's like vertex cover but now you're also telling at as part of the input you're telling me how many edges I have to cover. I get to choose which but you get to tell me how many. And it turns out this makes the problem really hard. Uh it's a W1 hard problem. So with this parameter it doesn't seem that there's an FPT algorithm and there was a a reduction from independent set that we went through over quickly. Basically by adding these blue vertices we make the graph regular in terms of the original vertices. And so um if you had a vertex if you had a vertex cover in the original graph uh you cover exactly these uh disjoint edges and that's an easy number to count. And if you give me that count that's the the only way to cover that is by picking um sorry these uh not very cover independent set by picking an independent set in the original graph.

3:24 Now uh to kind of wrap up the story a bit what I I never had on the slides but I think is uh important to state and I think verbally I said it. We don't believe that W1 is um uh is a subset of FPT or is the same in in fact the widely spread belief is that it is a superset but a strict superset. So problems can be in W1 but not in FPT which means they may not have an FPT algorithm right although they're still solvable with this specific non-determinism at the end. Uh and indeed you can tie this to um a different hypothesis from complexity theory that will um come haunt us in the next section. Uh the exponential time hypothesis that's what ETH stands for which is fairly widely believed. It's stronger than N P not equals NP. Uh but it's um I guess there's there's more more evidence for it than for some others.

4:34 And so this also implies if if this exponential time hypothesis is true, it means that these two are separate. FPT is not the same as W1. So really reducing problems to a W1 hard problem makes it very unlikely that it has an FPT algorithm. I wanted to say that a few times more to be super clear. Okay. uh we've seen reductions need to take the parameter into account but there that's actually the part where the natural definition uh just works. You have to make sure the parameter stays bounded in terms of the original parameter and that's pretty much all that you have to take uh care of. It might mean that for some reductions between problems you need you need to come up with new ideas. uh what we didn't dig into is further details of the complexity theory. You can further structure you may have wondered why this is a W1 and uh you can have other parameters there. Uh but the classes only really become different types of uh complexity classes or to define them properly with this general T you need to define them via some specific property of the formulas that you do weighted satisfiability on. and is is a lovely piece of theory but for the message of does a problem have an FPT algorithm or probably not it doesn't add any any extra punch uh essentially um is usually the dichotomy if you can find an FPT algorithm you know what what you're doing and otherwise you can probably show it's W1 hard because that's the easiest of the hardness classes all of these uh these WT classes are even even bigger Um, so W1 hard is is usually enough. Um, as an example that we didn't look at is the dominating set problem. It's a bit like vertex cover, but now you're picking vertices to cover all the vertices in the graph. Either you pick them directly or you pick one of the neighbors. That's a dominating set. And um, you can show that it's W1 hard, but actually it's unlikely to be in W1. Uh, indeed it's W2 complete.

6:48 Uh probably that's a strict inclusion again but in terms of the the message as an algorithm designer it doesn't make a big difference. Just don't bet on finding um an FPT algorithm for this problem. Exactly how hard it is uh maybe not so important. Okay. Any any general questions on on this part? uh so lower bounds in terms of uh parameterized problems via reductions particular to uh these W1 hard problems uh you'll have uh some on the upcoming exercise sheet some more uh examples of this so uh hopefully after that at the latest it's clear um and what I mentioned earlier there's this book cadal that's uh parameterized algorithms I think is the title they have um a chapter on on reductions as well even though this is not their focus they focus on the algorithmic uh techniques but they have some uh some chapter where they do a few reductions in full detail so if you'd like to see some more examples you could go there and you see there's there's a few uh that we've seen partial vertex cover and independent set and dominating Being said what I just mentioned uh here and different reductions between them and I will leave it with that.