Video 2-9: Important NP-Complete Problems

0:01 Two more things to cover in in this unit. The first one is a quick list of NP-complete problems that you often see. I'll basically just rattle these off and roughly try to illustrate them very very quickly. These are meant as a list for you to look back to in case we uh might potentially ask in some exercise sheets to do some reductions or things like that. Uh so let's look at some of these um they're also maybe just worth knowing the names of. Okay, a dominating set is in a graph a set of a collection of vertices so that um all the edges uh all the vertices are covered. So I want to select some vertices so that uh for every vertex I have one I have either the vertex or one of its neighbors in my set. So I guess here I can cover everything with these two for example. That would be a dominating set. Now of course always here these are the decision versions. So I'm also given a threshold. The question is can I pick at most K vertices so that for every vertex either the vertex itself is red is included in my set V prime or one of its neighbors is. in that set. Okay.

1:29 Is it a bit like vertex cover except that here we're actually covering the vertices by picking vertices. Whereas vertex cover as you will remember is putting lamp lights on a street network so you're covering the edges. Okay. Uh then Hamiltonian cycle is just a yes-no question for a graph. Is there a way to have a simple walk a tour that connects every vertex and visits uh visits every vertex exactly once. And um For example, here I cannot do it the way I put the graph. Well, not with my simple version, anyways. Maybe there is a way.

2:16 Let me cheat and modify the instance on the fly. So, this would be a yes instance because there is a way to go through every vertex exactly once, not revisiting anything, um but also not missing any vertex. A vertex simple for me is just every vertex appears just once. And I'm trying to stress that because you could also have an edge simple walk, which is a walk in a graph where you're allowed to come back to the same vertex, but not the same edge is used twice. If you replace in this problem, if we replace um edge simple cycle by uh by if we replace vertex simple cycle by edge simple cycle of length E, It's supposed to be an E. Which problem do I get then?

3:35 I'm given a graph. I'm trying to find a cyclic walk that uses every edge at most once, but also has length number of edges. How often can I use every edge? Well, at most once, but also need to use all of them because I'm I'm supposing the length is the same as the number of edges. So, that must be an ordered Euler cycle. Euler tour. And as you may know, here is is one of these cute examples where changing a bit the problem changes the complexity a lot. Then this would be finding an Euler tour in a graph.

4:17 And deciding whether a graph is Eulerian is is even trivial. You just look at all the degrees. You know this Euler theorem for for undirected graphs. Uh it has an Euler cycle if and only if all the degrees are even. Uh so, here this is just an as an aside, sometimes right changing the problem just slightly it feels like you're changing it slightly, but it makes the complexity vastly different. Okay, two more um graph problems. Clique is the question of whether you can find uh a complete embedded graph. So, here with K equals 4, I can find this K4 instance here. So, that uh if I pick just these vertices, so formally a subset of the vertices of a size at least that uh the given by the threshold, so that within that set all the edges are there. That's for example true for this little four uh clique here. An independent set is is the opposite.

5:22 It's the same problem except that here I want all the edges not to be there. So, clearly these two problems are the same on complementary graphs. If I flip for every pair of vertices whether an edge is there or not, then every clique here is in the complement graph an independent set.

5:52 Uh let me be lazy and say I'm picking an independent set in this graph by picking this and this and this, say. And also I want to maximize this. Okay? Questions? You know these problems?

6:10 Well, now you do. Hopefully. Um then we have traveling salesperson, what we've seen before. Here a bit more formally defined. We're given this matrix of distances. In the general case, no further restrictions. So these are It's just some tableau of numbers. Um almost always people mean the symmetric version, where going from I to J is the same as going from J to I. But in principle, you could also have different distances there. And the question is, is there some permutation, which is a tour, where you visit cities in a certain order, so that if you sum the edges along this permutation, you get at most K. So, let me add here the general version is unrestricted to in any way.

7:08 And asymmetric as Well, if it's not stated. But uh mostly people consider symmetric. And a very natural restriction for these distances is that they satisfy the triangle inequality, so that they form a metric.

7:42 So let's give that a name. Met- Okay, I'm going to try Metric TSP, so this means it's never cheaper to go from I via K to J than directly from I to J. Triangle inequality.

8:18 It's okay. So, this is supposed to be true for all triples IJK. Uh this turns out to help you a bit in solving the problem. Um Well, we'll see that um again later. Maybe as a foreshadow, you can keep keep that distinction in mind. It'll come up again. Maybe let me not spoil it with Okay, uh graph coloring is a different different question about graphs. Uh here if you don't say anything specific, then it's what it refers to is the vertex coloring. So, you have some graph with edges, and now the question is can you assign colors to these vertices so that along an edge I never see the same color. So, I could here say this is green and this is green. I can make this green, but sadly I have this odd cycle here, so I cannot do it with two colors. I need a third. But this would be a valid coloring.

9:18 There's no edge that connects vertices with the same color. And this minimum minimal number of color would be the optimization version here. We're given some threshold, and again the question is formally, what's a coloring? Well, it's a mapping from the vertices to the first K integers, and then every edge needs to be differently colored on the endpoints. Okay? Uh the set cover problem is a bit more abstract, but often a useful one. We have some some ground set. The um first n integers. And then we have m subsets of this ground set. And a number k, and the question is can I cover the entire universe with picking k of the sets? So here you might imagine the elements in the ground set are somehow points. Then maybe here my um sets are some subsets here.

10:18 And they can overlap in arbitrary ways. And the question is can I find three of them that together cover everything? And let me not make this so degenerate.

10:33 Uh namely, what is okay is to pick this one. Red for solution. So I pick this large That covers most things. I might cover these by adding this set. So I'm I'm double covering this point. This is okay. All I care about is that the union is everything.

11:05 That's also NP-hard and NP-complete. Um it remains so even if you assign costs to these sets. So some are cheaper to use than others. So we again we want the same restriction that we cover everything. But now we also have a budget for how many total costs we're allowed to spend on the sets. In a way if this is if this is NP-hard, then clearly this is even harder. You could just set all the costs to one and then it would be the same problem. So that's not surprising that this is harder, but also both are in in NP.

11:43 And last one, promise for now, that's it. Um, these are a bit more further out. Let me start with the last one because this is maybe something like the closest to being so restricted that you should think this is no longer hard, but it still is. Which turns it into a a very strong reduction partner. This is often one that you can good do good reductions from. And let me also mention the restriction so that I don't forget. So what is what is exact cover? Um, you're given again some ground set of the first and integers and subsets. It's the same question as for uh set cover, but now I'm I'm very strict. I want disjoint sets. In uh formal way of writing this here is that the sizes of the sets together have to be exactly in. If they're also covering n elements, then that means they are disjoint. So if I'm I'm reusing my example here, I could take this guy, but there's Yeah, this is a no instance for this problem.

13:06 Okay. There's no way here to cover everything with disjoint sets because of this guy, right? There's uh Uh, I can either pick this or I can pick this that. Um, I have to pick this longer set to cover the point here on the outside. But then I have no way of covering this point without What on what? No, this is the problem, right? This point I need to somehow cover. This point I need to somehow cover. This I need this set. Then here these these two points together are kind of the certificate for problems. They both need to be covered and they only occur in sets that overlap on this point. Okay. So, exact cover is a bit more restricted and you can even more restricted further to X3C.

14:12 Which is exact cover by three sets. And a three set is just a set that has three elements. So, here all the SI's have exactly three elements. And they should still be disjoint. So, here it feels like there's even it's even a challenge to come up with yes instances. Because they're so tightly constrained. Um but this is also NP-hard. NP-complete.

14:51 Okay. Uh the last two, um closest string is a um fun one that we'll come back to if you have some n strings over the over a joint alphabet of the same length and the threshold. Um you would like to find some some consensus string, some string they can all agree on at least mostly. So, some other string so that the Hamming distance, which just counts how many positions are different, the for every other string SI, the distance to this S, the number of disagreements, should be bounded by K. And that's so it sounds rather innocent. Maybe you just take the majority character in each position or something like this, but not in general possible. Um it doesn't doesn't always work with a simple algorithm, not that we know of, and is NP-complete. And the last one, max cut, is again a graph problem where you uh I think if you've done efficient algorithms, you will know the the max-flow min-cut theorem.

15:54 And you will remember that flow is actually an easy problem. You can even with fancy new results, solve it in near-linear time. Uh and so min-cut as well. But max cut is a different beast. Here um I have some edges here.

16:19 Um I'm now trying to find a way to put my vertices on two sides of a sub of a division. So there's the ones in my set here, C. There's the ones in my set C, and there's the others. And so I'm cutting all those uh edges that go from a vertex in the set to a vertex outside of the set. These are the ones that I want to count, and I want many of them. For min-cut, this was give me a cut that has few of these edges. And that's easy to solve, but if you want many of them, then it's hard.

17:08 I have to break my promise. I'm sorry, I forgot there's a fourth page. I was there. I was missing this one. Um because people asked about P complete problems initially.

17:20 Uh this we'll see in the next section. So, maybe we can skip them for now. Um bin packing is is a useful one sometimes. So, you're given items with certain weights. Larger and smaller blobs. And you want to assign them to a little buckets or baskets all of the same same size, little b. And question is how many of these baskets do you need? You can assign each item to one of the K baskets. You're given a threshold K how many you have at your disposal. The question is can you assign them so that every basket stays below its its size its capacity. Okay.

18:09 Subset sum is in a way a restricted version of this. You only have uh Uh okay, in this formulation slightly different. You have numbers and a target and you're trying to make that target specifically with picking a subset.

18:24 So, that the items in that subset add to exactly this value T. There's the a related problem partition which is the bin packing problem where you have exactly two bins and you want the all the items distributed so partition is bin packing with K equals two. And then of course this uh B uh is more restricted. B is just N half. So, the partition problem again one of those that seems to be at the edge of just so restricted that it should be solvable, but no. Uh just put elements into two equal equal weight subsets.

19:21 Okay, let's talk about this last one briefly. Who has seen linear programming before? Most. Yeah, linear programming or LPs, uh, linear integer programs and so on. Um, we'll we'll talk a a lot more about this later. So, for now, if you've not seen it, this this notation is maybe a bit cryptic. Um, but of course, um, in a way formally is everything's well defined. You're just given a matrix of numbers and some vectors and some, uh, some threshold K. And the question is, can you find some variables? There's a um, the number N is is part of the input. Each of the variables, you have N variables that you can set and they each can be zero or one. Is there a way to satisfy simultaneously these inequalities where this is, uh, a matrix vector product, right? And this less or equal is element-wise comparing um, the first component of this vector on the left and the first component of B and the second component, all of these should be less or equal.

20:29 And at the same time, um, this is a a scalar. CT is a um, is a row vector and then X * C, the the scalar product is a number and that should be at least some threshold. So, if you know linear programming, this is the standard form of linear programming if you do a um, a maximization problem. If you've never heard of linear programming, then you can forget it for now. We'll cover this in more detail or with more intuition later.

21:06 Okay. This version, of course, because I mentioned P complete, let me make that point clear. This is NP-complete. If you insist that the variables are integers, 0 1, that's what the the integer here means. It's the variables that that the inputs up here are integers. This is without much loss of generality. You could allow any rationals. Uh but here, this is important. If the variables can be continuous ranges, continuous reals between 0 1, then the problem is is in P and is also P complete in the right formula for formulation.