Video 10-2: Vertex Covers & Matchings

0:02 In the next section, let's see some some first simple examples uh of approximation algorithms. Uh these don't use a lot of fancy knowledge about the problems. They're more to get us started. Um but they're also in a way best possible. Um recall our good old friend vertex cover. So we have a graph any subset of vertices so that every edge has an endpoint in the chosen set of vertices. Uh that's a vertex cover.

0:34 Um in formal language you can write it like this. If if edges are two element subsets uh we certainly want the smallest such because taking all vertices always is a valid vertex cover. uh but how if we're given some some set C how can we prove that that is optimal or close to optimal right so you can easily check that it is a vertex cover amazing you can try to solve this we know npmplete problem to find the smallest vertex cover that's not not going to be uh practical so um we need some other way uh uh state we can't really modify the specific solution we got. So all we can do is try to get a lower bound on the optimal optimal value. Then we can compare against that.

1:41 How to do that is problem specific. Um here we can do something simple. we can uh look at matchings. A matching in a graph is just a a subset of the edges. So that if you take the the same vertices and just this subset of edges, the resulting graph has degree at most one or uh you can say it in many other things. You can say the edges uh form pairs of vertices or the connected components have at most two vertices in them. uh let's maybe do uh an example right so this is a matching there could be isolated vertices lying around and there could be some underlying graph that I'm not drawing but this is this is a matching what you can't have in a matching is further connections so that's an easy uh easy definition um we'll look at different types of matchings so uh just be sure to keep them separate. Uh there's maximal matchings or I like to call them inclusion maximal to make it a bit um more explicit what we mean. This is a matching where I cannot add any further edge from the graph without destroying the fact that it is a matching.

3:00 Um this uh could or could not be a large set. It just means you cannot add anything to the set. then a maximum matching is one of maximal cardality. So just the the two terms. Uh I'll try to use inclusion maximal and maximum to keep it keep it separate. Uh and finally a perfect matching is just one where we have as many edges as we could possibly have in a graph of of v n vertices. So uh all the vertices are paired. Perfect matching means everyone has a partner. And the perfect matching certainly is maximum because you cannot add anything and every maximum matching of course is maximal. Uh but the converse is not true.

3:54 So the good thing about maximal matchings is that they're very easy to find. If you're given a graph, you can just add random, pick an edge, add it to your matching as long as it doesn't connect anything that already has an edge. and you keep going. And if you can't add any of the edges in the graph, well then you're maximal by definition. So very easy to find. U maximum is a lot harder conceptually. It's complexity wise still polomial time even on general graphs. Uh but on general graphs the algorithms are somewhat intricate. So it runs in polomial time but not linear time. And the algorithm is is a bit tricky. uh it's it's admins's algorithm or the blossom algorithm if you want to look into that. Um we won't we won't use it or uh we won't use it beyond the fact that there's a poly time algorithm. So why am I talking about matchings and vertex cover?

4:56 Well, simple observation. If you have any matching and any vertex cover, the vertex cover is going to be at least as big as the matching. Why is that the case? Simple uh simple proof. Okay, there's this weird bug where the things jump around. Take any edge in the matching. See the vertex cover has to contain either of the end points or maybe both, but certainly one of them. And also all the matching edges are disjoint as sets. So if I'm trying to cover all edges in the graph, I have to cover all the matching edges. And uh for the end points, I know that they're in the matching edges. They're only usable for covering one matching edge. So I need to pick one endpoint per matching edge in any vertex cover. So C must have at least as many vertices as M has edges. Okay, simple. Again little picture. If this is your matching, even if it's not maximal, it could be many vertices that maybe have some uh uh some connections in the underlying graph. Let me draw the underlying graph as well.

6:23 I don't know if you can see any difference. So let's say the matching is the red thing. Then to cover the red edges, you have to pick one of the end points. But because they're disjoint, you have to pick one each uh to do a vertex cover. There's no way around it. Okay, that's easy observation, but it means we can get um a simple approximation algorithm for vertex cover as follows. Find an arbitrary maximal matching. We can do that with this greedy algorithm that I just sketched before. Here it's spelled out. You start with the empty set. You go through the edges in some arbitrary order and try to add each. And if that uh is no longer a matching, then you discard the edge. But if it is, you keep it. Now what's the output? You take for every matching edge both end points into your vertex cover.

7:22 And that's going to be a two approximation for vertex cover. Why? Well, two things we have to show, right? One, uh, the output is indeed a vertex cover. Say we call this C.

7:41 Uh, suppose some edge was left uncovered. So there's an edge here that I'm I'm not covering, but I took from all the matching edges both end points.

8:04 They might lie somewhere here, but I didn't take either of those two end points. Well, then I could have added this edge to the matching without violating that it is a matching. And that's a contradiction to how we picked things. So it has to be a vertex cover. And second, the fact that it's a two approximation follows from this lema. Every possible vertex cover has to be at least as big as our specific matching, even if that's not a maximal one. And so we only do uh twice as bad by picking both end points. So our C is two times this. And we know that opt has to be at least m. So you could uh puzzle together what C divided up is by using um here we have exactly sorry uh here's an equal so it's 2 m and for up we use the upper bound so we get two okay that's a very easy uh approximation algorithm and as a first example maybe that's all we all we do now it feels like you should be able to do better um than this very simple algorithm Maybe all we need is a a closer analysis of this specific algorithm.

10:02 Uh but it turns out that's not the case. And an exam an interesting tight example is the complete bipartite graph where you have all edges between the left and right points.

10:19 So everything is connected but uh there's no edges between the red and the green side. Bipartite means you can split the vertices into two sets so that there's only edges between the sets, not within the sets.

10:39 Um, a maximal matching could be this one. And because it's a complete graph, everything's symmetric, you can always pair up vertices somehow. You can always find a perfect matching in this graph. So that will be M. and you'll output all vertices uh in your greedy algorithm. But of course, you could have just picked all the red vertices and they have to cover all the edges because there can't be edges between the green vertices alone.

11:12 For example, this would have been enough. So here uh any algorithm that starts with matchings will end up with this factor two. And uh with a bit of an extra assumption without getting into what that is um there's a there's a conjecture if you assume that that conjecture is true then people have proven conditional on that there's no constant factor you can improve upon this two. You can do a two minus some function of the input size approximation. Uh but if you want epsilon greater zero and a constant that's unlikely to exist for vertex cover which is somehow striking that this very simple algorithm that we just uh proved correct on one slide is the best you could hope for in the worst case. It's a bit disappointing maybe but uh uh that's what the worst case looks like.