Transcript

the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu all right Welcome to our second lecture on what to do when you have an NP hard problem so two lectures ago we saw how to prove problem as NP hard last lecture we saw uh if you want polinomial time uh but you're willing to put up with a not perfect solution but you want to get within some factor of the best solution that's approximation algorithms today we're going to do uh a different thing called fixed parameter algorithms these are going to run in exponential time in the worst case but not so bad in a certain sense which we will get to in general the theme of these last uh two lectures and this one is that we'd really like to solve hard problems we'd like to solve them fast uh meaning polinomial time and we would like correct Solutions also known as Exact Solutions okay we'd love to solve NP hard problems in polinomial time exactly but that's not possible unless P equals NP so pick any two that's the general idea uh this is a bastardization of a joke which is uh sleep friends work pick any2 that's the MIT motto um here in algorithms hard fast exact picked any two so most of this class is about these two polinomial time algorithms give you exact things that's the class P uh last lecture was about hard problems uh we drop exactness we still want polinomial time we still want to solve hard problems so this is approximation algorithms and what we're doing today is the other combination so uh we want exact but we're going to sacrifice how fast things are they're not going to be polinomial time in a strict sense but it's going to be somewhere in between polinomial and exponential this is an area called fpt for fixed parameter tractability uh so what's this parameter business um in general the idea is that we we really want an exact solution to an NP hard problem which means it has to take exponential time in the worst case but we want to confine the exponential dependence uh to something called a parameter okay we actually use parameters all the time for example in a graph there's two typical parameters you think about the number of vertices and the number of edges if you're sorting an array the the usual parameter you think about is the size of the array okay that's all I mean a parameter uh in general is just some uh some kind of size or complexity measure so in general a parameter uh is going to be uh I'm going to call it K of X and it should be a non- negative integer and X is the input so you're you're thinking about some problem uh like a problem we'll be looking at today is vertex cover which we saw in last lecture vertex cover you're given a graph uh and based on that graph uh we're going to Define uh some function of that graph so this is the input to the problem and K is just going to be some non- negative integer which is a function of that input it's just some measure of how tough your problem is okay and what we would like is a running time that is exponential in K but polinomial in everything else Pol in the size of the problem in v and E okay so that's the the general uh goal is polinomial in the problem size which we usually call n and exponential in the parameter which I'm calling always going to call K in generally you could consider more parameters but we're just going to think of two uh the size of the overall size of the problem and some particular parameter that we look at called k um so if you can achieve this which we'll call fixed parameter tractability I'll Define it formally in a little bit because there's more than one way you might think of defining it some are right some are wrong um if you can achieve this what you get is an exact algorithm for your problem that runs really fast provided K is small so this is sort of a way of saying well you know the problem is empty hard in general but as long as this this measure K is reasonably small I'm I'm still able to solve it really fast so it's a way of characterizing kind a wide family of uh a big subset of the problem that you can solve you know that in general it's going to you're going to need exponential time but this gives you a measure of how hard your input is may not be the only measure may not be the best one in any sense but if you can if you can define a parameter and you know that in your practical scenarios that parameter will be small then you're golden then you can actually solve the problem in a reasonable amount of time and get an exact solution no approximation here so that's the that's the idea so that was a parameter uh we're also going to define a parameterized problem uh this is just a problem plus a parameter okay so we already have some Notions of problems we can take any problem that we've looked at before like vertex cover and if we just Define some parameter then we get a parameterized problem when we put these things together and usually we would write it as something like oh take this problem and then consider it with respect to uh this parameter and in general for a single problem there may be several natural parameters that you want to care about usually there's actually one obvious parameter uh so let's uh do that for vertex cover but in general we can talk about a problem with respect to different parameters and some of them may be feasible to solve in this sense some may be not all right so I'm going to define a k vertex cover this is almost the same as vertex cover just has a k INF front uh but the K means that it's a parameterized problem instead of uh just a general problem so as in vertex cover we're given a graph G uh and I'm going to think of the decision version of vertex cover so we're given a non- negative uh integer K and we want to know is there a Vertex cover of size K let say less than or equal to K uh is there a Vertex cover remember a Vertex cover is a set of vertices that cover all the edges uh and we want the size of s to be less than or equal to K okay so every for every Edge we need to choose one of the two end points we want the total number of chosen vertices to be at most K uh and so that's a regular decision problem but for parameterized problem we also want to define a parameter function and that parameter function guess what K most obvious thing given that I wrote the letter K here uh that's going to be our parameter okay and most problems a lot of problems especially decision versions of optimization problems like before we were minimizing the vertex cover this is the decision version where we want to decide whether there's one of size at most K if you can solve this of course you can binary search on K like you did in your quiz hopefully um so uh that's all good and a lot of problems have this some non- negative integer floating around and that's the kind of the obvious choice for the parameter doesn't have to be the only one but uh today we're just going to look at vertex cover with this parameterization uh in your problem set you look at another problem with another uh natural uh parameter this is usually called the natural parameter but there's no formal definition of natural right that's just intuition all right so that's the setup let's do some algorithms uh I guess the first note is that K can actually be small uh nice example is a star graph so you have uh V vertices uh but what's the smallest vertex cover one everyone's holding up one finger uh you choose this guy that in the center that covers all the edges so it can be the K is much smaller than V and our goal here is that uh we're going to get some polinomial dependence in the size of the graph but we're going to get an exponential dependence on K now there are many different ways you could think of exponential dependence but let's start with what would be the really obvious Brute Force solution to vertex cover okay I want exact uh not going to be clever what's the obvious algorithm to solve this yeah com try any combination of K vertices see if it's a Vertex cover how many combinations of K ver vertices are there and choose K see I'm a little out of practice it's been a while uh close off by one uh so uh try all n choose K I guess V choose K uh subsets of K vertices if I want wanted to match this definition exactly I should try all subsets of less than or equal to K vertices but hey uh if I if I choose fewer than K vertices why not add in a few extras until they get up to K so it's enough to look at Vose K subsets because uh subsets of size exactly K uh because that will end up giving the same answer as this question okay uh so for each test each of those choices for coverage so that just means we Loop over uh I guess for every vertex in our set we Mark all of the incident edges as covered and then we go through all the edges and see whether everyone got marked covered if not we uh reset try the next subset okay this is like a not smart Dynamic program you just guess what the subset is and see if it covers uh this is how you would prove that this problem is in NP right but now we're actually making it an exponential algorithm so what's the running time of this algorithm yeah e v e * V to the K good B uh so that's obviously exponential in a certain sense the dependence on e and V is in the bottom which is good uh and the K is in the exponent which makes sense so this is not surprising uh we also don't think of it as good we Define this to be bad okay in general we think of a running time like n to the F of K where n is sort of the overall problem size here here n is basically V plus e that's the overall input size for a graph if we have a running time uh where the exponent of n depends on K in a non-trivial way we think of that as a bad running time this is not this is a slow algorithm it's slow because even when k equals 2 if you have a large graph this is probably not something you want to run definitely when K is 10 you're completely hos this is very impractical and the formal sense in which it's impractical is that the exponent in N uh depends on K in general um you cannot say so I'd like so the I mean fix parameter the whole point is to think of the parameter being fixed like a constant okay now if the parameter is fixed if you think of it as at most 100 then uh indeed this will be at most you know n to the 101 or something so it is polinomial for any fixed K the catch is that the the exponent of the polinomial depends on K as you increase K as you increase your bound on K the exponent increases I can't say that this is an N squared algorithm for any fixed K okay so exponent depends on K that's the bad case so the good case we're going to Define uh is that the exponent doesn't depend on K that may seem like a small change it is a small change but it's a big one uh it's a small change with a big effect so I'm going to Define uh let's say a parameterized problem is fixed parameter tractable which given how many letters that is we're going to abbreviate to fpt uh if uh it can be solved in F of K times polinomial in n okay uh because this means that uh the exponent here doesn't depend on anything exponent of n uh doesn't depend on K okay so for this definition just to be explicit I want the constant here to be independent of course it should be independent of N and it should be independent of K uh this can be any function it's presumably an exponential function because this uh if this is an NP hard problem something's got to be exponential this clearly is not exponential so it's got to be here so this is the sense in which we're exponential in K polom in N but it's much better than this kind of running time okay well we can think about what in the sense in which it's much better once we have an actual algorithm of this type so let's do let's try to solve vertex cover in this kind of time I claim vertex cover is fixed parameter tractable there is such an algorithm and the algorithm is going to look familiar very similar to the two approximation algorithm that we had last class for vertex cover uh so uh but I'm going to give it a different name which is bounded search tree okay this algorithm is also going to feel like dynamic programming or we're going to use guessing in general exponential algorithms it's natural to use guessing but here when I guess I have to try all the possibilities here this was one way of trying all the possibilities we're going to be a little bit more sophisticated in how we try all the possibilities it actually exploits the properties of vertex cover uh first line is just like the two approximation algorithm look at any Edge in the graph okay uh here it is from U to V what do I know about that picture yeah of those has to one of those vertices has to be in the cover either U or V or both are in s for that edge to be covered now for the two approximation we just put those both in here we can't afford to do that because we want an exact solution uh so we'll try both options we don't know which one belongs let's guess so we know either U is in s or V is in s uh uh don't know which so guess uh so I should to be clear mention or both uh so we're going to guess which means we need to try both options uh we're going to try uh putting u in and then we're going to try putting V in so let's just see what happens we try that so in the first guess we say let's put u in s okay well when if we put u in s that means we cover all of the edges incident to U so I'd like to use recursion I'd like to simplify my problem get another vertex cover instance so in order to do that I'm just going to delete you and all of its incident edges we did a similar thing in the approximation algorithm but for u and v simultaneously so delete U as incident edges now we have a a vertex cover instance uh there's one other thing there's a new graph we have but we also need to update K because we just used one of those uh we just added something to S and then we deleted that from the graph which means in our new graph effectively K has gone down by one okay so I'll say decrement K now I have a new instance I have a new graph and a different value of K uh recurse of this algorithm uh I would say I'll call the new graph G Prime and the new integer K Prime K Prime equals K minus one okay and then uh the second case is do the same thing for V I won't write the code exactly the same but I delete V in its incident edges I still decrement K by one and I recurse and uh then I just return the or of these two answers so if this one finds a solution great I found a solution to the overall problem this one finds a solution great maybe both uh return Yes doesn't matter in general I just take the the uh inclusive ore of those two Boolean values that gives me an overall yes no answer to K vertex cover cool so uh next question is what the running time is but you can think of this as a dynamic program it's just here we recurse and we don't bother memorizing because in general memorization will never help us here and you may have even thought of algorithms like this in the dynamic programming world and we just say well that's not good enough because dynamic programming we want polinomial time this is like a dynamic program but the running time's exponential but it turns out it will be fixed parameter tractable that's the good news let's think about the running time so uh if I draw let's draw a recursion tree right this is a Rec this is a divide and conquer algorithm in a very weak sense uh we start up here with uh with a problem of size n and a parameter k and we make two recursive calls uh okay we deleted a vertex and maybe some edges so let's say we have a new problem of size something like n minus one but what really saves us is that K went down by one and we have two recursive calls each of them K is one smaller okay and then each of those has two recursive calls I don't really know what happens to n it doesn't probably doesn't get that much smaller but K goes down by another one okay so I'm writing here the size of the problems and the parameter of the problems nus 2 K minus 2 okay uh how much time do I spend in each of these nodes how much work am I doing uh non-recursive work am I doing in this algorithm yeah o e right o of E Yeah certainly at most order e probably also at most order V uh because there's only at most V incident edges to each vertex yeah linear time doesn't really matter uh how careful we are here um but I will say each of these nodes uh we spend at most uh V let's say order V time okay it happened that V went down down by one at each of these levels but certainly an upper bound is the original V in each of these nodes we spend at most the original V uh when does this recursion stop I didn't write a base case help me out what's a good base case for this this algorithm yeah when k equals z check if there are any edges when k Z I can't put anything into my vertex cover so if there are any edges they're not going to be covered that's bad news Okay so uh over here we have uh base case uh k equal z uh check or let's say return whether uh size of e is not zero if it's not zero sorry whether it equals zero get it right if it equals zero then the answer is yes there's a Vertex cover I can cover all of those zero edges using zero vertices that's good uh but when e does not equal zero there's no way I can cover that nonzero number of edges using zero uh vertices in my vertex cover okay so that's the base case which means this recursion keeps going until we get down to k equal 0 we start at K we uh end up with zero so the number of levels here is K okay the height of this tree this recursion tree is K so how many nodes are there are there in this tree two to the K so total running time is V * 2 to the K I guess I should write two to the K times V hey that is exactly what I wanted I got a function of K namely two to the k exponential that makes sense and I got a polinomial in N uh here uh it's n my the exponent is One V is at most n n is V plus e wow big Improvement this seems equally uh simple of an algorithm as this one but actually it's runs a lot faster okay let me give you a feeling I mean this is what we would call a linear time algorithm for fixed K the exponent here doesn't depend on K if K is 10 it's a linear time algorithm if K is 100 it's a linear time algorithm K is 100 that might be a little bit beyond but we could run but you know k equals 32 40 maybe that would probably be reasonable running time in practice okay that's a lot better than before where like k equals 2 or three this is probably unreasonable V is like a billion say big graph uh also from a theoretical perspective this works even up to k equals log n if k equal log n this will be you know n s that's nice k equal 2 log n it's n cubed okay so it you know it grows but uh we can handle k equals order log n and this will still be polinomial in general with fixed parameter algorithms it's not always going to be up to log n it's going to be up to whatever the inverse of this F of K is that's where we can still be polinomial uh so that's nice I consider this a good running time good in the sense that it is it follows that definition of fixed parameter tractable so the bounded search tree algorithm is good Brute Force algorithm is bad in this case BR uh bounded search Tre is a general technique you can use it for lots of problems uh we're going to see another technique today called kernelization uh but let's see before I get there I want to question this definition so this definition is nice it's natural in the sense that it gives you uh it it distinguishes between the exponent of n depending on K and not depending on K which is a natural thing to do but there's another natural definition of uh fixed parameter tractability so let's vertex cover you remember the problem by now uh so let's see we have this definition which is f of K * polinomial n but I would say the first time I saw fixed parameter tractability I thought well why do you define it that way I mean maybe it would be better to do F of K Plus polinomial in N that would be better right that would be faster seems like uh so I mean this is nice that we achieved this bound but could we hope for this even better bound okay turns out these Notions are identical this is weird the first time you see it so uh theorem uh you can solve a problem in this kind of time if and only if you can solve the problem in this kind of time so the of course f is going to change and why don't I label these constants so we have C up here and some C Prime up here but you can solve a problem in this multiplicative time if and only if you can solve it in an additive time with a different function and a different constant uh this is actually really easy to prove longer you think about it the more obvious it will be um if you have an instance of size n with parameter K uh there are two cases uh either n is less than or equal to F of K or uh n is greater than or equal to F of K right well got to be one of those maybe both uh if n is less than or equal to F of K that means that this running time uh F of K time n the C uh let's see n is at most F of K so this is at most F of K to the C+ one power right I multiply F of K to the C * F of K uh when n is greater than F of K then I know that this running time F of K * n the C well now I know an upper bound on F of K I know that this thing is at most n and so this is at most n the C + one okay so really I have two scenarios either I'm bounded by some purely function of K or I'm bounded by some purely polinomial of n which means in both cases uh the running time F of K * n the C uh is bounded above by the max of those two things Max of f of K to the C +1 n to the C + 1 okay and the max is always at most the sum I'm assuming everything here is non- negative so I take F of K C + 1 plus n the C + 1 boom that is an additive function of K Plus polom in N okay rather trivial uh this a funny area where you think oh this this deep question are these things the same and ends up yeah they're the same for obvious reasons uh so for example we have this uh linear basically n * 2 to the K algorithm if you apply this argument uh you get that this is at most so this uh n * to the K bound is at most what n^2 + 4 the K okay I'm basically just squaring both of the terms okay probably you prefer this time bound but if you really like an additive time bound the exact same algorithm satisfies this okay uh so not that exciting uh n in practice n squ looks like a bad thing so you probably prefer this kind of running time but there is a sense there's a quadratic thing going on here and that we have an n and we have a function of K multiplied together okay whatever um all right so this justifies the definition it's kind of robust to whether I put a dot here or plus so clearly this is the right definition we're going to use dot you could also use plus but all right uh but there's another thing called kernelization which in an intuitive sense matches this idea of Plus and it also matches an idea that's common in practice called pre-processing if I have a giant graph and I give I'm given some number K and I want to find a Vertex cover well maybe the first thing I could do is simplify My Graph maybe there's some parts that are really easy to solve I should throw those away first uh and that will make my problem smaller so if I'm going to have an exponential running time presumably I want to First make the problem as small as I can then deal with the one of these algorithms okay so we're going to do that uh first I'm going to tell you about it generically and then we'll do it for vertex cover so first uh let me give you uh definition of what we'd like out of this pre-processing procedure it's going to be called a kernelization procedure um kernelization algorithm is a polinomial Time algorithm okay back to polinomial timeland uh it's you can think of it as a reduction but you know with NP hardness we reduce from one problem a to another problem B here we're going to reduce from the problem a a to the same problem a it's a self reduction if you will but the input to the problem is going to get smaller so we're going to convert uh an input so this is for a parameterized problem so an input consists of some regular input X and a parameter K and we want to convert it into uh an equivalent small input uh X Prime K Prime uh to the same problem okay problem is fixed say vertex cover so we're given an arbitrary input this would be a graph and a number K and we want to convert it into an equivalent small input to uh which is another graph G Prime and another parameter K Prime so equivalent means that the answer is going to be the same okay I want the answer to the problem uh let's say answer of X comma K to be equal to the answer uh to X Prime and K Prime again same problem but different input uh I'm trying to be a little generic here it could be this we're going to think here about decision problems but this makes sense even for non-decision problems whatever the answer is here should be the same as the answer is here because I want an exact solution I want to solve exact exctly the problem I want to compute this answer exactly correctly so if I can reduce it to some X Prime K Prime with the same answer well now I can just solve x Prime K Prime so that's good now what does small mean I need to Define both of these small means that the size of X Prime which you might call n Prime uh should be at most some function of K cool so this is interesting so we started with a probably a giant problem X has size n and we have a parameter K which we presume is relatively small and we convert it into a new input X Prime that's very small its size is a function of K no more dependence on n n has disappeared from the problem okay we started with something a size n we produced something whose is function of K and then okay there's some other parameter K Prime doesn't matter much what it is it's going to also be a function of K so we started with something of size n we produced something of size K in polom time wow this is this would be big if we could do it because we start with giant problem small K and we kernel it down so here's the picture with this big thing and the intuition is that the hardness of the problem is just just from this thing of size K but there's no thing of size k at least we haven't found it yet right this the the K is the size of the vertex cover we're looking for but we don't know where that is it's hiding somewhere in this instance this is a morphous blob size K but somehow magically this kernelization procedure uh produces a new problem that's only a little bit bigger than K okay some function of K so we take the big problem we make it down to the small thing what do you do now you can run any algorithm you want any finite algorithm applied to this instance will run in some function of K time doesn't matter as long as it's a correct algorithm and if your problem is in NP uh there is a uh exponential time algorithm you just try all the guesses so we could use we have two of them here we could run either of these after we've kernelized uh and we would get an fpt time and indeed uh the fpt would mimic this kind of running time we do a polom amount of pre-processing that's the kernelization procedure that's the only dependence on N after we've done that the new problem is entirely a function of K and then you apply any algorithm to that you'll get an F ofk running time now if we want a good F ofk we should use the best algorithm we have but uh in general you could use anything all right so far so good um uh so we had this theorem that product is the same as Plus in fact kernelization is the same thing so uh these are all the same thing or I guess this one is equivalent to F being fbt that's the definition of fpt so um just write it here a problem is fpt if and only if uh it has a kernelization this is crazy uh I keep introducing stronger and stronger Notions of good and they all turn out to be the same again gives you a sense of robustness of this definition and why this is a natural thing to study so uh this sounds crazy how could I put all of the easy work at the beginning in this polinomial time algorithm and then In the End Produce something that is a reasonable size again this proof is going to be trivial I think everything in this field is either really hard or trivial I guess that makes sense um so let's first so I'm just looking at this inequal this implication we already did the other one uh the easy direction of course is this way I didn't even do it in this case if I have an additive running time it's certainly at most the product assuming both those numbers are at least one okay and again if I have a kernelization as I said I could run the kernelization algorithm in polinomial time and then run any finite algorithm to solve the problem and I would get some f of K running time so this is uh easy uh kernel eyes and then run any algorithm on the Kernel kernel is the produced output uh X Prime K Prime okay let's do the other direction this is the interesting part so suppose I have an algorithm that runs let's say in this running time I claim that uh I can turn it into a kernel and the proof is going to look just like before okay so there are two cases uh one is that F of K let's say is less than equal to n um actually I want to do the other case first a little more natural but it doesn't really matter they're both easy but for different reasons this the then parts are going to look different uh so the first case if n is at most F of K what do I do in that situation in order to Kernel this thing of size N I want to Kernel into something of size F of K nothing I'm done already so this is the already kernelized case that's that's great um so uh the other case is n is Big that's that's the more interesting case of course n is greater than equal to F of K what happens here well just like last time that means that this running time uh F of K is now at most n that means this running times is at most n the C + 1 right so that means uh the the fpt algorithm that I'm given because we're assuming here we're given an fpt algorithm we want to produce a kernel in that case that algorithm runs in uh n the C+ one time which means I can actually run it that's polinomial time okay so over here uh I needed a polinomial Time kernelization algorithm if it happens that F of K is at most n then I can actually run the fpt algorithm and that will be a valid kernelization procedure now the fpt algorithm actually solves the problem let's say it says yes or no uh whether uh the answer to my original question the kernelization procedure has to Output an input to the problem so uh what I need to add one thing here which is just output um a canonical yes or no uh input uh accordingly okay if the fbt algorithm here I'm thinking about decision problems if the fbt algorithm says yes I'm going to uh output one instance one input of the problem where the output is yes I know that one exists uh because this algorithm said yes so in in a constant amount of space I'm able to write a yes input or in a constant amount of space I write a no input so the new kernel will have constant size which is smaller than F of K okay uh that's it so either I output the same input that I was given or I output something of constant size that encodes a yes or a no so it's kind of trivial again um the catch is that the SI the size of the kernel the size of the output in general here is going to be exponential in K because F of K presumably is exponential in k that's annoying this is what you might call an exponential size kernel so an interesting question and an exponential size kernels are equivalent to fpt something that may not be equivalent is a polinomial size kernel it' be nice if I start with something that's polinomial in n and I reduce it to something that's polinomial in K and then I run something you know it's exponential on that but it will only be singly exponential in K hopefully whereas if I use use this kernelization procedure if I apply it to vertex cover uh with with one of these algorithms I'm going to get a new thing whose size is exponential in K if I run this uh one of these Brute Force algorithms I'm going to get something as like doubly exponential in K that's not so hot uh because I already know how to do exponential in K all right uh but that's the this is the general idea of kernelization and why uh it's not surprising that you can do it I have one catch here which is this is is an algorithm it Compares n to F of K in order to do this you have to know what K is minor technicality uh if you don't know what K is you can basically uh run this algorithm with a timer a stopwatch and if its running time exceeds n to the C+ one then you know you're not in this case if it finishes within that time bound great you found the answer if it doesn't finish uh then you know you must be in this case and then you just quit and output your original input say I'm kernelized done easy okay that's a technicality all right so much for general theory let's go back to algorithms uh yeah all of this work I want to write down over here we have a v * 2 the K algorithm on the one side and uh here we have an e b to the K algorithm just want to keep a running we're going to get a faster algorithm than both of those through kernelization so I claim uh that we can find a polinomial kernel polinomial size kernel it's going to be quadratic uh for vertex cover these are hard to find uh and there's a whole research industry for finding polinomial kernels um so I'm going to give you some some uh methods but they're specific to vertex cover so here's the first thing this is hard to draw so here I have a Vertex U and suppose I have an edge connected from U to U this is called a loop what can I do from a Vertex cover perspective what can I conclude about this picture yeah right you must be in the vertex cover uh because this Edge really only has one end point okay so far so easy so um what I can do in this case to say okay U is in the vertex cover and then uh Delete U uh and it's incident edges uh so and then we have to decrement K okay cool seems feels familiar uh but in this case we there's no guessing we just know you must be in the cover all right here's another case suppose I have u and v and there are many edges connecting them this is called a multi-edge uh so maybe you just assume your graph is simple but if you don't assume your graph is simple uh we might have these kinds of situations what can I do in this case what can I guarantee yeah REM you can remove all but one of the edges let's just delete all but one if I cover one of them I cover them all easy peasy see if you can get the other rules so delete all by one in general we're going to have a bunch of these kinds of simplification rules that are guaranteed correct they don't change the output but magically we're going to end up with something in size function of K we haven't done much yet but now we know that the graph is simple meaning it has no loops and it has no multi-edges cool all right next thing I want to think about is uh a vertex of degree greater than k k is the current value of K so suppose I have a high degree vertex more than K uh edges outgoing from it what can I say then yeah must it you must put it in the cover why right uh proof by contradiction if I don't put it in the cover that means all of these guys are in the cover there's more than K of them and the whole goal was to find uh a Vertex cover of size at most K so you better not put all of these in your vertex cover because that's more than K so that therefore this one has to be in there this is a cool argument simple but cool okay uh so any vertex of degree greater than K must be in the vertex cover which I was calling s okay so delete that vertex and it's incident edges decrement okay because we just Ed something okay so just keep doing this every time I see a vertex of degree more than K delete it decrement K now I have a new graph and a new value of K look for any vertices whose degree is more than K if I find one delete it repeat repeat keep repeating until you can't anymore how much how much time is this going to take I don't know most quadratic right I look at all the vertices uh look at their degrees uh you know I could look over all the edges increment the degrees uh in linear time I can find whether there's any vertex of degree more than k then delete it in linear time then try again and this will happen at most linear time many times because I can only delete a Vertex once so I delete at most V vertices so overall running time here is like at most um you know V * e polinomial probably if you're clever use a data structure to M to update degrees uh you could do this in order V time but uh Let's Not Be Clever yet all right uh so now after I've done all of these reductions I have a graph where every vertex has degree at most K so it's like a bounded degree graph why do I care about a bounded degree graph um remember I drew this example which was a star graph where n was large but K was very small n was n n was V and uh K was one now star graph is special because it has a very high degree vertex in general if I have a vertex of some degree say k um and I put it in the vertex cover it covers K edges okay so uh each vertex in S covers at most K edges whatever the degree is so that means you don't get much bang for your buck anymore we've already taken care of all the high degree vertices where you get a lot of reward for putting one vertex in the cover now uh and this is the new value of K it may have decremented from before every vertex that we uh could possibly put in the set will only cover K edges now we know that we only get to put K more vertices into the set right we know uh we're supposing that size of s is at most K uh so that means that uh the number of edges size of e must be at most K squ right because every one I put into S covers at most K edges all of them have to be covered and so uh K * K is k s huh interesting that means my graph is small now like catch there might be a whole bunch vertices that have no edges incident to them so I need to delete isolated vertices say degree zero vertices okay degree zero vertices you really don't want to put those into your vertex cover no point they don't cover any edges so delete those and now I still may not have a direct a connected graph but in the worst case I have a matching uh I know the total number of edges is at most k squ that means the total number of vertices is at twice that 2 K2 so after all of these operations I assumed that s was size at most K uh and then if I do all of these operations um I get a graph with at most two k squ vertices and at most K squ edges so the total size of the graph which I'm calling n uh n which is size of V plus size of E is order k^2 3 k^2 and uh I know I assumed that there was a Vertex cover of size at most K throughout this so what I do is I run this kernelization algorithm and I see is the graph that I produced size at most 3K s if it is output it that's a kernelized thing because it's small if it isn't if the graph I've produced is still too big that must mean that this assumption was wrong which means the answer to the vertex cover problem is no there is no vertex cover of size at most K and so then I just output a canonical no instance like uh so I mean this is sort of outside but if um the newly produced graph I'll call it uh V Prime uh plus e Prime is greater than 3 * k^ 2 then output and here I can actually give you one let's say I'm going to Output the graph which is a single edge with two vertices and k equals zero the answer to vertex cover in this instance is no so this is an example of a constant size no representative so either I get something that's small and I output that or it's big in which case I output this thing just to say nope can't be done that's chronization so I've produced a quadratic size quadratic in K in polom time question wow so this is kernelization at its finest polinomial kernel polinomial time we get it down to something that size polinomial in K this is how you should if you want to solve vertex cover you might as well do these reductions first because they will simplify your thing and now if you happen to know your vertex cover is small then the graph will be small so now we can run either of these algorithms okay presumably we should run the better one but for fun uh let's analyze both of them okay so I want to leave the running times here we're going to get a faster vertex cover algorithm from a fixed parameter tractability perspective uh so here's a new fpt algorithm two of them first we kernelized ve time again I think you can get that down to order V uh without too much effort obvious it's not totally obvious it's a good exercise be a good problem set problem but uh it's not on the problem set don't worry uh could be a good final exam problem I don't know that probably a little long um all right so now we could uh let's say option one let's use the Brute Force algorithm after that the running time of that is e * V to the K but now e is K2 and V is also order K squ let's not worry about uh actually I do have to worry about here because it's in the base of an exponent so I do so we're going to get uh k^ for the E term and then the V term is going to be uh 2 * k^ 2 and then that's going to be raised to the K power okay so simplify a little bit this is like 2 to the K times uh I guess K to the 2K okay it's K to the k 2 uh not bad overall running time is VE plus this that's a function of K it's exponential um but you know we have a better algorithm we have this V * 2 the K running time so we might as well use that one but the point is once you kernelized you can use pretty stupid algorithms and you still get really good running times okay we'll get a slightly better running time using the bounded tree search so if we use bounded treesearch we have v v is 2k^ 2 so here the constant doesn't matter because it's there's no exponent and then we have time 2 to the K so we're going to get a uh k^ 2 * 2 the K algorithm it's kind of funny symmetry here two and K are swi switching roles of course the two to the K is the big term but now it's only singly exponential in K this thing is like 2 to the K log K this thing is only 2 to the K so it's better this is like K factorial and this is just 2 to the K so it's a big Improvement this will be a much more practical algorithm so we run the kernelization then we run the bounded uh tree search algorithm and so the total running time uh is say ve + k^2 to the K the story doesn't end here there are dozens of papers about how to solve vertex cover from fixed parameter tractability perspective the best one so far uh I'm not going to cover but it is based on kernelization just more rules uh and you get K V plus 1 2 74 to the K okay some constant better than two but very similar that's vertex cover if you have a Vertex cover instance and you know that it's going to have a relatively small vertex cover these are the algorithms you should use any questions this ends our vertex cover story uh but the last thing I want to do is connect up these two areas last class we talked about approximation algorithms this class we talked about fixed parameter algorithms they are actually closely related uh and so for example we will get a fixed parameter algorithm to uh subset sum using what we already had last lecture so so far today I've basically been talking about decision problems but let's think a little bit about optimization ation problems so uh take your favorite optimization problem like any of the ones from last lecture and let's assume uh that the optimal solution value that the thing we're trying to optimize minimize or maximize is an integer assume that opt is an integer okay now uh let's look at the decision problem whenever you have an optimization problem you can convert it into a decision problem uh you can convert it into I don't know a few uh for example opt less than or equal to K or opt greater than or equal to K they're all going to turn out to work the same op equal K would also work uh now that's a decision problem but what I want is a parameterized decision problem what should my parameter be K okay that's the obvious parameter in some sense we're parameterizing by opt but we're adding a layer of indirection we're saying well opts we want to decide whether opt is less than or equal to K question mark and let's parameterize by K that's similar flavor to what we had with vertex cover if you're thinking of if we started with minimum vertex cover and converted it uh cool here's the theorem this is not going to be as strong as the other things we've seen no equivalence here so it's a one-way implication uh and I haven't defined this term yet uh but it's similar to one we saw last class uh if the optimization problem that we started with has an efficient pasas an efficient polinomial time approximation scheme then the decision problem uh you get from here is fixed parameter tractable with respect to K okay so what is EP Tas mean it's going to look familiar we're going to take an arbitrary function of 1 Epsilon times a fixed polom in N so last time uh we talked about pasas where we could have uh you could have something like n to the F of 1 over Epsilon I'm going to consider that bad as you might imagine from a fixed parameter tractability perspective better uh would be some function possibly exponential of 1 Epsilon time polinomial n this is going to be good from a fixed parameter perspective although it's about a approximation algorithms not about exact algorithms of course even better is the FP task we saw last time uh which is polinomial in one over Epsilon times polinomial in N that's ideal if you have an FP test it is also an EP test uh you just remove or you just add one more stroke to the first letter and you get an EP test um and last class we actually saw an EP test for subset sum we saw 2 1 Epsilon * n now in fact for that problem there's an FP task even better but you you can see from last lecture why it's nice to have an exponential dependence on one over Epsilon and what this is saying is you can do that as long as that exponential dependence is separated from the N part if it's uh multiplicatively or additively separated as you might imagine it's the same thing uh from n then we call this an efficient P test not fully not quite as good as an FP test but close and as long as you have such a thing you can convert it into an fpt algor Alm for the decision problem uh the way this is typically used so this tells us we get an fbt algorithm for subset sum uh in fact because there's an FP Tas we get a pseudo polinomial time algorithm which is in some sense better but anyway uh the way this theorem is usually used is in the contrapositive what this tells us is that if we can find a problem that is not fpt and there's a whole Theory like NP completeness for showing that problems are almost certainly not fixed parameter tractable then we know that there is not an EP Tas and this is the state-of-the-art for proving that these kinds of algorithms do not exist typically you look at it from a fixed parameter perspective and show that probably doesn't exist then you get that this probably doesn't exist okay let's prove this theorem it's again really easy but a nice connection between these two worlds all right so there are two cases the optimization problem we're thinking about could be a minimization or maximization problem let's say it's maximization just to be concrete it won't make too much difference but it will make a tiny difference in the order of or the inequality directions uh okay so what we're going to do so we're given an EP test and we want to solve fpt we want an fpt algorithm so what do we do uh well algorithm is going to be to run that EP test that's sort of the only thing we can do now the EP test this is an approximation scheme it has an extra input which is Epsilon we need to choose Epsilon because we're not for we're trying to solve it exactly but there's no Epsilon in that problem so we got to make one up let's run the EP t with anyone have good intuition what should Epsilon be yeah remind you of this tricky we want Epsilon to be small yes be one one over K is almost right anything less than that will work uh so I'll use one over 2K but you know one over k+ one would also work uh or anything a little bit tin one over K uh yeah one over K plus 001 something um anything a little bit less than one over K will turn out to work uh so why so so first of all how much does how much time does this take uh well we were given this running time one over this is 2K so uh this is going to take F of 2K time times polinomial in N okay we need to connect e and K because we're given sorry Epsilon and K uh because we're given something whose running time depends on Epsilon not K now we're setting Epsilon in terms of K so now the running time is a function of K not Epsilon uh and then times n so this is good this looks like an fpt running time I claim we've found the answer okay this is maybe the surprising part you had good intuition here uh and the the intuition is just that uh if you're this close to Optimal and optimal is actually an integer and you found an integer then uh you're going to be less than one away which means you're actually the same thing okay but let's do it more formally uh so we're within a 1 plus Epsilon Factor I'm going to call the Epsilon part relative error right that's how much it gets multiplied by opt uh in order to compute the error bound so the relative of error is Epsilon Epsilon is or I guess is it most Epsilon Epsilon is 1/ 2K which all I'm going to need is this is strictly less than 1 over K so this means if I look at Absolute error so in case you're not familiar relative error is I take uh my approximate solution uh I subtract off let's say the optimal solution did I get this right this is a maximization problem so yeah my solution is presumably no it's going to be the other way around for maximization problem it's going to be the optimal could be bigger than me so I take that difference this is called absolute error okay and relative error is when I just divide that by opt that's relative error so uh I have this one part already so usually you state in terms of 1 plus Epsilon if you state it in terms of relative error the one disappears you just get the absolute error which is opt minus apx is I take the relative error and I multiply it by opt okay so relative error is going to be less than one if opt is uh I guess greater than or equal to K I have less than in my notes but uh if opt is greater than or equal to k then absolute error is is less than one right hope let's check uh the relative error is actually um opt divided by K whoops no I got it the wrong way around it's corrected my notes okay relative error is this thing it's going to be strictly less than opt divid K this thing times opt okay so as long as opt is less than or equal to K this thing will be strictly less than one that's good absolute error less than one for an integer means that we actually have the same value have that written down more formly uh so let's go over here so if we find an integral solution uh value values the objective function we're trying to maximize let's say uh we achieve something uh value less than or equal to K uh which it better be if opt is less than equal to k um then opt okay this is basically doing the computation again in another way uh but we had one plus Epsilon Epsilon was chosen to be 1 12 one over K uh and then K was the solution value that we found and so we have this relation between opt and the thing um and therefore and this works out to exactly K plus a half so this is uh again strictly less than k + 1 and so if we found we assumed that opt was less or equal to K and so now it must actually be equal to K because there are no integers between K and K plus a half okay I could probably could have done that shorter so when we have an EP task we exactly get an fpt algorithm and that's the reverse does not hold there are some problems that have fpt algorithms but do not have EP testes but it's something uh and it connects these two fields and that's all we'll say about fixed parameter algorithms any final questions cool see you next week