CS787: Advanced AlgorithmsTopic: Fixed parameter algorithms Presenter(s): Noah Larsen, Hesam T. Dashti, David Guild17.7.1 IntroductionUnderstanding parameterization begins with the idea of decomposing a computational problem intoadditional parameters, and viewing the amounts of resources used by algorithms for such problemsas a function of not just the length of the input, but of other the other parameters as well. This isdone, for the purposes of complexity theory, to try to understand in terms of explicit parametersjust what makes a hard problem hard, and for the purposes of algorithm design, to try to developalgorithms for hard problems that can be considered tractable for large inputs given certain pa-rameters. This is not merely algorithm design for certain subclasses of inputs, as parameters forma cartesian product with the input space, instead of forming a strict subset that can be shown tobe solvable in polynomial time. The desired algorithms here are ones in which the exponentialhardness of the problem can be relegated in totality to a particular parameter as opposed to thelength of the input. The potential usefulness of these algorithms are that, in the same way thattraditional exponential running time algorithms are still tractable for all inputs of small length, forsmall values of the parameters, the algorithms here will be tractable for inputs of the same rangesof lengths as are tractable for traditional polynomial time algorithms - virtually all lengths thatoccur in practice. This phenoma can be further contrasted with algorithms for certain subclassesof inputs in that there the difference between tractability and intractability is sharp, as for certaininputs the problem is solvable in polynomial time and in general it is not known to be, whereashere the difference between tractability and intractability is a matter of degree.Parameterized ProblemA paramaterized problem is a language L ⊆{P∗×P∗}The parameter is usually a nonnegative integer.Fixed-Parameter TractableA problem is fixed-parameter tractable if there exists an algorithm that decides it that runs inf(k)p(|x|) time, where k is the problem’s parameter, f is some function depending only on k, andp is some polynomial function. Notice that while the running time must be polynomial in the sizeof the input, it does not have to polynomial in the parameter. FPT is the complexity class of suchproblems.KernelizationOne of the primary fixed-parameter algorithm design techniques is known as kernelization, andcan be informally thought of as data reduction/preprocessing rules that have provable performance1guarantees. It is defined as follows.Let L be a parameterized problem, that is, L consists of input pairs (I, k), where I is the probleminstance and k is the parameter. A reduction to a problem kernel (or kernelization) means toreplace an instance (I, k) by a reduced instance (I’,k’) called problem kernel such that(1) k’ = k,(2) the size of I’ is smaller than g(k) for some function g only depending on k and(3) (I, k) has a solution if and only if (I’,k’) has one. The reduction from (I, k) to (I’,k’) must becomputable in polynomial time.Theorem. A problem is fixed-parameter tractable if and only if it has a kernelization.The most important aspect of this theorem is why if a problem has a kernelization it is fixed-parameter tractable, and is precisely the reason why kernelizations can be used in the design offixed-parameter tractable algorithms. Such an algorithm can be created by reducing an instanceusing the reduction provided by the kernelization, and then solving the reduced parameterizedinput with some sort of brute force algorithm. As the size of the reduced instance is bounded bythe original parameter, the brute force algorithm will run in time exponential in that parameter.The smaller the size of the reduced instance is with respect to k, the more efficient the algorithm.Example of a Kernelization for Vertex CoverConsider the following parameterized version of Vertex Cover: given a graph, does there exist avertex cover consisting of k or fewer vertices? Below is a simple kernelization for vertex cover.Reduction Rule 1: Remove all isolated vertices.Reduction Rule 2: For vertices with a degree of one, put the neighboring vertex into the cover.Reduction Rule 3: Put any vertex that has a degree of at least k+1 into the cover.Because any vertice in the reduced graph has degree of at most k, and the solution has to have atmost k vertices, the reduced graph can have a solution only if it has at most k2edges. Because ofthis and the fact that every vertice in the reduced graph will have degree at least two, the reducedgraph can have a solution only if it has at most k2vertices. The size of the reduced graph is thusk2.17.7.2 A Parameterized Algorithm for the scheduling problemwith precedence constraints on a single machineThe scheduling problem for a collection of weighted tasks on a single machine with respect to a setof given precedence constraints is an NP-Hard problem [2]. The problem prototype is as follows:A set of tasks: T={t1, t2, . . ., tn}A set of weights W={w1, w2, . . ., wn}A set of processing times P={p1, p2, . . ., pn}2A set of ending times C={c1, c2, . . ., cn}The aim: minimizePni=1ciwiLets consider the given constraints as a directed acyclic graph (G(V, E)) which is represented byan adjacency matrix M.In order to propose a fixed parameter algorithm, we must extract some preliminary informationabout the tasks.17.7.2.1 Preliminaries:Based on the precedence matrix M, we can construct a depth(layer) tree which represents thepriority in considering the nodes; e.g. nodes with no-input are in depth 0, and nodes which justdepend on the nodes in layer 0, are located in depth 1. in layer 2 we have nodes that depend onthe nodes in layer 1 and/or layer 0. Generally, the nodes in layer i depend on the nodes in layeri − 1 and/or i − 2 . . . 0).Let L be the maximum number of nodes in the layers. The value of L can be calculated by apolynomial function via tracing entries of the M matrix where entries are 1 for in-edges and -1 forthe out-edges.Let K denote the maximum number of out-degree in the matrix M. This value is easily computablesince maximum absolute value of sums of ’-1’ in each row equals to K. An example of precedencegraph with its corresponding layers is indicated in Figure 17.7.2.1. In the next section we focus onparameterizing the scheduling problem.3Figure 17.7.2.1: This