Video 2-8: Example of an NP-Hardness Reduction

0:04 We've seen one NP hard problem now and now let me give you one example of how to do this usual step of going from say satisfiability to some other problem and show that that is also NP hard. That's what we usually do if we're guessing that a problem seems hard to solve. We try try to show that it's at least not our lack of creativity but rather some intrinsic problem of of the some some property of the problem and uh um at least we can stop looking for easy algorithms that solve it always in polomial time that's the way to think about it um for the full reduction uh I want to show the reduction from three sat to vertex cover as let's define these two problems first um Reset is almost satisfiability but it has a few further restrictions that just make it uh more convenient and so you will see many reductions starting from that.

1:03 Uh the definition is similar as SAT we're given some formula but it is more restricted. It's in three conjunctive normal form. Uh what does that mean? Well here's an example. Conjunctive normal form means the whole formula is one big and and it's an and of things. These things are called clauses.

1:33 and within a clause I can only have one big or and then the things the or is over is either a variable or a negated variable. These are then called literals.

1:50 literally one variable or a not before. Now this is conjunctive normal form as I described it so far. The 3 CNF adds the additional restrictions that I have exactly three literals per clause and you can prove well first of all the the goal is the same as in SAD. Is there some assignment for the variables so that the formula evaluates to true? Uh here's an example and you can see how it's satisfiable. This is uh only fixing two variables is enough in this case. Uh but if you make more and more of these clauses, the formula gets more and more restrictive and at some point it might no longer be satisfiable. Now what you can prove is that this restriction of taking only three variables per clause or exactly three variables per clause doesn't make the problem much easier. um unlike standard CNF so maybe this is something to tease apart I don't know have you seen this reduction sat reduces to threes again I don't want to okay maybe you don't or not that you heard not that you remember right now let me maybe distinguish two things CNF as the name says conjunctive normal form this is supposed to be something you can put any boolean formula into without changing it at all in the sense that it has the exact same truth value.

3:18 Uh so in this normal form means there exists an equivalent formula phi in conjunctive normal form uh for every formula you start with. And equivalent means really uh it has the same variables and whenever you set the variables somehow under any uh assignment the two formulas are the same. This you can do for conjunctive normal form. This this you cannot do I think with three conjunctive normal form but note that we don't need that all we need is that the formulas that we construct are equivalent up to satisfiability.

4:26 So given any formula that is arbitrary, but I might as well assume it's in conjunctive normal form because that reduction I can always do.

4:49 Let me call this satisfiability equivalent. I don't think that's a that's a term. What I mean what I mean by that is hopefully clear by prime is satisfiable if and only if by is satisfiable. But this gives us much more leverage in the sense that I might add more variables or um I might if this formula is satisfiable I might not preserve all the satisfying assignments in principle. It turns out this is uh this is not an issue. You can keep those but adding extra variables is important is useful. And so basically if you start with a formula with a long clause only informally. How to shrink long clauses.

6:05 So you have these this this clause with five literals. How can I make this true? or either of these three. So I'm adding a new variable. Um, now I should maybe write this. This is a bit stupid the notation. L3 L4 L5. This is a new variable that I'm introducing now. And uh for this I have to add that it's it's true when one of those is satisfiable.

7:02 And here we have to do this um a couple of steps. So uh you'll have to expand this further. Uh but by introducing new variables this in this way you can uh split this long clause up into several and you get rid of literals in the clause and you note that this is not equivalent in the strict sense from a normal for normal form perspective because I'm adding variables it can't be uh but that's enough for the reduction here. So yeah, if if you want to read the details uh there for example in in our book in German I'm sure there's also in in the um the book Aurora Barak that I s cited earlier here for this one uh this will also have the details I'm I'm rather sure uh so as a corollery if we do this uh reduction from SAT to threes and we use the cook levven theorem that sat is np hard then also threeset is np hard and clearly three set is still np in np because I can still guess an assignment So we can use threesat now as another problem on this plateau of mountains of the mountain of problems.

8:42 So we know sat is up here. We also know three is up here and even though it looks like it's more restrictive it only looks at formulas of this three CNF form computationally complex complexity is same. So it's equally hard as that. Okay, second problem is the vertex cover problem which you all know as uh putting up lamps to light streets, right?

9:28 I gave that an optical brush up if you want to revisit the game. I think it looks looks better now. Either way, uh formally it's given a graph simple and undirected. Uh neither of these are super important here, but um let's let's stick with that. Uh and also a threshold because vertex cover here, I'm I'm trying to be somewhat systematic or or consistent with this. The small cap font means this is now a problem. formally a language right is an algorithmic decision problem. So I'm given also the threshold and the question is a yes no question. Is there a way to pick a subset of the vertices at most k of them so that for every edge in my edge set one of the endpoints is picked in a in a concise way to write it because edges are essentially two element subsets of vertices. I can take the intersection between my set of vertices where I put a lamp and my edge and if that intersection is non- empty, one of the end points at least has been chosen.

10:40 So here's an example graph. Here's an example vertex cover. If I pick these vertices, then all edges are incident to a vertex. Right? This is always here.

10:58 For every edge, I can draw a dot at some uh red vertex. And that's all edges covered. Now, it turns out that this innocent problem that I asked you to solve last week is NP complete. Um the proof that it is in VP, which is the same as NP as we now know. Uh that's the easy part that we'll do first and then we'll do a reduction from three. This is I apologize this is the standard most standard reduction that there is out there. It it exists in two variations. So if I'm lucky you've seen the other one and maybe still have to think this one through. Uh chances are you've seen it before. In this case maybe um it's just a refresher. Either way, this gives a good a good example of what these reductions work like. So, I think it's worth going through. The first part is very easy though. I have to design a verifier for my problem. And the certificate is is plainly which vertices do I pick? If you want, you can represent it as an as a characteristic vector for every vertex, a zero or a one, whether I'm using it in set S or not. And then the verifier just goes through all the edges and asks for each of the endpoints is at least one of them in my set. Right? It can also check that I'm by counting very hard problem that my set is at most k elements and so I can clearly decide if a given set is a valid vertex cover for my instance. What I'm sweeping under the rug entirely here is that of course we also have to find an encoding of the graph as a string and pick anything you want. For here maybe the easiest to think about is just an adjacy matrix. It really doesn't matter because you can translate from one to the other in polomial time.

12:54 Um so you can make your life convenient and all of them will be equivalent in terms of the complexity. So we've shown vertex covers in VP. Amazing. But that was the easy bit. Um, for the hardness part, again, think of um, zoom out for a sec. This is the usual thing where where people get tripped up when they do this. Um, for first few times, we're trying to show three set is we're trying to show something about vertex cover. That's our new problem. And so we want to show that vertex cover is harder than threes. So clearly the lesser equal has to go this way around because it orders problems by hardness. Okay, the intuition at least. [snorts] Now finally to show this what we have to do is translate three set into vertex cover. So counterintuitively You have to assume that the new problem is already solved.

14:21 Suppose the new problem had an algorithm. How could you express three sets using this algorithm? How could you solve it with this algorithm? Now since I just introduced both problems maybe new and old is a bit uh a bit unclear here but three set is the one that we're already using that it's NP hard I've waved my hands why uh whereas vertx cover is the new problem that you don't know anything about pretend and so this is the slightly counterintuitive version that you assume the new problem is solved and and do the reduction that way around. Maybe that helps as a minimonic. Okay, intuition express three sets as a vertx cover instance. So what we're given is an instance of threes which is a formula in this uh three conjunctive normal form. At this point you also see why restricting this problem on the left side to some uh special normal form is useful because it means you get more to work with in your your input has a special uh shape and that is making the construction easier.

15:40 Okay. So we have a formula in general it has to look something like this. It's a big ant of clauses and each clause has three things that are ored together and these literals are one of these variables negated or not. Okay.

15:59 Now from this we have to define a graph and a value k a threshold so that it has a vertex cover of that size if and only if the formula is satisfiable. If you've seen this the first time this I always find this this sounds crazy. Why should this even be possible? And it's always a bit hard to explain how to come up with this idea other than playing around with vertex covers and noticing ah I can somehow smuggle in certain things. Let me here just present the solution and you'll do a few more examples in the tutorials. Anyways, it turns out we want to build a graph where the vertices are the literals. So the positions in the formula really and then I have two types of edges which I will have to cover with my vertex cover. The first types of edges are whenever literals are in the same clause. So because I have three positions in each clause these will all be little triangles. These three together there's an example in the next slide but they will essentially form a triangle like this. they're mushially connected and I haven't told you why we do that yet. It's just a definition. Then there's other edges which connect any positions where the corresponding literals are the same variable but negated.

17:24 Okay. And then the claim is if the formula is satisfiable, we should find a vertex cover of exactly 2n vertices in this. And that's an if and only if. So let's look at an example. Uh here's a formula in our three conjunctive normal form. It has four clauses. So I have four triangles. That's for the four clauses. And you see the dark blue edges are just connecting these uh literals in the in each clause. And the green edges connect whenever I have x1 not x1 x not x3 x3 and so on. And I have all the green edges where whenever I have a variable and it exists in a negated way. For example, x2 occurs more than than once. I have not x2 here and two occurrences of x2.

18:20 Now think about what this conra constrains um our solution like. Uh before we formally go a bit more structural through the proof, each of these triangles you need to cover. I'm sure you figured this out in the game as well. Any triangle you need to pick two vertices to cover all edges. There's no way to do it with one. Also, um for each of these green edges, you need to pick one of the end points. Also obvious now I'm picking the size, the target threshold for my vertex cover extremely tightly. n was the number of clauses. So here four, right? So I'm allowed to pick exactly eight vertices. That's exactly two per triangle. Otherwise, uh I'm already over budget. So um the the question reduces to this this more refined question. Can I pick exactly two vertices out of each triangle? Or more naturally maybe to think about it, which which of the vertices can I leave unpicked?

19:30 And the one I leave unpicked is actually the one that defines the satisfying assignment. And all I have to check is that the vertices that I I uh leave unpicked don't contradict each other. And that's what the green edges do. If I somehow decided I'll take I'll not take the x2 and not take the not take the x2 and not take the not x2. These are my two chosen vertices in these two triangles. Then that's not valid because they're connected by an edge. So that would be left uncovered. Okay, let's go through this a bit more structured. Um I think the intuition is what I've written down here. Um so let's look at a bit more structured what the proof should be. It always is an equivalence statement. So it has two parts. The two uh um sometimes called soundness and completeness but um is really just two implications. The first one says if my formula is satisfiable I have to show that there is some vertex cover.

20:38 If the formula is satisfiable then in every triangle every clause there is one literal at least one that is true otherwise the formula wouldn't be satisfied. So um take the other two vertices and uh put that in our set s and I claim that that's already it that solves that gives a valid vertex cover. So clearly this covers all the claws triangles, the blue ones because I've picked two vertices out of the triangle. Any two do the only thing is the green edges. But if any green edge remained uncovered, that would mean I have an x and a not x both in my set of literals that are true. And that can't be because I started with the satisfying assignment. Okay. So the green edges must also be covered. Hence all edges are covered and so I get a vertex cover of the right size. For the other direction it is always easier to not do contraosition but rather say suppose the graph has a vertex cover then you have a concrete object to work with. So suppose I have a vertex cover of size at most 2n in this graph. As we've already looked at the graph is so restricted that it actually has to be precisely that size. there's just no slack at all because I have to pick two classes from each triangle.

22:07 Uh that's the best I can do. So this already is a minimum vertex cover. We don't need that though. This is uh is not part of the proof if you like. Now we're going to define an assignment by essentially picking the non-picked vertices. Well, making them true. So if the variable is positive you put it to true. If the variable is negative then you put it to false. This cannot be uh contradictory because any non well-defined part where set a variable both ways would have uh a green edge uncovered.

22:50 Any two literals that contradict each other are connected by a green edge. A vertex cover has to cover these green edges. So I cannot have both end points uncovered. It's kind of the same argument uh back and forth.

23:06 But if you write it down separate for each d for the two directions, it becomes clearer why things are working out. And clearly this this has to make the formula true because um from each of these uh classes the one I don't pick I can set my assignment so that it makes this literal true and so every clause is set to true or evaluates to true. So my my formula is satisfiable and and note that I I've done actually more right. I've established a correspondence between satisfying assignments and vertex covers. I can not even say yes goes to yes. I can even show what the solution turns into in the other problem. This is stronger than what we needed to show but often works in these reductions that it it isn't just a Yeah, it it often works um but it's not guaranteed.

24:15 So it often works that you can also transfer a solution to a solution to the other problem as the the actual certificate. Okay. The third point that we have to argue is that we can do the reduction in polomial time. We've now shown if I can build the graph the way I described it then it satisfies this equivalence. Now you have to you have to say that you can find this in polomial time. This in this case is easy. I've essentially written down the formula how to do it here and you can uh say if the graph is represented as an adjacy matrix you know the number of vertices that's 3 n you create those and then you set one bits for each of these uh combinations of literals so way faster than just polomial but that's sufficient So we can do it in in quadratic time if you care but uh on a on an actual machine or a Turing machine who knows what degree you need um but it's polomial as always shown this reduction reset polomial time reduces to vertex cover because three was NP hard vertex cover is also NP hard because it was NP hard and NP and in NP it's NP complete more examples in the tutorials.

25:50 All of these are kind of cute puzzles because you have to come up with an idea of how to abuse a problem to encode something different. And in a way, this is really the essence of NP hardness. There is always some sneaky way of encoding a satisfiability problem. That's precisely it and is also in a way all there is to it.

26:40 is this graph that the formula a couple of slides back describes and well that's the function and that it's polomial time computable is what you have to separately show >> that's also why you meant that it's subjective because you only can do the covers for graphs with this tri >> that's right it's not subjective you see how you get a rather special kind of graph class here so this also means we've actually proven more than what we claimed we've proven that vert.x cover remains hard if you restrict it to this weirdo graph class of triangles with some some cross edges. Now if this is a natural like if this is worth spelling out as a special case is a bit unclear uh you could exactly say what these graphs look like. Sometimes this is indeed useful.

27:57 And I'm not going to even try to give this a name. It's the blue triangle, green edge graphs. But who knows, maybe you'll find some clever problem tomorrow where the reduction from precisely these graphs is easier. In which case, you could do it with the that special statement and not from general vertex cover. Maybe.