×

Parameterized computation and complexity: a new approach dealing with NP-hardness. (English) Zbl 1258.68065

Summary: The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable. The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979. · Zbl 0411.68039
[2] Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M. Complexity and Approximation ? Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999. · Zbl 0937.68002
[3] Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press, New York, 1995. · Zbl 0849.68039
[4] Michalewicz Z, Fogel D B. How to Solve It: Modern Heuristics. Springer, Berlin, 2000. · Zbl 0943.90002
[5] Roth-Korostensky C. Algorithms for Building Multiple Sequence Alignments and Evolutionary Trees [Dissertation]. No. 13550, ETH Zürich, 2000.
[6] Stege U. Resolving Conflicts from Problems in Computational Biology [Dissertation]. No. 13364, ETH Zürich, 2000.
[7] Cai L, Juedes D, Kanj I A. Inapproximability of non NP-hard optimization problems. Theoretical Computer Science, 2002, 289: 553-571. · Zbl 1061.68059 · doi:10.1016/S0304-3975(01)00343-7
[8] Cheetham J, Dehne F, Rau-Chaplin A, Stege U, Taillon P J. Solving large FPT problems on coarse-granined parallel machines. J. Computer and System Sciences, 2003, 67: 691-701. · Zbl 1114.68428 · doi:10.1016/S0022-0000(03)00075-8
[9] Lichtenstein O, Pnueli A. Finite state concurrent programs satisfy their linear specification. In Proc. 12th ACM Symposium on the Principles of Programming Languages, 1985, pp. 97-107.
[10] Henglein F, Mairson H G. The complexity of type inference for higher-order typed lambda calculi. Journal of Functional Programming, 1994, 4: 435-477. · Zbl 0827.03005 · doi:10.1017/S0956796800001143
[11] Chen J, Kanj I A. Constrained minimum vertex cover in bipartite graphs: Complexity and parameterized algorithms. Journal of Computer and System Sciences, 2003, 67: 833-847. · Zbl 1091.68076 · doi:10.1016/j.jcss.2003.09.003
[12] Nesetril J, Poljak S. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 1985, 26: 415-419. · Zbl 0571.05050
[13] Coppersmith D, Winograd S. Matrix multiplication via arithmetic progression. J. Symbolic Logic, 1990, 9: 251-280. · Zbl 0702.65046
[14] Papadimitriou C H, Yannakakis M. On the complexity of database queries. Journal of Computer and System Sciences, 1999, 58: 407-427. · Zbl 0939.68024 · doi:10.1006/jcss.1999.1626
[15] Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj I, Xia G. Tight lower bounds for certain parameterized NP-hard problems. In Proc. 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004, pp. 150-160. · Zbl 1161.68476
[16] Anthony M, Biggs N. Computational Learning Theory. Cambridge University Press, Cambridge, UK, 1992. · Zbl 0755.68115
[17] Papadimitriou C H, Yannakakis M. On limited nondeterminism and the complexity of VC dimension. Journal of Computer and System Sciences, 1996, 53: 161-170. · Zbl 0859.68031 · doi:10.1006/jcss.1996.0058
[18] Downey R, Fellows M. Parameterized Complexity. Springer-Verlag, 1999.
[19] Pevzner P A, Sze S-H. Combinatorial approaches to finding subtle signals in DNA sequences. In Proc. 8th International Conf. Intelligent Systems for Molecular Biology (ISMB?00), 2000, pp. 269-278.
[20] Sze S H, Lu S, Chen J. Integrating sample-driven and pattern-driven approaches in Motif finding, Lecture Notes in Computer Science 3240, 2004, pp. 438-449.
[21] Cai L, Chen J, Downey R, Fellows M. On the structure of parameterized problems in NP. Information and Computation, 1995, 123: 38-49. · Zbl 1096.68626 · doi:10.1006/inco.1995.1156
[22] Chen Y, Flum J. Machine characterizations of the classes of the W-hierarchy. Lecture Notes in Computer Science 2803 (CSL?03), 2003, pp. 114-127. · Zbl 1116.68470
[23] Flum J, Grohe M. Describing parameterized complexity classes. Lecture Notes in Computer Science 2285 (STACS?02), 2002, pp. 359-371. · Zbl 1054.68063
[24] Chen J. Simpler computation and deeper theory: On development of efficient parameterized algorithms. International Workshop on Parameterized Complexity, Chennai, India, 2000.
[25] Downey R, Fellows M, Stege U. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics, Graham R, Kratochvil J, Nesetril J, Roberts F (eds.), AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 49: 49-99. · Zbl 0935.68046
[26] Fellows M. Parameterized complexity: The main ideas and some research frontiers. Lecture Notes in Computer Science 2223 (ISAAC?01), 2001, pp. 291-307. · Zbl 1077.68651
[27] Cormen T, Leiserson C, Rivest R, Stein C. Introduction to Algorithms. McGraw-Hill, Boston, 2001. · Zbl 1047.68161
[28] Lovasz L, Plummer M. Matching Theory. North-Holland, Amsterdam, 1986.
[29] Nemhauser G, Trotter L. Vertex packing: Structural properties and algorithms. Math. Programming, 1975, 8: 232-248. · Zbl 0314.90059 · doi:10.1007/BF01580444
[30] Chen J, Kanj I A, Jia W. Vertex cover: Further observations and further improvements. J. Algorithms, 2001, 41: 280-301. · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186
[31] Fellows M. Blow-ups, win/win?s, and crown rules: Some new directions in FPT. Lecture Notes in Computer Science (WG?03), 2003, pp. 1-12. · Zbl 1255.68113
[32] Chor B, Fellows M, Juedes D. An efficient FPT algorithm for saving k colors. Manuscript, 2003.
[33] Alber J, Fellows M, Niedermeier R. Polynomial time data reduction for dominating set. J. ACM, 2004, 11: 363-384. · Zbl 1192.68337 · doi:10.1145/990308.990309
[34] Robson J M. Algorithms for maximum independent sets. J. Algorithms, 1986, 7: 425-440. · Zbl 0637.68080 · doi:10.1016/0196-6774(86)90032-5
[35] Tarjan R E, Trojanowski A E. Finding a maximum independent set. SIAM J. Comput., 1977, 6: 537-546. · Zbl 0357.68035 · doi:10.1137/0206038
[36] Woeginger G. Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science 2570, 2001, pp. 185-207. · Zbl 1024.68529
[37] Niedermeier R, Rossmanith P. A general method to speed up fixed-parameter tractable algorithms. Inform. Process. Lett., 2000, 73: 125-129. · Zbl 1014.68064 · doi:10.1016/S0020-0190(00)00004-1
[38] Balasubramanian R, Fellows M R, Raman V. An improved fixed parameter algorithm for vertex cover. Inform. Process. Lett., 1998, 65: 163-168. · Zbl 1337.05095 · doi:10.1016/S0020-0190(97)00213-5
[39] Chen J, Liu L, Jia W. Improvement on vertex cover for low-degree graphs. Networks, 2000, 35: 253-259. · Zbl 0974.05078 · doi:10.1002/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K
[40] Niedermeier R, Rossmanith P. Upper bounds for vertex cover further improved. Lecture Notes in Computer Science 1563 (STACS?99), 1999, pp. 561-570. · Zbl 0921.05046
[41] Baker B S. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 1994, 41: 153-180. · Zbl 0807.68067 · doi:10.1145/174644.174650
[42] Lipton R, Tarjan R. Application of a graph separator theorem. SIAM Journal on Computing, 1980, 9: 615-627. · Zbl 0456.68077 · doi:10.1137/0209046
[43] Chen J, Huang X, Kanj I, Xia G. Polynomial time approximation schemes and parameterized complexity. In Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Lecture Notes in Computer Science 3153, 2004, pp. 500-512. · Zbl 1096.68166
[44] Bodlaender H L. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 1996, 25: 1305-1317. · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[45] Eppstein D. Diameter and treewidth in minor-closed graph families. Algorithmica, 2000, 27: 275-291. · Zbl 0963.05128 · doi:10.1007/s004530010020
[46] Arnborg S. Efficient algorithms for combinatorial problems on graphs with bounded decomposability ? A survey. BIT, 1985, 25: 2-23. · Zbl 0573.68018 · doi:10.1007/BF01934985
[47] Alber J, Bodlaender H L, Fernau H, Kloks T, Niedermeier R. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 2002, 33: 461-493. · Zbl 1016.68055 · doi:10.1007/s00453-001-0116-5
[48] Fomin F V, Thilikos D M. Dominating sets in planar graphs: Branch-width and exponential speed-up. In Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA?03), 2003, pp. 168-177. · Zbl 1094.68610
[49] Kanj I, Perkovic L. Improved parameterized algorithms for planar dominating set. Lecture Notes in Computer Science 2420 (MFCS?02), 2002, pp. 399-410. · Zbl 1014.68218
[50] Alon N, Yuster R, Zwick U. Color-coding. Journal of the ACM, 1995, 42: 844-856. · Zbl 0885.68116 · doi:10.1145/210332.210337
[51] Chen J, Friesen D, Kanj I, Jia W. Using nondeterminism to design efficient deterministic algorithms. Algorithmica, 2004, 40: 83-97. · Zbl 1088.68835 · doi:10.1007/s00453-004-1096-z
[52] Jia W, Zhang C, Chen J. An efficient parameterized algorithm for m-set packing. Journal of Algorithms, 2004, 50: 106-117. · Zbl 1068.68171 · doi:10.1016/j.jalgor.2003.07.001
[53] Dehne F, Fellows M, Rosamond F. An FPT algorithm for set splitting. Lecture Notes in Computer Science 2880 (WG?03), 2003, pp. 180-191. · Zbl 1255.68080
[54] Niedermeier R. Invitation to Fixed-Parameter Algorithms [Thesis]. Universitat Tubingen, 2002. · Zbl 1095.68038
[55] Robertson N, Seymour P D. Graph Minors ? A Survey. In Surveys in Combinatorics 1985, Anderson I (ed.), Cambridge Univ. Press, Cambridge, 1985, pp. 153-171. · Zbl 0568.05025
[56] Robertson N, Seymour P D. Graph minors VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser. B, 1990, 48: 255-288. · Zbl 0719.05033 · doi:10.1016/0095-8956(90)90121-F
[57] Robertson N, Seymour P D. Graph minors XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 1995, 63: 65-110. · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006
[58] Fellows M, Langston M. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 1988, 35: 727-739. · Zbl 0652.68049 · doi:10.1145/44483.44491
[59] DIMACS Workshop on Faster Exact Solutions for NP-Hard Problems. Princeton, Feb. 23-24, 2000.
[60] Papadimitriou C H, Yannakakis M. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 1991, 43: 425-440. · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[61] Impagliazzo R, Paturi R. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 2001, 63: 512-530. · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[62] Abrahamson K, Downey R, Fellows M. Fixed-parameter tractability and completeness IV: On completeness of W[P] and PSPACE analogs. Ann. Pure Appl. Logic, 1995, 73: 235-276. · Zbl 0828.68077 · doi:10.1016/0168-0072(94)00034-Z
[63] Downey R, Estivill-Castro V, Fellows M, Prieto-Rodriguez E, Rosamond F. Cutting up is hard to do: The parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science, 2003, 78: 205-218. · Zbl 1270.68112
[64] Bodlaender H, Downey R, Fellows M, Hallett M, Wareham H. Parameterized complexity analysis in computational biology. Computer Applications in Biosciences, 1995, 11: 49-57.
[65] Cesati M. Compendium of parameterized problems (2004 version). Department of Computer Science, Systems, and Industrial Engineering, University of Rome ?Tor Vergata?, Italy. http://bravo.ce.uniroma2.it/home/cesati/research/compendium.ps.
[66] Deng X, Li G, Li Z, Ma B, Wang L. Genetic design of drugs without side-effects. SIAM J. Comput., 2003, 32: 1073-1090. · Zbl 1029.68159 · doi:10.1137/S0097539701397825
[67] Gramm J, Guo J, Niedermeier R. On exact and approximation algorithms for distinguishing substring selection. Lecture Notes in Computer Science 2751 (FCT?03), 2003, pp. 195-209. · Zbl 1278.68351
[68] Chen J, Huang X, Kanj I A, Xia G. Linear FPT-reductions and computational lower bounds. In Proc. 36th ACM Symp. Theory of Computing (STOC 2004), 2004, pp. 212-221. · Zbl 1192.68313
[69] Goldschmidt O, Hochbaum D. Polynomial algorithm for the k-cut problem. In Proc. 29th Ann. Symp. Foundations of Computer Science (FOCS?88), 1988, pp. 444-451.
[70] Bodlaender H, Fellows M, Hallett M. Beyond NP-completeness for problems of bounded width: Hardness for the W-hierarchy. In Proc. 26th Ann. ACM Symp. Theory of Computing (STOC?94), 1994, pp. 449-458. · Zbl 1345.68152
[71] Robson J M. Finding a maximum independent set in time O(2n/4)? LaBRI, Universite Bordeaux I, 1251-01, 2001.
[72] Cai L, Juedes D. On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences, 2003, 67: 789-807. · Zbl 1091.68121 · doi:10.1016/S0022-0000(03)00074-6
[73] Cai L, Chen J. On fixed parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences, 1997, 54: 465-474. · Zbl 0882.68064 · doi:10.1006/jcss.1997.1490
[74] Ausiello G, Marchetti-spaccamela A, Protasi M. Toward a unified approach for the classification of NP-complete optimization problems. Theoretical Computer Science, 1980, 12: 83-96. · Zbl 0442.68029 · doi:10.1016/0304-3975(80)90006-7
[75] Paz A, Moran S. Non deterministic polynomial optimization problems and their approximations. Theoretical Computer Science, 1981, 15: 251-277. · Zbl 0459.68015 · doi:10.1016/0304-3975(81)90081-5
[76] Woeginger G. When does a dynamic programming formulation guarantee the existence of an FPTAS? In Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA?99), 2001, pp. 820-829. · Zbl 0929.65034
[77] Kolaitis P, Thakur M. Approximation properties of NP minimization classes. Journal of Computer and System Sciences, 1995, 50: 391-411. · Zbl 0837.68028 · doi:10.1006/jcss.1995.1031
[78] Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proof verification and hardness of approximation problems. Journal of the ACM, 1998, 45: 501-555. · Zbl 1065.68570 · doi:10.1145/278298.278306
[79] Downey R. Parameterized complexity for the skeptic. In Proc. 18th IEEE Conference on Computational Complexity (CCC?03), 2003, pp. 147-169.
[80] Cesati M, Trevisan L. On the efficiency of polynomial time approximation schemes. Information Processing Letters, 1997, 64: 165-171. · Zbl 1337.68125 · doi:10.1016/S0020-0190(97)00164-6
[81] Khanna S, Motwani R. Towards a syntactic characterization of PTAS. In Proc. 28th Ann. ACM Symp. Theory of Computing (STOC?96), 1996, pp. 329-337. · Zbl 0922.68058
[82] Cai L, Fellows M, Juedes D, Rosamond F. Efficient polynomial-time approximation schemes for problems on planar structures: Upper and lower bounds. Manuscript, 2001.
[83] Huang X. Parameterized complexity and polynomial-time approximation schemes [Dissertation]. Department of Computer Science, Texas A&M University, December, 2004.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.