6885

Fixed-parameter tractable time The following O(.) expressions represent the worst-case running times of different algorithms, where n is a measure of the input size and p, q and r are parameters (you may assume that p, q, r = n). Which of the following running times are fixed-parameter tractable (fpt) running times? Give the smallest possible parameter set for which the running times are fpt (if one exists) and explain your answer. [4 × 3 = 12 points] (a) O(p q + rn2 ) Answer: This is a fpt running time. The smallest parameter set for which the running times are fpt is ? = {q}. When p and q are really small compared to n, in the worst case the runtime would be O(n 3 ) (when r = n), and hence it’s polynomial time. But for large values of q, the runtime is O(p q ) and this runtime can be represented in the form of f(?).poly(n). And for small values of q, the runtime would still be polynomial. Hence, the parameters responsible for intractability is ? = {q}. (b) O(r pn 3 q!) Answer: This is also fpt running time and the smallest parameter set is ? = {q, p}. In this case also the runtime is polynomial in n. But for large values of p or q, the runtime would be exponential. This can be also be represented in the form of f(?).poly(n), with poly(n) = n 3 and f(?) = r p q!. Hence, the parameters responsible for intractability is ? = {q, p}. (d) O(( p q ) 45 rn) Answer: This is also ftp running time and the smallest parameter set is ? = {r}. In the worst case the value of p q = n when p = n and q = 1. And, even in this worst case scenario, if r is small, the runtime would be O(n 2 ) which is polynomial. But if the value of r is huge, it would result in an exponential runtime and we can represent the runtime in the form of f(?).poly(n), with f(?) = 5r and poly(n) = p q 4 n. Hence, the parameters responsible for intractability is ? = { Document Preview:

Assignment2forCognition&Complexity(MKI40)2017-2018,byI.vanRooijandN.DonselaarAssignment 21 Fixed-parameter tractable timeThe following O(:) expressions represent the worst-case running times of different al-gorithms, where n is a measure of the input size and p, q and r are parameters (youmay assume thatp;q;rn). Which of the following running times are ?xed-parametertractable (fpt) running times? Give the smallest possible parameter set for which therunning times are fpt (if one exists) and explain your answer. [43=12 points]q 2(a) O(p +rn )Answer: This is a fpt running time. The smallest parameter set for which the run-ning times are fpt is=fqg.Whenp andq are really small compared ton, in the worst case the runtime would be3O(n ) (whenr =n), and hence it’s polynomial time. But for large values ofq, theqruntime isO(p ) and this runtime can be represented in the form off():poly(n).And for small values ofq, the runtime would still be polynomial. Hence, the param-eters responsible for intractability is=fqg.p 3(b) O(r n q!)Answer: This is also fpt running time and the smallest parameter set is=fq;pg.In this case also the runtime is polynomial in n. But for large values of p or q,the runtime would be exponential. This can be also be represented in the form3 pof f():poly(n), with poly(n) = n and f() = r q!. Hence, the parametersresponsible for intractability is=fq;pg.p4 r(d) O(( ) 5 n)qAnswer: This is also ftp running time and the smallest parameter set is=frg.pIn the worst case the value of =n whenp=n andq =1. And, even in this worstq2case scenario, ifr is small, the runtime would beO(n ) which is polynomial. But ifthe value ofr is huge, it would result in an exponential runtime and we can represent 4prthe runtime in the form off():poly(n), with f() = 5 andpoly(n) = n.qHence, the parameters responsible for intractability is=frg.p9 q(c) O(r n p)Answer: This is not fpt runtime.Even when the values ofr…

Attachments:

Ankur-Ankan-C….pdf