Computer Science 6789:
Parameterized Complexity Analysis: Foundations and Applications
(Winter 2014)

Course Objectives / Description

Course objectives: To give students a working knowledge of the techniques for determining which restrictions on NP-hard problems do and do not allow practical exponential-time optimal-solution algorithms for those problems. These techniques are largely drawn from the theory of parameterized computational complexity created by Mike Fellows and Rod Downey.

Course description: Many problems encountered in Computer Science are computationally intractable in general and hence do not allow efficient, i.e., polynomial-time, algorithms that obtain optimal solutions for all inputs. The typical response is to invoke efficient heuristics or approximation algorithms. However, there may yet be exponential-time optimal-solution algorithms that are practical for restricted classes of inputs encountered in practice. This course will look at techniques developed within the theory of parameterized computational complexity for determining whether such practical algorithms do or do not exist relative to specified restrictions. The emphasis will be on developing a working expertise in such analyses through an introduction to the basics of parameterized complexity theory and in-depth analyses of selected problems.

A computational complexity course and an algorithm design techniques course (undergraduate and/or graduate)

Evaluation Scheme (Tentative)

• Review: Classical computational complexity analysis (1 1/2 weeks)
  (algorithms, worst-case time asymptotic time complexity, polynomial time, polynomial-time many-one reducibility, NP-completeness)
• Parameterized complexity theory (2 1/2 weeks)
  (parameterized problems, fixed-parameter tractability, parameterized reducibility, parameterized classes)
• Illustrations of parameterized complexity analysis (6 weeks)
  (In-depth of analyses of selected problems (1-2 weeks apiece) drawn from (but not limited to) the following list:
  • Minimum Vertex Cover
  • Maximum Common Subgraph
  • Maximum Clique
  • Longest Common Subsequence
  • Closest Substring
  • Analogy Derivation
  • Robot Motion Planning
  • Subsumption Architecture Design
• Student presentations (2 weeks)

• Bodlaender, H., Downey, R.G., Fellows, M.R., Hallett, M.T., and Wareham, H.T. (1995) "Parameterized Complexity Analysis in Computational Biology." Computer Applications in the Biosciences, 11(1), 49-57.
• Cesati, M. and Wareham, H.T. (1995) "Parameterized Complexity Analysis in Robot Motion Planning." In Proceedings of the 25th IEEE International Conference on Systems, Man, and Cybernetics: Volume 1. IEEE Press; Los Alamitos, CA. 880-885.
• Downey, R. (2012) "A Basic Parameterized Complexity Primer." In H.L. Bodlaender, R.G. Downey, F.V. Fomin, and D. Marx (eds.) THE MULTIVARIATE ALGORITHMIC REVOLUTION AND BEYOND. Lecture Notes in Computer Science no. 7370. Springer. 91-128.
• Garey, M.R. and Johnson, D.S. (1979) COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS. W.H. Freeman.
• Downey, R. and Fellows, M.R. (1999) PARAMETERIZED COMPLEXITY. Springer.
• INTERNATIONAL WORKSHOP / SYMPOSIUM ON PARAMETERIZED AND EXACT COMPUTATION: PROCEEDINGS (2004, 2006, 2008-2012). Lecture Notes in Computer Science nos. 3162, 4169, 5018, 5917, 6478, 7112, and 7535. Springer.
• Niedermeier, R. (2006) INVITATION TO FIXED-PARAMETER ALGORITHMS. Oxford University Press.
• Sloper, C. and Telle, J.A. (2008) "An overview of techniques for designing parameterized algorithms." Computer Journal, 51(2), 122-136.
• van Rooij, I., Evans, P., Muller, M., Gedge, J., and Wareham, T. (2008) "Identifying Sources of Intractability in Cognitive Models: An Illustration using Analogical Structure Mapping." In B.C. Love, K. McRae, and V.M. Sloutsky (eds.) Proceedings of the 30th Annual Meeting of the Cognitive Science Society. Cognitive Science Society; Austin, TX. 915-920.
• van Rooij, I. and Wareham, T. (2008) "Parameterized Complexity in Cognitive Modeling: Foundations, Applications, and Opportunities." Computer Journal, 51(3), 385-404.
• Wareham, T., Kwisthout, J., Haselager, W., and van Rooij, I. (2011) "Ignorance is Bliss: A Complexity Perspective on Adapting Reactive Architectures." In the Proceedings of the First Joint IEEE International Conference on Development and Learning and on Epigenetic Robotics (Volume 2). 1-5. DOI: 10.1109/DEVLRN.2011.6037337.

Created: September 12, 2013
Last Modified: October 11, 2013