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. Witness the growth of the field in the 2015 Summary of PC/MVA.

PACE REPORT-Congratulations to all participants, committees, encouragers and the entire community.

TRACK A: Treewidth had submissions from ten universities: Brown, Frankfurt, IIT Madras, UC Irvine, Karlsruhe, Lübeck, Meiji, Sydney, TU Wien, and Utrecht.

Computing treewidth optimally with a sequential algorithm:
1st prize, 350e Hisao Tamaki (Meiji University)
2nd prize, 125e Hans Bodlaender, Tom van der Zanden (Utrecht University)
3rd prize, 75e Max Bannach, Sebastian Berndt, Thorsten Ehlers (Luebeck University)

Computing treewidth heuristically with a sequential algorithm:
1st prize, 350e Ben Strasser (Karlsruhe Institute of Technology)
2nd prize, 125e Eli Fox-Epstein (Brown University)
3rd prize, 75e Michael Abseher, Nysret Musliu, Stefan Woltran (TU Wien)

Computing treewidth heuristically with a parallel algorithm:
1st prize, 350e Kalev Kask, William Lam (University of California at Irvine)
2nd prize, 125e Ben Strasser (Karlsruhe Institute of Technology)
3rd prize, 75e Max Bannach, Sebastian Berndt, Thorsten Ehlers (Luebeck University)

TRACK B: Feedback Vertex Set had submissions from six universities: Bonn, Chennai, Kiel, Moscow (two teams), National Institute for Informatics NII Japan, Saarbrücken, and Tokyo.

Computing optimal feedback vertex sets:
1st prize, 500e Yoichi Iwata (National Institute of Informatics (NII)) and Kensuke Imanishi (University of Tokyo)
2nd prize, 300e Marcin Pilipczuk (University of Warsaw)
3rd prize, 200e Ruben Becker, Karl Bringmann, Dennis Gross, Erik Jan van Leeuwen, Natalie Wirth (MPI Saarbrücken)

See the full Report in the IPEC proceedings and at the website (https://pacechallenge.wordpress.com.)

Congratulations to Magnus Wahlström who has just got past probation at RHUL — a nice milestone! He also has received an EPSRC First Grant scheme grant, which It pays for one postdoc for one year, plus conference travels. Topic: "Polytope methods in parameterized complexity".


The ad runs for a relatively short time (deadline October 4th). Candidates for whom this is causing problems should contact Magnus directly.

Congratulations for best paper awards Last week there were 2 simultaneous general algorithms conferences whose best paper award went to a paper from the FPT community. Stefan Kratsch won the best paper award at ESA 2016 for his paper ''A randomized polynomial kernelization for Vertex Cover with a smaller parameter''. Bart Jansen and Astrid Pieterse won the best paper award at MFCS 2016 for their paper ''Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials''. Congratulations to all!

Congratulations to R. B. Sandeep on his excellent research, and many thanks to him for adding another "Table of Races" on the Complexity Status of Edge Modification Problems (See the page in the Menu on the right column of this Welcome page).

Be sure to "Friends" our new FPT facebook page started by Fran Rosamond. It is called: Mike Fellows - FPT Multivariate Algorithmics

Congratulations to ICALP Dissertation winners. Here they are being introduced by Luca Aceto. Georg Zetzsche:


"Monoids as storage mechanisms", Radu Curticapean: "The Simple, Little and Slow Things Count: On Parameterized Counting Complexity", and Heng Guo: "Complexity Classification of Exact and Approximate Counting Problems."

Update to PACE the 1st Parameterized Algorithms and Computational Experiments Challenge – Look for the PACE Session at IPEC 2016!


Thanks to the generous support of the NWO Gravitation project NETWORKS (http://thenetworkcenter.nl/), we canannounce the following Travel Awards and prizes for the first PACE challenge.

Three Travel Awards of 500 € each are available to help young researchers attend IPEC 2016. Apply by e-mailing a CV and a motivation letter by 20 July to on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF (Univ Bergen) Chair of the Steering Committee. To be eligible one must
– submit a working implementation in one of the PACE challenges,
– be a full-time student (undergraduate or graduate level, excluding PhD students),
— commit to attending IPEC 2016 in case one receives the travel award.

Competition prizes. Track A offers four ranked challenges: Exact sequential, Exact parallel, Heuristic sequential, and Heuristic parallel computation of Treewidth. For each ranked challenge, there will be a first, second, and third prize. Track B offers one ranked challenge and there will be altogether three prizes for Feedback Vertex Set.
See details on the PACE website https://pacechallenge.wordpress.com.

Update to Creative Mathematical Sciences Communication (CMSC) – Luebeck, Germany 4—7 October 2016 (http://www.tcs.uni-luebeck.de/cmsc)
Join Tim Bell and Mike Fellows (authors of Computer Science Unplugged!), Joek van Montfort (Scratchweb Foundation and CoderDojo), and other fun, creative folks interested in exploring new ways of popularizing computational thinking, algorithmic thinking, and the foundations and frontiers of computing. We encourage you to present your own efforts and demonstrate / discuss new ideas with outdoor activities, storytelling, art, dance, coding, lecture or other activities. This is Computer Science Unplugged! (www.csunplugged.org) and beyond! Ideas for round-table discussions welcome.
Send an Abstract of what you would like to do to Rudiger Reischuk (ed.kcebeul-inu.sct|kuhcsier#ed.kcebeul-inu.sct|kuhcsier) or Sebastian Berndt (ed.kcebeul-inu.sct|tdnreb#ed.kcebeul-inu.sct|tdnreb). Send a rough outline of your activity as soon as possible, please. This will help us prepare a program. Provide a title, a few descriptive sentences and let us know how much time you need. We accept later submissions due to the concept of this conference.

Michael Fellows made Order of Australia, Companion to the Queen. For eminent service to higher education, particularly in the field of theoretical computer science, as a leading academic, researcher and author, as a mentor, and through public outreach programs particularly for children. Mike and Fran are deeply honoured and humbled by this honour, and extend our congratulations and appreciation to the entire parameterized complexity and Computer Science Unplugged communities.

Congratulations! Jason Crampton, Gregory Gutin and Remi Watrigant won the best paper award at SACMAT 2016. For Jason Crampton and Gregory Gutin it's the second in a row: they won one at SACMAT 2015 as well. Both SACMAT 2015 and 2016 papers deal with FPT algorithms for access control problems. SACMAT is an IPEC analog for the infomation access control community.

Publication of FPT papers. Data collected by Bart Jansen.


See article in the Parameterized Complexity Newsletter, May 2016.


4 - 7 October 2016, Luebeck, Germany


Explore new ways of popularizing computational thinking underlying computer science with outdoor activities, storytelling, art, dance, and various coding activities. This is Computer Science Unplugged! (www.csunplugged.org) and Beyond!

Join others interested in computational thinking, algorithmic thinking, and the frontiers and foundations of computing. We encourage you to present your own efforts and discuss new ideas. Demonstrations welcome, as also ideas for leading round-table discussions.

Important dates:
Abstracts: As soon as possible, please send a rough outline of your activity. This will help us to prepare a program. Provide a title, a few descriptive sentences and let us know how much time you need. We have said 10 June, but we accept later submissions due to the concept of this conference. Final submissions will be handled later on separately. The final submission should contain 5 to 12 pages.
Submissions due: 8 July 2016
Early Registration: 15 August 2016
Conference: 4-7 October 2016

Rudiger Reischuk ed.kcebeul-inu.sct|kuhcsier#ed.kcebeul-inu.sct|kuhcsier
Sebastian Berndt ed.kcebeul-inu.sct|tdnreb#ed.kcebeul-inu.sct|tdnreb
Frances Rosamond on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf

Tribute to DAVID JOHNSON, creator of DIMACS Challenge and a leader in Theoretical Computer Science and algorithms.

The 1st Parameterized Algorithms and Computational Experiments Challenge (PACE) is respectfully dedicated to the memory of Professor David Johnson, a Computer Science leader and visionary.

Details are on the website https://pacechallenge.wordpress.com

Register your team NOW.

Benchmark instances available NOW.

Track A: Tree Decomposition: optimal solutions, heuristics, generating hard instances,
and collecting real-world instances. The tree decomposition validator is now available: https://github.com/holgerdell/td-validate/
GitHub holgerdell/td-validate td-validate - A validity checker for tree decompositions
Track B: Feedback Vertex Set: fixed-parameter algorithms.

• 1 June 2016: Register participation. Track A for TreeWidth send email to Holger Dell at moc.lledregloh|61ecap# moc.lledregloh|61ecap and for Track B Feedback Vertex Set send email to ed.anej-inu|zciweisumoK.naitsirhC#ed.anej-inu|zciweisumoK.naitsirhC
• 1 August 2016: DEADLINE TO SUBMIT Implementations.
• 22–26 August 2016: Results announced at the International Symposium on Parameterized and Exact Computation (IPEC 2016).

GOALS: PACE investigates the applicability of algorithmic ideas studied and developed in the subfields of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. It aims to:
• Bridge between algorithms design and analysis theory and algorithm engineering practice
• Inspire new theoretical developments
• Produce universally accessible libraries of implementations and repositories of benchmark instances
• Encourage the dissemination of these findings in scientific papers
The focus for the inaugural PACE 2016 is to identify specific challenge problems and explore possible organisational models to implement the main goals. It is expected that lessons learned from PACE 2016 will be incorporated into future studies. Researchers are encouraged to join or contact the Steering Committee to influence these developments.

2016 PACE Programme Committee
• TRACK A: Holger Dell (Saarland University, Simons Institute for the Theory of Computing ) and Thore Husfeldt (Lund Univ, IT Univ of Copenhagen)
• TRACK B: Falk Hüffner (TU-Berlin) and Christian Komusiewicz (Friedrich-Schiller-Universität Jena)

PACE Steering Committee
• Holger Dell (Saarland University, Simons Inst for the Theory of Computing )
• Thore Husfeldt (Lund Univ, IT Univ of Copenhagen)
• Bart M. P. Jansen (Eindhoven Univ of Technology)
• Petteri Kaski (Aalto University)
• Christian Komusiewicz (Friedrich-Schiller-Universität Jena)
• Amer Abdo Mouawad (Univ Bergen)
• Frances Rosamond (Chair)(Univ Bergen) EMAIL: on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF

PRIZES: We expect to award prizes but these are not yet finalized.
Please alert your programming students.


The Creative Mathematical Sciences Communication conference (CMSC) explores new ways of popularizing the rich mathematics underlying computer science including outdoor activities, art, dance, drama and all forms of storytelling. How do you explain your research to your colleagues down the hall, in different disciplines, government, your kids, mom.

Date: 4-7 October 2016
Location: Lübeck, Germany
Abstracts due: 10 June 2016
Submissions due: 8 July 2016
Early Registration: 15 August 2016
Website http://www.tcs.uni-luebeck.de/cmsc/

This is the third event in a conference series that explores new ways of helping students to achieve 21st Century competencies in mathematics and computer science. The previous conferences, held in Darwin, Australia, in 2013 and in Chennai, India, in 2014 (Videos from 2014) saw a unique interaction between computer science / mathematics researchers and educators and artists (theatre, dance, graphic arts).
The CMSC has several aspects.
Involve and support researchers to share the frontiers of computer science and mathematics with children and the general public.
Research communication is a “two-way street”. Explaining your research can inspire new research questions. For example, Mike Fellows describes how “Kid Crypto” inspired the new research of Polly Cracker crypto systems.
Future directions of Computer Science Unplugged! Discuss with Tim Bell, Mike Fellows and others future directions of this grass-roots movement, which is now translated into 19 languages.
Storyfull, whole-body, kinesthetic math activities. Demonstrate and design new whole body activities that connect math with the inner self and community. Design activities that include cultural understanding and relevance. Demonstrate activities that foster curiosity, enthusiasm and perseverance.
• Expand computational thinking across the curriculum, and explore how mathematical thinking strategies nurture 21st Century competencies.
• Policy makers in government, business and industry. What are the issues and unanswered questions of executives and policy makers?

The Parameterized Complexity Newsletter for Dec 2015 is on the newsletter page here. The Newsletter reports on an excellent workshop organized by Thore Husfeldt and D´aniel Marx at the Simons Institute as part of the semester on Fine-Grained Complexity, where one of the topics was FPT inside of P, discussed by George Mertzios in this newsletter. In a different direction, a conversation has started about holding an FPT Implementation Challenge. The importance of implementation and appreciation for this work is discussed in the article by Gregory Gutin. Read the New Ideas Section by Mike Fellows about Realistic Modeling. Enjoy the Newsletter and Happy Holidays. Mike and I have new email addresses starting January: on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF and on.biu.ii|swolleF.leahciM#on.biu.ii|swolleF.leahciM


Join the discussion taking place right now about an FPT Challenge. What problem, data-sets should we use? When will it take place? Join the discussion on SLACK. Send an email now to Holger Dell (ed.dnalraas-inu.icmm|lledh#ed.dnalraas-inu.icmm|lledh) or Fran Rosamond ( on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF)

Nominations: due February 15, 2016 for outstanding papers in the area of multivariate algorithmics meant in a broad sense, and encompasses, but is not restricted to, those areas covered by IPEC.

Eligibility: Any research paper or series of research papers by a single author or by a team of authors published in a recognized refereed journal. The year of publication should be at least two years and at most ten years before the year of the award nomination. The Award Committee is solely responsible for the selection of the winner of the award which may be shared by more than one paper or series of papers.

Nominations: Nominations may be made by any member of the scientific community including the members of the Award Committee. A nomination should contain a brief summary of the technical content of each nominated paper and a brief explanation of its significance. Nominations are done by an email to the Award Committee Chair with copies to the members of the committee. The Subject line of the nomination E-mail should contain the
group of words "Nerode Prize Nomination"

The award is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). IPEC 2016 takes place within ALGO 2016, August 22-26, 2016, Aarhus, Denmark.

Award Committee
David Eppstein (University of California, Irvine)
Daniel Marx (Hungarian Academy of Sciences)
Jan Arne Telle (University of Bergen, Norway. Chair)

For further information, including former winners, see: [http://www.eatcs.org/index.php/nerode-prize]


CONGRATULATIONS TO MAREK CYGAN for a 2015 ERC Starting Grant for the project: Technology transfer between modern algorithmic paradigms
, funded by approximately 1.48M Euro over 5 years. The project focuses on (a) parameterized complexity, (b) approximation algorithms, and (c) metaheuristics.


CONGRATULATIONS TO MEIRAV ZEHAVI for several awards,including the 2016 Women Postdoctoral Fellowship of Israel's Council for Higher Education (awarded to excellent female students). Mirav was also awarded the Best Student Paper Award at IWOCA'15, Best Student Paper Award at ESA'15, and Best Student Paper Award at MFCS'15. She has a Simons-Berkeley and I-CORE Joint Research Fellowship 08/2015 - 05/2016.

CONGRATULATIONS TO CHRISTINA BOUCHER, CHRISTINE LO and DANIEL LOKSHTANOV for winning the ESA 2015 Best Paper Award with Consensus Patterns (Probably) has no EPTAS.

CONGRATULATIONS TO MANUEL SORGE and STEFAN KRATSCH for the IPEC'15 Excellent Student Paper Award with On Kernelization and Approximation for the Vector Connectivity Problem.

CONGRATULATIONS TO RENE VAN BEVERN, CHRISTIAN KOMUSIEWICZ and MANUEL SORGE for the ATMOS'15 Best Paper Award with Approximation algorithms for mixed, windy, and capacitated arc routing problems.

CONGRATULATIONS TO RADU CURTICAPEAN for receiving the 2015 Best Student ICALP Paper Award, Track A, with Block Interpolation: A framework for tight exponential-time counting complexity. In 2013, Radu was awarded the Best Student ICALP Paper Award, Track A, with Counting matchings of size k is #W[1]-hard. ICALP best student paper awards are given to papers that are solely authored by students. Radu will finish his PhD. with Markus Blaser this summer, and has accepted a post-doc position with Daniel Marx.

CONGRATULATIONS TO JASON CRAMPTON, GREGORY GUTIN, DANIEL KARAPETYAN, Royal Holloway, University of London, for receiving the Best Paper Award at ACM SACMAT 2015 with Valued Workflow Satisfiability. The paper studies
theoretically and experimentally an FPT algorithm for a new generalization of a well-known problem in access

CONGRATULATIONS TO SAKET SAURABH and DANIEL LOKSHTANOV with FOUR papers at ICALP. This is the second time for Saket!

CONGRATULATIONS TO ALL with conference papers accepted. See Bart’s list on this wiki.

IPEC 2015: 10th International Symposium on Parameterized and Exact Computation covers research in all aspects of parameterized and exact exponential-time algorithms and complexity. In particular, studies on parameterized and exact computations for real-world applications and algorithmic engineering are especially encouraged.

Excellent Student-Paper Award
A paper is eligible for the award if at most one of its authors has received a PhD degree before the paper submission deadline. If there is a non-student author, the students' contributions must be substantial, and a student must give the presentation at the conference.

Accepted Papers
Accepted papers will be published in the symposium proceedings. Authors of accepted papers must present their work at the symposium.

Journal Special Issue
Authors of selected papers at IPEC 2015 will be invited to submit extended versions to a special issue of Algorithmica.

Important dates
• Abstract submission deadline: 26 June 2015, 23:59 UTC/GMT
• Paper submission deadline: 28 June 2015, 23:59 UTC/GMT
• Notification date: 25 July 2015
• Symposium: 16-18 September 2015
• Final version due: 30 September 2015, 23:59 UTC/GMT

IPEC is part of ALGO 2015. Dates for IPEC are 16—18 Sept. in Patras, Greece. ALGO is held 14—18 Sept. A special event will be organized during ALGO 2015 for honoring Paul Spirakis on the occasion of his 60th birthday.

SOCIAL CHOICE: 7th Summer Workshop of the Centre for Mathematics in Social Science of the Univ. of Auckland, NZ.
DATES: 18-19 February 2016.
TOPIC: Multi-Winner Elections—includes Complexity Theory to Social Choice to Political Science.
INVITED SPEAKERS: Bernard Grofman (UC, Irvine), Charles Plott (Caltech), Jean-Francois Laslier (Paris School of Economica), Rolf Niedermeier (Technical Univ. Berlin), Piotr Faliszewski (AGH Univ. Technology, Krakow).
CONTACT: Prof. Arkadii Slinko (zn.ca.dnalkcua|oknils.a#zn.ca.dnalkcua|oknils.a)

Michael Fellows named Honorary Fellow of the Royal Society of New Zealand
Remember those scientists that inspired awe in us as children? Einstein, Marie Curie, Charles Darwin, Sir Arthur Eddington, Sir Alexander Fleming, and many more are also Honorary Fellows RSNZ. Congratulations, Michael.

Congratulations to Bingkai Lin. SODA PC has decided to give both the Best Paper Award and the Best Student Paper Award to the biclique paper by Bingkai Lin. http://www.siam.org/meetings/da15/paper.php
k-BI-CLIQUE is W[1]-hard!
The k-BI-CLIQUE problem asks, given a graph G and integer k, whether G contains the complete bipartite graph $K_{k, k}$ as a subgraph. While this problem was long conjectured to be W[1]-hard, for a long time no one was able to give a proof. This earned the k-Biclique problem the first place in the open problem list of the new version the textbook by Downey and Fellows, listed among "The Most Infamous". But a W[1]-hardness proof has been found! Bingkai Lin, a PhD student in Tokyo, gave a parameterized reduction from k-Clique to prove that k-Biclique is W[1]-hard. His paper can be found on the arXiv. The crux of the proof is to find bipartite host graphs satisfying certain conditions, that allow a k-Clique instance to be embedded in them. Binkai gives a deterministic construction of such host graphs using Weil's character sum theorem, which transforms a k-Clique instance into a Biclique instance whose parameter value is roughly (k!). There is also a randomized construction that is more efficient, resulting in a parameter value of $k^2$. It implies that under a randomized version of the Exponential Time Hypothesis, k-Biclique cannot be solved in $f(k) n^{o(\sqrt{k})}$ time. We congratulate Binkai with this great result!


Friends gathered for 60th birthday celebrations for Jianer in College Station, Texas and at South-Center Univ in China. The Tsinghua Science and Technology Journal Vol. 19 No. 4/August 2014 is a Special Issue on Parameterized Complexity in honour of Chen's birthday. Guest edited by Liming Cai, Iyad Kanj, and Frances Rosamond.There are eight articles of recent results and surveys. Congratulations, Jianer!

The 2014 September Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences. Enjoy!


Christiaan Huygens Prize goes to Bart Jansen
Congratulations to Bart Jansen, Univ. Bergen, for winning the Christiaan Huygens award. This prestigious prize is awarded once every 5 years in the area of ICT for a PhD thesis that contributed significantly to science and has clear relevance to society. The prize consists of 10 000 Euros and a bronze statue of the Dutch scientist Christiaan Huygens. The head of the Dutch scientific funding agency NWO, and the Minister of Education, Culture, and Science presented the award. The award is partly sponsored by IBM, and an interview with Bart is on the IBM weblog:
Bart says: I was really honored, and very happy to meet all these people and share my passion for science with them. During the evening there was an interview with the 4 nominees. They asked us what really helped us in our research; my answer was that the opportunity to travel and meet other people in the field has really helped me grow. During my acceptance speech I told the entire audience about my trip to Australia, surfing and and doing research with Mike and Fran, and about the great and friendly community that I am lucky to be part of. (Photo credit goes to Martine Siemens.)

The 2014 June Parameterized Complexity Newsletter is on the newsletter page. Inside are many announcements of grants, awards,and graduations, new research,and conferences. Enjoy!


Humboldt Research Award to Toby Walsh
Congratulations to Toby Walsh, UNSW, NICTA,for a prestigious Humboldt Research Award.


Inaugural 2014 EATCS Fellow Fellows
Congratulations to Michael Fellows, Australian Professorial Fellow, Charles Darwin University.


Meltzer Prize to Michal Pilipczuk
Congratulations to Michal Pilipczuk, U. Bergen, for
the 2014 Meltzer Prize for Young Researchers.

DFG Award to Mattias Mnich
Congratulations to Mattias Mnich, Bonn, for a DFG award for the project, Big Data Ker-


DFG Mercator to Piotr Faliszewski
Congratulations to Piotr Faliszewski, AGH U. Krakow for a DFG Mercator Guest Professorship.


PCCR 2014: 2nd Workshop on the Parameterized Complexity of Computational Reasoning
July 17-18, 2014 in Vienna, Austria.

PCCR 2014 will be part of the Vienna Summer of Logic, the largest logic event in history with an expected 2,500 participants.
Invited speakers include Georg Gottlob, Dániel Marx, and Stefan Szeider.
Abstracts of contributed talks are due on May 9, 2014 May 12, 2014.
Please see the Workshop webpage for the submission of abstracts and registration information.

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.

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