Video 4-6: Depth-Bounded Search for Planar Independent Set

0:03 We next want to look at the independent set problem in a specific restriction and again see some defbounded search tree algorithms based on that. Um what I briefly recalled for the vertex cover problem is that we've not done so much algorithmic intelligence in our algorithms for these for these problems so far. Uh they were essentially a brute force method. We just observed that if the parameter that you care about happens to bound this this depth, then it's already a a result in the style that we ask about here.

0:37 And the next problem I want to look at is this the independent set problem. So again to briefly remind uh everyone what the independent set problem is, you have a graph with various edges. I'm just making some arbitrary example. And now the question is how many vertices can you pick where none of the picked vertices have an edge in between. So here it looks like you want to pick these two and maybe three is the best you can do.

1:19 At least that is a independent set. the vertices have mutually no edges in between or in other words the uh subgraph induced by the red vertices is the empty graph. That's the independent set problem and we're interested in finding a large such set. Now unfortunately this is a hard problem in several ways. First of all it is np hard or nplete even if you restrict the graphs a lot. if you restrict them to planer graphs and where the vertices only have three edges. So these are uh essentially um collections of such glued together triangles if you think about it and maybe some trees attached to it maybe with a bit more more um such triangles or could also of course be larger cycles. uh with a relatively restricted class of graphs and yet the problem remains hard if you um focus on those. Uh and further bad news is delayed to the next unit where we'll see strong indications that this problem in principle is not even an FPT if you parameterize it by the size of the independent set. Likely you're not going to be able to find an FPT algorithm. What exactly we mean by this you'll see then um but it's kind of a foreshadow. So independent set seems harder than vertex cover right because vertex cover is in FPT. We've seen this trivial 2 to the k * n vertex cover algorithm not very insightful but in FPT independent sets seems not to have such a thing. So what we'll uh do here is we'll throw these two things together and see like if if we add enough restrictions and look at a parameterized problem maybe something works and indeed that's the case. So um the problem I want to look at in this section is called the planer independent set problem where you restrict the inputs to be planer graphs and we parameterize by again the solution size of the independent set.

3:28 Formally speaking, again, here's the definition, but this is exactly what we had before. And we'll show that for this restricted parameterized problem, we can indeed find an FPT algorithm of uh not great exponential growth, but maybe if K is small, still usable. There's no um no galactic things hidden inside otherwise, but um okay.

3:57 Um maybe before we uh jump into that, let me uh remind people what planer graphs are because we'll use some of their properties. All of them are simple enough that I'll sketch a proof and if you've seen that before, you'll you'll recognize it. Uh but to be a bit self-contained, let's maybe um at least mention the key things. So um a planer graph G is a graph where there exists an embedding. So positions in the plane, you could say it's a x and y functions that map the vertex set to the real numbers. So I'm I'm placing a vertex at coord x coordinate and y coordinate x of v y of v. Oh, stay.

5:13 And that's that's what we mean by an embedding. And um In this embedding, there's a way to draw all the edges without crossings. Most of the examples I've been drawing happen to be planer embeddings because it's just nicer to draw graphs that way. So um oh what's happening today what's happening it's a uh Monday laptop okay so all of these are planer graphs you can think about any tree is planer and uh grid is planer so you could have um some squares and so on and so forth. Now you could also ask what is not planer? How can we uh show that something is not planer? And there's this um lovely theorem it's small Vagner's theorem or Kurovvskis and Vagner's theorem.

6:39 Um the the the cutest and shortest formulation certainly is this one. A graph is planer if and only if it does not contain these two special graphs. The complete graph on five vertices or the complete bipartite graph on three and three vertices as a minor. So what does that mean? Um, And this this definition with the embedding is kind of uh intuitive but is a bit hard to check, right? uh whereas this is now only talking about the structure of the graph. Much more convenient.

8:04 complete graph on five vertices and K33 has all these edges everything on top with connect connected with everything on the bottom. Now what does it mean to contain a graph as a minor? Um if I start with a graph then I'm allowed to do three operations. I can delete an edge. I can delete a vertex and I can contract an edge.

8:58 If I delete a vertex, all the incident edges are gone. So minor is everything I can obtain with such a procedure. You start with your graph and you do any operation sequence formed by these. I guess deleting edges or vertices is rather clear what that means.

9:31 Um, and contraction maybe is a bit less obvious. I'm uh I'm trying to stay planer. So I can get rid of a vertex. I can get rid of an edge. And contraction means I'm pulling the end points of a of an edge together and just declare this is now one big vertex. So everything that was connected to this one is now well connected to either this or to this is now connected to this large blob. So if you uh in imagine this is uh filled then now it's just a vertex that has degree three. And the uh the crucial observation here is if I throw away a vertex I cannot kill my embedding. I'm not get generating edge crossings by deleting edges. I can also not ruin the crossing freess of my uh drawing. And by contractions, if you do it the way I've drawn it, you just make this blob fatter. Um you can in a way say I'm routing the edges first into the blob and then inside the blob, nothing counts. I can't cross. So this also doesn't introduce edge crossings. So if I start with a planer graph and do these operations, And so you could ask yourself this question. If I start with uh arbitrary graphs and I keep doing these operations, what can I end up with? And there's a whole theory about this. The point for planer graphs is this this cute characterization.

11:31 If you ever end up with either of these two graphs, both of which are not planer, which uh is requires a separate proof. Um we'll see a route to proving that in a minute. uh if you first of all believe that these two are not planer then uh any graph that contains these as a minor can also not be planer right because it a contraosition to this one and uh the the clever or highly non-trivial part is that this is a characterization that's the only two obstacles to planerity that you can find if a graph doesn't contain either of those two as a as a minor then it is plar full stop. That's the really cool thing and that um is is a topic for a graph theory lecture. We won't won't go into this further. We'll just eat that as a black box. Uh a more elementary thing about planer graphs is uh Oilers's formula.

12:33 And for that uh I think we need a little example again. Let me try to do something that uh catches the corner cases. Okay. So that might be a planer graph or I guess an embedded planer graph in the plane.

13:05 Let me let me rewrite this as a planer map which is a bit more correct. A planer map is a graph plus an embedding.

13:22 Yeah, because some of these um things are uh properties of the embedding. Um the number of nodes and the number of edges of course doesn't depend on the embedding. Um but then the number of faces uh I guess also doesn't, right? Okay. Uh let me define those though. So vertices I guess is clear. All of those guys and edges is also clear.

13:53 Let's just use some uh some colors that's missing faces. Uh faces are the areas that the graph divides the plane into. So in my small example, there's one face here. Then there's one face inside here that includes this weird little uh tentacle. And then there's the outer face. Everything that's not enclosed by anything. So here I have three faces. Okay.

14:45 And let's count the vertices as well. So uh n is what? 38. nine. And so hopefully also in this graph we get that 8 - 9 is - 1 + 3 is 2. And oiler's formula says that is always the case. You always if you uh uh take the vertices subtract the edges and add the faces get two in any planer in any planer graph. And I guess the number of faces all of this is um I'll revise what I said earlier. This this is uh indeed all just depending on the graph. Uh let me I won't I won't prove this. It's a very very standard and and classical result. But let me give you some pneummonic intuition for the proof. It's not going to be very formal, but I think it's enough to see how you would prove this properly. And I think it's the way how to memorize the formula for me at least.

16:07 it's an induction on the number of faces because then you can start from some very simple graphs. Zero doesn't make sense. Every graph makes at least one face.

16:16 So the smallest sensible value is one. What does that mean? There's only one face. Well, this is only the outer face. So, I can never have any enclosed faces. Well, that means I cannot have cycles, right?

16:37 Uh, a crucial thing I didn't stress enough is that this is only true if the graph is connected. You can make obvious counter examples by adding just a bunch of isolated vertices. Then you bump up the number of vertices without affecting the other two. that cannot work. So it must be connected. Um what is that? A graph that is asyclic and connected. Well, we call these trees, right? So the graph is a tree.

17:11 And in trees, I guess you may know from the top of your head that you always have uh uh one more vertx vertices than edges because you could imagine even if the graph here is graph theoretic undirected, right? This is just some some construction like this. That could be your tree with the one face around it. You can always elect some arbitrary vertex to be the root and orient all the edges towards the root. This is unique. So then every vertex gets one outgoing edge. Exactly one outgoing edge except for this poor guy the root. So clearly uh you know here m is n minus one. And if you plug that in and using that f is one then that checks out right.

18:05 That's the induction basis. Now the inductive step this part so far is is formally true. Now the inductive step is we want to go to uh an one more phase.

18:24 And so you want to add some phase. And um for this, let's just do a picture proof of what this could look like. Um there you have several options and in a way they're all kind of uh covered, but that this is all cases needs a proper proof. So how can I make an a new face here? Well, one option is I could close off some part here. Then I have one more face and I used one extra edge. Uh how else could I and um let's let's keep the number of vertices constant. I can of course add more vertices but then I might as well have had them in the uh base case because that I can also do but then I'm adding a vertex and uh I'm just back to the the previous one. I could have um had the vertex connected into the graph before. That's one option. Uh another option is I make a self loop if that is allowed.

19:34 Uh it's not violated uh in the formula. I add one face and I add one edge. I can also have these these things here. Maybe I I connect that with vertex. That's another option. Um or I draw in a chord. That's maybe okay. Maybe we even allow multiple uh edges between the same two vertices. Uh we don't have to here. Um I can draw a chord through a cycle like this. All of these cases have the same effect. I'm I'm adding in unison one extra phase and one extra edge. And so of course these just cancel.

20:31 And this is this is indeed true. Now to fully rigorously prove that this is all the cases and nothing else can happen um may need an extra argument uh fake proof end of fake proof if you like. So this formula is convenient because um I think this is already sufficient to prove that the K33 is is not planer and uh probably for K5 even easier because it's has just so many crossings.

21:16 Now what what we'll use this for is uh if you take this and um restrict it to a simple planer graph then um you get an upper bound for the number of edges that the graph can possibly have.

21:41 And for that I called it just corollery but let's uh let's derive this. I think this is insightful. The the trick is to sum up the degree of all vertices. By that I'm overounting every edge exactly twice. This must be 2 * m. And uh that's for the second part. Do we even need this here?

22:29 Ah, I see. Um, let's first prove the the second part here. Uh, that's fine. I'll do the other one afterwards. Assuming this already is proven, then I'm I'm just plugging this in.

23:15 On the left I have the average degree and on the right upper bounded by well six minus something that decreases. So certainly less or equal six for every n that's strictly less than six. Uh for the first part for this um we have to make use of the simplicity. What is the smallest possible face?

23:53 Well, I could try to make one with a single edge, but that's not simple. We don't allow self loops. Or I could make one that involves two edges like this. Parallel edges. That's also not allowed, right? Not simple. Not simple. So I guess the smallest indeed is a triangle. That's the smallest sensible face in a simple planer graph.

24:28 That's a correct face. And um if I now sum up uh all the over all the faces over all faces and for each face count the number of edges on its boundary. Okay, then uh we don't I didn't introduce notation for how many edges are bounding this phase etc. So let's let's leave it a bit informal. I think it's clear that um this uh first of all counts every edge exactly twice always once from the one side and one from the other side. Okay. And of course um summing all boundary edges of all faces. This must be at least three * f because every uh phase is in a simple graph is enclosed with at least three fa uh edges. Okay. Question or >> this one >> the edge in the middle of this square count this edge twice because it's inside the face. >> You would count it as part of the boundary. In this case, it's a bit of a degenerate boundary, but yeah, uh I think the definition is you walk along, you do an oiler walk around the boundary. So this is yeah it's not cutting off anything but it's still part of the boundary.

26:32 >> Uh sure you could you could take it away and uh but if if this is supposed to be true for any graph I guess you still want to include it as as an option. Uh all all I'm saying is um I'm summing up all the edges that are con adjacent to the face. Maybe boundary is um is indeed a bad term here.

27:01 All I need is that they're adjacent to the face, that these are at least three each, and that this on this side here counts every edge twice. Okay, which then means 3 * f, right? This is less or equal 2 * m.

27:25 And um now we can use oilers's formula. If I rewrite this for f to the other side, so I get 2 + m - n. If I insert that here, then that's uh 6 + 3 m - 3 n and that's that's lesser equal to m. So if you uh rearrange we get m is less or equal 3 n minus 6 and that was where this comes from. So it's literally counting the adjacent edges of the faces using that we have a simple graph so that we have at least three boundary faces and then applying oilers's formula.

28:23 Now zooming out why is this useful? If you think about uh independent set and an FPT algorithm, uh this last property is rather useful because it means that typical uh vertex will not have too many edges. And um if you think about it for an independent set, if I take a vertex, I cannot take any of its neighbors. So maybe um it's good that uh there's a kind of a a bounded um number of different options. We're we're not entirely there yet. We need one more ingredient to make this work. Um as a as a corollery again from this average degree less than six uh by the probabilistic method if you want or just how averages are defined. If if the average is strictly below six, I find one vertex with a degree less than six.

29:51 where the degree is less than six so less or equal five. Now the crucial thing here this is true for any planer any simple planer graph.

30:20 So if I find such a lowderee vertex and remove it, delete the vertex and its incident edges, the resulting graph is again planer or still planer. So it will again have a vertex of small degree.

31:00 And this property that's um if you take um any induced subgraph of the graph you started with you always have uh a degree at most five vertex. This property is called degeneracy.

31:31 The graphs are called 5D generate which means um the short version to define is is that every induced subgraph And so that's that's that's useful for the reason that we can then uh after doing this once can rely on doing it again and again and again. We always find a low degree vertex.

32:08 Okay. [clears throat] uh let's put that into um a depth bounded search for our planer independent set problem. It's following a similar recursive structure as we've seen it for vertex cover. we have a graph and a current budget or well in this case it's rather a threshold right how many uh vertices can we do we want to get um if we don't want any independent vertices that's fine then we return the empty set and are happy if we're supposed to return more vertices than our down our total graph has then we certainly are done obvious um uh termination conditions otherwise the graph half is non-trivial yet. So we choose a vertex with minimal degree. Okay.

33:01 Linear scan over the graph unless you do it even smarter. And let's uh call the neighbors w1 to wd. If we start with a planer graph then we know that this is always at most five. And you immediately see this doesn't really depend on planerity. It rather depends on the degeneracy. But I think this is a bit of a more intuitive way and um you can swap in a different graph class that is only degenerate and the same trick works. [snorts] So we know um not too many neighbors. Now we try for each of these the vertex itself and its neighbors to make that vertex part of the solution. Um so we first form the set of the vertex and all its neighbors. Then we delete these from the graph and we check if we can find an independent set with one fewer vertices in the rest and then of course at the end we add this vertex back in. The way the the reason it's written like this here is that it might be that the recursive call says I can't do it. I think in the previous code I just wrote union with um this this one element set and the union with not possible is maybe a bit questionable but uh what we really do is here's at most six uh different vertices maybe the independent set contains one of those and um let's try all all options uh I think you You can also say why why is this even correct?

34:48 If you locally look at a graph, so this is the vertex we look at our V and its neighbors, they're connected to the rest of the graph in some arbitrary way and they can be connected among themselves just not to V. uh whatever independent set I try to pick in this graph, it's stupid not to pick not either at least one of those vertices. If I contain any of the outer ones, fine. If I contain this middle one, fine. But if I cont if I contain none of the red vertices, I might as well add the vertex V. So this uh relies on the idea that without loss of generality any any maximal independent set and maximal here just means I cannot add more vertices. It's not necessarily maximum overall largest size. Um but this is is certainly good enough and gives us uh a correct solution if we try all all options. Um for the running time observe that we have at most six recursive calls by plinarity and um in the worst case we have to go all the way down to k equals zero and then uh we always reduce k by one right. So clearly we have six to the k recursive calls in the worst case and so um um maybe each can be just uh what do we have to do? Um sounds like all of this can be done in linear time.

37:15 even if you just recmp compute this each time. So that's enough for the claimed total time from the theorem. Let's also use um another little trick here.

37:44 Few spoilers. So um this is of course correct, but note that in a planer graph the number of edges is at most 6 n. So we might as well write theta n. No difference.

38:01 Okay. So what we're seeing is um that this problem in general is hard independent set is is well we'll see uh W1 hard. So you can probably not find an FPT algorithm. Um the problem of independent set solving in general is is uh NP hard even for planer graphs and max degree three. But you can at least have an FPT algorithm for this restricted version. And this is even a slightly more general technique, right? That uses some graph theory. In this case, this degeneracy notion.

38:43 I think this often is rather a hope. This is um not quantifiable in some some interesting sense. It's just often you can return early. That's all I'm referring to here.