Video 6-5: LP-based kernelization

0:04 In this section, we'll look at how to use linear programming relaxations to get kernelizations for problems that we've seen before and indeed better kernels or smaller kernels than what we've achieved with our more ad hoc uh reduction rules before. And uh we'll revisit our good old friend vertex cover. Remember, it's one of those um really uh wellstudied FPT problems. It is an FPT. You can easily get a 2 to the K search space algorithm. We could actually get down to something 1.3 to the K. Uh that's not a result I've shown you in detail, but we could get uh I forget what it was. 1.4 something. Was that the 1.6 1.6 to the K?

1:05 Well, this was the the best result that I only cited in the previous unit. So, we know this is a from the perspective of fixed parameter tractability is a relatively tame problem. But let's uh let's look at it again from um the kernelization perspective. Uh the best thing we had was a quadratic kernel. So given an arbitrary graph and this parameter k what is the your your threshold for the size of a vertex cover? We could use this uh highderee rule. So just from removing every vertex of degree greater k uh we could get the graph shrunk to something of size k^ squ at most. So we'll see something slightly better here. Now first of all let's uh rewrite it as an integer linear program for vertex cover. That's that's also very easy. We have a variable as before for each vertex. Is it part of our vertex cover or not? Here we try to minimize the number of vertices that we have to pick.

2:16 But then the constraint is for every edge we have to pick one of the two vertices. I guess this the formulation as integer linear program again makes even more explicit why a vertex cover and independent set are so closely related. You almost see it immediately that they're kind of opposites of each other, right? Uh remember independent set was the same structure. It said maximize the number of vertices you pick and the constraint was um okay let's use UV here was at most one um except u as opposed to greater equal one. So they're really kind of doing opposite things. Okay, but that's beside the point um just because we talked about independent set a moment ago. So forget about this uh focus on the linear the integer linear program for vertex cover. Now again that's a precise representation of the problem but we cannot solve integer linear programs faster than uh the original problem. So instead of this we consider the relaxation. So we just get rid of the integrality constraint or more precisely we replace it uh with uh inequalities and we don't need the upper bound of one here. Uh it's enough to constrain the variables to be non- negative just because the minimization already makes sure that any using anything more than one is never going to be an optimal solution. That's one of the another kind of trick here.

4:13 It's a it's a general approach that you will see in many places and it sometimes makes things magically more uh approachable the resulting linear programs. So we essentially grow the feasibility region But in a way that we don't get any new optimal solutions. Let me write the set of uh optimal solutions as well.

5:08 uh because this is sometimes this is relevant. Usually we we want to grow the region in a way that uh we never make any new optimal solutions. So we take take that um linear program minimize the sum of XV subject to uh the sum of two end points of an edge being at least one and all variables non- negative and uh throw that into your favorite LP solver. You'll get some solution back. Uh you can you can prove that it will never have variables set to a value larger than one. They will all be between zero and one and they will satisfy the constraints but they might be uh fractional and um uh specifically we'll get some so uh let's write this down even though I just said it it will be between 0 and one. Um, whatever this uh optimal solution will be, I have to change that. Imagine that's a bold x instead of a x with an arrow. Um, whatever that solution will be, we can define three sets of vertices. Now, um, depending on what their value, uh, their variable has as value, there might be some that have exactly a value in the optimal solution.

6:41 um and those are in in this set B 0 and the other two are either um below 1/2 or above 1/2. Okay. Now the claim is we can take these three sets again uh maybe say uh uh what's what's a good pneummonic for I and C? I don't remember what I thought about uh when these were named.

7:15 uh well I is inferior so it's less than 1/2 and C is somehow the ones above 1/2. The claim is you can without loss of generality always take the vertices in C 0 as part of an an optimal vertex cover and you never need to take to take any of the vertices in I0 and then of course there's the ones in V 0 left where we don't know. Um but we'll see that we can we can use essentially restrict the input to just those vertices in V 0 and that's going to be the hard part of the problem. In other words, the kernel of the problem and you can bound the number of vertices that are in B 0. And so if you take a step back like what have we done? We take our vertex cover problem, we write it as an ILP and take the relaxation. So far so standard. And now we get some optimal solution back. And we uh we can just from the optimal solution learn a lot about potential optimal vertex covers and in particular how big an optimal vertex cover is. Um I still find that somewhat surprising that this is uh this kind of detour via LPS gives you so much um direct information about this graph.

8:34 So um let's let's prove this um and and kind of uh demystify what what happens here. Uh so we'll first prove this this uh claim one and then uh second part is is actually not not that hard.

8:58 So uh the thing is that um the statement here to be precise it only says there is some minimal vertex cover that contains all of Z0 and nothing of I there might be other optimal solutions. So uh when when we start we assume that s cover. Uh the goal will be to show that we can modify s to satisfy um we call that one sar. Uh we can modify sar to be like the s in the claim without making it bigger.

9:46 Okay. So we define the modified um solution where we take S star, we take out all the ones that are in I0 and then we add everything in Z0.

10:09 Um and we claim that's as well an optimal vertex cover. And that claim is two parts, right? It needs to be a vertex cover and it needs to be optimal size. Uh but let's rewrite this first. Um we can essentially rewrite this uh where now si is all the elements that are really in s. So sorry s star here I'm taking out an unknown number from i so I'm just giving that a name. all the uh elements in I that are in SAR, these are the ones I want to not have in my solution to satisfy the claim. And conversely, this SAR C is uh everything in Z0 that's not in SAR already. So part one is S is a vertex cover. Let's try to prove that first. When we add more vertices from this SC bar, we will not uncover uh any edges. So the only uh potential problem could be the vertices that we remove, right?

12:06 These are certainly the only ones we have to worry about. So suppose we have such an edge and say v is in i0. By definition i z these were the vertices where the uh corresponding optimal solution of the lp had a value less than 1/2. Right? So xv star was less than 12. But the solution has to satisfy the constraints. So the other end point has to 1/2 which means this W is in Z0 by definition of that set which means we'll eventually include W for short. So we might we might remove V 0 if it even was in the solution S star. But even if we remove it, we make sure that we add back in the other endpoint. So that edge will be Okay. And that's that's basically all. Uh any other edges we don't touch. If it has um no endpoint in B 0, whatever endpoint it previously had in in S star, it'll still be there. We don't remove it. So that proves that uh our constructed set S is indeed a vertex cover.

13:45 Again, that's good. Then uh we continue here with the claim that the size of S is the same as the size of the optimal solution, which means it's also an optimal vertex over and the way we've rewritten um our construction for S. So here uh so the the dot above this union here means disjoint union. It's just a way to express that uh I kind of know that the two sets will be disjointed. There's no notation for disjoint set difference, but if there was one, it probably will be a backslash with a dot above. I don't know. Right. So, what I'm what I'm saying here is this is also a disjoint set difference. Um, which means I mean this is uh is of course nonsense. A set difference for disjoint sets wouldn't do anything. But um we're not there's nothing in this set SI that is not in S star. It's kind of you're you're taking the set difference where the set you subtract is a subset.

15:13 Okay. Let's let's um doesn't hurt to write it down. That was the idea of the construction. I guess I said it maybe verbally, but SI is a subset of S star whereas the SC bar is disjoint from SAR. So to uh say something about the size of S you can take the size of S star you subtract the size of SI and then you add the size of SC bar. So let's do one more step here. So the size of our S uh stay here.

16:06 The size of R S is the size of S star minus the size of SI plus the size of SC bar. Okay, follows just from this. So it suffices to show uh that what we subtract is at least as much as what we add.

16:49 So let's try to do that. We'll have to somehow use the properties of these um I mean the the intuition here is uh both of these are only talking about vertices where the the value in the optimal x was not 1/2. It was strictly bigger respectively strictly smaller than 1/2. which means you can uh you can take these variables and uh change their their values a little bit and see what happens. Okay. So let's let's define some little epsilon which is the smallest uh slack you have between any of the xvs in uh zero and 1/2. So uh what's the minimal difference any of these has from 1/2? It's got to be non zero because these are just some real numbers and we define zero to be all the vertices that have a value strictly greater than 1/2. And so now we'll define some some new vector um which is the same as xar except for some uh entries. So when we have a vertex in si then we set this uh Let's call this x prime. Maybe we set x prime for that vertex to be uh the old epsilon. And for the vertices in SC bar we subtract the epsilon and we know that this leaves the value at at least one half still because uh epsilon was chosen. So that for all of those there's more than that uh of slack uh yeah epsilon is greater zero but then the difference is greater equal 1/2.

19:50 Okay. And the claim is that this still fulfills the constraints. Which means we have to check that for every Okay, maybe I'm uh running out of space here.

20:47 Now, where could this be violated? Um, it's an inequality. So, it's only going to be a problem if I make variables smaller. So, it it'll only affect edges that have some endpoint in SC bar.

21:29 Okay. And this was uh C 0 without our S star. Let me continue on the next page for this. Um endpoint was in in this set because it's uh it's not removed, right? So, um sorry, I think this is this is V. I've changed changed names here. So, let's let's say the the vertex that we look at is V. Uh that's the one you could only violate this constraint for an edge where one endpoint is among those where we subtract something from XV that must be in SC bar and so we distinguish cases where this uh vertex could be and uh suppose it was in this uh I without SAR SAR. Why do we also not have the other endpoint in in SAR?

25:11 Yeah, sorry. This this must be the other end point. So uh we have one endpoint in SC bar then we make distinguish we distinguish cases for the other endpoint. Uh it still follows now for both um because both vertices are in some set where we subtracted SC star. So if they were in SC star they would not be in this set difference. Right? So that's true for V because of the assumption here. And it's true for W because of the case distinction. So if V is an SC bar, it cannot be an S star. That's why V is not an S star. If W was in this set I Z without S star, then it would also not be an S star. But then SAR cannot be a vertex cover because there's an edge UV uh VW that's not covered.

26:25 true. Uh what other options do we have? We could have that w is in si. In this case it's one of those where we increment the variable by epsilon. Right? So uh x prime w is xar w + epsilon. And so if you sum up the two uh you satisfy the constraint. It's just the same as the old plus epsilon and a minus epsilon. And that was greater equal one because it was an optimal solution.

27:17 Okay. So then the third case is that W is uh not in I Z. This was in I Z but not in S. This was in I Z and in SAR. And now we have the case it's not in i that means it's it's uh value is greater equal 1/2 because uh it either was before even further increased it but it certainly um it was not in this set i so previously it had a value of 1/2 and we don't subtract anything from it.

28:13 And for um our edge here we subtract something but we leave that above 1/2. That's uh this this property. So if both are 1/2 then the sum is at least one right.

28:37 So in all possible cases for the other endpoint of an edge where we might subtract something from one of its from its variable uh the other endpoint makes up for it or the case is not possible. And so we've proven that this new x prime indeed fulfills the constraints of the Um because x is an optimal solution of LP, we get that uh the sum over all vertices in the new con solution we construct cannot be uh smaller.

29:35 And if you rewrite this the definition of this XV prime um this this entire sum here we sum over all the vertices and then it's the original XV and then we have epsilon times something we subtract and something we add. So if we go back to the part here, what do we add? Well, we add epsilon for every vertex in SI and we subtract something. We subtract epsilon for every vertex in SC bar and epsilon was greater zero. Right? So if you take this chain of inequalities together. It means that this difference must be at least zero. And so that means uh we've proven what we claimed here. It suffices to show that this SC bar is at most SI. That's the end of of part one. Okay, we've shown we can take uh an arbitrary optimal set cover. We can transform it into one that satisfies the conditions from the theorem, namely include all the vertices where the variable is strictly greater one than 1/2 and get rid of all the vertices that have value strictly less than 1/2 and the result is still an optimal vertex cover. which means uh we can essentially assume that we fix this solution and just look at the remaining vertices namely those with v 0. So the second part of of this uh theorem claims we have um an induced subgraph where we only look at the vertices in B 0 and we have to subtract from the threshold the vertices that we include for sure namely those in in Z0 and then that is a valid kernel for the original input and its size is bounded.

32:18 Okay. So, let's see that. Uh, and I need another page. So, claim two. First of all, we know the LP objective value, which what was that again? It's the sum of the XV stars, right? Is never worse than the ILP objective value. That's what we used before. Now um the ILP objective value is the size of an optimal vertex cover that's greater or equal than this thing sum of all vertices.

33:31 And what we're going to do now is uh look at so this is this is also true like for any graph right this is for any input to the to the vertex cover problem this is true. So what we'll do is uh we'll repeatedly apply the following reduction rule. You take the LP relaxation of the vertex cover problem. That gives you some optimal solution Xstar. And from XAR you get uh these these sets I Z I Z V 0 C 0. You I include in solution all vertices from Z0 and repeat this whole thing.

35:16 So in each recursive in each uh reduction step we get rid of every vertex in I0 and C 0. The only difference is that we keep keep track of the deleted vertices in Z0 because uh they will become part of the final output solution and we're left with the ice with the v0ero vertices.

35:36 Um I think it's hard to prove whether one round of this reduction is enough but we can just pretend we apply this reduction as long as we still get vertices where the optimal fractional value is not exactly 1/2. Okay. So after this um we'll have xar v is 1/2 for all vertices in our remaining graph. And let's call this V 0 as before was defined like that. Anyways, um at this point Um at this point we'll invoke this uh inequality from above. And now we know exactly what this sum is. It's 1/2 the size of our uh vertex set because every vertex has value 1/2. Okay. So what does that mean? It means the optimal vertex cover needs to pick um at least half of the vertices in my graph. So there's two options. Now uh if we have if we have more vertices in the graph than uh our parameter allows, then we're doomed. We cannot possibly pick a vertex cover from those. There's not enough. Our parameter restricts us too much. Okay. Then we can in terms of a kernelization you output a no instance.

38:12 vertices. And so we get uh a bound of the number of vertices in the That's the end of this part. Um, this shows how we can use an LP with a bit more sophisticated analysis to get a a stronger reduction rule. One that doesn't simply use these local uh arguments we've done before like just the degree of vertex of a vertex, but a more global picture because the LP is really taking uh the entire graph into account.