FPT papers in conferences

The purpose of this page is to give pointers to FPT-related papers that have appeared in recent conferences, to make it easier to keep track of all the new results. The papers are listed per conference, and for each conference it is listed how many of the total submissions were related to FPT.

2017

SODA 2018, New Orleans, USA (15 FPT-related papers out of 180)

  • Ken-Ichi Kawarabayashi and Benjamin Rossman. A Polynomial Excluded-Minor Approximation of Treedepth
  • Ramanujan M. S., Daniel Lokshtanov and Saket Saurabh. When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices
  • Lin Chen and Dániel Marx. Covering a tree with rooted subtrees — parameterized and approximation algorithms.
  • Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma
  • Nikola Yolov. Minor-matching hypertree width
  • Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Covering small independent sets and separators with applications to parameterized algorithms
  • Anupam Gupta, Euiwoong Lee and Jason Li. An FPT Algorithm Beating 2-Approximation for k-Cut
  • Daniel Lokshtanov and Amer Mouawad. The complexity of independent set reconfiguration on bipartite graphs
  • Mateus De Oliveira Oliveira. A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
  • David Coudert, Guillaume Ducoffe and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
  • Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stephan Thomasse and Meirav Zehavi. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems
  • Eun Jung Kim and O-Joung Kwon. Erdos-Posa property of chordless cycles and its applications
  • Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth
  • Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, Ramanujan M. S., Saket Saurabh and Meirav Zehavi. Parameterized Algorithms for Survivable Network Design with Uniform Demands
  • Daniel Lokshtanov, Ivan Mihajlin, Ramamohan Paturi and Pavel Pudlák. Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth

FOCS 2017, Berkeley, USA (1 FPT-related paper out of 90)

  • Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

ESA 2017, Vienna, Austria (13 FPT-related papers out of 69)

  • Dániel Marx and Marcin Pilipczuk. Subexponential parameterized algorithms for graphs of polynomial growth
  • Marthe Bonamy, Lukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała and Marcin Wrochna. Tight lower bounds for the complexity of multicoloring
  • Hisao Tamaki. Positive-instance driven dynamic programming for treewidth
  • Marek Cygan, Lukasz Kowalik and Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decompositions
  • Kristóf Bérczi and Yusuke Kobayashi. The Directed Disjoint Shortest Paths Problem
  • Ramanujan M. S., Daniel Lokshtanov and Saket Saurabh. A Linear-Time Parameterized Algorithm for Node Unique Label Cover
  • Aissi Hassene, A. Ridha Mahjoub and R. Ravi. Randomized Contractions for Multiobjective Minimum Cuts
  • Ramanujan M. S., Gregory Gutin, Felix Reidl and Magnus Wahström. Path-ontractions, edge deletions and connectivity preservation
  • Prakash Saivasan, Roland Meyer, Peter Chini, Andreas Krebs and Jonathan Kolberg. On the Complexity of Bounded Context Switching
  • Katherine Edwards, Irene Muzi and Paul Wollan. Half-integral linkages in highly connected directed graphs
  • Dušan Knop, Martin Koutecky and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications
  • Marc Roth. Counting restricted homomorphisms via Möbius inversion over matroid lattices
  • Jocelyn Thiebaut, Stéphane Bessy and Marin Bougeret. Triangle packing in (sparse) tournaments: approximation and kernelization.

MFCS 2017, Aalborg, Denmark (16 FPT-related papers out of 80)

  • Ivan Bliznets and Nikolai Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
  • Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh and Sudeshna Kolay. Kernelization of the Subset General Position problem in Geometry
  • Fedor Fomin, Petr Golovach and Dimitrios Thilikos. Structured Connectivity Augmentation
  • Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set
  • Michał Pilipczuk, Erik Jan van Leeuwen and Andreas Wiese. Approximation and parameterized algorithms for geometric independent set with shrinking
  • Sudeshna Kolay, Fahad Panolan and Saket Saurabh. Communication Complexity of Pairs of Graph Families with Applications
  • George Mertzios, André Nichterlein and Rolf Niedermeier. The Power of Data Reduction for Matching
  • Chloe Ching-Yun Hsu and Chris Umans. On Multidimensional and Monotone k-SUM
  • Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
  • Palash Dey and Neeldhara Misra. On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
  • Akanksha Agrawal. Fine-grained Complexity of Rainbow Coloring and its Variants
  • Shaohua Li, Qilong Feng, Xiangzhong Meng and Jianxin Wang. An Improved Fixed-parameterized Algorithm for Parameterized Flip Distance Problem
  • Ramanujan M. S., Danny Hermelin and Eduard Eiben. Lossy Kernels for Hitting Subgraphs
  • Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching
  • Alexandre Blanché, Konrad Kazimierz Dabrowski, Matthew Johnson, Vadim Lozin, Daniel Paulusma and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation
  • Irene Muzi, Michael P. O'Brien, Felix Reidl and Blair D. Sullivan. Being even slightly shallow makes life hard

AI 2017, Melbourne, Australia (? FPT-related papers out of ?)

  • Wanru Gao, Tobias Friedrich, Timo Tzing, and Frank Local Neumann. Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization.

WG 2017, Heeze, Netherlands (8 FPT-related papers out of 31)

  • Steven Chaplick, Martin Topfer, Jan Vobornik and Peter Zeman. On H-Topological Intersection Graphs
  • O-Joung Kwon, Michal Pilipczuk and Sebastian Siebertz. On Low Rank-Width Colorings
  • Akanksha Agrawal, Daniel Lokshtanov and Amer Mouawad. Critical node cut parameterized by treewidth and solution size is W[1]-hard
  • Yijia Chen, Martin Grohe and Bingkai Lin. The Hardness of Embedding Grids and Walls
  • Oliver Schaudt and Fabian Senger. The Parameterized Complexity of the Equidomination Problem
  • Pallavi Jain, Jayakrishnan M, Fahad Panolan and Abhishek Sahu. Mixed Dominating Set: A Parameterized Perspective
  • Till Fluschnik, Meike Hatzel, Steffen Härtlein, Hendrik Molter and Henning Seidler. The Minimum Shared Edges Problem on Grid-like Graphs
  • Dusan Knop, Martin Koutecky, Tomas Masarik and Tomas Toufar. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

CIAC 2017, Athens, Greece (7 FPT-related papers out of 36)

  • Structural Parameters for Scheduling with Assignment Restrictions. Klaus Jansen, Marten Maack and Roberto Solis-Oba
  • On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. Sándor Kisfaludi-Bak and Tom C. van der Zanden
  • Lars Jaffke and Bart M. P. Jansen. Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
  • Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar Tale. Paths to Trees and Cacti
  • Hans L. Bodlaender and Tom C. van der Zanden. Improved Lower Bounds for Graph Embedding Problems
  • Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier and Manuel Sorge. Assessing the Computational Complexity of Multi-Layer Subgraph Detection
  • Parameterized Resiliency Problems via Integer Linear Programming. Jason Crampton, Gregory Gutin, Martin Koutecký and Rémi Watrigant

STOC 2017, Montreal, Canada (3 FPT-related papers out of 103)

  • Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Ramanujan Sridharan. Lossy Kernelization
  • Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas. Faster Space-Efficient Algorithms for Subset Sum and k-Sum
  • Radu Curticapean, Holger Dell, Daniel Marx. Homomorphisms are a good basis for counting small subgraphs

CSR 2017, Kazan, Russia (1 FPT-related paper out of 22)

  • Cornelius Brand and Marc Roth. Parameterized counting of trees, forests and matroid bases

STACS 2017, Hannover, Germany (11 FPT-related papers out of 54)

  • Tillmann Miltzow, Édouard Bonnet and Paweł Rzążewski. Complexity of Token Swapping and its Variants
  • Zdenek Dvorak and Bernard Lidicky. Independent sets near the lower bound in bounded degree graphs
  • Mikołaj Bojańczyk and Michał Pilipczuk. Optimizing tree decompositions in MSO
  • Martin Koutecky, Dušan Knop and Matthias Mnich. Voting and Bribing in Single-Exponential Time
  • Fedor Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh and Meirav Zehavi. Matrix Rigidity: Matrix Theory from the Viewpoint of Parameterized Complexity
  • Robert Ganian, Ramanujan M. S. and Stefan Szeider. Combining Treewidth and Backdoors for CSP
  • Lin Chen, Dániel Marx, Deshi Ye and Guochuan Zhang. Parameterized and approximation results for scheduling with a low rank processing time matrix
  • Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Split Contraction: The Untold Story
  • Radu Curticapean, Holger Dell and Marc Roth. Counting edge-injective homomorphisms and matchings on restricted graph classes
  • Benjamin Burton, Sergio Cabello, Stefan Kratsch and William Pettersson. The parameterized complexity of finding a 2-sphere in a simplicial complex
  • Vikraman Arvind, Johannes Koebler, Sebastian Kuhnert and Jacobo Toran. Parameterized complexity of small weight automorphisms

WALCOM 2017, Hsinchu, Taiwan (3 FPT-related papers out of 37)

  • Kensuke Imanishi. An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances
  • Dong Yeup Kang, O-Joung Kwon, Torstein Stromme and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs
  • Miroslaw Kowaluk and Andrzej Lingas. A fast deterministic detection of small pattern graphs in graphs without large cliques

SODA 2017, Barcelona, Spain (14 FPT-related papers out of 182)

  • Klaus Jansen and Kim-Manuel Klein. About the Structure of the Integer Cone and its Application to Bin Packing.
  • Yixin Cao and R. B. Sandeep. Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
  • Bart M. P. Jansen and Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion
  • Karl Bringmann. Improved pseudopolynomial time algorithms for Subset Sum
  • Konstantinos Koiliaris and Chao Xu. A Faster Pseudopolynomial Time Algorithm for Subset Sum
  • Xue Chen and Yuan Zhou. Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints
  • Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Spanning Circuits in Regular Matroids
  • Fedor Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
  • Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova and Ryan Williams. Completeness and improved algorithms for first-order properties on sparse structures
  • Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams and Huacheng Yu. Beating Brute Force for Systems of Polynomial Equations over Finite Fields
  • Stephan Kreutzer, Roman Rabinovich and Sebastian Siebertz. Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
  • Mark Braverman, Young Kun Ko, Aviad Rubinstein and Omri Weinstein. ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
  • Magnus Wahlström. LP-branching algorithms based on biased graphs
  • Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, Meirav Zehavi and Daniel Lokshtanov. Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

2016

FSTTCS 2016, Chennai, India (4 FPT-related papers out of 44)

  • Fahad Panolan and Meirav Zehavi. Parameterized Algorithms for List K-Cycle
  • R Krithika, Pranabendu Misra, Ashutosh Rai and Prafullkumar Tale. Lossy Kernels for Graph Contraction Problems
  • Ashutosh Rai and Ramanujan M. S. Strong Parameterized Deletion: Bipartite Graphs
  • Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments

ASONAM 2016, San Francisco, USA (1 FPT-related paper out of 43)

GD 2016, Athens, Greece (1 FPT-related paper out of 50)

  • René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier and Manuel Sorge. Twins in Subdivision Drawings of Hypergraphs

FOCS 2016, New Brunswick, USA, (2 FPT-related papers out of 85)

  • Fedor V. Fomin, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
  • Yijia Chen, Bingkai Lin. The Constant Inapproximability of the Parameterized Dominating Set Problem

ECAI 2016, The Hague, Netherlands (3 FPT-related papers out of 298)

  • René van Bevern, Christian Komusiewicz, Hendrik Molter, Rolf Niedermeier, Manuel Sorge, Toby Walsh: h-Index Manipulation by Undoing Merges.
  • Ronald de Haan: Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation
  • Frederic Koriche, Daniel Le Berre, Emmanuel Lonca, Pierre Marquis: Fixed-Parameter Tractable Optimization under DNNF Constraints

ESA 2016 (Track A), Aarhus, Denmark (11 FPT-related papers out of 62)

  • Lukasz Kowalik, Juho Lauri and Arkadiusz Socala. On the fine-grained complexity of rainbow coloring
  • Karl Bringmann, László Kozma, Shay Moran and N.S. Narayanaswamy. Hitting Set for hypergraphs of low VC-dimension
  • Ely Porat, Eduard Shahbazian and Roei Tov. New Parameterized Algorithms for APSP in Directed Graphs
  • Jesper Nederlof. Finding Large Set Covers Faster via the Representation Method
  • Eduard Eiben, Robert Ganian, Kustaa Kangas and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth
  • Édouard Bonnet and Tillmann Miltzow. Parameterized Hardness of Art Gallery Problems
  • Stefan Kratsch. A randomized polynomial kernelization for Vertex Cover with a smaller parameter
  • Andrew Drucker, Jesper Nederlof and Rahul Santhanam. Exponential Time Paradigms Through the Polynomial Time Lens
  • Edouard Bonnet, Laszlo Egri and Daniel Marx. Fixed-parameter Approximability of Boolean MinCSPs
  • Radu Curticapean. Counting matchings with k unmatched vertices in planar graphs
  • Krzysztof Fleszar, Matthias Mnich and Joachim Spoerhase. New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

MFCS 2016, Krakow, Poland (10 FPT-related papers out of 84)

  • Vikraman Arvind, Frank Fuhlbrueck, Johannes Koebler, Sebastian Kuhnert and Gaurav Rattan. The parameterized complexity of fixing number and vertex individualization in graphs
  • Dimitris Chatzidimitriou, Archontia Giannopoulou, Spyridon Maniatis, Clement Requile, Dimitrios Thilikos and Dimitris Zoros. FPT Algorithms for Plane Completion Problems
  • Yijia Chen and Jörg Flum. Some lower bounds in parameterized $\AC^0$
  • Eduard Eiben, Robert Ganian and O-Joung Kwon. A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion
  • Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch and Vuong Anh Quyen. Preprocessing under uncertainty: Matroid intersection
  • Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul and Ramanujan M. S. On the Complexity Landscape of Connected f-factor Problems
  • Robert Ganian, Ronald de Haan, Iyad Kanj and Stefan Szeider. On Existential MSO and its Relation to ETH
  • Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials
  • Fahad Panolan, Sudeshna Kolay, Venkatesh Raman and Saket Saurabh. Parameterized Algorithms on Perfect Graphs for deletion to (r, l)-graphs
  • Sebastian Siebertz, Roman Rabinovich, Stephan Kreutzer and Michal Pilipczuk. The Generalised Colouring Numbers on Classes of Bounded Expansion

DOOR 2016, Vladivostok, Russia (2 FPT-related papers out of 129)

COCOON 2016, Ho Chi Minh City, Vietnam (2 FPT-related papers out of 51)

  • Jiri Fiala, Tomas Gavenciak, Dusan Knop, Martin Koutecký, Jan Kratochvíl. Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems - extended abstract
  • Mingyu Xiao. A Parameterized Algorithm for Bounded-Degree Vertex Deletion

WG 2016, Istanbul, Turkey (11 FPT-related papers out of 25)

  • Bruno Escoffier. Saving colors and Max Coloring: some fixed-parameter tractability results.
  • Leizhen Cai and Junjie Ye. Finding Two Edge-Disjoint Paths with Length Constraints.
  • Eric Angel, Evripidis Bampis, Bruno Escoffier and Michael Lampis. Parameterized Power Vertex Cover.
  • Fedor Fomin and Torstein Strømme. Vertex Cover Structural Parameterization Revisited.
  • Pedro Montealegre and Ioan Todinca. Distance-d Independent Set and other problems in graphs with "few" minimal separators.
  • Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau and Mordechai Shalom. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability.
  • Mingyu Xiao and Shaowei Kou. Almost Induced Matching: Linear Kernels and Parameterized Algorithms.
  • Édouard Bonnet, Nick Brettell, O-Joung Kwon and Dániel Marx. Parameterized vertex deletion problems for hereditary graph classes with a block property.
  • Sudeshna Kolay, Ragukumar Pandurangan, Fahad Panolan, Venkatesh Raman and Prafullkumar Tale. Harmonious Coloring: Parameterized Algorithms and Upper bounds.
  • Ondrej Suchy. On Directed Steiner Trees with Multiple Roots.
  • Ramanujan M. S. A Faster Parameterized Algorithm for Group Feedback Edge Set.

ICALP 2016 (Track A), Rome, Italy (8 FPT-related papers out of 89)

  • Till Fluschnik, Danny Hermelin, André Nichterlein and Rolf Niedermeier. Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
  • Hans L. Bodlaender, Jesper Nederlof and Tom van der Zanden. Subexponential Time Algorithms for Embedding H-Minor Free Graphs
  • Mark de Berg, Kevin Buchin, Bart M. P. Jansen and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants
  • Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
  • Radu Curticapean. Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
  • Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer Mouawad and Saket Saurabh. Kernelization of Cycle Packing with Relaxed Disjointness Constraints
  • Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
  • Andrea Lincoln, Virginia Vassilevska Williams, Joshua Wang and Ryan Williams. Deterministic Time-Space Tradeoffs for k-SUM

SWAT 2016, Reykjavik, Iceland (6 FPT-related papers out of 30)

  • Alina Ene, Matthias Mnich, Marcin Pilipczuk and Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs.
  • Petr Golovach, Dieter Kratsch, Daniel Paulusma and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs
  • Petr Kolman, Martin Koutecky and Hans Raj Tiwary. Extension Complexity, MSO Logic, and Treewidth
  • Andreas Björklund. Coloring Graphs having Few Colorings over Path Decompositions
  • Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen. Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
  • Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh. Lower bounds for approximation schemes for Closest String

SoCG 2016, Boston, USA (2 FPT-related papers out of 61)

  • Petr Hlineny and Marek Derňár. Crossing Number is Hard for Kernelization
  • Markus Chimani and Petr Hlineny. Inserting Multiple Edges into a Planar Graph
  • Peyman Afshani, Edvin Berglin, Ingo van Duijn and Jesper Sindahl Nielsen. Applications of incidence bounds in point covering problems

CSR 2016, St. Petersburg, Russia (3 FPT-related papers out of 28)

STOC 2016, Cambridge, Massachusetts (1 FPT-related paper out of 92)

  • Fedor Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact Algorithms via Monotone Local Search

LATIN 2016, Ensenada, México (9 FPT-related papers out of 52)

  • Matthias Mnich, Heiko Röglin and Clemens Rösner. New Deterministic Algorithms for Solving Parity Games
  • Pål Grønås Drange, Markus Dregi and R.B. Sandeep. Compressing bounded degree graphs
  • Michal Kotrbcik, Rastislav Kralovic and Sebastian Ordyniak. Edge-editing to a Dense and a Sparse Graph Class
  • Saket Saurabh and Meirav Zehavi. $(k,n-k)$-Max-Cut: An $\OO^*(2^p)$-Time Algorithm and a Polynomial Kernel
  • Akanksha Agrawal, Daniel Lokshtanov, Sudeshna Kolay and Saket Saurabh. A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
  • Pradeesha Ashok, Sudeshna Kolay and Saket Saurabh. Parameterized Complexity of Red Blue Set Cover for lines
  • N. R. Aravind, R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
  • Syed Mohammad Meesum and Saket Saurabh. Rank Reduction of Directed Graphs by Vertex and Edge Deletions
  • Ashutosh Rai, Ramanujan M. S. and Saket Saurabh. A Parameterized Algorithm for Mixed-Cut

WALCOM 2016, Kathmandu, Nepal (1 FPT-related paper out of 28)

  • Matthias Mnich. Large Independent Sets in Subquartic Planar Graphs.

STACS 2016, Orleans, France (13 FPT-related papers out of 54)

  • Eva-Maria Hols and Stefan Kratsch. A randomized polynomial kernel for Subset Feedback Vertex Set
  • Michael Elberfeld and Pascal Schweitzer. Canonizing Graphs of Bounded Tree Width in Logspace
  • Bart M. P. Jansen. Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight
  • Maurice Chandoo. Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace
  • Per Austrin, Petteri Kaski, Mikko Koivisto and Jesper Nederlof. Dense Subset Sum may be the hardest
  • Fedor Fomin, Petr Golovach, Fahad Panolan and Saket Saurabh. Editing to Connected f -Degree Graph
  • Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments
  • Pål Grønås Drange, Markus Dregi, Fedor Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz and Somnath Sikdar. Kernelization and Sparseness: the case of Dominating Set
  • Michał Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs
  • Matthias Mnich and Erik Jan van Leeuwen. Polynomial Kernels for Deletion to Acyclic Digraphs
  • Stefan Fafianie, Stefan Kratsch and Vuong Anh Quyen. Preprocessing under uncertainty
  • Akanksha Agrawal, Daniel Lokshtanov, Amer Mouawad and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective
  • Mateus de Oliveira Oliveira. Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function

SODA 2016, Arlington, USA (11 FPT-related papers out of 147)

  • Yixin Cao. Linear Recognition of Almost Interval Graphs
  • Marcin Pilipczuk and Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs
  • Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk and Michal Pilipczuk. Subexponential parameterized algorithm for Interval Completion
  • Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh and Sofya Vorotnikova. Kernelization via Sampling with Applications to Dynamic Graph Streams
  • Jisu Jeong, Eun Jung Kim and Sang-Il Oum. Constructive algorithm for path-width of matroids
  • Daniel Lokshtanov, Marcin Pilipczuk and Erik Jan van Leeuwen. Independence and Efficient Domination on $P_6$-free Graphs
  • Robert Ganian, Ramanujan M. S. and Stefan Szeider. Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
  • Marek Cygan, Fedor Fomin, Alexander Golovnev, Alexander Kulikov, Ivan Mihajlin, Jakub Pachocki and Arkadiusz Socala . Tight bounds for graph homomorphism and subgraph isomorphism
  • Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth and cliquewidth
  • Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach and Michal Pilipczuk. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
  • Shivam Garg and Geevarghese Philip. Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

2015

ATMOS 2015, Patras, Greece (1 FPT-related paper out of 11)

  • René van Bevern, Christian Komusiewicz, Manuel Sorge: Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems (best paper award winner)

MFCS 2015, Milano, Italy (7 FPT-related papers out of 81)

  • Meirav Zehavi. Maximization Problems Parameterized Using Their Minimization Versions: The Case of Vertex Cover
  • Michael Etscheid, Stefan Kratsch, Matthias Mnich and Heiko Röglin. Polynomial Kernels for Weighted Problems
  • Stefan Fafianie and Stefan Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time
  • Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou and Sebastian Ordyniak. Parameterized Algorithms for Parity Games
  • Robert Ganian, Eun Jung Kim and Stefan Szeider. Algorithmic Applications of Tree-Cut Width
  • Geevarghese Philip, Ashutosh Rai and Saket Saurabh. Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
  • Ramanujan M. S., Petr Golovach, Fedor Fomin and Remy Belmonte. Metric Dimension of Bounded Width Graphs

ESA 2015, Patras, Greece (14 FPT-related papers out of 85)

  • Meirav Zehavi. Mixing Color Coding-Related Techniques
  • Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth and Total Unimodularity
  • Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for Trivially Perfect Editing
  • Dániel Marx and Michal Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
  • Éric Colin de Verdière. Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
  • Hans L. Bodlaender and Jesper Nederlof. Subexponential time algorithms for finding small tree and path decompositions
  • Hadas Shachnai and Meirav Zehavi. A Multivariate Framework for Weighted FPT Algorithms
  • Gregory Gutin, Mark Jones and Magnus Wahlström. Structural Parameterizations of the Mixed Chinese Postman Problem
  • Kenta Kitsunai, Yasuaki Kobayashi and Hisao Tamaki. On the Pathwidth of Almost Semicomplete Digraphs
  • Yoichi Iwata and Yuichi Yoshida. On the Equivalence among Problems of Bounded Width
  • Arnaud De Mesmay and Vincent Viallat Cohen Addad. A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
  • Ariel Gabizon, Daniel Lokshtanov and Michal Pilipczuk. Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
  • Christina Boucher, Christine Lo and Daniel Lokshtanov. Consensus Patterns (Probably) Has no EPTAS
  • Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov and Blair D. Sullivan. On the Threshold of Intractability

20th ACM SACMAT, Vienna, Austria (1 FPT-related paper out of 18)

  • Jason Crampton, Gregory Gutin and Daniel Karapetyan, Valued Workflow Satisfiability Problem (best paper award)

CIAC 2015, Paris, France (4 FPT-related papers out of 30)

  • Cristina Bazgan, André Nichterlein and Rolf Niedermeier. A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
  • Konrad Kazimierz Dabrowski and Daniel Paulusma. Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
  • Vikram Kamat and Neeldhara Misra. Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints
  • Guillerme Duvillié, Marin Bougeret, Vincent Boudet, Trivikram Dokka and Rodolphe Giroudeau. On the complexity of Wafer-to-Wafer Integration

COCOON 2015, Beijing, China (7 FPT-related papers out of 60)

  • Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora. Complexity of Grundy Coloring and Its Variants
  • Bang Ye Wu. A Measure and Conquer Approach for the Parameterized Bounded Degree-one Vertex Deletion
  • Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh. Unique Covering Problems with Geometric Sets
  • Shuai Hu, Wenjun Li, Jianxin Wang. An Improved Kernel for the Complementary Maximal Strip Recovery Problem
  • Ashutosh Rai, Saket Saurabh. Bivariate Complexity Analysis of Almost Forest Deletion
  • Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman, Sasanka Roy, Saket Saurabh. Time-space Tradeoffs for Dynamic Programming in Trees and Bounded Treewidth Graphs
  • Meesum Syed Mohammad, Pranabendu Misra, Saket Saurabh. Reducing Rank of the Adjacency Matrix by Graph Modification

WG 2015, Munich, Germany (8 FPT-related papers out of 32)

  • Mateus de Oliveira Oliveira: A Slice Theoretic Approach for Embedding Problems on Digraphs
  • Luis Pedro Montejano and Ignasi Sau: On the complexity of computing the k-restricted edge-connectivity of a graph
  • Eunjung Kim, Martin Milanic and Oliver Schaudt: Recognizing k-equistable graphs in FPT time
  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen and Marcin Wrochna: Polynomial kernelization for removing induced claws and diamonds
  • Mathieu Liedloff, Pedro Montealegre and Ioan Todinca: Beyond classes of graphs with “few” minimal separators: FPT results through potential maximal cliques
  • Thiago Marcilon and Rudini Sampaio: The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
  • Bart M.P. Jansen: On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT
  • Rémy Belmonte, Yota Otachi and Pascal Schweitzer: Induced Minor Free Graphs: Isomorphism and Clique-width

WADS 2015, Victoria, British Columbia, (4 FPT-related papers out of 51)

  • Wenjun Li, Jianxin Wang, Jianer Chen and Yixin Cao. A 2k-Vertex Kernel for Maximum Internal Spanning Tree
  • Eduard Eiben, Robert Ganian and Stefan Szeider. Solving Problems on Graphs of High Rank-Width
  • Falk Hüffner, Christian Komusiewicz and André Nichterlein. Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes
  • Fahad Panolan, Ramanujan M. S. and Saket Saurabh. On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids

ICALP 2015 (Track A), Kyoto, Japan (10 FPT-related papers out of 89)

  • Archontia Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov and Saket Saurabh. Uniform Kernelization Complexity of Hitting Forbidden Minors
  • Yixin Cao. Unit Interval Editing is Fixed-Parameter Tractable
  • Andreas Björklund, Holger Dell and Thore Husfeldt. The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems
  • Andreas Björklund, Vikram Kamat, Lukasz Kowalik and Meirav Zehavi. Spotting Trees with Few Leaves
  • Fedor V Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for Steiner Tree
  • Fedor V Fomin, Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin. Lower Bounds for the Graph Homomorphism Problem
  • Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan and Saket Saurabh. Deterministic Truncation of Linear Matroids
  • Serge Gaspers and Gregory Sorkin. Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets
  • Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity
  • Daniel Lokshtanov, Saket Saurabh and Ramanujan M. S.. Linear Time Parameterized Algorithms for SUBSET FEEDBACK VERTEX SET

ICALP 2015 (Track C), Kyoto, Japan (1 FPT-related paper out of 20)

  • Andreas Emil Feldmann. Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs

STOC 2015, Portland, Oregon, USA (5 FPT-related papers out of 93)

  • Martin Grohe, Pascal Schweitzer. Computing with Tangles
  • Ken-ichi Kawarabayashi, Stephan Kreutzer. The Directed Grid Theorem
  • Julia Chuzhoy. Excluded Grid Theorem: Improved and Simplified
  • Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture
  • Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

STACS 2015, Munich, Germany (4 FPT-related papers out of 55)

  • Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich and Sebastian Siebertz: Graph Searching Games and Width Measures for Directed Graphs
  • Per Austrin, Petteri Kaski, Mikko Koivisto and Jesper Nederlof: Subset Sum in the Absence of Concentration
  • Karl Bringmann, Danny Hermelin, Matthias Mnich and Erik Jan van Leeuwen: Parameterized Complexity Dichotomy for Steiner Multicut
  • Iyad Kanj and Ge Xia: Flip Distance is in FPT time O(n+ k * c^k)

SODA 2015, San Diego, USA (5 FPT-related papers out of ?)

  • Bingkai Lin. The Parameterized Complexity of k-Biclique
  • Dániel Marx and Paul Wollan. An exact characterization of tractable demand patterns for maximum disjoint path problems
  • Rajesh Chitnis, Graham Cormode, Mohammadtaghi Hajiaghayi and Morteza Monemizadeh. Parameterized Streaming: Maximal Matching and Vertex Cover
  • Bart M P Jansen and Daniel Marx. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
  • Ramanujan M S., Daniel Lokshtanov, Fedor Fomin, Saket Saurabh and Neeldhara Misra Solving d-SAT via Backdoors to Small Treewidth

2014

CiE 2014, Budapest, Hungary (2 FPT-related papers)

  • Cristina Bazgan, Morgan Chopin, André Nichterlein and Florian Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations
  • Stefano Beretta and Riccardo Dondi. Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability

IWOCA 2014, Duluth, USA (2 FPT-related papers)

  • Faisal Abu-Khzam, Florian Sikora and Edouard Bonnet. On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
  • Yuma Tamura, Takehiro Ito and Xiao Zhou. Deterministic Algorithms for the Independent Feedback Vertex Set Problem

FSTTCS 2014, New Delhi, India (4 FPT-related papers out of 47)

  • Manu Basavaraju, Fedor Fomin, Petr Golovach and Saket Saurabh. Connecting Vertices by Independent Trees
  • Christoph Berkholz and Michael Elberfeld. Parameterized Complexity of Fixed-Variable Logics
  • Konrad Kazimierz Dabrowski, Petr Golovach, Pim van 't Hof and Daniel Paulusma. Editing to Eulerian Graphs
  • Archontia Giannopoulou, Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy. Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)

COCOA 2014, Maui, Hawaii (4 FPT-related papers out of 47)

  • Iyad Kanj and Stefan Szeider. Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
  • Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
  • Faisal Abu-Khzam, Judith Egan, Michael Fellows, Frances Rosamond and Peter Shaw. On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints
  • Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang and Binhai Zhu. Algorithms for Cut Problems on Trees

ISAAC 2014, Jeonju, Korea (6 FPT-related papers out of 60)

  • Mingyu Xiao and Hiroshi Nagamochi. Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
  • Pawel Gawrychowski and Damian Rusak. Euclidean TSP with few inner points in linear space
  • Amer Mouawad, Naomi Nishimura and Venkatesh Raman. Vertex Cover Reconfiguration and Beyond
  • Jan Obdrzalek, Petr Hlineny, Sebastian Ordyniak and Jakub Gajarsky. Faster Existential FO Model Checking on Posets
  • Faisal Abu-Khzam, Cristina Bazgan, Morgan Chopin and Henning Fernau. Approximation Algorithms Inspired by Kernelization Methods
  • Takehiro Ito, Marcin Kami?ski and Hirotaka Ono. Fixed-Parameter Tractability of Token Jumping on Planar Graphs

IPEC 2014, Wroclaw, Poland (26 FPT-related papers out of 27)

  • Marthe Bonamy and Lukasz Kowalik. A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition
  • Petr Golovach. Editing to a Graph of Given Degrees
  • Julien Baste and Ignasi Sau. The role of planarity in connectivity problems parameterized by treewidth
  • Gregory Gutin, Stefan Kratsch and Magnus Wahlström. Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
  • Vuong Anh Quyen and Stefan Kratsch. On kernels for covering and packing ILPs with small coefficients
  • Henry Perret Du Cray and Ignasi Sau. Improved FPT algorithms for weighted independent set in bull-free graphs
  • Tatsuya Akutsu, Jesper Jansson, Atsuhiro Takasu and Takeyuki Tamura. On the Parameterized Complexity of Associative and Commutative Unification
  • V. Arvind, Johannes Köbler, Sebastian Kuhnert and Jacobo Torán. Solving Linear Equations Parameterized by Hamming Weight
  • Simone Bova, Robert Ganian and Stefan Szeider. Quantified Conjunctive Queries on Partially Ordered Sets
  • Paul Bonsma, Amer Mouawad, Naomi Nishimura and Venkatesh Raman. The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
  • Amer Mouawad, Naomi Nishimura, Venkatesh Raman and Marcin Wrochna. Reconfiguration over tree decompositions
  • Patrick Traxler. The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments
  • Ran Ben-Basat, Ariel Gabizon and Meirav Zehavi. The $k$-Distinct Language: Parameterized Automata Constructions
  • Jannis Bulian and Anuj Dawar. Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
  • Holger Dell. A simple proof that AND-compression of NP-complete problems is hard
  • Igor Razgon. No small nondeterministic read-once branching programs for CNFs of bounded treewidth
  • Vikraman Arvind and Gaurav Rattan. The Parameterized Complexity of Geometric Graph Isomorphism
  • Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi. Improved Parameterized Algorithms for Network Query Problems
  • Jan Obdrzalek, Jakub Gajarský, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, Somnath Sikdar and Sebastian Ordyniak. Finite Integer Index of Pathwidth and Treewidth
  • Janka Chlebikova and Morgan Chopin. The Firefighter Problem: A Structural Analysis
  • N.R. Aravind, R.B. Sandeep and Naveen Sivadasan. On Polynomial Kernelization of H-free Edge Deletion
  • Cristina Bazgan and André Nichterlein. Parameterized Inapproximability of Degree Anonymization
  • Sebastian Ordyniak and Alexandru Popa. A Parameterized Study of Maximum Generalized Pattern Matching Problems
  • Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel and Daniel Paulusma. Finding Shortest Paths between Graph Colourings
  • Zoltán Király. Shortest Paths in Nearly Conservative Digraphs
  • Rajesh Chitnis, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Saeedreza Seddighin. A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands

FOCS 2014, Philadelphia, USA (3 FPT-related papers out of 69)

ESA 2014, Track A, Wroclaw, Poland (8 FPT-related papers out of 57)

  • Gregory Gutin, Mark Jones and Bin Sheng. Parameterized Complexity of the k-Arc Chinese Postman Problem
  • Bart M. P. Jansen. Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
  • Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk and Michał Pilipczuk. A subexponential parameterized algorithm for Proper Interval Completion
  • Zdenek Dvorak and Matthias Mnich. Large Independent Sets in Triangle-Free Planar Graphs
  • Petr Golovach, Marcin Kamiński, Spyridon Maniatis and Dimitrios Thilikos. The Parameterized Complexity of Graph Cyclability
  • Hadas Shachnai and Meirav Zehavi. Representative Families: A Unified Tradeoff-Based Approach
  • Fedor Fomin, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh. Representative Sets of Product Families
  • Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy. Solving Multicut Faster than 2^n

WABI 2014, Wroclaw, Poland (1 FPT-related paper out of 28)

  • Sharon Bruckner, Falk Hüffner and Christian Komusiewicz: A Graph Modification Approach for Finding Core-Periphery Structures in Protein Interaction Networks

MFCS 2014, Budapest, Hungary (12 FPT-related papers out of 95)

  • Hasan Abasi, Nader Bshouty, Ariel Gabizon and Elad Haramaty: On r-simple k-path
  • Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier and Nimrod Talmon: Combinatorial Voter Control in Elections
  • Ruiwen Chen, Valentine Kabanets and Nitin Saurabh: An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
  • Yijia Chen and Moritz Mueller: Bounded variable logic, parameterized logarithmic space, and Savitch’s theorem
  • Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michal Pilipczuk: Hitting forbidden subgraphs in graphs of bounded treewidth
  • Stefan Fafianie and Stefan Kratsch: Streaming Kernelization
  • Petr Golovach: Editing to a Connected Graph of Given Degrees
  • Peter Jonsson, Victor Lagerkvist, Johannes Schmidt and Hannes Uppman: Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
  • Jan Kratochvil, Jan Arne Telle and Marek Tesar: Computational Complexity of Covering Three-Vertex Multigraphs
  • Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi: Deterministic Parameterized Algorithms for the Graph Motif Problem
  • Ramanujan M. S., Sudeshna Kolay, Pranabendu Misra and Saket Saurabh: Parameterized Approximations via d-Skew Symmetric Multicut
  • René Van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier and Gerhard Woeginger: Network-Based Dissolution

WG 2014, Orléans, France (8 FPT-related papers out of 32)

  • Gregory Gutin, Mark Jones, Bin Sheng and Magnus Wahlström. Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs
  • Sigve Hortemo Sæther and Jan Arne Telle. Between Treewidth and Clique-width
  • Henning Bruhn, Morgan Chopin, Felix Joos and Oliver Schaudt. Structural parameterizations for boxicity
  • Leo van Iersel and Steven Kelk. Kernelizations for the hybridization number problem on multiple nonbinary trees
  • Michael Lampis, Kazuhisa Makino, Valia Mitsou and Yushi Uno. Parameterized Edge Hamiltonicity
  • Stéphan Thomassé, Nicolas Trotignon and Kristina Vuskovic. A polynomial Turing-kernel for weighted independent set in bull-free graphs
  • Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier and Martin Rötzschke. The Parameterized Complexity of the Rainbow Subgraph Problem
  • Hadas Shachnai and Meirav Zehavi. Parameterized Algorithms for Graph Partitioning Problems

ICALP 2014, Track A, Copenhagen, Denmark (4 FPT-related papers out of 87)

  • Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar, A Faster Parameterized Algorithm for Treedepth
  • Michael Lampis, Parameterized Approximation Schemes using Graph Widths
  • Ramanujan M. S., Saket Saurabh, Pranabendu Misra, Manu Basavaraju, Fedor Fomin, and Petr Golovach, Parameterized Algorithms to Preserve Connectivity
  • Markus Sortland Dregi and Daniel Lokshtanov, Parameterized Complexity of Bandwidth on Trees

SWAT 2014, Copenhagen, Denmark (4 FPT-related papers out of 33)

  • Fedor Fomin, Mathieu Liedloff, Pedro Montealegre and Ioan Todinca. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
  • Vincent Froese, André Nichterlein and Rolf Niedermeier. Win-Win Kernelization for Degree Sequence Completion Problems
  • Yota Otachi and Pascal Schweitzer. Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
  • Keigo Oka and Yoichi Iwata. Fast Dynamic Graph Algorithms for Parameterized Problems

LATIN 2014, Montevidio, Uruguay (2 FPT-related papers out of 65)

STOC 2014, New York, NY (1 FPT-related papers out of 91)

CSR 2014, Moscow, Russia (4 FPT-related papers out of 27)

IPCO 2014, Bonn, Germany (1 FPT-related paper out of 34)

STACS 2014, Lyon, France (4 FPT-related papers out of 54)

ITCS 2014, Princeton, New Jersey (1 FPT-related paper out of 48)

  • Kazuo Iwama and Yuichi Yoshida. Parameterized Testability

SODA 2014, Oregon, USA (15 FPT-related papers out of 136)

2013

PODS 2013, New York, USA (1 FPT-related paper out of 24)

LATA 2013, Bilbao, Spain (1 FPT-related paper out of 45)

WADS 2013, London, Ontario, Canada (6 FPT-related papers out of 44)

COCOON 2013, Hangzhou, China (9 FPT-related papers out of 56)

FOCS 2013, Berkeley, USA (4 FPT-related papers out of 79)

MFCS 2013, Klosterneubeurg, Austria (8 FPT-related papers out of 67)

  • Meirav Zehavi. Parameterized Algorithms for Module Motif
  • Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt and Heribert Vollmer. Paradigms for Parameterized Enumeration
  • Fedor Fomin, Petr Golovach and Janne H. Korhonen. On the parameterized complexity of cutting a few vertices from a graph
  • Moritz Müller and Stefan Szeider. Revisiting Space in Proof Complexity: Treewidth and Pathwidth
  • Neeldhara Misra, Fahad Panolan and Saket Saurabh. Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?
  • Vincent Froese, René Van Bevern, Rolf Niedermeier and Manuel Sorge. A Refined Computational Complexity Analysis of Combinatorial Feature Selection Problems
  • Robert Ganian, Friedrich Slivovsky and Stefan Szeider. Meta-Kernelization with Structural Parameters
  • Prachi Goyal, Vikram Kamat and Neeldhara Misra. On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

ESA 2013, Track A, Sophia Antipolis, France (8 FPT-related papers out of 53)

WABI 2013, Sophia Antipolis, France (1 FPT-related paper out of 27)

  • Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz and Irena Rusu: A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications

WG 2013, Lübeck, Germany (7 FPT-related papers out of 34)

  • René Van Bevern, Andreas Emil Feldmann, Manuel Sorge and Ondřej Suchý. On the Parameterized Complexity of Graph Bisections
  • Hans L. Bodlaender, Stefan Kratsch and Vincent Kreuzen. Fixed-Parameter Tractability and Characterizations of Small Special Treewidth
  • Jianer Chen, Jia-Hao Fan and Sing-Hoi Sze. Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees
  • Michael R. Fellows and Bart M. P. Jansen. FPT is Characterized by Useful Obstruction Sets
  • Frank Kammer. A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem
  • Neeldhara Misra, Fahad Panolan, Ashutosh Rai, Venkatesh Raman and Saket Saurabh. Parameterized Algorithms for Max Colorable Induced Subgraph problem on Perfect Graphs
  • Manfred Cochefert, Jean-François Couturier, Petr Golovach, Dieter Kratsch and Daniel Paulusma. Sparse Square Roots

ICALP 2013, Track A, Riga, Latvia (7 FPT-related papers out of 71)

ICALP 2013, Track B, Riga, Latvia (1 FPT-related paper out of 33)

  • Hubie Chen and Daniel Marx. Block-Sorted Quantified Conjunctive Queries

ICALP 2013, Track C, Riga, Latvia (1 FPT-related paper out of 20)

  • Sepp Hartung, André Nichterlein, Rolf Niedermeier and Ondrej Suchy. A Refined Complexity Analysis of Identity Anonymization on Graphs

WADS 2013, Ontario, Canada (6 FPT-related papers out of 44)

  • Iyad Kanj and Ge Xia. When is weighted satisfiability FPT?
  • Michael J. Bannister, David Eppstein and Sergio Cabello. Parameterized Complexity of 1-Planarity
  • Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca and Yngve Villanger. Treewidth and pathwidth parameterized by vertex cover
  • Robert Bredereck, Jiehua Chen, Sepp Hartung, Christian Komusiewicz, Rolf Niedermeier and Ondrej Suchy. On Explaining Integer Vectors by Few Homogenous Segments
  • Naomi Nishimura and Narges Simjour. Parameterized Enumeration of (Locally-) Optimal Aggregations
  • Avinatan Hassidim, Orgad Keller, Moshe Lewenstein and Liam Roditty. Finding the Minimum-Weight $k$-path

SOCG 2013, Rio de Janeiro, Brazil (1 FPT-related paper out of 48)

  • João Paixão, Jonathan Spreer, Benjamin A. Burton and Thomas Lewiner. Parameterized Complexity of Discrete Morse Theory.

Complexity 2013, Palo Alto, USA (1 FPT-related paper out of 29)

STOC 2013, Palo Alto, USA (3 FPT-related papers out of 100)

STACS 2013, Kiel, Germany (10 FPT-related papers out of 54)

  • Andreas Björklund, Petteri Kaski and Lukasz Kowalik, Probably Optimal Graph Motifs
  • Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Yngve Villanger, Tight bounds for Parameterized Complexity of Cluster Editing
  • Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos, Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
  • Fedor Fomin and Yngve Villanger, Searching for better fill-in
  • Jisu Jeong, O-Joung Kwon and Sang-Il Oum. Excluded vertex-minors for graphs of linear rank-width at most $k$,
  • Stefan Kratsch, On Polynomial Kernels for Sparse Integer Linear Programs
  • Ramanujan M. S., Saket Saurabh, Serge Gaspers, Stefan Szeider and Sebastian Ordyniak, Backdoors to q-Horn
  • Daniel Paulusma, Friedrich Slivovsky and Stefan Szeider, Model Counting for CNF Formulas of Bounded Modular Treewidth
  • Michal Pilipczuk, Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
  • Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski and Erik Jan van Leeuwen, Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs

SODA 2013, New Orleans, USA (7 FPT-related papers out of 134)

2012

MFCS 2012, Bratislava, Slovakia (9 FPT-related papers out of 63)

And a paper accompanying an invited talk:

AAAI Conference on Artificial Intelligence (AAAI 2012), Toronto, Canada (6 FPT-related paper out of 294)

Conference on Computer and Communications Security (CCS 2012), Raleigh, USA (1 FPT-related paper out of 80)

IPEC 2012, Ljubljana, Slovenia (20 FPT-related papers out of 23)

  • Yijia Chen, Kord Eickmeyer and Jörg Flum. The exponential time hypothesis and the parameterized clique problem
  • Bruno Escoffier, Jerome Monnot, Vangelis Paschos and Mingyu Xiao. New results on polynomial inapproximability and fixed parameter approximability of EDGE DOMINATING SET
  • Ivan Bliznets and Alexander Golovnev. A New Algorithm for Parameterized MAX-SAT
  • Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. Restricted and Swap Common Superstring: a Parameterized View
  • Lukasz Kowalik. Nonblocker in H-minor free graphs: kernelization meets discharging
  • Joerg Flum and Moritz Mueller. Some definitorial suggestions for parameterized proof complexity
  • Fedor V. Fomin, Bart Jansen and Michal Pilipczuk. Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
  • Cédric Bentz. A polynomial-time algorithm for planar multicuts with few source-sink pairs
  • Chiranjit Chakraborty and Rahul Santhanam. Instance Compression for the Polynomial Hierarchy and Beyond
  • Abhijin Adiga, Jasine Babu and L. Sunil Chandran. Polynomial Time and Parameterized Approximation Algorithms for Boxicity
  • Petteri Kaski, Mikko Koivisto and Jesper Nederlof. Homomorphic Hashing for Sparse Coefficient Extraction
  • Petteri Kaski, Mikko Koivisto and Janne H. Korhonen. Fast Monotone Summation over Disjoint Sets
  • Markus Bläser and Radu Curticapean. Weighted counting of k-matchings is #W[1]-hard
  • James Abello, Pavel Klavík, Jan Kratochvil and Tomas Vyskocil. MSOL Restricted Contractibility to Planar Graphs
  • Michael Elberfeld, Christoph Stockhusen and Till Tantau. On the Space Complexity of Parameterized Problems
  • Adam Bouland, Anuj Dawar and Eryk Kopczyński. On Tractable Parameterizations of Graph Isomorphism
  • Sepp Hartung, Christian Komusiewicz and Andre Nichterlein. Parameterized Algorithmics for Finding 2-Clubs: Upper and Lower Bounds and Computational Experiments
  • Christian Komusiewicz and Manuel Sorge. Finding Dense Subgraphs of Sparse Graphs
  • Narges Simjour and Naomi Nishimura. Enumerating neighbour and closest strings
  • Faisal Abu-Khzam and Mazen Bu Khuzam. An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem

CPM 2012, Helsinki, Finland (6 FPT-related papers out of 33)

FOCS 2012, New Jersey, USA (4 FPT-related papers out of 79)

ESA 2012, Track A, Ljubljana, Slovenia (6 FPT-related papers out of 56)

WG 2012, Jerusalem, Israel (7 FPT-related papers out of 29)

  • Marek Cygan, Marcin Pilipczuk and Michal Pilipczuk. On group feedback vertex set parameterized by the size of the cutset
  • Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé. Parameterized Domination in Circle Graphs
  • Matthias Mnich and Rico Zenklusen. Bisections Above Tight Lower Bounds
  • Pinar Heggernes, Pim Van 'T Hof, Daniel Marx, Neeldhara Misra and Yngve Villanger. On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
  • Pranabendu Misra, Venkatesh Raman, Ramanujan M. S. and Saket Saurabh. Parameterized Algorithms for Even Cycle Transversal
  • Lukasz Kowalik and Marcin Mucha. A 9k kernel for nonseparating independent set in planar graphs
  • Petr Golovach, Pinar Heggernes, Pim Van 'T Hof, Fredrik Manne, Daniel Paulusma and Michal Pilipczuk. How to Eliminate a Graph

ICALP 2012, Track A, Warwick, United Kingdom (10 FPT-related papers out of 71)

ICALP 2012, Track B, Warwick, United Kingdom (2 FPT-related papers out of 30)

ICALP 2012, Track C, Warwick, United Kingdom (2 FPT-related papers out of 22)

SAT 2012, Trento, Italy (3 FPT-related papers out of 29)

COCOON 2012, Sydney, Australia (3 FPT-related papers out of 50)

  • Juanjo Rué, Ignasi Sau and Dimitrios Thilikos. Dynamic Programming for $H$-minor-free Graphs (Extended Abstract)
  • Fahad Panolan and Ashutosh Rai. On the kernelization complexity of problems on graphs without long odd cycles
  • René Van Bevern. Towards Optimal and Expressive Kernelization for d-Hitting Set

SWAT 2012, Helsinki, Finland (9 FPT-related papers out of 34)

  • Marek Cygan. Deterministic parameterized connected vertex cover
  • Ramanujan M. S., Pranabendu Misra, Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Fahad Panolan and Ashutosh Rai. Faster Parameterized Algorithms for Deletion to Split Graphs
  • Eun Jung Kim, Christophe Paul and Geevarghese Philip. A single-exponential FPT algorithm for K4-minor cover problem
  • Aistis Atminas, Vadim Lozin and Igor Razgon. Linear time algorithm for computing a small biclique in graphs without long induced paths
  • Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen. Induced Disjoint Paths in AT-free graphs
  • Archontia Giannopoulou, Iosif Salem and Dimitris Zoros. Effective Computation of Immersion Obstructions for Unions of Graph Classes
  • Martin Lackner and Marie-Louise Bruner. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
  • Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth
  • Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai and Venkatesh Raman. Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs

FUN 2012, Venice, Italy (1 FPT-related paper out of 34)

  • Leo Brueggeman, Michael Fellows, Rudolf Fleischer, Martin Lackner, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler and Frances Rosamond. Train Marshalling is Fixed Parameter Tractable

STOC 2012, New York, USA (1 FPT-related paper out of 90)

LATIN 2012, Arequipa, Peru (4 FPT-related papers out of 55)

STACS 2012, Paris, France (7 FPT-related papers out of 54)

SODA 2012, Kyoto, Japan (10 FPT-related papers out of 139)

2011

WADS 2011, New York, NY, USA (3 FPT-related papers out of 61)

COCOON 2011, Dallas, TX, USA (6 FPT-related papers out of 55)

TAPAS 2011, Rome, Italy (2 FPT-related papers out of 25)

FSTTCS 2011, Bombay, Mumbai, India (3 FPT-related papers out of 37)

ISAAC 2011, Yokohama, Japan (8 FPT-related papers out of 76)

  • Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski and Daniel Paulusma. Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
  • Sheng-Ying Hsiao. Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
  • Sylvain Guillemot. Parameterized algorithms for inclusion of linear matchings
  • Sepp Hartung, Rolf Niedermeier, Ondra Suchy and Jiong Guo. The Parameterized Complexity of Local Search for TSP, More Refined
  • Martin Dörnfelder, Jiong Guo, Christian Komusiewicz and Mathias Weller. On the Parameterized Complexity of Consensus Clustering
  • Chunhao Wang and Qian-Ping Gu. Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem
  • Cristina Bazgan, Morgan Chopin and Michael Fellows. Parameterized complexity of the firefighter problem
  • Pranabendu Misra, Ramanujan M. S., Venkatesh Raman and Saket Saurabh. A polynomial kernel for Feedback Arc Set on Bipartite Tournaments

CP 2011, Perugia, Italy (1 FPT-related paper out of 58)

IJCAI 2011, Barcelona, Spain (6 FPT-related papers out of 400)

IPEC 2011, Saarbrucken, Germany (20 FPT-related papers out of 21)

  • Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. On Multiway Cut parameterized above lower bounds
  • Isolde Adler, Stavros Kolliopoulos and Dimitrios Thilikos. Planar Disjoint-Paths Completion
  • Peter Damaschke. Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing
  • Hans L. Bodlaender, Bart Jansen and Stefan Kratsch. Kernel Bounds for Path and Cycle Problems
  • Robert Ganian. Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
  • Jiong Guo, Iyad Kanj and Stefan Kratsch. Safe approximation and its relation to kernelization
  • Pinar Heggernes, Pim Van 'T Hof, Benjamin Leveque, Daniel Lokshtanov and Christophe Paul. Contracting graphs to paths and trees
  • Bart Jansen and Stefan Kratsch. On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
  • Yong Zhang and Minghui Jiang. Parameterized Complexity in Multiple-Interval Graphs:Domination
  • Hajo Broersma, Petr Golovach and Viresh Patel. Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-width
  • Alexander Golovnev. New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
  • Petr Golovach, Marcin Kaminski, Daniel Paulusma and Dimitrios Thilikos. Increasing the Minimum Degree of a Graph by Contractions
  • Marek Cygan, Fedor Fomin and Erik Jan Van Leeuwen. Parameterized Complexity of Firefighting Revisited
  • Michael Lampis. Parameterized Maximum Path Coloring
  • Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. On cutwidth parameterized by vertex cover
  • Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle and Martin Vatshelle. Finding Good Decompositions for Dynamic Programming on Dense Graphs
  • Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. On the hardness of loosing width
  • Sepp Hartung, René Van Bevern, Rolf Niedermeier, Mathias Weller and Frank Kammer. Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
  • Torben Hagerup. Linear-Time Kernelization for Planar Dominating Set
  • Eun Jung Kim and Ryan Williams. Improved Parameterized Algorithms for Above Average Constraint Satisfaction

FOCS 2011, Palm Springs, California (3 FPT-related papers out of 85)

ESA 2011, Saarbrucken, Germany (5 FPT-related papers out of 68)

MFCS 2011, Warsaw, Poland (6 FPT-related papers out of 47)

FCT 2011, Oslo, Norway (7 FPT-related papers out of 28)

WG 2011, Tepla Monastery, Czech Republic (5 FPT-related papers out of 28)

ICALP 2011, Zürich, Switzerland (7 FPT-related papers out of 114)

TAMC 2011, Tokyo, Japan (5 FPT-related papers out of 51)

STOC 2011, San Jose, California (5 FPT-related papers out of 84)

SOFSEM 2011, Novy Smokovec, Slovakia (2 FPT-related papers out of 47)

SODA 2011, San Francisco, CA (4 FPT-related papers out of 133)

STACS 2011, Dortmund, Germany (5 FPT-related papers out of 54)

2010

ESA 2010, Liverpool, United Kingdom (3 FPT-related papers out of 50)

STACS 2010, Nancy, France (4 FPT-related papers out of 59)

ISAAC 2010, Jeju Island, Korea (5 FPT-related papers out of 40)

STOC 2010, Cambridge, MA (5 FPT-related papers out of 78)

SWAT 2010, Bergen, Norway (7 FPT-related papers out of 39)

ICALP 2010, Track A, Bordeaux, France (3 FPT-related papers out of 60)

ICALP 2010, Track B, Bordeaux, France (1 FPT-related paper out of 30)

CIAC 2010, Rome, Italy (5 FPT-related papers out of 33 papers in total)

FSTTCS 2010, Chennai, India (5 FPT-related papers out of 38)

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