Abstract
Problem parameters are ubiquitous. In every area of computer science, we find all kinds of “special aspects” to the problems encountered. Hence, the study of parameterized complexity for computationally hard problems is proving highly fruitful. The purpose of this article is to stir the reader’s interest in this field by providing a gentle introduction to the rewarding field of fixed-parameter algorithms.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the Vertex Cover problem: theory and experiments. In: Proc. ALENEX 2004, ACM/SIAM (2004)
Alber, J.: Exact Algorithms for NP-hard Problems on Networks: Design, Analysis, and Implementation. PhD thesis, WSI für Informatik, Universität Tübingen, Germany (2003)
Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. In: Proc. International Network Optimization Conference (INOC 2003), Evry/Paris, France, October 2003, pp. 1–6 (2003)
Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica 33(4), 461–493 (2002)
Alber, J., Dorn, F., Niedermeier, R.: Experimental evaluation of a tree decomposition based algorithm for Vertex Cover on planar graphs. Discrete Applied Mathematics (2004) (to appear)
Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: Refined search tree technique for Dominating Set on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 111–122. Springer, Heidelberg (2001) Long version to appear in Journal of Computer and System Sciences
Alber, J., Fellows, M.R., Niedermeier, R.: Efficient data reduction for Dominating Set: A linear problem kernel for the planar case. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 150–159. Springer, Heidelberg (2002) Long version to appear in Journal of the ACM
Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 261–272. Springer, Heidelberg (2001) Long version to appear in Journal of Algorithms
Alber, J., Fernau, H., Niedermeier, R.: Graph separators: A parameterized view. Journal of Computer and System Sciences 67(4), 808–832 (2003)
Alber, J., Gramm, J., Niedermeier, R.: Faster exact solutions for hard problems: a parameterized point of view. Discrete Mathematics 229, 3–27 (2001)
Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM 42(4), 844–856 (1995)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation — Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)
Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: Privara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg (1997)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1–45 (1998)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147(1-2), 31–54 (1995)
Cai, L.: Parameterized complexity of Vertex Colouring. Discrete Applied Mathematics 127(1), 415–429 (2003)
Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Science 54(3), 465–474 (1997)
Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences 67(4), 789–807 (2003)
Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Information Processing Letters 64(4), 165–171 (1997)
Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse-grained parallel machines. Journal of Computer and System Sciences 67(4), 691–706 (2003)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. In: Manuscript, a preliminary version appears in 36th ACM STOC 2004 (2004)
Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further observations and further improvements. Journal of Algorithms 41, 280–301 (2001)
Dantsin, E., Hirsch, E.A., Ivanov, S., Vsemirnov, M.: Algorithms for SAT and upper bounds on their complexity. Technical Report TR01-012, Electronic Colloquium on Computational Complexity (2001)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Bidimensional parameters and local treewidth. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 109–118. Springer, Heidelberg (2004)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs. In: Proc. 15th SODA, pp. 830–839. ACM/SIAM (2004)
Deng, X., Li, G., Li, Z., Ma, B., Wang, L.: Genetic design of drugs without side-effects. SIAM Journal on Computing 32(4), 1073–1090 (2003)
Downey, R.G.: Parameterized complexity for the skeptic. In: Proc. 18th IEEE Annual Conference on Computational Complexity, pp. 147–169 (2003)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Downey, R.G., Fellows, M.R., Prieto-Rodriguez, E., Rosamond, F.A.: Fixedparameter tractability and completeness V: parametric miniatures. Manuscript (2003)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1972)
Ellis, J., Fan, H., Fellows, M.R.: The Dominating Set problem is fixed parameter tractable for graphs of bounded genus. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 180–189. Springer, Heidelberg (2002)
Fedin, S.S., Kulikov, A.S.: Automated proofs of upper bounds on the running time of splitting algorithms. Manuscript (September 2003)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45(4), 634–652 (1998)
Fellows, M.R.: Parameterized complexity: The main ideas and connections to practical computing. In: Fleischer, R., Moret, B.M.E., Schmidt, E.M. (eds.) Experimental Algorithmics. LNCS, vol. 2547, pp. 51–77. Springer, Heidelberg (2002)
Fellows, M.R.: Blow-ups, win/win’s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 1–12. Springer, Heidelberg (2003)
Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 505–520. Springer, Heidelberg (2003)
Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of Closest Substring and related problems. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 262–273. Springer, Heidelberg (2002)
Fernau, H.: Parametric duality: kernel sizes & algorithmics. Technical Report TR04-027, Electronic Colloquium on Computational Complexity (2004)
Flum, J., Grohe, M.: The parameterized complexity of counting problems. In: Proc. 43rd FOCS, pp. 538–550. IEEE Computer Society, Los Alamitos (2002)
Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2n nondeterministic bits. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 555–567. Springer, Heidelberg (2004) (to appear)
Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. In: Proc. 14th SODA, pp. 168–177. ACM/SIAM (2003)
Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 56–67. Springer, Heidelberg (2004)
Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proc. Logic in Computer Science, pp. 215–224. IEEE Computer Society, Los Alamitos (2002)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Garg, N., Vazirani, V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Gramm, J.: Fixed-Parameter Algorithms for the Consensus Analysis of Genomic Sequences. PhD thesis, WSI für Informatik, Universität Tübingen, Germany (2003)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004)
Gramm, J., Guo, J., Niedermeier, R.: On exact and approximation algorithms for Distinguishing Substring Selection. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 261–272. Springer, Heidelberg (2003) Long version to appear in Theory of Computing Systems
Gramm, J., Niedermeier, R.: Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach. Bioinformatics 18(Suppl. 2), S128–S139 (2002)
Gramm, J., Niedermeier, R.: A fixed-parameter algorithm for Minimum Quartet Inconsistency. Journal of Computer and System Sciences 67(4), 723–741 (2003)
Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for Closest String and related problems. Algorithmica 37(1), 25–42 (2003)
Grohe, M.: Parameterized complexity for the database theorist. SIGMOD Record 31(4), 86–96 (2002)
Guo, J., Hüffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. Manuscript (April 2004)
Guo, J., Niedermeier, R.: Exact algorithms for Tree-like Weighted Set Cover. Manuscript (April 2004)
Guo, J., Niedermeier, R.: Fixed-parameter tractability results for Mulitcut in Trees. Manuscript (May 2004)
Hirsch, E.A.: New worst-case upper bounds for SAT. Journal of Automated Reasoning 24(4), 397–420 (2000)
Hochbaum, D. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1997)
Hoffmann, M., Okamoto, Y.: The traveling salesman problem with few inner points. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 268–277. Springer, Heidelberg (2004) (to appear)
Hofri, M.: Analysis of Algorithms: Computational Methods and Mathematical Tools. Oxford University Press, Oxford (1995)
Hromkovič, J.: Algorithmics for Hard Problems. Springer, Heidelberg (2002)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. Technical Report TR03-053, Electronic Colloquium on Computational Complexity (2003), Also appears in Proc. ACM/SIAM SODA 2004
Juedes, D., Chor, B., Fellows, M.R.: Linear kernels in linear time, or how to save k colors in o(n2) steps. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257–269. Springer, Heidelberg (2004) (to appear)
Khuller, S.: The Vertex Cover problem. SIGACT News 33(2), 31–33 (2002)
Küchlin, W., Sinz, C.: Proving consistency assertions for automotive product data management. Journal of Automated Reasoning 24(1-2), 145–163 (2000)
Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science 223(1-2), 1–72 (1999)
Li, M., Ma, B., Wang, L.: On the Closest String and Substring problems. Journal of the ACM 49(2), 157–171 (2002)
Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM Journal on Computing 9(3), 615–627 (1980)
Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms 31(2), 335–354 (1999)
McCartin, C.: Parameterized counting problems. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 556–567. Springer, Heidelberg (2002)
Michalewicz, Z., Fogel, B.F.: How to Solve it: Modern Heuristics. Springer, Heidelberg (2000)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Nemhauser, G.L., Trotter, J.L.E.: Vertex packing: structural properties and algorithms. Mathematical Programming 8, 232–248 (1975)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2005) (forthcoming)
Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parametertractable algorithms. Information Processing Letters 73, 125–129 (2000)
Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for Weighted Vertex Cover. Journal of Algorithms 47(2), 63–77 (2003)
Nikolenko, S.I., Sirotkin, A.V.: Worst-case upper bounds for SAT: automated proof. In: 15th European Summer School in Logic Language and Information, ESSLLI 2003 (2003)
Pearl, J.: Heuristics. Addison–Wesley, Reading (1984)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet Shortest Common Supersequence and Longest Common Subsequence problems. Journal of Computer and System Sciences 67(4), 757–771 (2003)
Sinz, C.: Visualizing the internal structure of SAT instances (preliminary report). In: Proc. 7th Intl. Conf. on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, Canada (May 2004)
Sinz, C., Kaiser, A., Küchlin, W.: Formal methods for the validation of automotive product configuration data. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17(1), 75–97 (2003)
Stearns, R.E., Hunt III, H.B.: Power indices and easier hard problems. Mathematical Systems Theory 23, 209–225 (1990)
Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 548–558. Springer, Heidelberg (2003)
Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 188–202. Springer, Heidelberg (2004)
Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709, pp. 610–621. Springer, Heidelberg (1993)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niedermeier, R. (2004). Ubiquitous Parameterization — Invitation to Fixed-Parameter Algorithms. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds) Mathematical Foundations of Computer Science 2004. MFCS 2004. Lecture Notes in Computer Science, vol 3153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28629-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-28629-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22823-3
Online ISBN: 978-3-540-28629-5
eBook Packages: Springer Book Archive