Overview of the Field 2008

A quick 2008 summary of the Field of Parameterized Complexity

Monographs:
1. R. G. Downey, M. R. Fellows: Parameterized Complexity Springer-Verlag, 1999.
2. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
3. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
4. M. R. Fellows and F. A. Rosamond. Parameterized Complexity Extremal Theory. Cambridge University Press. In progress.
5. H. Fernau. Parameterized Algorithmics: A Graph-Theoretic Approach. Habilitationsschrift, Wilhelm-Schickard Institut f ur Informatik, Universitat Tubingen, 2005. Book in progress.

Newsletter FPT News: The Newsletter of Parameterized Complexity. Editor: Frances Rosamond (Contact Frances.Rosamond at Newcastle dot edu dot au).

Wiki Here we are at our favorite wiki which is http://www.fpt.wikidot.com

Special Issues:

• The Computer Journal Vol 1 and Vol 3, 2008. Special Eds. Michael Fellows, Rod Downey and Michael Langston.
• ACM SIGACT News, 38(1):31–45, 2007. Invitation to data reduction and problem kernelization. Jiong Guo and Rolf Niedermeier.
• Theoretical Computer Science, 351 (3), p. 295, Feb 2006. R. Downey, M. Langston and R. Niedermeier guest editors.
• Bulletin of the ESA. Vol 86, June 2005. Column on Algorithmics. M. Serna, D. Thilikos: Parameterized Complexity for Graph Layout Problems.
• Journal of Computer and System Sciences. Volume 67, Issue 4. Dec. 2003. Special issue on Parameterized Computation and Complexity. J. Chen and M. Fellows guest editors.
• Interview with Rod Downey by Cristian Calude in EATCS Bulletin, Number 85, February 2005.

International Conference Series: IWPEC
International Workshop on Parameterized and Exact Computation
2000 Chennai, India
2002 Kanpur, India
2004 Bergen
2006 ETH Zurich, Switzerland (joint with ESA)
2008 Victoria, BC Canada (co-located with STOC)
2009 Copenhagen (joint with ESA)
2010 Chennai, India (tentative)

Dagstuhl Workshops

1. 2009 Seminar 09511, 13.12.09 - 17.12.09 Parameterized complexity and approximation algorithms. Erik Demaine (MIT - Cambridge, US), MohammadTaghi HajiAghayi (AT&T Research - Florham Park, US), Daniel Marx (Budapest Univ. of Technology & Economics, HU).
2. 2009 Seminar 09171, 19.04.09 - 24.04.09. Adaptive, Output Sensitive, Online and Parameterized Algorithms. Jérémy Barbay (DCC - Universidad de Chile, CL), Rolf Klein (Universität Bonn, DE), Alejandro Lopez-Ortiz (University of Waterloo, CA), Rolf Niedermeier (Universität Jena, DE)
3. 2007 Seminar 07281, 08.07.07 - 13.07.07. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Erik Demaine (MIT - Cambridge, US), Gregory Z. Gutin (RHUL - London, GB), Daniel Marx (Budapest Univ. of Technology & Economics, HU), Ulrike Stege (University of Victoria, CA).
4. 2005 Seminar 05301, 24.07.05 - 29.07.05. Exact Algorithms and Fixed-Parameter Tractability.
5. R. Downey (Univ. of Wellington, NZ), M. Grohe (HU Berlin, DE), M. Hallett (McGill Univ., CA), G. Woeginger (Univ. of Twente, NL).
6. 2003 Seminar 03311, 27.07.03 - 01.08.03. Fixed Parameter Algorithms. M. Fellows (Univ. of Newcastle, AUS), M. Hallett (McGill Univ. of Montreal, CDN), R. Niedermeier (Univ. Tübingen, D), N. Nishimura (Univ. of Waterloo, CDN).
7. 2001 Seminar 01311, 29.07.01 - 03.08.01. Parameterized Complexity. R. Downey (Wellington), M. Fellows (Victoria), R. Niedermeier (Tübingen), P. Rossmanith (TU München).

Summer Schools and Workshops

• 2008-08-24–2008-09-06 Workshop with speakers Rolf Niedermeier and Peter Rossmanith in Taiwan at National Chung Cheng University, National Tsing Hua University, National Dong Hwa University, and Academia Sinica, Taipei.
• 2008-06-17–2008-06-21 FPT'08: International Summer School on Fixed Parameter Algorithms, Fudan University, Shanghai, China (AAIM'08 satellite event).
• 2008-FOM 6th International Summer School in Formal Languages and Applications. Joerg Flum (Freiburg). Parameterized Complexity (July/August 2008).
• 2008-"Mini-Symposium: Intractability and Cognitive Modelling: Part 2 - Formalization of Analogical Structure Mapping" (Organizers: M. Muller, I. van Rooij and Todd Wareham), Nijmegen Institute for Cognition and Information (NICI), Radboud University Nijmegen, Nijmegen, the Netherlands. June 5, 2008.
• 2008-"Approximating Solution Structure" (with M. Hamilton, M. Muller, and I. van Rooij), Department of Computer Science, Memorial University of Newfoundland, St. John's, NL, Organizers: Todd Wareham and I. van Rooij. February 2008.

Researchers all or partly funded for Parameterized Complexity
Australia U. Newcastle. Michael Fellows (Algorithms, Generalist), Pablo Moscato (Comp Bio) U. Griffith. Vladimir Estivill-Castro (Algorithms, Game Theory)
Brazil Jayme L. Szwarcfiter.
Canada McGill U. Sue Whitesides (Geometry), Michael Hallett (Biology). University of Victoria, BC. Ulrike Stege. St. Johns, Todd Wareham. Waterloo, Naomi Nishimura, Prabhakar Ragde. Carleton, Frank Dehne (parallel algorithms). New Brunswick, Patricia Evans.
China Shanghai, Rudolf Fleischer.
France CIRM Luminy, Christophe Paul. Paris, Christine Bazgan.
Germany Aachen, Rossmanith. Berlin, Grohe. Freiburg, Flum. Jena, Niedermeier. Karlsruhe, Seese. Rostock Saarbruecken Trier, Fernau.
Greece Athens, Dimitrios M. Thilikos.
Hungary Budapest, Daniel Marx.
Hong Kong Leizhen Cai
India Chennai, V. Arvind, Meena Mahajan, Venkatesh Raman
Ireland Cork: Barry O'Sullivan, Igor Razgon
Israel Haifa, Danny Hermelin. Tel Aviv, Ron Shamir.
Italy Marco Cesati.
Lebanon Faisal Abu-Khasam.
Netherlands Utrech: Hans Bodlaender. Arie M. C. A. Koster. Eindhoven, Gerhard Woeginger. Nijmegen: Iris van Rooij.
New Zealand Auckland, Arkady Slinko. Massey, Catherine McCartin. Wellington, Rodney Downey
Norway Bergen, Fedor Fomin, Jan Arne Telle, Pinar Heggernes.
Slovak Republic Petr Hliney.
UK Oxford, Georg Gottlob, Stefan Kreutzer. Durham, Stefan Szeider. Royal Holloway, Gregory Gutin.
United States Central Florida, Ron Dutton. Georgia, Liming Cai. Texas A&M, Jianer Chen. MIT, Erik Demaine Erik D. Demaine, MohammadTaghi Hajiaghayi. U. Tennessee and Oak Ridge National Labs, Michael Langston. U. Ohio, David Juedes. U. Chicago, Marcus Schafer, Iyad Kanj.