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. Follow the news on facebook with @MikeFellowsFPT

IPEC 2019 will be part of ALGO 2019, which also hosts ESA 2019 and a number of more specialized conferences and workshops. IPEC 2019 will take place September 11-13, 2019, in Munich, Germany.

*Important dates*

Title and short abstract registration deadline: May 29, 2019, 23:59 AoE
Full paper submission deadline: June 1, 2019, 23:59 AoE
Notification: July 15, 2019
Conference: September 11-13, 2019

See the full call for papers for more information.

2019 CALL FOR NOMINATIONS: The EATCS-IPEC Nerode Prize For Outstanding Papers in Multivariate Algorithmics. Deadline: March 15, 2019
The EATCS-IPEC Nerode Prize is an annual prize for outstanding work in multivariate algorithmics and parameterized complexity, published in a recognized refereed journal by an individual or a team of authors. The Prize is named in honor of Anil Nerode in recognition of his major contributions to mathematical logic, theory of automata, computability, and complexity theory.
The Call for Nominations for 2019 EATCS-IPEC Nerode Prize is open. Please send your nomination via emails to the Prize Committee Chair Jianer Chen at ude.umat.esc|nehc#ude.umat.esc|nehc no later than March 15, 2019. The nomination should contain a brief summary of the technical content of the nominated paper and a brief explanation of its significance. The Subject line of the nomination E-mail should contain the group of words "Nerode Prize Nomination".
Note that the past rules that require a certain number of years before/after the publication of the nominated paper have been removed. Thus, nominations for any past work in this area that you feel deserves the recognition will be welcome.
The award presentation will take place at ALGO/IPEC 2019 (The 14th International Symposium on Parameterized and Exact Computation) September 11-13, 2019 in Munich, Germany.
The EATCS-IPEC Nerode Prize Committee: Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> Award Committee Chair (Texas A&M University, USA), Hans L. Bodlaender <ln.uu|rednealdob.l.h#ln.uu|rednealdob.l.h>
(Utrecht University, The Netherlands), Virgi V. Williams ude.tim|igriv#ude.tim|igriv (MIT, USA)


CONGRATULATIONS to Mateus de Oliveira Oliveira (Univ Bergen, Norway). Mateus’ project Automated Theorem Proving from the Mindset of Parameterized Complexity has been granted by the Norwegian Research Council IKTPLUSS program: Young Research Talents. The Research Council's awards for young outstanding researchers reward high scientific merit, independence and innovative thinking, and are intended to motivate prize recipients at an early stage in their careers to expand their efforts and continue to pursue a career in research.

Visit the JOBS AVAILABLE page on this wiki.

CALL FOR PAPERS: 22nd Symposium on Fundamentals of Computation Theory (FCT). August 11–14, 2019 at the University of Copenhagen, Denmark. Abstract registration: March 31, 2019. Full-paper submission: April 7. Notification to authors: May 19. Camera-ready submission: June 2. Submit original research papers in all areas related to the foundations of computer science (algorithms, complexity, and formal methods). FCT was established in 1977. It is a biennial conference that circulates on a regular basis in Eastern Europe, Western Europe, and the Nordic countries.

NOMINATE outstanding Masters or Undergraduate Thesis for the VCLA International Student Awards. The Vienna Center for Logic and Algorithms (VCLA) of TU Wein annually award authors of scientific works across the wide spectrum of Logic and Computer Science. Deadline March 15, 2019. The degree must have been awarded between 15 Nov 2017 and 31 Dec 2018.
The main area of interest are:
Computational Logic, covering theoretical and mathematical foundations
Databases and Artificial Intelligence, concerned with logical methods for modeling, storing, and drawing inferences from data and knowledge. argumentation, planning).
Verification, concerned with logical methods and automated tools for reasoning about the behavior and correctness of complex state-based systems such as software and hardware designs as well as hybrid systems.
For nomination instructions, please visit
<https://logic-cs.at/award-call-2019/> https://logic-cs.at/award-call-2019/

Inquiries: <mailto:award@logic-cs.at> ta.sc-cigol|drawa#ta.sc-cigol|drawa
Award Committee: Robert Ganian (committee co-chair), Magdalena Ortiz (general chair), Revantha Ramanayake (committee co-chair)

IN MEMORIAM: The award is dedicated to the memory of Helmut Veith, the brilliant computer scientist who tragically passed away in March 2016, and aims to carry on his commitment to promoting young talent and promising researchers in these areas.

Remember to NOMINATE: Presburger Award for Young Scientists.
: December 31st, 2018. Official website: http://www.eatcs.org/index.php/presburger

CONGRATULATIONS to Eduard Eiben, post-doc at Univ Bergen,


who was awarded the National Award of Excellence by the Austrian Federal Ministry of Education, Science and Research (BMBWF) for his outstanding dissertation. The award ceremony took place in Vienna on December 5th, 2018. Eduard Eiben has been awarded for his dissertation Exploiting new types of structure for fixed-parameter tractability. The work was carried out as part of a research project funded by the Austrian Science Fund FWF at the Institute for Logic and Computation at the Faculty of Informatics at TU Wien. The supervisors were Prof. Stefan Szeider and Dr. Robert Ganian.

Eduard Eiben is the first graduate of the Doctoral Program “Logical Methods in Computer Science” (LogiCS), which was founded in 2014 by professors at TU Wien, TU Graz, and JKU Linz.

I am particularly pleased that an algorithmic work has been awarded, because algorithms will in future gain an increasingly important role in technological innovation, says Prof. Georg Gottlob, the head of the LogiCS Doctoral College.

Workshop on Kernels 2019 will be held at University of Bergen, Norway,


on June 3-7 2019. Workshop on Kernels (WorKer) is an irregular meeting focused on kernelization: rigorous theory of preprocessing. The 2019 edition will be the sixth installment of the workshop, featuring a tutorial on coresets by Christian Sohler and a tutorial on lossy kernels.

For more information, in particular a tentative list of invited speakers, please visit http://worker2019.mimuw.edu.pl. Registration will open in early Spring 2019. Please feel free to forward this announcement to your students and colleagues.

CONGRATULATIONS to Vangelis Paschos (Lamsade, Univ Dauphine) for


receiving a Visiting Professorship in the Department of Management and Production Engineering (DIGEP) at the Univ of Torino. The department is the point of reference in Politecnico di Torino for research in the relationship between systems of production of goods and services and the economic environment in which they operate. The DIGEP promotes basic and applied research, training, technology transfer and services to the local community in the areas of systems of production, quality management, product design, management and accounting, industrial plants law and economics.


CONGRATULATIONS to Jessica Enright (Univ of Edinburgh) and Kitty Meeks (Univ Glasgow) who have been elected to the Young Academy of Scotland.


There are only 126 members from all disciplines. The Academy: provides a platform for able and innovative young entrepreneurs, professionals and academics to develop a coherent and influential voice, and to address the most challenging issues facing society in Scotland and beyond. Jessica and Kitty are using parameterized complexity to exploit the structural properties of networks that describe how cattle and sheep move around Britain, as well as how farms contact each other geographically and via wind movement. Jess is the General Secretary of the Edinburgh Mathematical Society, Kitty currently holds a Royal Society of Edinburgh Personal Research Fellowship at the Univ of Glasgow.

(1) Classes of Directed Graphs, Editors: Bang-Jensen, Jørgen and Gutin, Gregory, Springer, 2018.


This book gives a detailed account of the theory of directed graphs from the perspective of important classes of digraphs, with each chapter written by experts on the topic. Authors
include Stephan Kreutzer, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlstrom.

This book provides a comprehensive overview of the latest research in the field. It covers core new results on each of the classes discussed, including chapters on tournaments, planar digraphs, acyclic digraphs, Euler digraphs, graph products, directed width parameters, and algorithms. Explored are structural results as well as algorithms and complexity, including results on fixed parameter tractability. Detailed indices ease navigation while more than 120 open problems and conjectures ensure that readers are immersed in all aspects of the field.

Classes of Directed Graphs provides a valuable reference for graduate students and researchers in computer science, mathematics and operations research. As digraphs are an important modelling tool in other areas of research, this book will be a useful resource to researchers working in bioinformatics, chemoinformatics, sociology, physics, medicine, etc.

(2) Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Iris van Rooij, Johan Kwisthout, Todd Wareham, and Mark Blokpoel. Cambridge University Press, 2019.


This book covers both classical and parameterized complexity. It introduces the mathematical concepts and proof techniques that can be used to test one's intuition of (in)tractability. It
describes how these tools can be applied to cognitive modeling to deal with intractability and its ramifications in a systematic way. Aimed at students and researchers in philosophy, cognitive neuroscience, psychology, artificial intelligence, and linguistics who want to build a firm understanding of intractability and its implications in their modeling work, it is an ideal resource.

Advance praise: Computational complexity has long been the elephant in the room in cognitive science. Researchers, including myself, blithely propose models that, if taken literally, would imply the brain can solve computational problems that are known to be intractable. This excellent introduction to both the technical results and their cognitive relevance should alert students and researchers to these pressing questions. Nick Chater -Univ of Warwick.

(3) Kernelization: Theory of Parameterized Preprocessing. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. Cambridge Univ Press. Anticipated Dec 2018.


Preprocessing, or data reduction, is a standard technique for simplifying and speeding up computation. Written by a team of experts, this book introduces a rapidly developing area of preprocessing analysis known as kernelization. The authors provide an overview of basic methods and important results, with accessible explanations of the most recent advances
such as meta-kernelization, representative sets, polynomial lower bounds, and lossy kernelization. The text covers upper bounds, meta-theorems, lower bounds, and beyond kernelization. The methods are demonstrated through extensive examples using a single data set. Written to be self-contained, the book only requires a basic background in algorithmics and will be of use to professionals, researchers and graduate students in theoretical
computer science, optimization, combinatorics, and related fields.

Advance praise: Kernelization is one of the most important and most practical techniques coming from parameterized complexity. In parameterized complexity, kernelization is the technique of data reduction with a performance guarantee. From humble beginnings in the 1990's it has now blossomed into a deep and broad subject with important applications, and a well-developed theory. Time is right for a monograph on this subject. The authors are some of the leading lights in this area. This is an excellent and well-designed monograph, fully suitable for both graduate students and practitioners to bring them to the state of the art. The authors are to be congratulated for this fine book. Rod Downey, Victoria Univ of Wellington.

Nominate for the EATCS PRESBURGER AWARD for Young Scientists 2019. Deadline: December 31st, 2018. Nominate outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. Nominatees must be at most 35 years at the time of the deadline of nomination (i.e., for 2019 the date of birth should be in 1983 or later). The 2019 Award Committee consists of Thore Husfeldt (Lund Univ and IT Univ of Copenhagen), Anca Muscholl (LaBRI, Bordeaux) and Jukka Suomela (Aalto, chair).

Nominations, consisting of a two page justification and (links to) the respective papers, as well as supporting letters, should be sent by e-mail to: gro.sctae|drawa-regrubserp#gro.sctae|drawa-regrubserp

The subject line of every nomination should start with Presburger Award 2019, and the message must be received before December 31st, 2018.

The award includes an amount of 1000 Euro and an invitation to ICALP 2019 for a lecture.

Official website: http://www.eatcs.org/index.php/presburger


CONGRATULATIONS Eunjung Kim (Charge de Recherche, CNRS, LAMSADE, Paris Dauphine Univ). Eunjung has been awarded 210,000 Euro by the National Research Agency (ANR) of France for her research project, Algorithms with Small Separations acKnowledged: graphs and linear matroids (ASSK). The theme of this project is small separation phenomena on graphs and linear matroids, emphasizing the applications on algorithm design. The grant duration will be 2019-2022, with a postdoc position available.


CONGRATULATIONS Bart Jansen (Eindhoven Univ of Technology, Netherlands). Bart has received an ERC Starting Grant for his project, REDUCESEARCH: Rigorous Search Space Reduction. The project will develop preprocessing methods that reduce the search space of problem-solving algorithms. See the announcement at https://www.tue.nl/en/our-university/departments/mathematics-and-computer-science/news/erc-starting-grant-for-bart-jansen-simplifying-prior-to-solving/.


CONGRATULATIONS Saket Saurabh (University of Bergen). Saket has been awarded an ERC Consolidator Grant. This is Saket’s second ERC grant; he held an ERC starting grant between 2013-2017. See the announcements at
https://www.uib.no/matnat/122333/han-vil-gjere-big-data-mindre, and
https://www.uib.no/en/matnat/122331/making-sense-big-data. The Department of Informatics celebrated Saket with cake and champagne.


CONGRATULATIONS Mike Fellows AC HFRSNZ MAE, University of Bergen, for being elected to Academia Europaea.The Academia Europaea is an independent learned society and European Union’s Academy of Humanities and Sciences. On the initiative of Royal Society and other National Academies in Europe, the Academia was founded in 1988 as the functioning Europe-wide Academy that encompasses all fields of scholarly inquiry.


CONGRATULATIONS Professor Rod Downey FRSNZ. Rod has been awarded the Rutherford Medal by Royal Society Te Apārangi for his revolutionary research into mathematical logic and computer science.

The Rutherford Medal is the highest honour awarded by the Society for an exceptional contribution to advancing and promoting knowledge for the benefit of New Zealand.

Rod gives a brief comment about parameterized complexity and its usefulness on the website https://royalsociety.org.nz/what-we-do/medals-and-awards/medals-and-awards-news/2018-rutherford-medal-solving-cant-compute-and-is-that-random-sequence-really-random/

Professor Rod Downey, of Victoria University of Wellington, is an internationally recognised logician known for his research into computability—how can mathematical processes be algorithmically implemented either in theory or practice — and the study of randomness, and co-founder of Parameterized Complexity with Mike Fellows.


CONGRATULATIONS to NERODE PRIZE WINNERS Stefan Kratsch and Magnus Wahlström for Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal (ACM Trans. Algorithms 10(4): 20:1-20:15, 2014).


CONGRATULATIONS to Marc Roth (Saarland University and Cluster of Excellence (MMCI), Saarbrücken, Germany), Johannes Schmitt (ETH Zürich, Zürich, Switzerland). The 2018 IPEC Program Committee has selected their paper, Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness for the IPEC 2018 Excellent Student Paper Award and for the IPEC 2018 Best Paper Award.

CONGRATULATIONS to Ronald de Haan who was endowed with the honor of participating in the Heidelberg Laureate Forum (HLF). The HLF is a gathering of laureates of some of the most prestigious prizes in mathematics and computer science. Held in Heidelberg, Germany, from September 23-28 2018, the Heidelberg Laureate Forum brings these laureates at the apex of their careers together with 200 high-achieving graduate student and postdoctoral counterparts from around the world. The HLF gives early career researchers an opportunity for interaction that is typically not available within the normal university environment or in their home university department.

CONGRATULATIONS to Gregory Gutin who has been awarded a British pounds 210K grant for 3 years
in access control in info security, where parameterized algorithmics will be used. The project is Analyzing Security-aware Workflows.

Gregory is looking for a postdoc for a 3-year position with a very decent salary (37K pounds a year the 1st year and +2K each consecutive year). The start day is 1st Oct 2018. The topic is parameterized algorithmics applied to access control in info security, but not limited to it. It's a continuation of the previous parameterized algorithmics + access control grant, where Gregory had three PDRAs of which two
quite easily found permanent positions soon afterwards, in UK and France, and one, simply did not want a permanent position yet. Contact: <ku.ca.luhr.sc|nitug#ku.ca.luhr.sc|nitug>

CONGRATULATIONS to Ignasi Sau who defended his Habilitation at LIRMM Université de Montpellier on Parameterized Complexity on Monday 25 June. Reports were from Mike Fellows, Fedor Fomin, Rolf Niedermeier. Examiners were Dimitrios Thilikos, Jean-Claude Bermond, Marc Noy and Gilles Trombetton.

ICALP 2018 satellite workshop: Algorithmic Aspects of Temporal Graphs will be held in Prague on Monday 9 July 2018. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented. Some of the key challenges will be highlighted. A participant can register only to the workshop (Monday 9 July), or to both the workshop and the conference (Monday 9 July to Friday 13 July). See https://iuuk.mff.cuni.cz/~icalp2018/registration

ICGT 2018 - 10th International Colloqium on Graph Theory and combinatorics ICGT is a conference created in the honour of C.Berge in 1976 and organized by the French community in Graph Theory every 4-5 years. This 10th edition succeeds the editions of Grenoble in 2014, Orsay in 2010 and Hyères in 2005, and will take place in Lyon from July 9th to 13th 2018. See http://liris.cnrs.fr/~icgt2018/
mail: rf.srnc.siril|8102tcgi#rf.srnc.siril|8102tcgi

Apply for the 2018 Algorithms PhD Students Travel Award. The Algorithms Journal Editor-in-Chief, Henning Fernau announces that the award aims to assist junior researchers to attend an international conference. Deadline to apply is 31 May. The winner will be announced by 15 June. See

CONGRATULATIONS!! The paper "Recognizing hyperelliptic graphs in polynomial time",
by Jelco Bodewes and Marieke van der Wegen, and coauthored by Hans Bodlaender and Gunther Cornelissen, has received the Best Student Paper award at WG 2018. Marieke is a PhD student in Utrecht.

CONGRATULATIONS to Prof. Jurik Nesetril, who has received the Donatio Universitatis Carolinae


prize “for his contribution to mathematics and for his leading role in establishing a world-renowned group in discrete mathematics at Charles University”. The prize was given by the rector of the university on the occasion of the 670th anniversary of the establishment of Charles University. It comes with one million CZK support. (https://www.mff.cuni.cz/verejnost/konalo-se/2018-04-nesetril/)

The Parameterized Approximation Algorithms Workshop (PAAW) will take place as a satellite workshop of ICALP 2018 in Prague, Czechia, on Monday July 9th 2018. https://sites.google.com/site/aefeldmann/workshop
Register through the ICALP registration page (early registration deadline is May 31): https://iuuk.mff.cuni.cz/~icalp2018/registration

CONGRATULATIONS TO NERODE PRIZE WINNERS Stefan Kratsch and Magnus Wahlström for


Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. ACM Trans. Algorithms 10(4): 20:1-20:15 (2014)

The search for polynomial kernelization algorithms played a central role in the research on parameterized complexity during the last decade. By now, there are well-developed tools for both positive and negative results in this area. Kratsch and Wahlström were the first to recognize the applicability of the matroidbased machinery (developed earlier by Marx, based on classic results of Lovász) to the compression of NP-hard cut problems. Their work settled the long-standing open problem about the polynomial kernelizability of the Odd Cycle Transversal problem in a beautiful way.

The paper, and its follow-up (Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS 2012), have been very influential and paved the way for several other matroid-based kernelizations, such as those for Vertex Multiway Cut, Above-Guarantee Vertex Cover, and Subset Feedback Vertex Set. Moreover, experiments show
that matroid-based compression is not merely a nice theoretical concept, but also gives relevant practical speedups (Stefan Fafianie, Stefan Kratsch: An Experimental Analysis of a Polynomial Compression for the
Steiner Cycle Problem. SEA 2015: 367-378). For this reason, the Nerode Prize 2018 Committee unanimously decided that the this foundational paper by Kratsch and Wahlström deserves to win the Nerode prize.

PARAMETERIZED COMPLEXITY FOR PRACTICAL COMPUTING (PCPC). Mike Fellows has put the pdf of his Research Council of Norway Toppforsk awarded grant proposal on the Publications page of his personal website: Michael Ralph Fellows <www.mrfellows.net>. The proposal describes the practical computing ecology and introduces new terminology and ideas such as: “The Third Wave of FPT”, “Reverse Kernelization”, “Inductive Gradients”, ”Smooth (Groovy) Kernelization” , "Permissive Turbocharging", and other new, cool ideas. Please cite his proposal for these topics. Citation:
Michael R. Fellows: Norwegian Research Council Toppforsk Proposal, “Parameterized Complexity for Practical Computing” (PCPC). Submitted 2017. Awarded 2018. (Retrieved from http://www.mrfellows.net/publications/)

FPT Workshop in Hobbit-Land, NEW ZEALAND, JULY 25. Parameterized Complexity for Practical Computing


The workshop will be held in Wellington, New Zealand on 25 July 2018. Register by sending an email to Catherine McCartin <zn.ca.yessam|nitraCcM.M.C#zn.ca.yessam|nitraCcM.M.C> or Frances Rosamond <on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf>. There is no fee for the workshop.
For more information see https://www.cmsc.nz/ftp-workshop/
The main objective of this workshop is to stimulate discussion on the useful purpose of FPT. Topics include turbo-charging heuristics, groovy FPT, reverse kernelization, extremal gradients. Discussion may include how parameterized complexity interacts with operations research, algorithms engineering, machine learning, artificial intelligence, and other areas.

Keynote speaker Mike Fellows will talk about Future Directions of the Field including some of the new directions for which he was awarded the Research Council of Norway Toppforsk Award or about 25 million (See www.mrfellows.net for a copy of the Toppforsk grant proposal).

The original book introducing parameterized complexity written by Downey and Fellows and published in 1999, envisioned the central goal of the program: “to serve the community”.

The main objective of this workshop is to stimulate discussion on outreach to other disciplines or subfields for useful purpose of FPT. To encourage wide participation and discussion, there will be no formal publication of workshop proceedings. Accepted papers will be posted online for the benefit of the workshop participants. Therefore, submission of preliminary work and papers being prepared for other major venues in the field are invited. Participation can be via Skype.

The workshop is informal and broad, and appropriate for PhD, PostDoc and Masters students as well as more senior academics.

Come early and attend CMSC 2018 (See www.cmsc.nz) to explore ways of sharing your research ideas broadly, to non-science audiences.

SOFJA KOVALEVSKAJA AWARD FOR YOUNG RESEARCH TALENTS: APPLICATION DEADLINE: 31 JULY 2018. The Alexander von Humboldt Foundation promotes outstanding talent and best conditions for research. Award winners receive up to €1.65 million each, enabling them to spend five years establishing and heading their own research groups at a research institution in Germany.

Junior academics of all disciplines from abroad with outstanding qualifications, who completed their doctorates within the last six years, are eligible to apply for the Sofja Kovalevskaja Award. Applications may also be submitted on completion of doctoral studies. Six awards are scheduled to be granted.

Visit www.humboldt-foundation.de/skp_en [2] for further information and a link to the online application package. If you have any questions about the Sofja Kovalevskaja Award or would
like individual guidance, please contact us at ed.hva|ofni#ed.hva|ofni.

VIDEO COMPETITION at IJCAI 2018, part of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence the premier international gathering of researchers in AI! Conference is in Stockholm July 9-19. Submission Deadline: May 5, 2018.

Competition description: A wide range of videos related to artificial intelligence can be submitted to the competition. The topic of a video might, for example, be a general or specific area of AI, the work of a particular researcher or group (yourselves or others), or a concrete application that depends on one or several AI techniques and that may be based entirely on software or partly on hardware. A video may concern work with different levels of maturity: you can introduce something new and interesting, describing known but ongoing research, or summarize a mature area or application, showing its impact on society. The intended audience of a video can be students learning about a topic in a classroom, researchers interested in learning more about subfields outside their own, the general public or the media.

DEADLINE EXTENDED to 30 March. ICGT 2018 - 10th International Colloqium on Graph Theory. ICGT is a conference created in the honour of C.Berge in 1976 and organized by the French community in Graph Theory every 4-5 years. This 10th edition will take place in Lyon from 9—13 July 2018.
mail: srnc.siril|8102tcgi#srnc.siril|8102tcgi

FPT Data Wrangling for Social Good (Wellington, New Zealand, July 25, 2018.
This FPT workshop immediately follows the Creative Mathematical Sciences Communication (CMSC 2018)
conference which will be held 21-23 July in Wellington. Come for both. For details contact organizers Catherine McCartin (zn.ca.yessam|nitraccm.m.c#zn.ca.yessam|nitraccm.m.c) and Peter Shaw (zn.ca.yessam|wahs.p#zn.ca.yessam|wahs.p), both at Massey Univ.

4th Creative Mathematical Sciences Communication conference (CMSC2018). Wellington, NZ, 21—23 July.
(Website is http://www.cmsc.nz). Join scientists, researchers, teachers, and artists in developing new ways of communicating mathematical and computational thinking. Stay for the FPT workshop immediately following.

The 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) will be part of ALGO 2018 and takes place 22-24 August 2018, in Helsinki, Finland.

IMPORTANT DATES: Note that the submission deadline is earlier this year. Title and short abstract
deadline: May 14, 23:59 AoE Full paper submission deadline: May 17, 23:59 AoE, Notification: July 1.

AWARDS: The Program Committee may award one or more Best Paper Award(s) and Best Student Paper
Award(s). Advise the Program Committee if you are submitting for a Best Student Paper Award. A student
is someone who has not received a PhD degree before the full paper submission deadline. A paper accepted to the conference is eligible for the Best Student Paper Award if either all its authors are students, or if there is one nonstudent co-author that confirms that a clear majority of conceptual work on the paper was done by the student co-author(s). It is expected that a student gives a presentation
at the conference.

NERODE PRIZE: An invited talk will be given by the 2018 EATCS-IPEC Nerode Prize winner.
TUTORIAL: Radu Curticapean will give an invited tutorial on Counting Problems in Parameterized Complexity.
PACE: There will be a session presenting the results of the 3rd Parameterized Algorithms and Computational Experiments Challenge (PACE 2018).

Congratulations to Matthias Mnich (Maastricht Univ, Universitat Bonn) who has received a personal grant of 578.000 Euro from DFG - Deutsche Forschungsgemeinschaft for his project Multivariate Algorithms for Scheduling Problems. Dr. Mnich is also directing Kernelization for Big Data, a DFG project.

The February FPT Newsletter is on the Newsletter page of this website. Editors Frances Rosamond (Univ Bergen) on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF and Valia Mitsou (Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv.
Announcements of awards and prizes, graduates, new jobs, and wonderful research. This newsletter features an article by PACE prize-winner Hisao Tamaki (Meiji University, JP) on Positive-instance
driven dynamic programming for treewidth, and an article on Erdos-Posa property of chordless cycles and its applications by Eun Jung Kim (Universite Paris-Dauphine) and O-joung Kwon (Incheon National University).

CALL FOR PAPERS: Parameterized Approximation Algorithms Workshop (PAAW) will take place
as a satellite workshop of ICALP 2018 in Prague, Czechia, on Monday July 9th 2018.

Topics of interest
- Parameterized approximation algorithms
- Lossy kernelization
- Parameterized inapproximability
- Fine-grained complexity of approximation
- Efficient polynomial-time approximation schemes

Contributed talks: If you would like to contribute a talk at this workshop, please send an email with subject "PAAW talk" to "feldmann.a.eatgmail.com" containing the title and an abstract, no later than Friday April 20th. Both talks on already published as well as yet unpublished results on the above listed
topics are welcome. There will not be any published proceedings for this workshop.


Important dates
Submission deadline: Friday April 20th, 2018
Notification: Friday May 18th, 2018
Early registration deadline: Thursday May 31, 2018
Workshop: Monday July 9th, 2018

Registration:To participate please register through the ICALP registration page.

Congratulations to Michael Fellows. We are pleased to announce that the Research Council of Norway has awarded a Toppforsk grant of about NOK 25 million for his project, Parameterized Complexity for Practical Computing. The funding scheme supports “scientific quality at the forefront of international research; boldness in scientific thinking and innovation”.

Congratulations to Faisal N. Abu-Khzam (Lebanese American Univ) for his project Efficient Algorithms for repairing quality in dynamic networks. The grant should cover 10 research visits, over two years, between LAU and University of Paris-Dauphine. His partners at Dauphine are Joyce El-Haddad and Cristina Bazgan. The project is funded by CEDRE, the Hubert Curien Partnership (PHC) Franco-Lebanese. It is implemented in France by the Ministry of Europe and Foreign Affairs (MEAE) and the Ministry of Higher Education, Research and Innovation (MESRI). In Lebanon, by the Ministry of Education and Higher Education.

PACE 2018: Coders— prizes & travel awards
Teams or individuals are invited to compete in PACE 2018, the Parameterized Algorithms and Computational Experiments Challenge. Investigate the practical applicability of algorithmic ideas of multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms.

Through the generous sponsorship of NETWORKS (http://thenetworkcenter.nl/ ), an NWO Gravitation project of the Univ of Amsterdam, Eindhoven Univ of Technology, Leiden Univ, and the Center for Mathematics and Computer Science (CWI), we announce 4000 euros that will be divided into prizes and travel awards for participants.

The challenge consists of three tracks on the Steiner Tree problem. Detailed instructions about the three tracks, their rules, the instance sets, and the input and output formats: Challenge https://pacechallenge.wordpress.com/pace-2018/

Register here: https://docs.google.com/forms/d/e/1FAIpQLScHH6lNpUYwLT6GDVMO9ik0s9iwhQTRbxnaJED1wdZOWBtJRg/viewform .
Download the public instances on the PACE challenge website and start your implementation.
Test your code on this platform now: https://pacechallenge.wordpress.com/2017/12/12/optil-io/ .

May 1st, 2018: Submission of final program
May 10th, 2018: Result are communicated to participants
August 20-24 2018: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki

Congratulations to Rod Downey (Victoria University of Wellington, NZ) who will give the Gödel Lecture at The Logic Colloquium 2018, the annual European summer meeting of the Association of Symbolic Logic (ASL), that will be held during July 23—28, 2018 at the University of Udine, Italy.

Congratulations to Rod also for winning the 2016 Shoenfield Prize for his book with Denis Hirschfeldt: Algorithmic randomness and complexity (Theory and Applications of Computability, Springer-Verlage New York, 2010).

CALL FOR NOMINATIONS — EATCS-IPEC Nerode Prize — Due March 1, 2018
The Nerode Prize is an annual prize for outstanding work in multivariate algorithmics and parameterized complexity, published in a recognized journal by an individual or a team of authors. Please think of any past work in this area that deserves to be recognized by this prize, and send your nominations.

Nominations should contain a brief summary of the technical content of the 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". Deadline is March 1, 2018.

COMMITTEE: Daniel Marx <uh.emb.sc|xramd#uh.emb.sc|xramd> Award Committee Chair (Hungarian Academy of Sciences),
Jianer Chen <ude.umat.esc|nehc#ude.umat.esc|nehc> (Texas A&M), Hans L. Bodlaender <ln.uu|rednealdob.l.h#ln.uu|rednealdob.l.h> (Utrecht University).

NEWS-Now send your graduation information, grant, new job, book, workshop, submissions, announcements or other news to be included in the next FPT Newsletter. Send to Editors Frances Rosamond on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF or Valia Mitsou rf.srnc.siril|uostim#rf.srnc.siril|uostim.

Congratulations to Anil Nerode on his 85th birthday, which is being celebrated at the Symposium on Logical Foundations Of Computer Science (LFCS) in Deerfield Beach, Florida. Anil especially invited Mike Fellows and Frances Rosamond (Anil was Fran’s advisor at Cornell), and Mike will give the opening plenary on “The Evolution and Future of Parameterized Complexity”.

Jianer Chen writes: Submission for FAW 2018 is December 29, 2017. The EasyChair submission server is available at
The 12th International Frontiers of Algorithmics Workshop will be held on May 8-10, 2018 at Guangzhou, Guangdong Province, China (www.itcs.shufe.edu.cn/FAW2018/contact.html.)

Online herehttp://events.iitgn.ac.in/2017/comsoc/

Where the lectures are being broadcast live.

We started a day late because Edith's flight was re-routed, so only the
introductory lectures have finished so far, and about 10+ hours are coming
up still. IIT-Gandhinagar with Edith Elkind and Neeldhara Misra.

Lorentz Center workshop on Fixed-Parameter Computational Geometry II, taking place May 14-18, 2018. Contact organizers for invitation: Mark de Berg, Hans Bodlaender, Benjamin Burton and Christian Knauer.

EATCS Deadlines for award nominations:
EATCS Award 2018 <http://eatcs.org/index.php/eatcs-award> : December 31, 2017
Presburger Award 2018 <http://eatcs.org/index.php/presburger> : December 31, 2017
Eatcs Fellows 2018 <http://eatcs.org/index.php/eatcs-fellows> : December 31, 2017
EATCS Distinguished Dissertation Award 2017 <http://eatcs.org/index.php/dissertation-award> : December 31, 2017

More information can be found at http://www.eatcs.org/index.php/eatcs-awards


COMPUTATIONAL SOCIAL CHOICE course at the Indian Institute of Technology Gandhinagar from 4—8 December 2017 with speaker Prof. Edith Elkind (Oxford). Contact Neeldhara Misra.

Announcing PACE 2018, the Parameterized Algorithms and Computational Experiments Challenge. PACE 2016 and PACE 2017 have been hugely successful (official reports are here https://pacechallenge.files.wordpress.com/2016/06/lipics-ipec-2017-30.pdf). The goal of PACE is to investigate the practical applicability of algorithmic ideas studied and developed in multivariate, fine-grained, parameterized, or fixed-parameter tractable algorithms. The challenge this year consists of three tracks on the Steiner Tree problem.

Given an undirected edge-weighted graph G and a subset T (terminals) of its vertices, find a subgraph of G spanning T with the smallest total edge-weight.

TRACK 1 (Exact with few terminals)

You have 30 minutes per instance. Win by solving more instances than the other participants.
In all the instances, there are only a few terminals.

TRACK 2 (Exact with low treewidth)

You have 30 minutes per instance. Win by solving more instances than the other participants.
In this track only, the instances come with a tree decomposition and the treewidth is low.

TRACK 3 (Heuristic)

Here the instances are significantly larger, have many terminals, and high treewidth, but you are not expected to find an optimum solution. You still have 30 minutes per instance. Win by finding Steiner trees of smaller weight than the other participants. We will rank by average approximation ratio.

Detailed instructions about the three tracks, their rules, the instance sets, and the input and output formats: https://pacechallenge.wordpress.com/pace-2018/

You can already register for the challenge: https://docs.google.com/forms/d/e/1FAIpQLScHH6lNpUYwLT6GDVMO9ik0s9iwhQTRbxnaJED1wdZOWBtJRg/viewform .
You can also download the public instances on the PACE challenge website and start your implementation. We cooperate with the platform optil.io (https://www.optil.io/optilion/). In a short while, you will be able to run your code on this platform. We will let you know when it is ready and how to proceed.


November 14th, 2017: Announcement of the challenge
May 1st, 2018: Submission of final program
May 10th, 2018: Result are communicated to participants
August 20-24 2018: Award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki



Track 1, 2, 3:
- Édouard Bonnet (Middlesex University, London)
- Florian Sikora (Paris-Dauphine University)


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

Best of luck with your code!

The PACE Committees


CONGRATULATIONS, Tim Bell!! The 2018 SIGCSE Award for Outstanding Contribution to Computer Science Education has been awarded to Professor Tim Bell, University of Canterbury, New Zealand. Tim and Mike Fellows and Ian Witten authored "Computer Science Unplugged" (csunplugged.org). Computational thinking has been infused into schools around the world as a result. Tim is a Keynote Speaker at the Creative Mathematical Sciences Communication Conference (CMSC4) in New Zealand 21-24 July 2018. All welcome. There will be an FPT Workshop adjacent to CMSC4. See cmsc.nz

CONGRATULATIONS!! There are 15 Parameterized Complexity papers at SODA 2018. Eight of them are from the University of Bergen.

PARAMETERIZED COMPLEXITY WEEK AT IMSC, CHENNAI, October 24—26. In honor of wedding of MSR. Organized by Venkatesh Raman. See t www.imsc.res.in/~vraman/pcweek.pdf
schedule for PC Week

If you are looking for a position in the UK, then look on the page www.jobs.ac.uk. The UK is attending to another RQF (Research Quality Framework) and they are looking to hire researchers with high-profile, quality papers, ability to recruit students, grants, and impact—it helps to have experience in programming competitions (PACE, see https://pacechallenge.wordpress.com) and other outreach.

Congratulations to Marc Roth (Saarland Univ) who was awarded the 2017 ESA Best Student Paper Award for Counting restricted homomorphisms via Möbius inversion over matroid lattices.

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: Expected Outcomes and Manipulations in Online Fair Division, which won Best Paper Prize at the 40th German Conference on Artificial Intelligence (KI'2017). This is the second time Martin has won a best paper award during his PhD.

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