Computer Science 6789:
Parameterized Complexity Analysis: Foundations and Applications
(Fall 2026)

http://www.cs.mun.ca/~harold/Courses/CS6789

Instructor	Office	Office Hours	Lectures
Todd Wareham harold@mun.ca	EN-2034 864-4601	TBA	Tue, 1:30-3:30pm EN-2034

Lecture Outline (Tentative)

• Review: Classical computational complexity analysis
  (algorithms, worst-case time asymptotic time complexity, polynomial time, polynomial-time many-one reducibility, NP-completeness)
• Parameterized complexity theory
  (parameterized problems, fixed-parameter tractability, parameterized reducibility, parameterized classes)
• Illustrations of parameterized complexity analysis

The lectures and displays (and all material) delivered or provided in this course by the instructor, including any visual or audio recording thereof, are subject to copyright owned by the instructor.. It is prohibited to record or copy by any means, in any format, openly or surreptitiously, in whole or in part, in the absence of express written permission from the instructor any of the lectures or materials provided or published in any form during or from the course.

Evaluation Scheme

• 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.
• Downey, R. and Fellows, M.R. (1999) Parameterized Complexity. Springer.
• Flum, J. and Grohe, M. (2006) Parameterized Complexity Theory. Springer; Berlin.
• Niedermeier, R. (2006) Invitation to Fixed-parameter Algorithms. Oxford University Press.
• van Rooij, I., Blokpoel, M., Kwisthout, J., and Wareham, T. (2019) Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Cambridge University Press.

• Memorial University of Newfoundland is committed to supporting inclusive education based on the principles of equity, accessibility, and collaboration. Accommodations are provided within the scope of the University Policies for the Accommodations of Students with Disabilities ( www.mun.ca/policy/site/policy.php?id=239). Students who may need an academic accommodation are asked to initiate the request with the Glenn Roy Blundon Centre at the earliest opportunity ( https://www.mun.ca/student/about-us/units-and-contacts/accessibility-services---the-blundon-centre/).
• Students are expected to adhere to those principles which constitute proper academic conduct. A student has the responsibility to know which actions, as described under Academic Offences in the University Regulations, could be construed as dishonest and improper. Students found guilty of an academic offence may be subject to a number of penalties commensurate with the offence including reprimand, reduction of grade, probation, suspension or expulsion from the University. For more information regarding this policy, students should refer to the University Regulations for Academic Misconduct (Section 6.12) in the University Calendar.

Created: July 30, 2026
Last Modified: August 6, 2026