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.

Congratulations to Gregory Gutin, Professor of Computer Science, Royal Holloway, University of London who has been elected to the Academia Europaea as a Member of the Informatics Section. See http://www.ae-info.org/ae/Member/Gutin_Gregory

Congratulations to Matthias Bentert,Till Fluschnik, André Nichterlein and Rolf Niedermeier for winning Best Student Paper Award at the 21st Symposium on Fundamentals of Computation Theory (FCT '17) for their paper, Parameterized Aspects of Triangle Enumeration. They also won ALGOSENSORS 2017 Best Paper Award. Great teamwork.

Optimisation Summer School in Australia, January 14th to 19th 2018 (http://tinyurl.com/optschool). Spend a week by the beach learning about the latest optimisation technologies. The school will focus on solving large scale combinatorial optimisation problems in practice. The school is intended for undergraduate students (3rd year or later), masters or early stage PhD students. Every undergraduate participant will be assigned an individual mentor. Topics covered include: introduction to constraint programming, modelling, integer programming, parameterized complexity techniques, column generation, vehicle routing, scheduling, evolutionary methods and research skills.Organizer Prof. Toby Walsh, UNSW and Data61.

Slides from the 2017 IPEC Business Meeting Report (by Stefan Kratsch), PC Chairs Report (by Daniel Lokshtanov and Naomi Nishimura, and Publicity Report (Frances Rosamond) are available on the IPEC page. There will be a brief summary in the next newsletter. Thank you to incoming IPEC Steering Committee members Christophe Paul, Michał Pilipczuk, and Magnus Wahlström. Thank you to those outgoing this year for your valuable service: Thore Husfeldt, Iyad Kanj and Gerhard Woeginger.

Congratulations to Martin Aleksandrov and Toby Walsh for their paper: Most Competitive Mechanisms in Online Fair Division, which won Best Paper Prize at the the 40th German Conference on Artificial Intelligence (KI'2017).

Congratulations to Marek Cygan, Lukasz Kowalik, Arkadiusz Socala who won the ESA Best Paper Award Track A for their paper, Improving TSP tours using dynamic programming over tree decompositions.

Congratulations to Matthias Bentert, René van Bevern, André Nichterlein, and Rolf Niedermeier who won the ALGOSENSORS Best Paper Award Algorithms Track at ALGO for their paper, Parameterized algorithms for power-efficient connected symmetric wireless sensor networks.

The EATCS-IPEC Nerode Prize 2017 for outstanding papers in the area of multivariate algorithmics has been awarded to Fedor V. Fomin (Univ Bergen), Fabrizio Grandoni (IDSIA, Univ Lugano), and Dieter Kratsch (Univ Lorraine - Metz) for their paper: A measure & conquer approach for the analysis of exact algorithms (Journal of the ACM 65 (5): Article 25, 2009). Congratulations!


Congratulations to all PACE 2017 winning teams and participants. The PACE 2018 Steering Committee Chair is Bart Jansen. The PACE 2018 PCs are Édouard Bonnet and Florian Sikora. Thank you to our PACE sponsor Networks. Photos thanks to Rudolf Fleischer are on facebook (@MikeFellowsFPT). Lightswords curtesy of Frances Rosamond. Sign up for the PACE Newsletter at pacechallenge.wordpress.com.

Track A: Optimal Tree Decomposition
1. Lukas Larisch (King-Abdullah Univ Science and Engineering), Felix Salfelder (Univ Leeds)
2. Hiromu Ohtsuka, Hisao Tamaki (Meiji Univ)
3. Max Bannach (Univ Lübeck), Sebastian Berndt (Univ Lübeck), Thorsten Ehlers (Univ Kiel)

Track A: Heuristic Tree Decomposition
1. Keitaro Makii, Hiromu Ohtsuka, Takuto Sato, Hisao Tamaki (Meiji Univ)
2. Ben Strasser (Karlsruhe Institute of Technology)
3. Michael Abseher, Nysret Musliu, Stefan Woltran (TU Wien, Institute of Information Systems)

Track A Honors
4. Max Bannach (Univ Lübeck), Sebastian Berndt (Univ Lübeck), Thorsten Ehlers (Univ Kiel)
5. Philippe Jégou, Hanan Kanso, Cyril Terrioux (Aix-Marseille Université, LSIS)
6. Lukas Larisch (King-Abdullah Univ Science and Engineering), Felix Salfelder (Univ Leeds)

Track B: Minimum Fill-In
1. Yasuaki Kobayashi (Kyoto Univ) and Hisao Tamaki (Meiji Univ)
2. Jeremias Berg, Matti Järvisalo, Tuukka Korhonen (Univ Helsinki).
3. Édouard Bonnet (UnivParis-Dauphine), R.B. Sandeep (Hungarian Academy of Sciences), Florian
Sikora (Univ Paris-Dauphine)

Track B Honors
4. Anders Wind Steffensen, Mikael Lindemann (IT Univ Copenhagen)
5. Kaustubh Joglekar, Akshay Kamble, Rajesh Pandian (Indian Institute Of Technology, Madras)
6. Saket Saurabh (Univ Bergen), Prafullkumar Tale (Institute of Mathematical Sciences, Chennai)
7. Mani Ghahremani (Univ Portsmouth)
8. Frederik Madsen, Mikkel Gaub, Malthe Kirkbro (IT Univ Copenhagen).

Congratulations Radu Curticapean (Hungarian Academy of Sciences), Holger Dell (Saarland Univ), Fedor Fomin (Univ Bergen), Leslie Ann Goldberg (Univ Oxford) and John Lapinskas (Univ Oxford) who have won IPEC 2017 Best Paper Award for A Fixed-Parameter Perspective on #BIS. A summary of their award-winning paper will appear in the next newsletter.


Congratulations Astrid Pieterse and Bart M. P. Jansen (Eindhoven Univ of Technology) for winning the IPEC2017 Excellent Student Paper Award with Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. A summary of their award-winning paper will appear in the next newsletter.

SEEKING CHALLENGE PROBLEMS. Send your suggestion for the 2018 PACE Challenge problems to Holger Dell <moc.liamg|lled.regloh#moc.liamg|lled.regloh>, 'Christian Komusiewicz' <ed.anej-inu|zciweisumok.naitsirhc#ed.anej-inu|zciweisumok.naitsirhc>, "Bart M. P. Jansen" <moc.liamg|nesnajpmb#moc.liamg|nesnajpmb>. The 2017 PACE CHALLENGE WINNERS will be announced at the PACE meeting immediately following the IPEC Business meeting, and in the same room.

Congratulations!! Hisao Tamaki (Meiji University) has won the best ESA Track B paper award for his paper accompanying his PACE17 submission. The title of his paper is Positive-instance driven dynamic programming for treewidth. He says this work would not have happened without the motivation of the PACE challenge.

The 2017 June, Vol 13, no 2 Parameterized Complexity Newsletter is on the newsletter page. Co-editors: Valia Mitsou (LIRIS, CNRS Univ Lyon 1) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and and Frances Rosamond (Univ of Bergen) on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF. This newsletter contains announcements of many awards, prizes, best papers and graduates. There is an insightful article by Fahad Panolan on Lossy Kernelization. Ronald de Haan, winner of the Dutch E. W. Beth Dissertation Prize, discusses a new direction of FPT SAT Encodings. Workshops and events are announced. Enjoy!

Tutorial: An Introduction to Parameterized Complexity with Applications in Algorithmic Decision Theory.italic text ADT 2017 Tutorial and Doctoral Consortium day: October 24, 2017. Serge Gaspers (School of Computer Science and Engineering, UNSW Sydney and Data61, CSIRO, Australia).

5th Intl Conf on Algorithmic Decision Theory (ADT 2017)
Luxembourg, 25—27 October 2017

Early registration: before August 31

The ADT 2017 seeks to bring together researchers and practitioners coming from diverse areas such as Artificial Intelligence, Database Systems, Operations Research, Discrete Mathematics, Theoretical Computer Science, Decision Theory, Game Theory, Multiagent Systems, Computational Social Choice, Argumentation Theory, and Multiple Criteria Decision Aiding in order to improve the theory and practice of modern decision support. Some of the scientific challenges facing the Algorithmic Decision Theory (ADT) community include big preference data, combinatorial structures, partial and/or uncertain information, distributed decision making, and large user bases. Such challenges occur in real-world decision making in domains like electronic commerce, recommender systems, argumentation tools, network optimization (communication, transport, energy), risk assessment and management, and e-government.

Congratulations to Ronald de Haan. The Association for Logic, Language and Information (FoLLI) has awarded the E. W. Beth Dissertation Prize, named in honor of the Dutch mathematician Evert Willem Beth to Ronald for his outstanding dissertation, Parameterized Complexity in the Polynomial Hierarchy, Technical University of Vienna. See Ronald's article in the June 2017 Parameterized Complexity Newsletter.

There is a lot happening in Australia this summer:
1. Computational & Algorithmic Topology Workshop (CATS), The Univ of Sydney, 27 June – 1 July 2017. Serge Gaspers will give an introductory lecture on parameterized complexity.
2. Computational Geometry Week (CG Week 2017), the premier international forum for advances in computational geometry and its many applications. Univ of Queensland, Brisbane, July 4–7. Benjamin Burton, local organizer.
3. The 28th International Workshop on Combinatorial Algorithms (IWOCA2017), Newcastle, July 17–21. Special memorial to Mirka Miller.
4. ICML and UAI in Sydney, August 6–15.
5. The big IJCAI / SAT / CP / ICLP event in Melbourne, August 19 – September 1.

Recent Advances in Parameterized Complexity (rapctelaviv.weebly.com). The event will be held on December 3-7, 2017, at Tel Aviv, Israel.

The purpose of Recent Advances in Parameterized Complexity is twofold. First, the event would present an overview of several recent, exciting advances in the field of Parameterized Complexity. Second, to attract new researchers to work on topics in this field of research, the program would also consist of a preparatory school at the level of an introductory course. We thus invite both graduate students and established researchers to participate in Recent Advances in Parameterized Complexity. For more details, see rapctelaviv.weebly.com.

PACE deadline extended until May 25. Thanks to the cooperation with OPTIL.io (http://www.optil.io ), the notification will still be sent out June 1. Good luck and fun to all participants in the remaining weeks. We look forward to seeing you at IPEC, where there will be a special surprise for all participants.

New positions have been announced on the JOBS PAGE.

STOC 2017 BEST PAPER AWARD FPT results have been selected for a STOC2017 BEST PAPER AWARD: Deciding Parity Games in Quasipolynomial Time by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephen. See https://www.comp.nus.edu.sg/~fstephan/publications.html, publication number 181. See also the article in the Vol12 (2) November 2016 Parameterized Complexity Newsletter.

Faster Space-Efficient algorithms for Subset Sum and k-Sum by Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas.
Homomorphisms Are a Good Basis for Counting Small Subgraphs by Radu Curticapean, Holger Dell, Dániel Marx.
Lossy Kernelization by Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Ramanujan Sridharan.

SEE FPT PAPERS ONLINE here and PAPERS IN CONFERENCES here. Many thanks to Bart Jansen for collecting.

PARAMETERIZED COMPLEXITY SUMMER SCHOOL The 3rd Parameterized Complexity Summer School will be held in Vienna, Austria, from 1 to 3 September 2017 (Friday-Sunday) co-located with ALGO 2017 and will take place in the same venue. See https://algo2017.ac.tuwien.ac.at/pcss/

PACE UPDATE: Submission is possible from now until May 1 for both tracks of PACE 2017. We are happy to announce that PACE 2017 will cooperate with OPTIL.io to handle the submission process and the evaluation of submissions. OPTIL.io is a website for organizing programming challenges for optimization problems, created and maintained by the Institute of Computing Science of Poznan University of Technology.

CALL FOR PAPERS: IPEC 2017 Vienna, Austria 4—8 September 2017.

Important Dates
Abstract Submission: June 25, 2017
Paper Submission: June 28, 2017
Notification of acceptance: July 25, 2017
Symposium: September 6-8, 2017

Excellent Student Paper Award eligibility: at most one author has received a PhD degree before the paper submission deadline. The students' contributions must be substantial, and a student must give the presentation at the conference. IMPORTANT Please identify if you are submitting a Student Paper. There will also be Best Paper Award (not necessarily student).

Stefan Szeider would like to bring to the attention of the Parameterized Complexity community the call for the 8th Vienna Research Groups for Young Investigators. The level of excellence is similar to an ERC starting grant, but the setup is slightly different. A crossover between mathematics and CS might be an interesting combination for the call. A successful candidate has good chances for negotiating a permanent contract with TU Vienna. Submit proposals by July 13, 2017. All interested parties are cordially invited to an open Proposers’ Day on April 6, 2017. Detailed information is available online (www.wwtf.at).

ARE YOU READY FOR A CHALLENGE? See https://pacechallenge.wordpress.com/pace-2017
TRACK A (Treewidth Challenges)
1) Compute a tree-decomposition of minimum width. You have 30 minutes per instance. Win by solving more instances than the other participants.

2) Compute some tree-decomposition. You have 30 minutes per instance. Win by printing solutions of smaller width than the other participants.

Detailed instructions and fresh instance sets:

TRACK B (Minimum Fill-In Challenge)
Given an undirected graph G, compute a smallest set of edges E such that adding E to G results in a chordal graph. You have 30 minutes per instance. Win by solving more instances than the other participants.

Detailed instructions and an instance set:

Congratulations to George Mertzios (Durham University) who has received an EPSRC award (the UK research funding body) for "Algorithmic Aspects of Temporal Graphs". The project topic is algorithms and complexity for problems in temporal (i.e. dynamically changing) graphs. Apply for a 3-year full-time PostDoc position (start date is April 2017, or soon thereafter; there is some flexibility on the starting date). The salary will be £32000 - £35000 p.a. Candidates with a good knowledge of parameterized complexity and algorithms are encouraged to apply. More details about the project can be found here: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/P020372/1. For inquires about the project and the application process, please contact George Mertzios (ku.ca.mahrud|soiztrem.egroeg#ku.ca.mahrud|soiztrem.egroeg; see also http://community.dur.ac.uk/george.mertzios/)

The The February 2017 Parameterized Complexity Newsletter is on the wiki newsletter page here. It lists awards and prizes, graduates, new jobs, and wonderful research. Michael Wehar gives a new look at fine-grained FPT. IPEC Excellent Paper winner Marcin Wrochna writes about “FPT inside P”. NWO award winner Johan Kwisthout discusses a framework for Fixed-error Randomized Tractability. Australia's Chris Wallace Award for a notable CS breakthrough has been awarded to Haris Azis. Haris writes about cake-cutting and suggests open problems. Enjoy!

Congratulations to Eunjung Kim (Charge de Recherche CNRS (Junior Researcher) LAMSADE, Univ


Dauphine) who has been awarded the Bronze Medal by the National Center for Scientific Research (CNRS). The Medal is intended to recognize and encourage an already productive French junior researcher who is a well-committed and promising specialist in computer science.

Prof. Dr. Henning Fernau, Editor-in-Chief of Algorithms announces a competition for an annual Travel Award sponsored by Algorithms. The Travel Award consists of 800 Swiss Francs and will be granted to a PhD student in the area of algorithms and their applications, to attend a conference in 2017. Applications until 31 March 2017.

NERODE PRIZE DEADLINE MARCH 1, 2017 The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics.

ELIGIBILITY: 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 research work nominated for the award should be in the area of multivariate algorithms and complexity meant in a broad sense, and encompasses, but is not restricted to, those areas covered by IPEC.

NOMINATE: Send an email to Award Committee Chair containing a brief summary of the technical content of each nominated paper and a brief explanation of its significance. Send copies to the members of the committee. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination".

David Eppstein <ude.icu|nietsppe#ude.icu|nietsppe> Award Committee Chair (University of California, Irvine)
Daniel Marx <uh.emb.sc|xramd#uh.emb.sc|xramd> (Hungarian Academy of Sciences)
Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> (Texas A&M)

Recent Advances in Algorithms: International Computer Science Student School
May 22–26, 2017, St. Petersburg, Russia. http://raa-school.org

Application: February 10, 2017
Notification: February 20, 2017
Registration: February 27, 2017

AIM OF THE SCHOOL The school offers the unique opportunity to learn about recent breakthroughs in several domains of algorithms: from classical areas like network algorithms and longest paths in graphs to recently emerged areas like streaming
algorithms and algorithms for high dimensional data. The lectures will be taught by the leading researchers in these areas. Each of the tutorials will provide an introduction to the area and gradually bring to the current research frontiers.

The primarily audience consists of PhD students interested in Algorithms. Bright master students, postdocs, young researchers and even faculty are also very welcome.

Michael Kapralov (EPFL) Streaming Algorithms

Aleksander Mądry (MIT) Graph Algorithms and Continuous Optimization

Ilya Razenshteyn (MIT) Algorithms for High-Dimensional Data

Saket Saurabh (IMSc) Longest Paths in Graphs: Parameterized Algorithms

VENUE The school is hosted by St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences which is located in the very center of St. Petersburg.

CONFERENCES. Consider submitting.
FAW 2017: 11th International Frontiers of Algorithmics Workshop will be held on June 23-25, 2017 at Chengdu, Sichuan, China. Submission deadline: February 3.

TCS 2017 : Topics in Theoretical Computer Science will be held September 12—14 at Institute for Research in Fundamental Sciences (IPM), Tehran, Iran. Abstract Registration: 1 May. Submission Deadline: 8 May

See http://community.dur.ac.uk/tom.friedetzky/conf.html


Congratulations to Johan Kwisthout (Donders Institute for Brain, Cognition and Behaviour) who has received an NWO EW Physical Sciences Division TOP grant for the project Parameterized Complexity of Approximate Bayesian Inference. The 217,000 Euro grant is for four years (April 2017-March 2021). Applications for a PhD candidate on a fully paid fellowship for four years plus additional costs are being accepted.

Congratulations to Professor Fedor Fomin (Univ Bergen) who has received a Norwegian Research Council (NFR) grant for Multivariate Algorithms: New Domains and Paradigms. There will be 2 postdoctoral and 1 PhD position. Please apply.

There has been a very powerful cyclone in Chennai, with everyone being cut off from internet for several days. Fedor has recently returned from Chennai and reports it an experience! We send all our Chennai friends the very best wishes.

Congratulations to Saket Saurabh (Univ of Bergen) who is now Associate Editor of JCSS. Mike Fellows (Univ Bergen) has been appointed to the Editorial Board of JCSS. Congratulations to Bart Jansen (Eindhoven Univ) who is now Associate Editor of TALG. These positions embody an enormous amount of volunteer work and responsibility. Please help these new editors by reviewing promptly and with good will. They are contributing mightily to the PC community and to TCS largely.

Congratulations to Professor Toby Walsh (UNSW School of Computer Science and


Engineering) who has won the NSW Premier's Award for Excellence in Engineering and Information and Communications Technologies. Toby is a global leader in AI and one of the top five most-cited computer scientists in Australia. He builds computer programs for important tasks, such as optimising the efficiency of distributing donated food to charities. He researches the interface between optimisation (making better decisions), social choice (taking account of agents’ preferences), and game theory (taking account of self-interested agents).

The Parameterized Complexity Newsletter, Vol 12, no 2, Nov 2016 is on the wiki. Read announcements of many awards, prizes and graduates. There is an insightful article by Gregory Gutin (Royal Holloway, Univ London) on FPT algorithms beating MIP Solver, and an article by Michal Wlodarczyk (Univ Warsaw) on New Algebraic tools for Treewidth-motivated Convolutions. We also announce breakthrough results in parity games. Please welcome Valia Mitsou (Hungarian Academy of Sciences) as new co-editor of the newsletter.

The 2017 Parameterized Algorithms and Computational Experiments Challenge (PACE): consists of two separate tracks. See: https://pacechallenge.wordpress.com/pace-2017https://pacechallenge.wordpress.com/pace-2017 for details.

TRACK A (Treewidth Challenges)

1) Compute a tree-decomposition of minimum width. You have 30 minutes per instance. Win by solving more instances than the other participants.

2) Compute some tree-decomposition. You have 30 minutes per instance. Win by printing solutions of smaller width than the other participants.

TRACK B (Minimum Fill-In Challenge)

Given an undirected graph G, compute a smallest set of edges E such that adding E to G results in a chordal graph. You have 30 minutes per instance. Win by solving more instances than the other participants.


December 1st, 2016: Announcement of the challenges
March 1st, 2017: Submission of preliminary version for bugfixing and leaderboard
May 1st, 2017: Submission of final version
June 1st, 2017: Announcement of the results
September 4-8, 2017: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2017) in Vienna


Track A (tree width):
- Holger Dell (Saarland University and Cluster of Excellence (MMCI))

Track B (min fill-in):
- Christian Komusiewicz (chair) (Friedrich-Schiller-University Jena)
- Nimrod Talmon (Weizmann Institute of Science)
- Mathias Weller (Laboratory of Informatics, Robotics, and Microelectronics of Montpellier (LIRMM))


- Holger Dell (Saarland University and Cluster of Excellence, MMCI)
- Bart M. P. Jansen (Eindhoven University of Technology)
- Thore Husfeldt (ITU Copenhagen and Lund University)
- Petteri Kaski (Aalto University)
- Christian Komusiewicz (Friedrich-Schiller-University Jena)
- Frances A. Rosamond (chair) (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF, University of Bergen)

Workshop: The Sydney Algorithms Workshop (SAW 2016)
Where: Sydney (Australia).
When: 6-9 December 2016.
Organizers: Joachim Gudmundsson, Serge Gaspers, Stefan Rümmele, and Julián Mestre.
Register: <https://sydneyalgorithms.wordpress.com/2016/10/25/sydney-algorithms-workshop-2016/>
Focus is on parameterized complexity and computational geometry.

Nearby events happen the following week: ISAAC 2016 (Sydney), the Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC 2016 in Newcastle), and the workshop on Applied Probability, Combinatorics and Optimisation
(APCO in Newcastle).

Workshop: Combinatorial Optimization meets Parameterized Complexity
Where: Bonn at Universitätsclub Bonn, located at Konviktstraße 9, 53113 Bonn.
When: 13th and 14th of December 2016.
Organizers: Britta Peis, Heiko Röglin, and Stefan Kratsch.
Register: FREE, but send an email with the subject “Workshop Registration” to
ed.nnob-inu.sc|5terces#ed.nnob-inu.sc|5terces containing your name, address, and affiliation. Please indicate whether you will be attending both or just one day of the workshop.

Further information can be found at http://tcs.cs.uni-bonn.de/doku.php?id=research:workshop2016

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