Video 4-5: Depth-bounded search for p-PlanarIndependentSet

0:02 In the next section, we return to the depthbounded exhaustive search technique that we've seen before for a a few introductory examples. Um, and I have a few more examples that take some more properties of the input into account uh to do something that's maybe not completely obvious at first that it's doable, but they fit in this in this schema of of exhaustive storage as well.

0:29 That's what uh what I just said. There were um the previous examples were basically uh simple brute force algorithms. And we'll try to look a bit uh closer now.

0:47 Um this one I I've moved so you can't recall this. We we will see uh we'll see that the problem of independent set in a graph. So remember what that is. Uh you're given some graph undirected graph uh could have cycles and whatever could look complicated doesn't need to be connected. In general, the task in the independent set problem is to find a largest set of vertices that are mutually unconnected.

1:22 So no edges between any of them. So what's the maximal independent set here? I suppose I have to pick these. Um um I'm guessing it's a good idea to pick these leaves, but it's really a hard problem. So I might not get the optimal solution this way. probably these two and that's that's all.

1:45 Oops. So I guess that's an maximal independent set in this case or maximum I should say. That was the independent set problem. Now I haven't told you what W1AR means. So just forget about it for the moment. We'll come to that probably tomorrow where we start we'll start with that part tomorrow. Uh what this means intuitively is we shouldn't expect an FPT algorithm for this problem in general. Okay. Um as as often in complexity theory, we we can't really prove that. Same as for NP hard problems, we can't prove there's no poly time algorithm. Uh but it's a bit unlikely. So what we'll look at here is a restriction of this problem where the graph that we're given is planar and uh indeed the example I've chosen is a planar graph just because they're nicer to draw. Uh so first of all I I'll define this a little bit um because I don't know how much uh graph theory background people have. So it's the same problem just that now the graph is planar and the rest is the formalization of what I've shown on the example. We're given a parameter and we try to find k vertices that are mially not connected. I've shown you the optimization version of the problem.

3:17 Now, uh, what's a planer graph? Maybe would be a a useful question for Slido. Uh, who knows what planer graphs are? Who doesn't know what planer graphs are? Have you heard the term before? So a planer graph um is a graph that can be drawn in the plane like this without any edges crossing.

4:02 So embedding is the formal term but you can think of it as a placement of the R2. And I'm just going to say a drawing of the edges. You can make this more formal, but maybe it's not needed Stay. Now if you come up with examples maybe it seems like every graph should be possible to be drawn like this. A famous example that is not planar is the k33 the complete bipartite graph with three vertices on each side. So uh every vertex here connects to every vertex on the other end. But it's bipartite which means all the edges go from one set of vertices to the other set of vertices. Here we have the the lower and the upper vertices and there's no edges that stay among the lower or among the upper vertices. And now the way I've drawn this graph clearly has edge crossings. Now the trick with planer graphs is all that counts is the graph with the set of vertices and edges. Uh my drawing is just one drawing. Maybe there's a better drawing if I was if I'm smarter with routing the edges. Maybe there is a way to not have them cross. But here the answer is no. There is no way and provably so. Um and I guess we'll we'll see in a second why. I mean it's a it's a classic and simple argument.

6:14 Uh another example is is K5 the complete graph of five vertices bit more messy to draw. Initially looks like a nice thing but now is that all? Yeah, it looks like everything has four edges. So that's that's a complete graph on five vertices. That's also not planer.

6:48 And then there's a cool theorem that essentially these two graphs are the only obstacles. Uh whenever a graph is not planer, it contains a concealed potentially concealed instance of one of these two graphs. That's a deep theorem in in graph theory that we won't need for now. Uh so you can forget about this. Um but that's that's a nice way to check if a graph is planer.

7:17 So we're looking at this independent set problem and maybe you can uh maybe you can get a an intuition that potentially this problem is easier on graphs that are not like this. Right? These are forbidden now. Uh only graphs like this where I can draw them in the plane. Maybe you have a I get a feeling that uh the problem might be easier on these graphs just because things are are uh separated out. If they're far away in the plane, then maybe there's also no edge between them because it would probably cross a lot of things. But this is very vague. That's not the way to prove anything. uh what we'll show at the end of this part is that indeed you can do um independent set on planer graphs with this running time which is a fixed parameter tractable algorithm and remember for the general problem this is unlikely to exist. So the restriction to planer graphs here really helps us and whether six to the k is is a good running time is a different question. Um I've only shown you a very simple algorithm which indeed um this is the worst case. It's often much better. But how does this work? How can you get uh how can you exploit this this property that the graph can somehow be drawn in the plane which is not even clear how to construct this if you first see planer graphs. So how can we use this to do a faster search for independent sets? Okay.

8:52 uh we'll use a bit of uh background knowledge on planer graphs but it's all fairly fundamental now I'm saying this from today's perspective uh it all builds on famous results including uh stuff from Leonard Ola and so on which at the time of their invention was I guess fairly non-obvious uh but I can explain all the concepts on uh on one slide or two uh the famous result that that oiler proved um is is summarized with this equation. Whenever you have a planer graph with the additional restriction that it's connected um again algorithmically that's not not a problem. If I have an instance of my independent set problem with several disconnected parts of the graph, I'm just solving the problem independently on all the disconnected parts. And the independent set of the entire graph is the union of the independent sets of the parts. Right? That's what happened here as well. Uh in my drawing here, the graph was was disconnected. There was an isolated vertex. There was this tiny component and there was this bigger component. And I could just independently solve the problem on each of them. So assume for this part that the graph is connected. uh then it has n vertices m edges and uh f faces that's not defined uh it's the faces missing um which is in such a drawing is the regions of the plane that are cut off by edges. It's a very graphical kind of notion. Um then you can relate these numbers and in any in any connected planer graph this equality holds exactly. It's a powerful tool. Uh I'm not going to prove this but I'm giving giving you some idea for the proof because you can almost prove this inductively.

11:02 Um so first of all let's um let's make clear that the the terminology is clear. So I'm I'm drawing a tiny planer graph and there can be funny business like this as well. So let's let's quickly count the three quantities here. What's the number of vertices? Well, 1 2 3 4 5 6 7. Okay, you correct me if I'm doing stunt nonsense. Seven. Then the number of edges 1 2 3 4 5 6 7 8. And the number of faces. Now this is um maybe we can shade those a bit. There's one face. There's another face which goes around this vertex. This is still the same face, right? And then there's the outer face which is everything outside of the graph. So we should have three faces. And now if we check uh the formula here, we have 7 - 8 + 3, which indeed is 2, right? 10 - 8. So it works out in the example.

12:23 That's good. That's not a proof though. Um, I'm not claiming a formal proof, but I want to give you an intuition because I think it's just so nice and uh there's enough people that haven't seem not to have seen it. So, effectively, it's an induction on the number of phases. Uh if you look at graphs with a single phase, how can these possibly look? No graph can get rid of this outer face, the dark blue one. So the only option to not add another face is to avoid any cycles. As long as I'm never closing off a part, I keep one phase. And uh whenever I close a cycle, I must enclose another face. So if I have a single face then G is a tree and then basically it looks something like this. It might branch off. It can have arbitrary degree, right? It can have long branches or it can have highderee vertices. Uh but it will always look something like this. And um computer science basic knowledge question.

13:50 No graph can avoid it in the outer face. Sure. The one you draw for example has zero faces. Which one? One you draw. This one isn't as one face. Uh namely the outer face but there's still one. So a face is a part of the ukidian plane. And uh if it's enclosed by edges then it's also a face. But also the thing that is on the outside of the graph is one phase. An alternative equivalent way to view it is to see the graph embedded on a sphere. Then there's no outer and inner. There's just faces. Uh it's very annoying to draw uh spheres and make it clear and visually. But if you have good 3D uh imagination, maybe you find it easier to imagine this wrapped on a sphere. And then this this blue thing is just the thing that wraps around the back of the sphere. And uh it's not a special face in any sense.

14:57 It's one of the uh faces that it has. And if you take a take a sphere and draw a tree on it, there's still the the sphere. So uh but it's a good point. I guess it's um how to define faces properly is is maybe tricky. So uh faces should be thought of as Now computer science basic knowledge is uh in a tree there's one more vertices than than edges and the simple picture proof would be pick any vertex say this one and orient all the edges towards that guy they're far away there's still a unique path because they can't be cycles and uh once you've done that every vertex has exactly outderee one apart from the poor guy we chose which has no no outderee.

16:08 Right? So here always n is m + one and if you plug that in it satisfies the equation. Okay. So that was the induction basis of this induction. And then the inductive step is take any graph and a drawing and add another phase. How can that happen? And it basically happens by closing another cycle. That's virtually the only way how you can add a new phase. You have to somehow close a cycle and That's where that's the part where I'm I'm just giving you some idea and I'm not trying to to do a rigorous proof. Uh how could things look? So there there could be many uh many weird things how a face could be created. Maybe this is our graph that we start with currently has uh three faces, right? The outermost and these two. Now, um, one way to create another face would be to close an edge here. That would add this face, and it would add one edge.

17:31 Um, another option would be to draw an edge in here, which cuts one of those cycles in half, adds another face. Another option is to connect this one. But in each case, what I'm doing is add one edge and close off one cycle.

17:55 So I'm getting a plus on the edges and a plus on the faces. That's the key operation. And if you look what happens here, the difference between uh faces and edges doesn't matter. I I can add edges. If I also increase the faces by the same amount, I won't invalidate this equation. And you can think about what what else can you do to a graph to grow it? Well, you can add vertices. Um, if they're isolated or just connected somewhere, then they don't add a face. Um, so if I'm I'm adding a vertex here, something like this, I'm making n1 bigger, but also m1 bigger. And uh I don't get another phase. Uh, then again, the equation is satisfied. This kind of uh I'll I'll stop at this point. Um the idea is that this formula can be proven by going through all possible cases. How you can modify a graph and you can use induction on say the number of phases uh to see what happens in each case.

19:14 Okay. So far so good. yeah we norm we normally don't allow loops when when I say graph I I think of a simple graph. Um does it violate the formula though? Uh two vertices one and group one edge and one group like this. So you have two faces, two edges and two vertices. That seems fine, right? Okay. It seems right. So it has to be connected. That's uh that's definitely like um the way to break it is to just say I have two vertices or I have four vertices and they're not connected then then things break. That's why the connected here is important. Uh it's it's an interesting point what happens with self loops. Um for most of the algorithms I think I'm I'm implicitly assuming simple graphs but I think this specific theorem would actually work fine. the same same argument here. Uh seems to work. Uh right. Let me just do this in in dotted. Uh I'm also adding one one edge and one face. I don't think it breaks. Okay.

20:56 What we use this equation for is the following simple observation which again is is a something to keep in mind about planer graphs because it's it's useful in many many places. Um and here here we need simple um if I have a a planer graph um a simple planer graph with not vertices and edges I can bound the number of edges it can have uh simply by using that formula and the fact that faces uh can't be arbitrarily small. So what's the smallest face I can make? Well, I could try to do this, but that's not allowed in a simple graph. Then, uh I would have a a face that's delimited by just one edge. I could try to make a face that's delimited by two edges, but then actually these would have again uh they connect the same vertices. So, this is also not a simple graph. So the smallest configuration I can make that closes off a phase is a triangle.

22:06 Okay. So in a simple simple graph means every phase is delimited by at least edges and so uh whatever my graph looks like I can uh just count uh how things go. So let me again do this mostly by example. Um uh might actually be enough. So I have three faces. This one, this one, and the outer face. Um, I must have three edges uh three uh edges for each of these, but I'm double counting each edge exactly twice, right?

23:38 Uh okay I guess um that's not true as I wrote it here listing summing over the edges that del limit a phase would double count every edge twice. If I say I use the minimal number so I get an uh a bound on uh the number of edges.

24:22 Um, but then I can also insert what I know about bit. So what do we get? uh three times and then it's 2 - n + m. I'm just solving this for f and uh hopefully don't goof by doing it. And so uh uh stay here that's the overall thing. Now you can uh simplify this further. So it's 6 - 3 n + 3 m. So you now have uh the entire equation and I'm I'm subtracting 2 m from this. So I take this equation minus 2 m and bring this part to the other side. So also + 3 n - 6. So I'm left with m on this side and on the other side here I get less or equal 3 n minus 6. Is that clear? I'm just taking this one equation right 3 m greater= 6 - 3 n + 3 m and uh moving things on the other side I get exactly what we claimed. So this is cool because it means the number of edges in any planer graph is at most linear in the number of vertices. All planer graphs are sparse.

26:18 It also means that the average degree of a vertex cannot be very big just because the uh summing up all the degrees for this second part summing over all vertices and then the degree of a vertex that counts every edge twice once from each end point. And so we know this is at most uh 6n. And so you can divide by n and then you get the average average degree is at most six. And because there's actually 6 n minus 12, you get a strictly less here. That's where the strictly less comes from.

27:16 Good. Fine. Um, this also means maybe this worth listing explicitly. What what follows from this that the average degree is less than six. This also means I will always have a vertex of degree at most five in any planer graph. And the proof is by contradiction. If all vertices had degree at least six, then the average would be at least six. It's as simple as that. You could call it the probabilistic method. If you want the expected value, if you draw a random vertex, the expected value is less than six, then there must be a vertex that's below the expectation. Of all this uh prelude, this is actually the statement that we're going to use. Okay. Uh in every planer graph there is there's always a degree of a vertex of degree at most five. Um and this property is also called the degeneracy of a graph.

28:58 So degeneracy means is the property that in in a graph I can find a vertex of at most that degree and also if I take any induced subgraph the same is And while we're doing the detour on on graph theory, do people know what an induced subgraph is? uh there's often this notation if we have a graph G v E the standard notation I know is is this or induced subg graphs so where V prime is some subset of the vertices it's a simple thing it's just the graph where you take the subset of the vertices and you take all the edges of the original graph that only talk about vertices in V prime A concise way to write this is to take the edges as a set of two element sets or yeah I guess I'm cheating a tiny bit here. Uh maybe I should write it out just to be to be formal. Uh it's all the edges in the graph UV.

30:59 So that uh u and v are in v prime and the same edge exists in the original edge set of the graph. That's an induced subg graph. You only focus on a subset of vertices and you forget of all the edges that would have a dangling end. That's all. Uh but this notation is useful because I think I uh I used it in some pseudo code. So keep that in mind. If if you have a graph and then square brackets with a vertex set, that means induced subgraph. And so yeah, this is that's that notation. Brilliant. Um maybe you also have a feeling now how this independent set algorithm could work.

31:51 Let me just go back to the claim that we had a while ago. Uh the claim was if I have a planer graph, I can find independent sets with that running time 6 to the k * n. Now uh this this constant six popped up here as a bound on the degree or the the degeneracy. So maybe this this is not so far away. Um and indeed the idea is um for independent set [Music] um if you have any vertex one of this days again if you have any vertex and its neighbors you can only include uh either the neighbors or one of the neighbors or the center vert vertex in an independent set. You cannot include uh both because that vertex in the middle is connected to the others. So they are not part of an independent Oops. Okay. Uh this cable. So let me just draw the picture for what I just said.

33:37 Um if I have if I have this uh vertex and uh and its I'm the point is independent sets can be any subset but if I if it's an independent set that has any chance to be maximum So a maximal subset means uh can't add more vertices to this non-independent. If you have an maximal independent set, you have to take one of those five vertices. If you did not include any, then you could have taken the center and added to it because you're not including any of the neighbors of this vertex V.

35:03 set could add V itself. So, uh any maximal independent set, any of those that have any chance of being the largest, they must pick either the center vertex or some of the neighbors. They could include many of the neighbors, but at least one of them. That's the idea behind this algorithm. And so what it does is uh obviously a depth bounded search. That's still the chapter we're in. Um so uh we're given given a graph and uh the the parameter which is the size of the independent set we're trying to construct. If k is uh larger than the number of vertices in the entire graph, then we're certainly out of luck. Whereas if the edge set is empty, then that's easy. we can just return the uh entire set. Everything's independent. And otherwise, if we're not in the boring corner cases or base cases, then we have to choose a vertex um as a basis for this for this uh star.

36:10 And here we can pick a vertex of minimal degree to reduce the number of choices. So we have a vertex V and its neighbors. And because the graph is planer, we know that this minimal degree vertex will always have degree at most five. That's just by the magic of planarity. And then we go for each of these vertices. Uh we try including that vertex in the independent set and recurse. One of them has to succeed.

36:42 uh well I should say if anything succeeds then a solution with one of them has to succeed. So formally this looks like I'm constructing a partial solution. Um this is this is this uh uh I'm constructing the graph where I've removed the vertices that I'm I'm dealing with now. So I I remove this vertex and its neighborhood because if I pick one vertex, I cannot include any of its neighbors in any independent set. So I take take the vertex U and all its neighbors. That's what that that's supposed to mean. Um I remove those from the vertex set and I remove all the edges that have an element in there. So I could have written here GU is uh G reduce is uh the induced subgraph on V without D. Um and then I try recursively to solve the problem where I only look at this graph and I have one less vertex to include. Um if that is solution is is indeed successful I should add vertex U the center that I picked. So we try this for all the options. Either this vertex V in the center or any of its neighbors. And if uh any of these solutions succeeds, that's great. Then we return the largest of those. Might as well. And if none of them succeeds, then we know there's no possible solution. We've tried all maximal independent sets. And so the maximum independent set can't have size K.

38:38 So um maybe on this slide it's convenient to analyze the search space. We still have to show this running time. So uh because of planerity we know D is at most five but I have to include V. So we have at most six recursive calls in each in each call. And uh we may have to go all the way down. Sometimes we're lucky and we can abort early, but in the worst case we have to go down until K is at zero. That's the zero? How do we stop if K gets smaller and uh I guess it has to be that the graph gets too small and then we can't continue. So in the worst case um depth? I guess there's a case missing. Uh if K is is zero, we should just return the empty set. and stop. I don't see if that's somehow implicitly caught in any of the other cases. This is this is the worst case that we don't stop before that happens.

40:47 So, we go down with K all the way. And so we branch out sixfold in each step and we go k steps down. That gives us a search space of six to the k. Again, this is just the worst case. Most graphs won't have the maximal degree equal to six all the time is actually a is hardly possible in planer graphs but as a simple bound that's the best we can say. Uh and then how costly is each recursive call? Uh that depends on how how you implement things in detail but you can say it's linear in the graph size. Um and so because here n and m are linearly related uh each takes linear in n and m and that here is is just linear in n. So the total size the total running time is bounded by the six to the k and then times n as we had it in the claim.

42:21 Okay. Uh so one remark is that indeed the six to the k may not be the absolute best possible but some exponential dependence on k is is likely uh not avoidable because uh the problem is still np hard even on planer graphs um when the vertice degree even is at most three. So even even a much more restricted version of independent set is an np hard problem. So you can't expect to solve it in polomial time but this fpt time is possible. Uh and the same same algorithm works for any bounded degeneracy graph. All we needed or all we used was there's always a degree dvertex a small degree vertex and then we can bound the running time in a similar way.