The field is growing by leaps and bounds—Herein you will find applications, open problems, the 'FPT Races' Table, the FPT Newsletter, and resources including courses about parameterized complexity and open positions. Read the "Quick Summary of Parameterized Complexity - 2012".


Special Issue in journal "Algorithms"

There will be a special issue on "Parameterized Algorithms - Challenges from Real-World Applications" in the open-access journal Algorithms published by MDPI. The submission deadline is 31 May 2014, but you may send your manuscript at any time before then. If you plan to contribute a research or review article, please send a short abstract to the Editorial Office (moc.ipdm|smhtirogla#moc.ipdm|smhtirogla).

Submissions should study the parameterized complexity of NP-hard problems arising from application areas including (but not limited to) network analysis (biological, social, and technical), computational geometry, SAT solving, bioinformatics, string problems, operations research and combinatorial optimization, computational
social choice, data clustering, and mining.

Particularly welcome are submissions that introduce practically relevant problem formulations and/or parameterizations, present linear-time fixed-parameter tractability and/or kernelization results, or that take into account aspects of algorithm engineering.

This special issue is edited by Christian Komusiewicz, Stefan Kratsch, and Rolf Niedermeier. The guest editors and the editorial office aim for a rapid publication process. The journal levies an Article Processing Charge for accepted papers,
currently 300 CHF (Swiss Francs) per accepted paper.

More info including a detailed call for submissions can be found at http://www.mdpi.com/si/algorithms/Parameterized_Algorithmics

DATES: Monday, 18th August — Friday, 22nd August 2014 at the Conference Center in Będlewo, Poland.
CONTENTS: Basic introductory courses as well as an overview of very recent developments, including many exercises and open problems. We target interested master students, grad students and young researchers willing to join the research in parameterized algorithms and complexity. However, even more experienced participants will find many of the presentations interesting and fruitful.
FEE around 250 euros (to be determined later) will cover accommodation and full board. We expect to be able to provide support for interested researchers with funding difficulties.
The workshop is supported by European Research Council grants "Rigorous Theory of Preprocessing" (no. 267959) and "Parameterized Approximation" (no. 306992), and by Warsaw Center of Mathematics and Computer Science.

MORE INFO: http://fptschool.mimuw.edu.pl
CONTACT: lp.ude.wumim|loohcstpf#lp.ude.wumim|loohcstpf

Erasmus Mundus grants
The Erasmus Mundus offers grants for scientists at any level to visit their consortium universities. Grant deadline is 15 February 2014. See https://sites.google.com/site/emthelxinoe/call.
Associated universities are: Malaga, Montpellier, Athens, Wroclaw, Kosice, Dresden, University of Newcastle Australia, Wollongong UOW Wollongong, La Trobe, Melbourne, Victoria Univ Wellington. Email: ua.ude.eltsacwen|otacsoM.olbaP#ua.ude.eltsacwen|otacsoM.olbaP

Please post JOB opportunities the JOBS page. For example:
Applications close: Wednesday 05 March 2014. Research Associate, University of Newcastle, Australia. Develop a research program using supercomputer-based approaches together with memetic algorithms, to address key areas in graph optimization. See: http://www.seek.com.au/job/25987255. For more information, email: ua.ude.eltsacwen|otacsoM.olbaP#ua.ude.eltsacwen|otacsoM.olbaP

New course in PC
See http://www.stanford.edu/~rrwill/cs266.html for the description of CS266 — Parameterized Algorithms and Complexity, the Stanford course taught by Ryan Williams last spring.


ETH Zurich ABZ International Medal of Honor to Michael Fellows
Congratulations to Michael Fellows, Australian Professorial Fellow, Charles Darwin University. Mike has been presented with the ETH Zurich ABZ International Medal of Honor for fundamental contributions to Computer Science Education, one of the highest possible honours in Computer Science Education circles worldwide, at an award ceremony at the annual Swiss Computer Science Day in Zurich, Switzerland on January 7. The medal was awarded for the worldwide impact of the innovative book Computer Science Unplugged!, written by Professor Fellows with New Zealand colleagues Tim Bell (Uni of Canterbury, NZ) and Ian Witten (Otago Univ, NZ). The concept is aimed at presenting the mathematical ideas of computer science to primary school students. It has been translated into 18 languages and has spurred a global grass-roots movement (see www.csunplugged.org).

“The plan was to develop materials based around modern research in computer science and mathematics and have these ideas used to make early education more exciting and engaging,” Professor Fellow said. “Woven through “Computer Science Unplugged” is the importance of story: that presenting math and computing topics through story-telling and drama can captivate children and adults alike, and provides a whole new level of engagement with what can be perceived as a dry topic. It is also about not paying attention to boundaries, whether teaching advanced computer science concepts to elementary school children or running a mathematics event in a park."

Frances Rosamond was invited to the stage with Mike, and Juraj Hromkovic presented them with the beautiful oil painting.


Fabrizio Grandoni wins ERC Starting Grant
Congratulations to Fabrizio Grandoni, Algorithms and Complexity Group of IDSIA, University of Lugano (Switzerland) for the ERC Starting Grant New Approaches to Network Design. The grant is supporting a PostDoc position in algorithms. Contact moc.liamg|inodnarG.oizirbaF#moc.liamg|inodnarG.oizirbaF


Danny Hermelin receives EU Award
Congratulations to Danny Hermelin, Ben-Gurion University of the Negev, who has received 100K Euros for a period of 4 years for his proposal: "MetaKer - New Directions in Meta-Kernelization." The grant's name is "Marie Curie Career Integration Grant" and it is given by the EU as part of the Marie Curie Auctions. Well done, Danny.


DFG Award to Gabor Erdelyi
Congratulations to Gabor Erdelyi, Univ Seigen, who has received a 167.000,00 Euros, two-year award for the project that includes parameterized and average-case complexity of decision-making problems. All the best to Olivia, Gabor and little Alex.

The Parameterized Complexity Newsletter, Vol 9, no 3, November 2013 is on the wiki. Congratulations to award winners Gregory Gutin, Stefan Szeider, Tobias Freidrich, Frank Neumann, and IPEC Excellent Student Paper Award Winners: Mateus de Oliveira Oliveira, Bart Jansen, Lukas Mach, and Tomas Toufar. There are two excellent articles, and announcements about the Nerode Award.


DAAD Grant to Katrin Casel
Congratulations to Katrin Casel, who has received a DAAD grant to visit Dr. Ljiljana Brankovic, Univ. Newcastle, Australia. Katrin is a PhD student of Prof. Dr. Henning Fernau.


Australian Research Council Award to Tobias Freidrich and Frank Neumann
Congratulations to Tobias Freidrich, Friedrich Schiller Univ–Jena and Frank Neumann, Univ Adelaide for a 300k Australian Research Council Award for Parameterised Analysis of Bioinspired Computing, 2014–2016.


Royal Society Wolfson Research Merit Award to Gregory Gutin
Congratulations to Prof. Gregory Gutin at Royal Holloway, London for his project to study Parameterised Combinatorial Optimisation Problems. Gregory has been awarded the Royal Society Wolfson Research
Merit Award which provides a salary supplement for 5 years.


Austrian Science Fund Award to Stefan Szeider
Congratulations to Prof. Stefan Szeider at TU-Wein for a project to study Parameterized Knowledge Compilation. The project has been awarded a three-year Eur 340k Austrian Science Fund Award.

The call for nominations for the 2014 EATCS-IPEC Nerode Prize is out. The deadline is January 1, 2014. More information can be found here.


IPEC 2013 Excellent Student Paper Awardees
Congratulations to Mateus de Oliveira Oliveira (KTH, Stockholm) for {\it Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs}, Bart M.P. Jansen (U. Utrecht) for {\it On Sparsification for Computing Treewidth}, and Lukas Mach (DIMAP, U. Warwick) and Tomas Toufar (Charles U., Prague) for {\it Amalgam Width of Matroids}. Mach accepted the award at the meeting.

The IPEC-2013 Report shows a record breaking 29 papers accepted out of 58 submissions. Thank you to the 2013 IPEC Committee Co-Chairs Gregory Gutin (Royal Holloway, U. London) and Stefan Szeider (Vienna U. of Technology).

The 2013 April Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences.

The 2013 EATCS-IPEC Nerode Prize winners for outstanding papers in the area of multivariate algorithmics have been announced by the Nerode Prize 2013 Committee: Georg Gottlob (Oxford), Rolf Niedermeier (TU Berlin, chair), and Peter Widmayer (ETH Zurich).The committee has unanimously awarded Chris Calabro (Google Inc.), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser U.), Ramamohan Paturi (UC San Diego), and Francis Zane (Alcatel Lucent). See eatcs.org for more information. Congratulations.


Vienna DBAI Group is 3-Time Winner
Congratulations to Prof. Dr. Reinhard Pichler and the Data-Base and Artificial Intelligence Group at TU-Wein for being awarded three
FWF Austrian Science Fund awards.

The FAIR project, {\it Fixed-Parameter Tractability in Artificial Intelligence and Reasoning} studies the parameterized complexity of logic based problems such as answer-set programming and description logics. Awarded 350k EUR.

The D-FLAT project, {\it Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving} combines tree decomposition techniques with the declarative language “answer-set programming” (ASP). It extends Group previous work, including a tool that allows to specify a dynamic programming algorithm by means of ASP and serves for rapid prototyping of algorithms that exploit bounded treewidth. Awarded 280k EUR.

The project FAIR: {\it Fragment-Driven Belief Change} studies belief revision, update, and merging, which are subareas of Artificial Intelligence that deal with incorporating new information into existing knowledge bases. A part of the project is devoted to a parameterized complexity analysis of these problems. Awarded 350k EUR.

AMS Special Session on Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, and Its Frontiers and the Field of Incrementalization
took place at the Joint Mathematics Meetings in San Diego. There were two days of excellent presentations. Anil Nerode, Mike Fellows, Annie Liu and Rod Downey gave a final summary. Here are (SLIDES), and (ABSTRACTS).

First International Conf on Creative Mathematical Sciences Communication. 2013 Theme of Computer Maths and Curiosity, Art, Story. August 2—10, 2013, Darwin. Preceded by 'Not-About-Graphs III' on July 31/August 1. Extensive website: www.cdu.edu.au/conference/csmaths

Mike Fellows has long wanted mathematical sciences outreach to be a respected research area. Take Computer Science Unplugged! to the next level. Mike Fellows and Tim Bell will help us create new cs maths activities incorporating Indigenous, Both-Ways, 21C Competencies, computational thinking to be used in ALL subjects, across curriculum.

The conference will include an excursion into the Outback of the Northern Territories. Contact ua.ude.udc|dnomasoR.secnarF#ua.ude.udc|dnomasoR.secnarF.

Please announce the conference on mailing lists and websites where it may be of interest.


Congratulations to Ivan Bliznets and Alexander Golovnev, both of St. Petersburg University of the Russian Academy of Sciences. The 2012 IPEC Program Committee has selected their paper, A New Algorithm for Parameterized MAX-SAT, for the IPEC 2012 Excellent Student Paper Award. Ivan Bliznets accepted the award at the meeting.


Erik Demaine and Mohammad Taghi Hajiaghayi, in the past three months, have been awarded two very competitive grants. The first from DARPA with 1 million each and the second NSF midsize (400K Erik and 200K Mohammad) on fixed parameter algorithms for graph problems and its connection to other fields. So in total, just in the past three months, they have been awarded 2.6 million USD. We can say now in the past three months the whole community has gotten about 8 million Euro in the field, which is very impressive.

The August 2012 Parameterized Complexity Newsletter is on the wiki. Over 5 million Euros in new research funding has been awarded to research groups in the PC community. See some of the winners in the picture. Please join the mailing list if you would like an email notification: mailing list enrolment Instructions. Everybody who subscribes receives an email where (s)he needs to confirm the subscription, without needing approval. If you have changed email address, please un-subscribe and then resubscribe with your new address.



The 2012 WorKer (Kernelization) held at Dagstuhl (filled to overflowing) was brilliant, inspiring, warm, loving——fabulous! Many thanks to organizers and everyone who came and to those who wanted to come but couldn't. Thursday talks celebrated Mike Fellows' birthday, describing the early history of the field and many future directions. Fran Rosamond described Mike's outreach of Computer Science Unplugged! and Mathematical Passion Plays. Rod Downey presented a mysterious pile under a white cloth. The Festschrift, “The Multivariate Algorithmic Revolution and Beyond” (Springer LNCS 7370) was revealed when Mike pulled aside the cloth. Authors are in the photo. Mike is 'walking on air' very happy!!

The May 2012 Parameterized Complexity Newsletter is on the wiki. There are excellent articles and announcements. Please join the mailing list if you would like an email notification: mailing list enrolment Instructions. Everybody who subscribes receives an email where (s)he needs to confirm the subscription, without needing approval. If you have changed email address, please un-subscribe and then resubscribe with your new address.

The 7th International Symposium on Parameterized and Exact Computation

IPEC2012 will be co-located with ALGO in Ljubljana, Slovenia. Accepted papers will be published in the Springer LNCS series.

Paper submission: June 19, 2012

Symposium: September 12-14, 2012

Invited Speakers:
Dániel Marx (Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI)),
Andreas Björklund (Lund University).

Workshop on Subexponential Parameterised Algorithms
Saket Saurabh (Institute for Mathematical Sciences: IMSc, Chennai).

Excellent Student Paper Awards may be awarded by the Program Committee to one or more papers accepted to the symposium. A paper is eligible for the award if all authors are students at the time of submission, where a student is someone who has not been awarded a PhD.

NEWS: The "AND-Conjecture solved!! Andrew Drucker, MIT, has new results. A preliminary version of his paper, "New Limits to Classical and Quantum Instance Compression", is available at http://people.csail.mit.edu/andyd/papers.html. See also AND-Conjecture at http://intractability.princeton.edu/blog/2012/03/theory-lunch-february-17. Bodlaender et al. (ICALP 2008) showed that the intractability of "OR-compression" would have important consequences in the study of FPT problems. They showed something similar for the corresponding "AND-compression," but it still remained mysterious. Andy has promised an article for our next newsletter. See the related article, “The AND-Conjecture may be Necessary” by Magnus Wahlstrom, MPI (Nov 2011 FPT Newsletter).


Congratulations to Yiannis Koutis, who has been awarded an NSF CAREER AWARD for his proposal about spectral graph theory and linear time algorithms. Together with another internal grant, he will be managing about 600K over the next 5 years. Yiannis is in the Computer Science Dept. at the Univ. Puerto Rico, Rio Piedras.


Congratulations to Rod Downey, who has been awarded the 2011 Hector Medal by the New Zealand Royal Society for outstanding work in mathematical and information sciences by a New Zealand researcher. Rod was awarded the medal for his influential and innovative work in mathematical logic. Ernest Rutherford was a recipient in 1916.


Congratulations to Serge Gaspers, who has been awarded the Australian DECRA for 375,000AUD for his project, “Solving intractable problems: from practice to theory and back”. Serge has accepted a PostDoc at UNSW with Toby Walsh.

Congratulations to Mohammad Taghi Hajiaghayi, who during 2011 has been awarded the prestigious Office of Naval Research (ONR) Young Investigator Award, an NSF CAREER Award, and a Google Faculty Research Award with total more than 1M dollars.


Congratulations to Yoichi Iwata for the 2011 IPEC Excellent Student Paper Award for “A Faster Algorithm for Dominating Set Analyzed by the Potential Method”.

The November 2011 Parameterized Complexity Newsletter is here. Congratulations to Serge Gaspers and Mohammad Taghi Hajiaghayi for multiple awards, to Yoichi Iwata for the IPEC Excellent Student Paper award, and to others on new positions. This newsletter includes useful citation statistics by Mike Fellows. Neeldhara Misra has agreed to be Column Editor of a regular column about blogs. Magnus Wahlstr\"{o}m, Stefan Kratsch and Danny Hermelin have each contributed outstanding articles on latest results. There is an excellent report on WorKer, including Open Problems. The Table of Races is quite large, and so I have placed it at the end of the newsletter. Please help keep it updated at our community wiki {\bf www.fpt.wikidot.com}. We also report new available positions, conferences, and call for papers. This is a huge, power-packed newsletter.

Slides of talks about kernelization: Links to WorKer 2011 talks and the IPEC 2011 tutorial are now available from the techniques and methodology page.

Announced by Dániel Marx: Postdoc positions available in Budapest, Hungary in parameterized complexity & algorithms. Read more.

Announced by Klaus Jansen: Klaus' DFG proposal "Approximation algorithms for scheduling on unrelated processors" has been accepted, and he has an opening for a postdoc for three years. Contact <ed.leik-inu.kitamrofni|jk#ed.leik-inu.kitamrofni|jk>

Announced by Stephan Kreutzer: The Logic and Semantics Group at the Inst for Software Engineering and TCS at the Technical Univ, Berlin, is offering a fully funded Ph.D. studentship in the area of logic or graph theory. Closing date for applications is 28 Aug 2011. See http://logic.las.tu-berlin.de.

Algorithms key to faster computing, see article in The Australian August 9, 2011 about Mike Fellows. SMARTER algorithms, rather than computer hardware, will deliver greater improvements in computer speed, a leading researcher says. Article here:



awarded a prestigious European Research Council Starting Grant. Dániel's 1.15M EUR, 5-year project will start January 2012 in Budapest, Hungary. The project is “PARAMTIGHT: Parameterized complexity and the search for tight complexity results”.

The July 2011 Parameterized Complexity Newsletter is here. The July 2011 newsletter congratulates Dániel Marx on a 1.15M EUR award, Cristina Bazgan on an IUF, and Iyad Kanj on a Spirit of Inquiry Award. Breakthrough results of Stefan Kratsch and Magnus Wahlström are described by Mike Fellows. “Solving MSO-Definable Problems” are described by Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. “Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds” are described by Anders Yeo. There are announcements of conferences, openings, and congratulations to new PhD and new positions. See all the newsletters by clicking here.

IPEC 2011 in Saarbrucken in September
Full description is here.
IPEC 2011 will be part of ALGO 2011, which also hosts ESA, WABI, WAOA, ATMOS, and ALGOSENSORS. ALGO 2011 will take place September 5-9, 2011 in Saarbr¨ucken, Germany.

NEW NEW New postdocs and other positions advertised. See the JOBS section.

Workshop on Parameterized Complexity—“NOT-ABOUT-GRAPHS!” and Problem-Solving Workshop Frequent updates on this wiki.
Website is here http://www.cdu.edu.au/parameterized-nag.

Location: Charles Darwin University, Northern Territory, Australia this August. DATES: 5, 6, 7, 8 August 2011, plus 9-13 August for Problem-Solving “walkabout”.
Starts 6pm on Friday everning August 5, and ends at noon on Monday August 8. On Tuesday morning 9 August, we will continue with a “Barbados style” Problem-Solving Workshop, traveling into the bush and working on flip-charts, and returning to Darwin on Saturday 13 August. See the Workshop section of this wiki for frequent updates on Participants List and Description and Program. For more information or letter of invitation email ua.ude.UDC|dnomasoR.secnarF#ua.ude.UDC|dnomasoR.secnarF.



Two outstanding papers. Very fine work.

  • Jesper Nederlof and Johan M. M. van Rooij,

‘Inclusion/Exclusion Branching for Partial Dominating Set Set Splitting’.

  • M. Praveen,

‘Small Vertex Cover Makes Petri Net Coverability and Boundedness Easier’.

The April 2011 newsletter appreciates the winners of the IPEC student excellent papers awards.

The November 2010 newsletter describes many achievements and awards. Fedor Fomin: ERC Advanced Grant. Daniel Lokshtanov: Bergen Research Foundation award and also Simons Foundation Postdoc at UCSD. Pinar Heggernes: Norwegian Research Council award. Igor Razgon: President of Ireland Young Researcher Award. Daniel Marx: Humboldt Fellowship for Experienced Researchers. Matthias Mnich: Philips Prize of the Royal Mathematical Society, Netherlands and post doc at Berkeley. Research grants to: Vlad Estivil-Castro, Mike Fellows, Frances Rosamond. Petr Hliney. Klaus Jansen. Saket Saraubh. Todd Wareham.

Congratulations, Mike Fellows!


Mike Fellows has been awarded an Australian Professorial Fellowship, beginning 2010 for five years for Multivariate Algorithmics: Meeting the Challenge of Real World Computational Complexity. The award is for an "outstanding researcher with proven international reputation to undertake research that is of major importance in its field and of significant benefit to Australia." We are proud of you, Mike.

Congratulations, Chunmei Liu!


Chunmei Liu has won the 2009 NSF CAREER award for her project titled, "CAREER: A Complete System for Protein Identification with Computational Approaches". The project uses parameterized complexity and tree decomposition. Chunmei received her Ph.D. in Computer Science at University of Georgia in 2006. Her advisor was Liming Cai, RNA-Informatics Group. She is currently an assistant professor at Howard University, Washington DC. The NSF CAREER award is the most prestigious award to faculty in their early careers.

Number of electrons as the parameter! Wow!

The reduced density matrix method and some complexity issuesby Bastiaan Braams, Emory University at the Fields Institute Thematic Program on Mathematics in Quantum Information.


“I will review the classical formalism of electronic structure theory that is based on the two-body reduced density matrix and associated representability conditions. The N-representability problem is unsolved and results from computational complexity theory indicate that it won't be solved in any concise form. I hope on the one hand to make clear that it doesn't matter, and on the other hand to outline the challenge of obtaining what could be called anyway a solution to the N-representability problem. Finally I will discuss the computational complexity of the Hartree-Fock problem. As an algebraic problem with general 2-body terms in the hamiltonian (not limited to Coulomb interaction) it is NP-hard, while in the setting of parameterized complexity theory, with the number of electrons as the parameter, it is W[1]-hard.”

Administrative parameters! Very interesting paper!

Symbolic Reachability Analysis for Parameterized Administrative Role Based Access Control
B Scott, D. Stoller, Ping Yang, Mikhail Gofman,C. R. Ramakrishnan. Presented at SACMAT’09.
From the abstract: Role based access control (RBAC) is a widely used access control paradigm. In large organizations, the RBAC policy is managed by multiple administrators. It is often difficult to fully understand the effect of an ARBAC policy by simple inspection, because sequences of changes by different administrators may interact in unexpected ways. Allowing administrative roles and administrative permissions to have parameters significantly enhances the scalability and practical applicability of the administrative model.

Structural Study on Proteins in Maize Silk: Parameterized Complexity Approach!

Published by the American Society of Agricultural and Biological Engineers, St. Joseph, Michigan www.asabe.org Citation: Computers in Agriculture and Natural Resources, 4th World Congress Conference, Proceedings of the 24-26 July 2006 (Orlando, Florida USA) Publication Date 24 July 2006 701P0606.
Authors: X. Huang
Keywords: proteins, protein tertiary structure, computational approach


gives a brief summary of a parameterized computational approach for the study of tertiary structures of extension protein variants in maize silk. The structure predictions will be used in future studies to design mutants with desired structural properties to transform into maize and test cell wall properties with these altered proteins.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License