HOW TO RECEIVE THE NEWSLETTER BY EMAIL: sign onto Frances Rosamond’s mailing list (under the heading “Subscribing to Fptnews”) here:
[http://mrfellows.net/mailman/listinfo/fptnews_mrfellows.net]
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.
Send us news directly to our emails.
Feel free to add your listing to the JOBS page on the wiki. Also, update Wikipedia with your new results.
Add to the "FPT Complexity" Youtube Channel. Follow fb page \url{@MikeFellowsFPT}.
Wishing you all the best from Frances Rosamond (on.biu|dnomasor.secnarf#on.biu|dnomasor.secnarf), Valia Mitsou (rf.firi|uostimv#rf.firi|uostimv) and Benjamin Bergougnoux (lp.ude.wumim|xuonguogreb.nimajneb#lp.ude.wumim|xuonguogreb.nimajneb) and the News Team.
2022 April, Vol.18, No. 1
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergen on.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb and the News Team.
It is with the deepest sadness that this newsletter reports the death of three esteemed friends: our beloved Rolf Niedermeier, Gerhard Woeginger, and Benny Chor. Their passing is a huge loss to many of us personally as well as to us all professionally.
Congratulations is extended to all for many awards and prizes, graduates, new jobs, and research. Enjoy two research articles: Parameterized Approximations via Randomized Branching by Ariel Kulik and Hadas Shachnai and Revising Johnson's table for the 21st century by Ana Silva, Celina de Figueiredo, Alexsander de Melo. We also announce the retirement of Michael Fellows, who turns 70 in June, and the retirement of your Parameterized Complexity Newsletter Editor, Frances Rosamond, who has truly enjoyed serving the PC Community with the Newsletter, this website, the fb page, the IPEC Annual Publicity Report, and many other opportunities.
2021 December, Vol.17, No. 3
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb and the News Team.
Congratulations to all for many awards and prizes including IPEC2021 awards, graduates, new jobs, and research. Read two research articles: Clique-Width of Point Confgurations by Petr Hlinený and Abhisekh Sankaran, and Tree-width Dichtomy by Vadim Lozin and Igor Razgon. Please add to the FPT Complexity Youtube Channel. Update Wikipedia with your new results. Follow fb page @MikeFellowsFPT. Send us news via Google form https://forms.gle/sfZNzKFsbfqSywgy7 or directly to
our emails. Please keep well. Take good care of yourselves. Enjoy a happy holiday season.
2021 July, Vol.17, No. 2
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb and the News Team.
See a report on grants received for PC projects: the French National Research Agency has awarded four Young Researcher awards for projects related to Parameterized Complexity. The Norwegian Research Council and UK EPSRC have given awards.
Read three research articles: "Constant Approximating k-Clique is W[1]-hard" by Bingkai Lin, "Vertex Deletion Parameterized
by Elimination Distance and Even Less" by Michal Wlodarczyk, and "Twin-width" by Édouard Bonnet. Note that Edouard will be giving an invited tutorial on Twin-Width at IPEC.
Congratulations to Neeldhara Misra, selected as an Associate of the Indian Academy of Sciences.
Congratulations to PhD graduates, winners of Best Paper and Best Student Paper awards, and more.
Please add to the FPT Complexity Youtube Channel. Update Wikipedia with your new results. Follow fb page MikeFellowsFPT. Add your listing to the Jobs page on the wiki. Send us news or add your news directly to the PC wiki (www.fpt.wikidot.com).
- 2021 March, Vol.17, No. 1
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb and the News Team.
Welcome to the Parameterized Complexity Newsletter.
Deep condolences are sent to the family of Dieter Kratsch and we add our own fond memories to those expressed in the Memoriam by Hans Bodlaender and Haiko Müller.
The newsletter sends congratulations to all for many awards and prizes, graduates, new jobs, research and family matters.
There are two research articles:
Parameterized Algorithmics: Experimental Research by Gregory Gutin, Daniel Karapetyan, and Decreasing Graph Transversals via Edge Contractions by Paloma Lima.
Please add to the FPT Complexity Youtube Channel by sending to Jungho Ahn at Kaist, Korea.
Update Wikipedia with your new results. Follow fb page @MikeFellowsFPT.
Send us news via Google form https://forms.gle/sfZNzKFsbfqSywgy7 or directly to our emails. The next newsletter will be sent in August.
Please keep well. Take good care of yourselves. Wishing you all the best.
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb and the News Team.
Welcome to the Parameterized Complexity Newsletter.
Congratulations to all for many awards and prizes, graduates, new jobs, and wonderful research. Read two research articles: Parameterized Algorithmics for Temporal Graph Problems by Hendrik Molter (TU Berlin) and Phylogenetics and parameterized complexity by Steven Kelk (Maastricht Univ). Please update Wikipedia with your results. Add your presentations to the FPT Complexity Youtube. Contact Jungho Ahn (Kaist) rk.ca.tsiak|nhaohgnuj#rk.ca.tsiak|nhaohgnuj for assistance. Send us news via our new Google form (https://forms.gle/sfZNzKFsbfqSywgy7) or directly to our emails. We love hearing from you.
- 2020 March, Vol.16, No. 1
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb. Welcome to the Parameterized Complexity Newsletter.
Congratulations to all for many awards and prizes, graduates, new jobs, and wonderful research. This issue announces an FPT Youtube Channel. Conferences are being postponed or cancelled due to the virus. This newsletter features an article on Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs by Karolina Okrasa and Paweł Rzążewski (Warsaw University of Technology & University of Warsaw), and an article onThe Complexity Landscape of Decompositional Parameters for ILP by Robert Ganian (Vienna University of Technology) and Sebastian Ordyniak (University of Sheffield).
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF), Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv and Benjamin Bergougnoux University of Bergenon.biu|xuonguogreb.nimajneb#on.biu|xuonguogreb.nimajneb. Welcome to the Parameterized Complexity Newsletter.
Congratulations to all for many awards and prizes, graduates, new jobs, and wonderful research. This issue announces PACE 2019 winners and includes a PC history by Mike Fellows. Sign the doodle to update Wikipedia. Follow fb page @MikeFellowsFPT. Welcome to a new co-editor, Benjamin Bergougnoux, post-doc with Jan Arne Telle, Univ. Bergen, and welcome to a news Reporter, Emmanuel Sam, PhD student with Mike Fellows, Univ. Bergen.
- 2019 May, Vol 15, no 1
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF) and Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv. Welcome to the Parameterized Complexity Newsletter.
Congratulations to all for many awards and prizes, graduates, new jobs, and wonderful research. Read about the Polynomial Planar Directed Grid Theorem by Meike Hatze et al. and the article Fine-Grained Complexity of
Program Verification Tasks by Peter Chini et al. Compete in the new Parameterized Complexity Essay Contest.
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF) and Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv. Welcome to the Parameterized Complexity Newsletter. Congratulations to all for many awards and prizes, graduates, new jobs, and wonderful research. Read Programming Toolbox: Part II by Martin Koutecky. by and the PACE report by Edouard Bonnet and Florian Sikora. Compete in the new Parameterized Complexity Essay Contest. Follow fb page @MikeFellowsFPT.
- 2018 June, Vol 14, no 2
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF) and Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv.
Welcome to the Parameterized Complexity Newsletter. This edition celebrates award winners and graduates. It features two outstanding articles. "Programming Toolbox: Part I" is by Martin Koutecky. "Part II" will follow in the Fall newsletter. Also featured is "On the Parameterized Complexity of Approximating Dominating Set" by Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi.
Please visit the wiki: www.fpt.wikidot.com [1] and follow the facebook page: @MikeFellowsFPT. Enjoy!
Editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF) and Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv. Inside this newsletter you will find announcements of many prizes, new PhDs, and moves to new positions. 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).
Co-editors: Frances Rosamond University of Bergen (on.biu|dnomasoR.secnarF#on.biu|dnomasoR.secnarF) and Valia Mitsou (IRIF, Univ Paris Diderot) rf.srnc.siril|uostimv#rf.srnc.siril|uostimv. Inside this newsletter you will find announcements of many prizes, new PhDs, and moves to new positions. There were ten awards given at ALGO this year. Eight were related to Parameterized Complexity. Good work, everyone! There is an article by IPEC Best Paper award winners, "A Fixed-Parameter Perspective on #BIS" by Radu Curticapean (MTA SZTAKI), Holger Dell (MMCI), Fedor Fomin (Univ Bergen), Leslie Ann Goldberg (Univ Oxford), and John Lapinskas (Univ Oxford). There is an article by IPEC Best Student Paper award winners Bart Jansen and Astrid Pieterse (Eindhoven Univ of Technology, NL)"Optimal Data Reduction for Graph Color-ing Using Low-Degree Polynomials". Enjoy! We especially thank Roohani Sharma, PhD candidate at University of Bergen for her help with the newsletter.
- 2017 June, Vol 13, no 2
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). 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!
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.
- 2016 May, Vol 12, no 1
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
- 2015 August, Vol 11, no 1
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.
- 2014 June, Vol 10, no 1
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.
- 2012 August
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.
- 2012 May
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.
- 2011 November
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.
- 2011 July
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.
- 2011 April
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.
- 2010 November
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).
- 2010 June
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).
- 2009 September
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.
- 2009 June
- 2009 April
- 2008 May
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
ICALP’07.
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.
- 2006 November
- 2006 May
- 2005 May