FPT News: The Parameterized Complexity Newsletter

HOW TO RECEIVE THE NEWSLETTER BY EMAIL: sign onto Frances Rosamond’s mailing list (under the heading “Subscribing to Fptnews”) here:


The current setting is that 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.

Co-editors: Valia Mitsou (LIRIS, CNRS Univ Lyon 1) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and and Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF).
Nominations are due for the 2017 EATCS-IPEC NERODE PRIZE on 01 March. Email David Eppstein, Chair of Nominations Committee: ude.icu|nietsppe#ude.icu|nietsppe. The newsletter 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!

Co-editors: Valia Mitsou Hungarian Academy of Sciences (uh.ikatzs|uostimv#uh.ikatzs|uostimv) and Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF).
This newsletter contains 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.

Frances Rosamond, Editor, University of Bergen. on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF
Bart Jansen provides an insightful graph showing the dynamic expansion of the field. It may be useful in grant applications. Featured are two excellent articles, Graver basis optimization methods: n-Fold Integer Programming for FPT by Martin Koutecky, and Fixed-Parameter Algorithms in Operations Research: Opportunities and Challenges by Rene van Bevern. Sign up for the very first Parameterized Algorithms and Computational Experiments Challenge (PACE) (https://pacechallenge.wordpress.com). We hope the libraries developed will be useful for Masters projects. Let me know if you would like to join the PACE discussion on SLACK.Winners will be announced at the 11th IPEC in Aarhus in August (note that ALGO has changed from its usual Sept date).
Join the 3rd Creative Mathematical Sciences Communication conference from 4 - 7 October 2016, Luebeck, Germany ( http://www.tcs.uni-luebeck.de/cmsc). Hang out with interesting people who are exploring new ways of popularizing the rich mathematics underlying computer science including outdoor activities, art, dance, drama and all forms of storytelling. This is Computer Science Unplugged! (www.csunplugged.org) and Beyond.

This 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

In this newsletter we celebrate many awards and honours and new PhDs and new positions. Herein is an article on Parameterized Streaming by Rajesh Chitnis. There is a review of the new Parameterized Algorithms book, and announcements of conferences and workshops. Enjoy.

In this newsletter we celebrate awards and honors to Mike Fellows, Hans Bodlaender, and Danny Hermelin who accepted the Nerode Prize at IPEC/ESA in Wroclaw, and to award and prize winners Jesper Nederlof and Bart Jansen who both won VENI awards, to Serge Gaspers for an ARC Future Fellowship, Henning Fernau for a DFG, Danny Hermelin for Israel Science Foundation, and Michal Pilipczuk for Polish NSC. ** Herein is Parameterized Logarithmic Space and Fine-Structure of FPT by Moritz Muller. There are congratulations to graduates and new positions, announcements of conferences and future FPT-ers. Enjoy.

In this newsletter we mourn the passing of Prof Ed Blum, friend and founder/editor of JCSS. We celebrate awards and honors to Mike Fellows, Toby Walsh, Hans Bodlaender, Rodney Downey, Danny Hermelin, Lance Fortnow, Rahul Santhanam, Katrin Casel, Gabor Erdelyi, Fabrizio Grandoni, Mattias Mnich, Michal Pilipczuk, and Piotr Faliszewski. Herein are New Ideas by Mike Fellows, and new results on Outer-planar Diameter Improvement by Nathann Cohen, Eun Jung Kim, Daniel Goncalves, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, and Mathias Weller. There are congratulations to graduates and new positions, announcements of conferences and Algorithmic special issue. Enjoy.

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.

  • 2013 September Congratulations to award winners and graduates. This newsletter focuses on psychology and cognitive science.

We have an article about Bayesian Models by Johan Kwisthout and Iris van Rooij (Radboud U.), and an article by Tarek Besold (U. Osnabrueck) and Robert Robere (U. Toronto). Johan, Iris and Mark Blokpoel (Radboud) and Todd Wareham (Memorial U. Newfoundland) gave tutorials about using parameterized complexity analysis in cognitive science at CogSci2013.

  • 2013 April Inside are many announcements of grants, awards,and graduations. There is new citation statistics information from Mike Fellows, Charles Darwin Univ; research on Protein, Hitting Set and Linear Algebra by Peter Damaschke and Leonid Molokov, Chalmers Univ.; conferences and more!

Parameterized Complexity has a BLOG. Please join the Blog Group by signing up at http://www.fptnews.org/contribute. The BLOG can be accessed at http://www.fptnews.org. Any questions, contact Neeldhara Misra, IIS Bangalore at moc.arahdleen|liam#moc.arahdleen|liam.

The Parameterized Complexity Newsletter for August 2012 is attached. Inside are announcements of approximately 5 million Euros in new research funding, won by Saket Saurabh, Stefan Kratsch, Gregory Gutin, Xiuzhen Huang, Jiong Guo, Tobias Friedrich. The Best Paper Award at CiE was awarded to Sepp Hartung and Andre Nichterlein, who summarize their award-winning paper in an article. The Best Paper Award from COCOON was awarded to a research team from Bergen, Remy Belmonte, Pinar Heggernes, Piom van 't Hof, Reza Saei. Johan Kwisthout and Iris van Rooij were invited, among 11 other authors, to
submit a reworked version of their ICCM'12 conference paper to the "Best of ICCM'12" special issue of Cognitive Systems Research. Mike Fellows writes about APAC. There are workshops at AMS in San Diego, in Oman, and in Japan. Congratulations to many who have found permanent positions.

The 2012 May Newsletter announces new research results by Andy Drucker on the AND Conjecture. It offers Congratulations to Yiannis Koutis (Univ. Puerto Rico) who was awarded a prestigious NSF CAREER AWARD, and other awards with total about USD600,000. There are two excellent articles. Vlad Estivill-Castro and Mahdi Parsa (Griffith Univ.) write about game theory. U´everton dos Santos Souza, F´abio Protti and Maise Dantas da Silva (Federal University of Rio de Janeiro) write about answer set programming and bounded treewidth. There are announcements and the IPEC Call for Papers.

The November newsletter: Congratulations to Serge Gaspers who was awarded the UNSW Vice-Chancellor Award, and also the Australian Research Council Discovery Early Career Researcher Award (DECRA), and 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, and to Yoichi Iwata for winning an IPEC 2011 Excellent Student Paper Award. Articles: Some Notes on the Performance of the Field by Michael Fellows; The AND-conjecture may be necessary by Magnus Wahlstr¨om; Hierarchies of Inefficient Kernelizabilty by Danny Hermelin, and Co-nondeterministic Compositions by Stefan Kratsch. New blog column The Theory Blogosphere by Neeldhara Misra, Column Editor. Report and Open Problems from WorKer 2011 by Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Table of Races, announcements, workshops, Tutorial at CATS, new positions.

The July 2011 FPT Newsletter congratulates D\'aniel Marx on a 1.15M EUR award, Cristina Bazgan on an IUF, and Iyad Kanj on a {\it Spirit of Inquiry Award}. Breakthrough results of Stefan Kratsch and Magnus Wahlstr\"{o}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.

The April 2011 FPT Newsletter celebrates the Chennai IPEC 2010 and presents the CFP for 2011 IPEC joint with ALGO. It introduces the new ACM SIGACT Chapter in Shanghai. Key article is "Parameterized Complexity for Answer Set Programming" by Michael Morak, Nysret Musliu, Andreas Pfandler, Reinhard Pichler, Stefan RÄummele, and Stefan Woltran.

The November 2010 FPT Newsletter celebrates over 8 million euro in research grants, awards and prizes to the PC Community this year. Key article: Finding Topological Subgraphs is FPT (Grohe, Kawarabayashi, Marx, Wollan).

The June 2010 FPT Newsletter announces a new online compendium by A. Perez. Key articles: Polynomial Lower Bounds for Kernels (Holger Dell), and Protein Structure Prediction (Xiuzhen Huang).

This fully-packed Newsletter features articles by Georgia Kaouri, Michael Lampis and Valia Mitsou describing new directions in treewidth, continuing work reported at ISAAC, and an article by Serge Gaspers on new uses of measure and conquer for parameterized branching algorithms, and a bit of History and ILP by D. Marx. We have a report on the marvelous Corsica AGAPE Workshop by Anke Truss and Mathias Weller, and a report on Bangalore Meeting by Vankatesh Raman, and another New Ideas column by Mike Fellows. Great picture of Daniel Laksthanov winning $100.

The May 2008 FPT Newsletter reports on the long-outstanding parameterized Directed Feedback Vertex Set that has been solved and the paper by Chen, Liu, Lu, O’Sullivan, and Razgon appears at STOC’08. Directed “Spanning Tree with Constraints” problems, such as Directed Maximum Leaf or Directed Spanning Tree, have solutions based on the methodology of reducing to bounded treewidth. The paper, ‘Minimum-Leaf Outbranching’, parameterized by the number of non-leaf vertices by Gutin, Razgon, and Kim appeared at AAIM’08 , and “Parameterized Algorithms for Directed Maximum Leaf Problems” by Alon, Fomin, Gutin, Krivelevich and Saurabh was presented at

Given a 2-CNF formula, is it possible to remove at most k clauses so that the resulting 2-CNF formula is satisfiable? This problem known as ‘Almost-2-SAT’, ‘Allbut- k-2-SAT’, ‘Minimum 2-CNF-Deletion’, or ‘2-SATDeletion’, now has an O(15k) algorithm due to Razgon
and O’Sullivan. The extended abstract appears at ICALP’08. The full version of the algorithm is available
at http://arxiv.org/abs/0801.1300. More on this and other results are in the Newsletter.

The May 2008 FPT Newsletter also has an article on "k-Local Search" by Daniel Marx and an article "Treewidth: History, Applications, Algorithms, and
Programs" by Hans Bodlaender.

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