Video 2-8: Further hard problems

0:02 In this section, I'll briefly introduce some these problems that you've you've seen and used before. Uh but just so that they're um given with some specific notation that we can refer to. Uh I hope I've been consistent whenever I use them. So dominating set is you're given a graph and you cover all the vertices by picking vertices a subset of vertices so that every vertex is either picked or one of its neighbors is picked. Hamiltonian cycle means a path in a vertex that visits every vertex exactly once. So there's two versions directed and undirected given depending on whether the graph has has direction on the on the edges. These are all uh part of the classic problems that you worked on or some of you worked on. Uh click is can you find in a graph a complete subgraph of circle size where all possible edges are there. An independent set is the opposite. Can you find an empty subgraph of a circle size? Then we had the the traveling salesperson problem which appeared uh earlier on. So I don't want to repeat the definition.

1:22 Um we'll come back to that uh in the next chapter. And then graph coloring is a it's a problem where again given some graph and we have to assign colors to the vertices so that none of the edges have the same color on the two end points and the question is can we do this with a certain number of colors. Uh set cover is a is a problem that will will come back to us at some point uh later. We're given subsets of a universe and we try to cover the entire universe. We have to pick subsets so that all elements are covered and the question is can we find a small enough selection. There's a weighted version where the sets have specific costs and then the question is can you do with them bound on the cost. Um this is actually a general theme that you will see in many problems. There's often a a combinatorial version where the cost is just the number of things. Uh and then there's a weighted version where the cost is the sum of the costs of of the elements you select. And often times the two are very similar. It's uh it's often the case that both are hard or both are easy.

2:36 I mean one one example where both are easy is is uh shortest paths in graphs. If you have a graph that's unweighted then this is just refer search and you find the shortest paths by number of edges and if the edges have weights then you know algorithms for that as well either Dystra's algorithm if the edges are non- negative or Bellman Ford then you can find the shortest paths by the sum of edge weights right in this case both problems are in P they're efficiently solvable Now uh a problem that's a bit different from the others we've previously seen is this one closest string. Here we're given uh a collection of strings of the same length. And the question is can you find some some other string that has distance at most k to each of those strings. And distance just means how many characters are different. So you count how many mismatches you have and that's also a hard problem. Um we might come back to this at some later point. Uh max cut is again in a graph. Can you uh distribute the vertices into two sides, a left and a right or a set s and t so that uh the number of edges that go across the cut have one end point in one set and the other in the other set is maximized or is above a a certain threshold. And we know that the converse problem minimum cuts is in is is a problem in P. It's efficiently solvable.

4:16 That's the famous max flow min cut that you may have seen in in algorithms classes. But if you flip around the problem and you ask for a cut with many edges across the cut, it's a hard problem. Uh and last one is again famous uh cut problem exact cover. It's similar to set cover. You have subsets of some universe and you want to cover all of the elements in the universe, but this time uh you're supposed to cover each element only once. So the sets have to be disjointed as well. Any questions on those problems? Many will be familiar like you've uh had those before. As I as I said, I just wanted to have a canonical definition that we can refer to if we use those problems with those names. Of course, there's many more problems and many more NP hard problems. In particular, this book uh on computers and intractability. Gary Johnson has hundreds of problems that are known to be NP hard or NP complete in many cases.

5:24 I think all those problems are NP complete. Uh but we don't we don't need all those problems here. Yeah. Um how is Hamiltonian cycle different from ah yeah so the traveling salesperson problem I I didn't go over the definition properly but we'll actually need it in the next section. So maybe it's good to uh revisit uh here the input is is a complete graph but it has weights on the edges. So in a way um you could say uh TSP is a weighted version of the Hamiltonian path problem where the Hamiltonian path has a graph without weights. there's either an edge or not an edge between two vertices and you're trying to find some round trip but you can only use existing edges and tsp all the edges are in principle there although you could put the cost of an edge so high that it's effectively not usable anywhere um in principle all the connections are there but they have different costs and so the question is to find the shortest round trip or or one that's below a threshold. Wow, that was a good question. Um, but the problems still feel very similar, right? They they're closely related. This will this will come back actually.

7:00 Okay. Uh, other questions about the problems. Uh there's a few more um that have a a slightly um more numerical flavor. Uh subset sum is given a list of integers um and asks if there is a selection of those that sum to exactly zero. So really these are positive or negative. uh you can I guess we technically haven't defined um for our touring machines how we deal with negative numbers but I guess you can imagine there's a minus in front and you have to adjust how the uh arithmetic works. Uh you could also formulate the problem with giving a specific value that you're trying to match. But this uh I found this one surprising when I first learned about it. So you just a a collection of numbers. Why should it be hard to find some subset that sums to a certain value is uh but it's also a hard problem? Uh you can do reductions. Um the knapsack problem uh we'll see later again is given a collection of items. So these items one up to n they have a weight and they have a value and you're trying to fit um as much value in in your knapsack but you can't exceed the weight bound. So the collection of items that you select has to sum in weight to at most a certain threshold and you're trying to achieve at least value K.

8:44 Um, bin packing is also given items, but here we only have weights and some some capacity for for bins. And we're trying to put the items into as few bins as possible. So here the uh the way I've formalized it here is you assign um the elements to one out of out of K bins and then in each bin you have to sum to at most capacity. Uh there's for most of these problems there's an optimization version and the decision version. Uh we'll come back to that. Uh and the last one um uh this might also be a good question. This will this will come back in in in many cases. Who has who has done some course on uh linear programs and linear optimization LPS and ILPS? Has anyone seen that is okay then maybe um it's worth spending some time on this in another chapter is a beautiful beautiful piece of theory or applied mathematics or um I don't know what you want to call it is often done as part of operations research so businessoriented studies often do a little bit of that because it's a a standard tool that you can use to optimize business processes production and so on. uh that is also a great algorithmic tool. Okay, so I'll I'll plan a little bit on that. Um for this problem, maybe this sounds a bit weird then for for for you, but uh uh the definition I guess is easy. You're given some uh matrices or vectors of numbers. This matrix A and a vector B and another vector C and some threshold.

10:33 And the question is can you find a vector of zeros and ones so that here this is a matri matrix vector product standard linear algebra comes haunting us again. So you multiply this this vector on the matrix and you get back a vector and so this lesser equal is intended to be element wise lesser equal the first entry of the vector should be smaller second and so on. So this is uh essentially a a system of linear inequalities. That's what that says. Um so you're trying to find some some vector x that satisfies a system of linear inequalities. N has a dot product with this other vector c that's above a threshold.

11:21 So the theory of of um linear optimization these are site conditions maybe um capacities of some machines that you cannot exceed and this is somehow the uh the gain or the the reward you get your your profit and x is somewhere you can have a decision do it here or do it there. uh we we'll come back to this then. Okay. But as an abstract question, this is also an NP hard problem if you're trying to find these uh 01 vectors that satisfy these inequalities. Okay. Uh that should be all uh questions on this on the second set of problems more integer related ones.