Video 11-5: Vertex Cover and Matching via Duality

0:04 In the last section, I've shown you uh the the LP duality theory. Let's have at least a quick example of how you can apply this in algorithms. And we'll uh we'll look again at our friend's vortex cover. And we've seen the very first kind of approximation algorithm that we looked at was taking a maximal matching and just taking both end points. And that turned out to be a two approximation for vertex cover. It turns out there's a a much much nicer deeper structure behind this idea. Uh first of all you can write down vertex cover and maximum matching the overall largest in this case uh both as as integer linear programs. Right? Vertex cover you have a variable for each vertex. You can either pick it or not but you need to make sure every edge has at least one of the end points picked. So the sum of the end points must be at least one.

0:57 uh whereas for for matching uh we have a variable for each edge. We try to pick as many as possible but for every uh vertex I can only pick in total uh value one on all its incident edges and if you restrict that to integral inte integral variables then it's exactly the notion of a matching you could pick one of the edges of of every vertex at most. Um uh so then that's that's exactly the two problems. Now if we look at their LP relaxations, we see that the they're duals of each other. And here's just by concrete example to also make the structure extremely visible. It's a a small graph with some uh four vertices, five edges. Um the problem for minimum vertex cover the the LP can be written like this. Yeah. So you have a uh for each edge you have a constraint which says one of the end points has to be picked but in LP language just the sum of the end points has to be at least one and for maximum matching uh you have a variable for each edge and then you have a constraint for each vertex. For example vertex V1 uh has E1 E2 E4 and so the matching constraint says their SAM cannot be more than one.

2:18 And again you can see from the structure they're exactly dual uh or you make uh the game from before. Um if you look at the matrix A which is the the matrix of the constraints then uh there's a bit inconvenient but here the the natural one is for the dual. If you look at this matrix that's also known as the the incidence matrix of the graph. You have the vertices as rows and the edges as columns and you have a one if they're incident and a zero otherwise. Uh and so that that turns exactly into the coefficient matrix for the constraints for matching. Uh it's all not too deep or surprising. Uh but the fact that these problems are dual means our lema from earlier that the vertex cover is at least as big as a matching is just weak duality and nothing more.

3:21 Um and it indeed works on the integer linear programs not just on on the linear programs. uh we'll look at this um in a bit more general sense uh later. The the last bit I wanted to mention here is um this notion of a duality gap that we um that we haven't had before. We've talked about integrality gaps. Uh duality gap would be so you can have the um integer feasible for the primal and you can have integer feasible for the dual there's no uh there's no duality gap for for LPS. Um but for the integral problems, there's a gap from going from all solutions to integer solutions in either of the two problems. And so there's also a gap when going from the integer linear program to the dual integer linear program. And that's what what what we call the duality gap. So that's the And of course we also have this guy here.

5:07 That's the integrality gap that we've we've seen before. Uh and for vertex cover and matching a simple example and we've seen this before is that the this duality gap is is two. In the worst case it is at least two and it's also never more than two.

5:38 Okay. Yeah. Um this we don't actually need. So it's just for in bipartite graphs. It turns out the duality gap is gone. um because you can always have the the matrix you get is totally unimodular. So it always has an optimal feasible an optimal integral solution even for the LP and since that's true for for both primal and dual problems also the integral the ILPs have to match have to have the same optimal objective value. Uh let's declare that's uh just enrichment.