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.
2024
FOCS 2024, Chicago, USA
- Jan Dreier. Ioannis Eleftheriadis. Nikolas Mählmann. Rose McCarty. Michał Pilipczuk, Szymon Toruńczyk. First-Order Model Checking on Monadically Stable Graph Classes
- Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht. Obstructions to Erdős-Pósa Dualities for Minors
- Nikhil Bansal, Dor Katzelnick, Roy Schwartz. On Approximating Cutwidth and Pathwidth
- Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang. An Improved Pseudopolynomial Time Algorithm for Subset Sum
- Tuukka Korhonen, Michał Pilipczuk, Giannοs Stamoulis. Minor Containment and Disjoint Paths in almost-linear time
- Vaishali Surianarayanan, Daniel Lokshtanov, Saket Saurabh, Jie Xue, Vika Korchemna. Efficient Approximation of Hypertree Width
- Friedrich Eisenbrand, Lars Rohwedder, Karol Wegrzycki. Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
2021
FOCS 2021, Denver, USA
- Tuukka Korhonen. A Single-Exponential Time 2-Approximation Algorithm for Treewidth
- Marco Bressan and Marc Roth. Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
- Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Celine M. F. Swennenhuis. Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
- Samuel Fiorini, Gwenaël Joret, Stefan Weltge and Yelena Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row
- Sándor Kisfaludi-Bak, Jesper Nederlof and Karol Węgrzycki. A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
- Sitan Chen, Adam Klivans and Raghu Meka. Learning Deep ReLU Networks Is Fixed-Parameter Tractable
- Rahul Ilango. The Minimum Formula Size Problem is (ETH) Hard
ESA 2021, Lisbon, Portugal
- Éric Colin de Verdière and Thomas Magnard. An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
- Joergen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh. k-Distinct Branchings Admits a Polynomial Kernel
- Radu Curticapean, Holger Dell and Thore Husfeldt. Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
- Marek Cygan, Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms
- Zhiyang He, Jason Li and Magnus Wahlström. Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
- Leon Kellerhals, Malte Renken and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems
- Tomas Martinez-Munoz and Andreas Wiese. FPT and FPT-approximation algorithms for Unsplittable Flow on Trees
- Daniel Neuen. Isomorphism Testing Parameterized by Genus and Beyond
- Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif. Balanced Crown Decomposition for Connectivity Constraints
- Ramanujan M. Sridharan. On Approximate Compressions for Connected Minor-hitting Sets
MFCS 2021, Talinn, Estonia
- Giacomo Paesani, Daniel Paulusma and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
- Sayan Bandyapadhyay, Fedor Fomin, Petr Golovach and Kirill Simonov. Parameterized Complexity of Feature Selection for Categorical Data Clustering
- Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders
- Maël Dumas, Anthony Perez and Ioan Todinca. A cubic vertex-kernel for Trivially Perfect Editing
- Nikolas Mählmann, Sebastian Siebertz and Alexandre Vigny. Recursive Backdoors for SAT
- Bart M. P. Jansen, Shivesh K. Roy and Michal Wlodarczyk. On the Hardness of Compressing Weights
- Hendrik Molter, Malte Renken and Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting
- Gabriel Duarte, Mateus De Oliveira Oliveira and Uéverton Souza. Co-degeneracy and co-treewidth: Using the complement to solve dense instances
- Nils Morawietz and Petra Wolf. A Timecop's Chase Around the Table
WG 2021, Warsaw, Poland
- Huib Donkers and Bart M. P. Jansen. Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
- Hans L. Bodlaender. Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation
- Öznur Yaşar Diner, Archontia Giannopoulou, Giannos Stamoulis, and Dimitrios Thilikos. Block Elimination Distance
- Isja Mannens, Jesper Nederlof, Céline Swennenhuis, and Krisztina Szilagyi. On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
- Bart M. P. Jansen and Jari J.H. de Kroon. FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
- Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R B Sandeep, Sagnik Sen and R Subashini. On subgraph complementation to H-free graphs
- Avinandan Das, Lawqueen Kanesh, Jayakrishnan Madathil and Saket Saurabh. Odd Cycle Transversal in Mixed Graphs
- Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz and Frank Sommer. Preventing Small (s,t)-Cuts by Protecting Edges
- Christophe Crespelle, Benjamin Gras and Anthony Perez. Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Sylwester Swat and Marta Kasprzak. A heuristic approach to the treedepth decomposition problem for large graphs
- Van Bang Le and Jan Arne Telle. The Perfect Matching Cut Problem Revisited
- Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi and Alexandru I. Tomescu. A linear-time parameterized algorithm for computing the width of a DAG
- Fedor Fomin, Petr Golovach and Dimitrios Thilikos. Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs
STOC 2021, Rome, Italy
- Radu Curticapean. A Full Complexity Dichotomy for Immanant Families
- Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk. Vertex Deletion Parameterized by Elimination Distance and Even Less
- Bingkai Lin. Constant Approximating k-Clique Is W[1]-Hard
- Jesper Nederlof and Karol Wegrzycki. Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
- Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Finding Large Induced Sparse Subgraphs in C_{>t}-Free Graphs in Quasipolynomial Time
SODA 2021, Alexandria, USA
- Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Solving hard cut problems via flow-augmentation
- Willian Lochet. A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
- Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)
- Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. FPT-approximation for FPT Problems
- Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. Strong Connectivity Augmentation is FPT
- Stefan Kratsch, Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, and Manuel Sorge. Optimal Discretization is Fixed-parameter Tractable
- Itai Dinur. Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting
- Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin. On Two-Handed Planar Assembly Partitioning with Connectivity Constraints
STACS 2021, Saarbrücken, Germany
- Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. An FPT Algorithm for Elimination Distance to Bounded Degree Graphs.
- Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, Saket Saurabh. Diverse Collections in Matroids and Graphs.
- Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration.
- Anselm Haak, Arne Meier, Om Prakash, B. V. Raghavendra Rao. Parameterised Counting in Logspace.
- Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos. Digraph Coloring and Distance to Acyclicity.
- Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov. b-Coloring Parameterized by Clique-Width.
- Shaohua Li, Marcin Pilipczuk, Manuel Sorge. Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings.
- William Lochet, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. Exploiting Dense Structures in Parameterized Complexity.
- Marta Piecyk, Pawel Rzazewski. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth.
- Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
- Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses
2020
ESA 2020, Pisa, Italy
- Eduard Eiben and William Lochet. A Polynomial Kernel for Line Graph Deletion
- Fedor Fomin and Petr Golovach. Kernelization of Whitney Switches
- Fedor Fomin and Petr Golovach. Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs
- Fedor Fomin, Petr Golovach, Giannos Stamoulis, Dimitrios Thilikos. An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
- Eva-Maria Hols, Stefan Kratsch, Astrid Pieterse. Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Bart Jansen and Michal Wlodarczyk. Optimal Polynomial-Time Compression for Boolean Max CSP
- Mamadou Moustapha Kanté, Christophe Paul, Dimitrios Thilikos. A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth
- Tomohiro Koana, Christian Komusiewicz, Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Daniel Marx. Chordless Cycle Packing Is Fixed-Parameter Tractable
- Daniel Marx and R. Sandeep. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy
- Karolina Okrasa, Marta Piecyk, Paweł Rzążewski. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs
- Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth.
- Jan Dreier, Philipp Kuinke, Peter Rossmanith. First-Order Model-Checking in Random Graphs and Complex Networks.
- Lin Chen, Martin Koutecký, Lei Xu, Weidong Shi. New Bounds on Augmenting Steps of Block-Structured Integer Programs.
- Tanmay Inamdar, Kasturi R. Varadarajan. Capacitated Sum-Of-Radii Clustering: An FPT Approximation.
- Friedrich Eisenbrand, Moritz Venzin. Approximate CVP_p in Time 2^{0.802 n}
- Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström. Many Visits TSP Revisited.
ICALP 2020, Saarbrucken, Germany
- Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg. Extending Partial 1-Planar Drawings
- Amir Abboud, Karl Bringmann, Danny Hermelin and Dvir Shabtay. Scheduling Lower Bounds via AND Subset Sum
- A.Bulatov, A. Dadsetan. Counting homomorphisms in plain exponential time
- Jan Dreier, Henri Lotze and Peter Rossmanith. Hard Problems on Random Graphs
- Armin Weiß. Hardness of equations over finite solvable groups under the exponential time hypothesis
- Michal Wlodarczyk. Parameterized inapproximability for Steiner Orientation by gap amplification
- Martin Grohe. Counting Bounded Tree Depth Homomorphisms
- Johannes K. Fichte, Markus Hecher and Andreas Pfandler. Lower Bounds for QBFs of Bounded Treewidth
- Fedor Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh and Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
- Marin Bougeret, Bart M. P. Jansen and Ignasi Sau. Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
- Martin Fürer, Carlos Hoppen and Vilmar Trevisan. Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
- Timothy Chan, Jacob Cooper, Martin Koutecký, Dan Král and Kristýna Pekárková. Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming
- Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos. An FPT-algorithm for recognizing k-apices of minor-closed graph classes
- Alexander Göke, Dániel Marx, Matthias Mnich. Hitting long directed cycles is fixed-parameter tractable
- Magnus Wahlström. On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems
STOC 2020, Chicago, USA
- Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, Meirav Zehavi. An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
- Jesper Nederlof. Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
- Jesper Nederlof. Bipartite TSP in O*(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication
- Anupam Gupta, Euiwoong Lee, Jason Li. The Karger-Stein Algorithm is Optimal for k-cut
- Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Hitting Topological Minors is FPT
SOFSEM 2020, Limassol, Cyprus
- Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz and Frank Sommer. Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
- Faisal Abu-Khzam, Cristina Bazgan and Henning Fernau. Parameterized Dynamic Variants of Red-Blue Dominating Set
- Shahin Kamali, Avery Miller and Kenny Zhang. Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs
- Ronny Tredup. Parameterized complexity of synthesizing b-bounded (m,n)-T-systems
SODA 2020, Salt Laky City, USA
- Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos. Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh. 2-Approximating Feedback Vertex Set in Tournaments
- Karolina Okrasa, Paweł Rzążewski. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Julien Baste, Ignasi Sau, Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- Jason Li, Jesper Nederlof. Detecting Feedback Vertex Sets of Size k in O^*(2.7^k) Time
- Marc Roth, Philip Wellnitz. Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
- Sebastian Siebertz, Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich. Linear rankwidth meets stability
- M. S. Ramanujan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Ken-Ichi Kawarabayashi, Bingkai Lin. A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Archontia Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon. The Directed Flat Wall Theorem
- Michele Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Stefan Weltge. The stable set problem in graphs with bounded genus and bounded odd cycle packing number
- Pasin Manurangsi. Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems(via t-Wise Agreement Testing Theorem)
- Sándor Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time
- Holger Dell, John Lapinskas, Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle
2019
DISC 2019, Hungary, Budapest
- Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman. Parameterized Distributed Algorithms
ESA 2019, Munich, Germany (11 FPT-related papers out of 83)
- Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz and Karol Węgrzycki. Equal-Subset-Sum Faster Than the Meet-in-the-Middle
- Elena Farahbakhsh Touli and Yusu Wang. FPT-Algorithms for computing Gromov-Hausdorff and interleaving distances between trees
- Fedor Fomin, Petr Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Going Far From Degeneracy
- Fabrizio Grandoni, Stefan Kratsch and Andreas Wiese. Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Mamadou Moustapha Kanté and Benjamin Bergougnoux. More Applications of the $d$-neighbor equivalence: Connectivity and Acyclicity Constraints
- Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants
- Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen and Lukasz Kowalik Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
- Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum and Michał Włodarczyk. Constant factor FPT approximation for capacitated k-median
- Ramanujan M. Sridharan. An Approximate Kernel for Connected Feedback Vertex Set
- Eduard Eiben, Daniel Lokshtanov and Amer Mouawad. Bisection of Bounded Treewidth Graphs by Convolutions
- Ulrich Bauer, Abhishek Rathod and Jonathan Spreer. Parametrized complexity of expansion height
ICALP 2019 Track A, Patras, Greece (11 FPT-related papers out of 94)
- Andreas Bjorklund, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Approximate Counting of $k$-Paths: Deterministic and in Polynomial Space
- Klaus Jansen, Alexandra Lassota and Lars Rohwedder. Near-Linear Time Algorithm for n-fold ILPs via Color Coding
- Andreas Bjorklund and Ryan Williams. Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Decomposition of Map Graphs with Applications
- Bingkai Lin. A Simple Gap-producing Reduction for the Parameterized Set Cover Problem
- Fedor Fomin, Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
- Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee and Jason Li. Tight FPT Approximations for k-Median and k-Means
- Andreas Bjorklund, Petteri Kaski and Ryan Williams. Solving systems of polynomial equations by a parity-counting self-reduction
- Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering
- Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
- Akanksha Agrawal, Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Prafullkumar Tale. Path Contraction Faster than 2^n
ICALP 2019 Track B, Patras, Greece (2 FPT-related papers out of 31)
- Holger Dell, Marc Roth and Philip Wellnitz. Counting Answers to Existential Questions
- Katrin Casel, Joel Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
WG 2019, Vall de Núria, Catalonia, Spain (10 FPT-related papers out of 29)
- Karolina Okrasa and Paweł Rzążewski. Subexponential algorithms for variants of homomorphism problem in string graphs
- Bart Jansen, László Kozma and Jesper Nederlof. Hamiltonicity below Dirac’s condition
- Sebastian Wiederrecht, Meike Hatzel and Roman Rabinovich. Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs
- Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel and Joanna Tomasik. Fixed-parameter tractability of counting small minimum (S,T)-cuts
- Huib Donkers and Bart M.P. Jansen. A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
- Ivan Bliznets and Danil Sagunov. On Happy Colorings, Cuts, and Structural Parameterizations
- Robert Ganian and Sebastian Ordyniak. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
- Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono and Yota Otachi. Independent Set Reconfiguration Parameterized by Modular-Width
- Martin Dyer, Catherine Greenhill and Haiko Muller. Counting independent sets in graphs with bounded bipartite pathwidth
- Hubie Chen, Radu Curticapean and Holger Dell. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms
MFCS 2019, Aachen, Germany (8 FPT-related papers out of 78)
- Radovan Červený and Ondrej Suchy. Faster FPT Algorithm for 5-Path Vertex Cover
- Dušan Knop, Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems
- Christoph Berkholz and Nicole Schweikardt. Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
- Julian Dörfler, Marc Roth, Johannes Schmitt and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
- Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut and Meirav Zehavi. Packing Arc-Disjoint Cycles in Tournaments
- Jayakrishnan Madathil, Roohani Sharma and Meirav Zehavi. A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
- Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths
- Eduard Eiben, Robert Ganian, Thekla Hamm and O-Joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
WADS 2019, Edmonton, Canada (5 FPT-related papers out of 42)
- Hans Bodlaender, Sudeshna Kolay and Astrid Pieterse. Parameterized Complexity of Conflict-free Graph Coloring
- Max Bannach and Sebastian Berndt. Positive-Instance Driven Dynamic Programming for Graph Searching
- Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Balanced Stable Marriage: How Close is Close Enough?
- Steven Chaplick, Fedor Fomin, Petr Golovach, Dušan Knop and Peter Zeman. Kernelization of Graph Hamiltonicity: Proper H-Graphs
- Daniel Lokshtanov, Ramanujan M. Sridharan, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS
CSR 2019, Novosibirsk, Russian Federation (6 FPT-related papers out of 31)
- Neeldhara Misra, Fahad Panolan, and Saket Saurabh: On the Parameterized Complexity of Edge-Linked Paths
- Neeldhara Misra and Piyush Rathi: The Parameterized Complexity of Dominating Set and Friends Revisited
- Ruhollah Majdoddin: Uniform CSP Parameterized by Solution Size is in W[1]
- Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman: Parameterized Complexity of Conflict-Free Set Cover
- Mahdi Belbasi and Martin Fürer: A Space-efficient Parametrized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation
- Jayakrishnan Madathil, Fahad Panolan, Abhishek Sahu, and Saket Saurabh: On the Complexity of Mixed Dominating Set
SOFSEM 2019, Nový Smokovec, Slovakia (7 FPT-related papers out of 35)
- Jouke Witteveen, Ralph Bottesch and Leen Torenvliet: A Hierarchy of Polynomial Kernels
- Julien Baste, Didem Gözüpek, Mordechai Shalom and Dimitrios Thilikos: Minimum Reload Cost Graph Factors
- Sebastiaan B. van Rooij and Johan M. M. van Rooij: Algorithms and complexity results for the capacitated vertex cover problem
- Neeldhara Misra and Chinmay Sonar: Determining Robustness of Multiwinner Rules on Restricted Domains
- Christian Komusiewicz and Frank Sommer: Enumerating Connected Induced Subgraphs: Improved Delay and Experimental Comparison
- Nils Donselaar: Probabilistic Parameterized Polynomial Time
- Frank Gurski and Carolin Rehs: Forbidden Directed Minors, Directed Path-Width and Directed Tree-Width of Tree-like Digraphs
STACS 2019, Berlin, Germany (10 FPT-related papers out of 54)
- Eva-Maria Hols and Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters
- Bart M. P. Jansen, Marcin Pilipczuk and Erik Jan van Leeuwen: A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
- Max Bannach and Till Tantau: On the Descriptive Complexity of Color Coding
- Fedor Fomin, Petr Golovach and Dimitrios Thilikos: Modification to Planarity is Fixed Parameter Tractable
- Robert Krauthgamer and Ohad Trabelsi: The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
- Dušan Knop, Michal Pilipczuk and Marcin Wrochna: Tight complexity lower bounds for integer linear programming with few constraints
- Eduard Eiben, Dušan Knop, Fahad Panolan and Ondrej Suchy: Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz and Szymon Torunczyk: Progressive Algorithms for Domination and Independence
- Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich and Sebastian Siebertz: Algorithmic Properties of Sparse Digraphs
- Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond and Dimitrios Thilikos: Lean tree-cut decompositions: obstructions and algorithms
SODA 2019, San Diego, USA (9 FPT-related papers out of 183)
- Gregory Gutin, Magnus Wahlstrom and Meirav Zehavi. On $r$-Simple $k$-Path and Related Problems Parameterized by $k/r$
- Michał Pilipczuk and Sebastian Siebertz. Polynomial bounds for centered colorings on proper minor-closed graph classes
- Amir Abboud, Karl Bringmann, Danny Hermelin and Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Fahad Panolan, Saket Saurabh and Meirav Zehavi. Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity
- Akanksha Agrawal, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Interval Vertex Deletion Admits a Polynomial Kernel
- Sándor Kisfaludi-Bak, Jesper Nederlof and Erik Jan van Leeuwen. Planar Steiner Tree with Terminals on Few Faces
- Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis and Jevgēnijs Vihrovs. Quantum Speedups for Exact Exponential Dynamic Programming Algorithms
- Meike Hatzel, Ken-Ichi Kawarabayashi and Stephan Kreutzer. Polynomial Planar Directed Grid Theorem
- André Berger, László Kozma, Matthias Mnich, Roland Vincze. Time- and space-optimal algorithms for the many-visits TSP
2018
STOC 2018, Los Angeles, USA (4 FPT-related papers out of 111)
- Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden. Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi. On the Parameterized Complexity of Approximating Dominating Set
- Holger Dell, John Lapinskas. Fine-grained reductions from approximate counting to decision
- Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof. More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
ICML 2018, Stockholm Sweden (1 FPT-related paper)
- Robert Ganian, DePaul Iyad Kanj, Sebastian Ordyniak, Stefan Szeider. Algorithms for the Matrix Completion Problem
FOCS 2018, Paris, France (4 FPT-related papers out of 86)
- Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
- Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida. 0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms
- Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP
- Anupam Gupta, Euiwoong Lee, Jason Li. Faster Exact and Approximate Algorithms for k-Cut
IWOCA 2018, Wellington, New Zealand (4 FPT-related papers out of 32)
- Christine Dahn, Nils M. Kriege and Petra Mutzel : A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
- Laurent Bulteau, Romeo Rizzi and Stéphane Vialette : Pattern matching for $k$-track permutations
- Bogdan Alecu, Vadim Lozin and Viktor Zamaraev : Linear clique-width of bi-complement reducible graphs
- Neeldhara Misra : Structural Parameterizations for Colorful Components
ATMOS 2018, Helsinki, Finland (1 FPT-related paper out of 16)
- René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for safe convoy routing
ESA (All tracks) 2018, Helsinki, Finland (13 FPT-related papers out of 73)
- Arijit Ghosh, Sudeshna Kolay and Gopinath Mishra. FPT algorithms for embedding into low complexity graphic metrics
- Yixin Cao, Ashutosh Rai, R.B. Sandeep and Junjie Ye. A Polynomial Kernel for Diamond-Free Editing
- Stefan Kratsch and Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions
- Rajesh Chitnis, Andreas Emil Feldmann and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Fedor Fomin, Fahad Panolan, Ramanujan M. S. and Saket Saurabh. On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
- Bart M. P. Jansen and Astrid Pieterse. Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
- Daniel R. Schmidt, Bernd Zey and François Margot. An exact algorithm for the Steiner forest problem
- Fedor Fomin, Petr Golovach and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs
- Johannes K. Fichte, Markus Hecher, Stefan Woltran and Markus Zisser. Weighted Model Counting on the GPU by Exploiting Small Treewidth
- Bart M. P. Jansen and Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
- Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions
- Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier and Philipp Zschoche. Data Reduction for Maximum Matching on Sparse Graphs: Theory and Experiments
ICALP (Track A) 2018, Prague, Czech Republic (12 FPT-related papers out of 99)
- Alexandra Kolla, Ioannis Koutis, Vivek Madan and Ali Kemal Sinop. Spectrally Robust Graph Isomorphism
- Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
- Eduard Eiben and Iyad Kanj. How to navigate through obstacles?
- Fedor Fomin, Petr Golovach and Fahad Panolan. Parameterized Low-Rank Binary Matrix Approximation
- Felix Reidl and Magnus Wahlström. Parameterized Algorithms for Zero Extension and Metric Labelling Problems
- Friedrich Eisenbrand, Christoph Hunkenschröder and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure
- Jiehua Chen, Danny Hermelin, Manuel Sorge and Harel Yedidsion. How hard is it to satisfy (almost) all roommates?
- Jisu Jeong, Eun Jung Kim and Sang-Il Oum. Finding branch-decompositions of matroids, hypergraphs, and more
- Martin Grohe, Daniel Neuen, Pascal Schweitzer and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs
- Martin Koutecky, Asaf Levin and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Michael Lampis. Finer Tight Bounds for Coloring on Clique-Width
- Sixue Liu. Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
ICALP (Track B) 2018, Prague, Czech Republic (2 FPT-related papers out of 30)
- Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz and Szymon Toruńczyk. First-order interpretations of bounded expansion classes
- Ramanujan M. S., Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs
SWAT 2018, Malmo, Sweden (6 FPT-related papers out of 30)
- Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi and Florian Sikora. Parameterized Orientable Deletion.
- Fedor Fomin, Petr Golovach, Torstein Strømme and Dimitrios Thilikos. Partial complementation of graphs.
- Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks.
- Evripidis Bampis, Bruno Escoffier, Michael Lampis and Vangelis Paschos. Multistage Matchings.
- Lukasz Kowalik and Arkadiusz Socala. Tight Lower Bounds for List Edge Coloring.
- Petr Golovach, Pinar Heggernes, Athanasios Konstantinidis, Paloma Lima and Charis Papadopoulos. Parameterized Aspects of Strong Subgraph Closure.
LATIN 2018, Buenos Aires, Argentina ( FPT-related papers out of 64)
- Julio Araujo, Victor Campos, Ana Karolinna Maia, Ignasi Sau and Ana Silva. On the complexity of finding internally vertex-disjoint long directed paths
- Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh and Sudeshna Kolay. Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set
- R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi. The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue
- Serge Gaspers, Joachim Gudmundsson, Michael Horton and Stefan Rümmele. When is Red-Blue Nonblocker FPT?
- Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Saket Saurabh and Venkatesh Raman. A Polynomial Sized Kernel for Tracking Paths Problem
- Davis Issac, L. Sunil Chandran, Anita Das and Erik Jan van Leeuwen. Algorithms and Bounds for Very Strong Rainbow Coloring
- Hang Gao and Wenyu Gao. Kernelization for Maximum Happy Vertices Problem
STACS 2018, Caen, France (9 FPT-related papers out of 54)
- Rémy Belmonte, Michael Lampis and Valia Mitsou. Parameterized (Approximate) Defective Coloring
- Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
- Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC$^0$-Circuits
- Eduard Eiben, Robert Ganian and Sebastian Ordyniak. Small Resolution Proofs for QBF using Dependency Treewidth
- Lars Jaffke, O-Joung Kwon and Jan Arne Telle. A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width
- Robert Ganian, Fabian Klute and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
- Laszlo Egri, Dániel Marx and Paweł Rzążewski. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization
- Yoichi Iwata, Tomoaki Ogasawara and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
- Eduard Eiben, Mithilesh Kumar, Amer Mouawad, Fahad Panolan and Sebastian Siebertz. Lossy Kernels for Connected Dominating Set
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
2017
COCOON 2017, Hong Kong, China (3 FPT-related papers out of 48)
- Jakub Gajarský, Petr Hlineny, Martin Koutecky and Shmuel Onn. Parameterized Shifted Combinatorial Optimization
- Qilong Feng, Senmin Zhu and Jianxin Wang. An improved kernel for Parameterized Bisection above Tight Lower Bound
- Pranabendu Misra, Fahad Panolan, Ramanujan M. S. and Saket Saurabh. Linear Representation of Transversal Matroids and Gammoids parameterized by rank
FSTTCS 2017, Ahmedabad, India (2 FPT-related papers out of 41)
- Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer Mouawad and Ramanujan M. S. On the Parameterized Complexity of Simultaneous Deletion Problems
- Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Balanced Judicious Partition is FPT
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)
- René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon and Gerhard J. Woeginger. Precedence-constrained scheduling problems parameterized by partial order width
- René van Bevern, Rolf Niedermeier and Ondřej Suchý. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack (presentation only)
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)
- Petr Golovach and George Mertzios: Graph Editing to a Given Degree Sequence
- René van Bevern and Artem V. Pyatkin: Completing partial schedules for Open Shop with unit processing times and routing
- René van Bevern, Vincent Froese and Christian Komusiewicz: Parameterizing edge modification problems above lower bounds
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)
- Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
- Radu Curticapean, Dániel Marx. Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
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)
- Martin Fürer. A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- Toshimasa Ishii, Hirotaka Ono, Yushi Uno: (Total) Vector Domination for Graphs with Bounded Branchwidth
STOC 2014, New York, NY (1 FPT-related papers out of 91)
CSR 2014, Moscow, Russia (4 FPT-related papers out of 27)
- Heidi Jazmin Romero Gonzalez and Alejandro Lopez-Ortiz. A Parameterized Algorithm for Packing Overlapping Subgraphs
- Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk. Fast branching algorithm for Cluster Vertex Deletion
- Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer and Sebastian Siebertz. Vertex Disjoint Paths in Upward Planar Graphs
- Huiwen Yu and Martin Fürer. Space Saving by Dynamic Algebraization
IPCO 2014, Bonn, Germany (1 FPT-related paper out of 34)
STACS 2014, Lyon, France (4 FPT-related papers out of 54)
- Valentin Garnero, Christophe Paul, Ignasi Sau and Dimitrios M. Thilikos. Explicit Linear Kernels via Dynamic Programming
- Dániel Marx and Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
- Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk and Yngve Villanger. Exploring Subexponential Parameterized Complexity of Completion Problems
- Yixin Cao and Dániel Marx. Chordal Editing is Fixed-Parameter Tractable
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)
- Andreas Björklund, Petteri Kaski and Łukasz Kowalik. Counting thin subgraphs via packings faster than meet-in-the-middle time
- Yixin Cao and Dániel Marx. Interval Deletion is Fixed-Parameter Tractable
- Michel X. Goemans, Thomas Rothvoss. Polynomiality for Bin Packing with a Constant Number of Item Types
- Fedor Fomin, Daniel Lokshtanov and Saket Saurabh. Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Fedor Fomin, Ioan Todinca and Yngve Villanger. Large induced subgraphs via triangulations and CMSO
- Ken-Ichi Kawarabayashi and Stephan Kreutzer. An Excluded Grid Theorem for Digraphs with Forbidden Minors
- Stefan Kratsch, Geevarghese Philip and Saurabh Ray. Point Line Cover: The Easy Kernel is Essentially Tight
- Philip Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs
- Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time
- Bart M. P. Jansen, Daniel Lokshtanov and Saket Saurabh. A Near-Optimal Planarization Algorithm
- Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Dániel Marx. Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- Laurent Bulteau and Christian Komusiewicz. Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable
- Magnus Wahlström. Half-integrality, LP-branching and FPT Algorithms
- M. S. Ramanujan and Saket Saurabh. Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Yoichi Iwata, Keigo Oka and Yuichi Yoshida. Linear-Time FPT Algorithms via Network Flow
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)
- Michael J. Bannister, Sergio Cabello, David Eppstein. Parameterized Complexity of 1-Planarity
- Robert Bredereck, Jiehua Chen, Sepp Hartung, Christian Komusiewicz, Rolf Niedermeier, Ondrej Suchý. On Explaining Integer Vectors by Few Homogenous Segments
- Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger. Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty. Finding the Minimum-Weight k-Path
- Iyad A. Kanj, Ge Xia. When Is Weighted Satisfiability FPT?
- Naomi Nishimura, Narges Simjour. Parameterized Enumeration of (Locally-) Optimal Aggregations
COCOON 2013, Hangzhou, China (9 FPT-related papers out of 56)
- Qilong Feng and Jianxin Wang and Shaohua Li and Jianer Chen. Random Methods for Parameterized Problems
- Jan Baumbach, Jiong Guo, Rashid Ibragimov. Covering Tree with Stars
- Bernard Mans, Luke Mathieson. On the Treewidth of Dynamic Graphs
- Robert Crowston, Gregory Gutin, Mark Jones, Gabriele Muciaccia. Maximum Balanced Subgraph Problem Parameterized above Lower Bound
- Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki. A Linear Edge Kernel for Two-Layer Crossing Minimization
- dos Santos Souza, Fábio Protti, Maise Dantas da Silva. Parameterized Complexity of Flood-Filling Games on Trees
- Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora. Parameterized Approximability of Maximizing the Spread of Influence in Networks
- Yunlong Liu, Jianxin Wang, Chao Xu, Jiong Guo, Jianer Chen. An Effective Branching Strategy for Some Parameterized Edge Modification Problems with Multiple Forbidden Induced Subgraphs
- Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang. Parameterized Algorithms for Maximum Agreement Forest on Multiple Trees
FOCS 2013, Berkeley, USA (4 FPT-related papers out of 79)
- Marek Cygan. Improved approximation for 3-dimensional matching via bounded pathwidth local search
- Serge Gaspers and Stefan Szeider. Strong Backdoors to Bounded Treewidth SAT
- Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michal Pilipczuk. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
- Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk. An O(c^k) n 5-Approximation Algorithm for Treewidth
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)
- Marek Cygan, Fabrizio Grandoni and Danny Hermelin. Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Stefan Kratsch. On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Fedor Fomin and Michał Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
- Michael Fellows, Danny Hermelin, Frances A. Rosamond and Hadas Shachnai. Tractable Parameterizations for the Minimum Linear Arrangement Problem
- Rajesh Chitnis, Laszlo Egri and Daniel Marx. List H-Coloring a Graph by Removing Few Vertices
- Fedor Fomin and Petr Golovach. Long Circuits and Large Euler Subgraphs
- Ramanujan M. S., Saket Saurabh, Daniel Lokshtanov, Ondrej Suchy and Mark Jones. Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez and Somnath Sikdar. Kernelization Using Structural Parameters on Sparse Graph Classes
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)
- Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions
- Hans Bodlaender, Marek Cygan, Stefan Kratsch and Jesper Nederlof. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
- Radu Curticapean. Counting matchings of size k is #W[1]-hard
- Michael Lampis. Model Checking Lower Bounds for Simple Graphs
- Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree
- Dániel Marx and László A. Végh. Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
- Per Austrin, Petteri Kaski, Mikko Koivisto and Jussi Määttä. Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
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)
- Sepp Hartung, André Nichterlein. On the Parameterized and Approximation Hardness of Metric Dimension
STOC 2013, Palo Alto, USA (3 FPT-related papers out of 100)
- Anupam Gupta, Kunal Talwar, and David Witmer. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
- Chandra Chekuri and Julia Chuzhoy. Large-Treewidth Graph Decompositions and Applications
- Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings
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)
- Fedor V. Fomin, Michał Pilipczuk. Jungles, bundles, and fixed parameter tractability
- Zdenek Dvorak and Ken-Ichi Kawarabayashi. List-coloring embedded graphs
- Martin Grohe, Ken-Ichi Kawarabayashi and Bruce Reed. A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory
- Marek Cygan, Marcin Pilipczuk and Michal Pilipczuk. Known algorithms for Edge Clique Cover are probably optimal
- Ken-Ichi Kawarabayashi. Totally odd subdivisions and parity subdivisions: Structures and Coloring
- Ken-Ichi Kawarabayashi, Marek Krcal, Daniel Kral and Stephan Kreutzer. Packing directed cycles through a specified vertex set
- Ken-Ichi Kawarabayashi. 5-coloring $K_{3,k}$-minor-free graphs: Beyond Thomassen
2012
MFCS 2012, Bratislava, Slovakia (9 FPT-related papers out of 63)
- Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis. Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
- Petr Golovach, Pim Van 'T Hof and Daniel Paulusma. Obtaining Planarity by Contracting Few Edges
- Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo. Parameterized Study of the Test Cover Problem
- Martin Doucha and Jan Kratochvil. Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Cristina Bazgan and Morgan Chopin. The Robust Set problem: parameterized complexity and approximation
- Robert Ganian, Petr Hlineny, Jaroslav Nesetril, Jan Obdrzalek, Patrice Ossona de Mendez and Reshma Ramadurai. When Trees Grow Low: Shrubs and Fast MSO1
- Mingyu Xiao and Jiong Guo. A Quadric Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
- Torben Hagerup. Kernels for Edge Dominating Set: Simpler or Smaller
- Jesper Nederlof, Erik Jan van Leeuwen and Ruben van der Zwaan. Reducing a Target Interval to a Few Exact Queries
And a paper accompanying an invited talk:
AAAI Conference on Artificial Intelligence (AAAI 2012), Toronto, Canada (6 FPT-related paper out of 294)
- Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider. The Complexity of Planning Revisited - A Parameterized Analysis
- Robert Bredereck, Jiehua Chen, Sepp Hartung, Rolf Niedermeier, Ondrej Suchy, and Stefan Kratsch. A Multivariate Complexity Analysis of Lobbying in Multiple Referenda
- Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond, and Stefan Rümmele. The Parameterized Complexity of Abduction
- Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, and Stefan Szeider. On Finding Optimal Polytrees
- Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, and Stefan Szeider. Don't Be Strict in Local Search!
- Andrew M. Sutton and Frank Neumann. A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem
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)
- Sharon Bruckner, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Sven Thiel, Johannes Uhlmann. Partitioning into Colorful Components by Minimum Edge Deletions
- Haitao Jiang, Binhai Zhu. A Linear Kernel for the Complementary Maximal Strip Recovery Problem
- David Fernández-Baca, Sylvain Guillemot, Brad Shutters, Sudheer Vakati. Fixed-Parameter Algorithms for Finding Agreement Supertrees
- Riccardo Dondi, Nadia El-Mabrouk. Minimum Leaf Removal for Reconciliation: Complexity and Algorithms
- Liviu Petrisor Dinu, Alexandru Popa. On the Closest String via Rank Distance
- Zhi-Zhong Chen, Lusheng Wang, Wenji Ma. The Parameterized Complexity of the Shared Center Problem
FOCS 2012, New Jersey, USA (4 FPT-related papers out of 79)
- Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions
- Andrew Drucker. New Limits to Classical and Quantum Instance Compression
- Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization
- Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms
ESA 2012, Track A, Ljubljana, Slovenia (6 FPT-related papers out of 56)
- Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen. Induced Disjoint Paths in Claw-Free Graphs
- Yasuaki Kobayashi and Hisao Tamaki. A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- Jan Arne Telle and Yngve Villanger. Solving domination problems on larger graph classes by linear-time FPT algorithms
- Fedor Fomin, Saket Saurabh and Yngve Villanger. A Polynomial kernel for Proper Interval Vertex Deletion
- Danny Hermelin, Matthias Mnich and Erik Jan van Leeuwen. Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
- Marek Cygan, Guy Kortsarz and Zeev Nutov. Steiner Forest Orientation Problems
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)
- Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlstrom. Clique cover and graph separation: New incompressibility results
- Bingkai Lin and Yijia Chen. The parameterized complexity of k-edge induced subgraphs
- Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
- Michael Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai. Parameterized Approximation via Fidelity Preserving Transformations
- Serge Gaspers and Stefan Szeider. Backdoors to Acyclic SAT
- Ramanujan M. S. and Daniel Lokshtanov. Parameterized Tractability of Multiway Cut with Parity Constraints
- Robert Crowston, Mark Jones and Matthias Mnich. Max-Cut Parameterized Above the Edwards-Erdos Bound
- Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs
- Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Philip Klein and Dániel Marx. Solving planar $k$-terminal cut in $O(n^{c \sqrt{k}})$ time
ICALP 2012, Track B, Warwick, United Kingdom (2 FPT-related papers out of 30)
- John Fearnley and Sven Schewe. Time and Parallelizability Results for Parity Games with Bounded Treewidth
- Tomás Gavenciak, Daniel Kral and Sang-Il Oum. Deciding first order logic properties of matroids
ICALP 2012, Track C, Warwick, United Kingdom (2 FPT-related papers out of 22)
- Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth
- Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk. Minimizing Rosenthal Potential in Multicast Games
SAT 2012, Trento, Italy (3 FPT-related papers out of 29)
- Nadia Creignou and Heribert Vollmer. Parameterized Complexity of Weighted Satisfiability Problems
- Anders Yeo, Venkatesh Raman, Gregory Gutin, Robert Crowston, Mark Jones and Saket Saurabh. Fixed-parameter tractability of satisfying beyond the number of variables
- Serge Gaspers and Stefan Szeider. Strong Backdoors to Nested Satisfiability
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)
- Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Venkatesh Raman. Parameterized Complexity of MaxSat Above Average
- Hadas Shachnai, Gal Tamir and Tami Tamir. A Theory and Algorithms for Combinatorial Reoptimization
- Archontia C. Giannopoulou, Sudeshna Kolay and Saket Saurabh. New Lower Bound on Max-Cut of hypergraphs with an application to r-Set Splitting
- Fedor Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan Van Leeuwen, Martin Vatshelle and Yngve Villanger. k-Gap Interval Graphs
STACS 2012, Paris, France (7 FPT-related papers out of 54)
- Marcin Kaminski and Dimitrios Thilikos. Contraction Checking in Graphs on Surfaces
- Ken-Ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor
- Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdrzalek, Peter Rossmanith and Somnath Sikdar. Lower bounds on the complexity of MSO1 model-checking
- Ramanujan M. S., Venkatesh Raman, Saket Saurabh and Narayanaswamy N. S. LP can be a cure for Parameterized Problems
- Dieter Mitsche and Guillem Perarnau. On treewidth and related parameters of random geometric graphs
- Fedor V. Fomin and Petr Golovach. Parameterized Complexity of Connected Even/Odd Subgraph Problems
- Paul Bonsma. Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces
SODA 2012, Kyoto, Japan (10 FPT-related papers out of 139)
- Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Dániel Marx. Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- Stefan Kratsch. Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem
- Danny Hermelin and Xi Wu. Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization
- Fedor V. Fomin and Yngve Villanger. Subexponential Parameterized Algorithm for Minimum Fill-in
- Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
- Andreas Björklund, Thore Husfeldt and Nina Taslaman. Shortest Cycle Through Specified Elements
- Holger Dell and Dániel Marx. Kernelization of Packing Problems
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos. Linear Kernels for (Connected) Dominating Set on H-minor-free graphs
- Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh. Bidimensionality and Geometric Graphs
- Stephan Kreutzer and Siamak Tazari. Directed nowhere dense classes of graphs
2011
WADS 2011, New York, NY, USA (3 FPT-related papers out of 61)
- Paul Bonsma and Daniel Lokshtanov. Feedback Vertex Set in Mixed Graphs
- Jianer Chen, Jia-Hao Fan, Iyad Kanj, Yang Liu and Fenghui Zhang. Multicut in trees viewed through the eyes of vertex cover
- Peter Damaschke and Leonid Molokov. Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
COCOON 2011, Dallas, TX, USA (6 FPT-related papers out of 55)
- Minghui Jiang and Yong Zhang. Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
- Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis and C. M. Lau. Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
- Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki and Xiao Zhou. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
- Neeldhara Misra, Geevarghese Philip, Venkatesh Raman and Saket Saurabh. On Parameterized Independent Feedback Vertex Set
- Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer Chen. Cograph Editing: Complexity and Parameterized Algorithms
- Qilong Feng, Jianxin Wang and Jianer Chen. Matching and P 2-Packing: Weighted Versions
TAPAS 2011, Rome, Italy (2 FPT-related papers out of 25)
- Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier and Johannes Uhlmann. Exploiting Bounded Signal Flow for Graph Orientation Based on Cause-Effect Pairs
- Iyad A. Kanj and Fenghui Zhang. 3-hitting set on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size
FSTTCS 2011, Bombay, Mumbai, India (3 FPT-related papers out of 37)
- Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stephan Thomasse and Anders Yeo. Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average
- Fedor V. Fomin, Geevarghese Philip and Yngve Villanger. Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
- Pinar Heggernes, Pim Van 'T Hof, Daniel Lokshtanov and Christophe Paul. Obtaining a bipartite graph by contracting few edges
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)
- Nadja Betzler, Rolf Niedermeier, and Gerhard J. Woeginger. Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard
- Felix Brandt, Markus Brill, and Hans Georg Seedig. On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions
- Michael Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, and Frances Rosamond. Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable
- Serge Gaspers and Stefan Szeider. Kernels for Global Constraints
- Johannes Klaus Fichte and Stefan Szeider. Backdoors to Tractable Answer-Set Programming
- Sebastian Ordyniak and Stefan Szeider. Augmenting Tractable Fragments of Abstract Argumentation
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)
- Mikkel Thorup and Ken-ichi Kawarabayashi. The minimum k-way cut of bounded size is fixed-parameter tractable
- Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Michal Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time
- Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan. The Graph Minor Algorithm with Parity Conditions
ESA 2011, Saarbrucken, Germany (5 FPT-related papers out of 68)
- Dimitrios Thilikos. Fast sub-exponential Algorithms and Compactness in Planar Graphs
- Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh and Stéphan Thomassé. Hitting and Harvesting Pumpkins
- Fedor Fomin, Ioan Todinca and Yngve Villanger. Exact algorithm for the maximum induced planar subgraph problem
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Scheduling partially ordered jobs faster than 2^n
- Venkatesh Raman, Ramanujan M. S. and Saket Saurabh. Paths, Flowers and Vertex Cover
MFCS 2011, Warsaw, Poland (6 FPT-related papers out of 47)
- Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: a logical approach
- Christophe Paul, Stéphan Thomassé and Anthony Perez. Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and related problems
- Jianxin Wang, Yongjie Yang, Jiong Guo and Jianer Chen. Linear Problem Kernels for Planar Graph Problems with Small Distance Property
- Mingyu Xiao, Ton Kloks and Sheung-Hung Poon. New Parameterized Algorithms for Edge Dominating Set
- Robert Bredereck, André Nichterlein, Rolf Niedermeier and Geevarghese Philip. Pattern-Guided Data Anonymization and Clustering
- Petr Golovach, Marcin Kaminski and Daniel Paulusma. Contracting a chordal graph to a split graph or a tree
FCT 2011, Oslo, Norway (7 FPT-related papers out of 28)
- Bart M. P. Jansen and Stefan Kratsch. Data Reduction for Graph Coloring Problems
- Gregory Gutin, Mark Jones and Anders Yeo. A New Bound for $3$-Satisfiable MaxSat and its Algorithmic Application
- Paul Hunter. LIFO-search on digraphs: A searching game for cycle-rank
- Pinar Heggernes, Pim Van 't Hof, Bart Jansen, Stefan Kratsch and Yngve Villanger. Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- Robert Bredereck, André Nichterlein, Rolf Niedermeier and Geevarghese Philip. The Effect of Homogeneity on the Complexity of k-Anonymity
- Stéphane Bessy and Anthony Perez. Polynomial kernels for Proper Interval Completion and related problems
WG 2011, Tepla Monastery, Czech Republic (5 FPT-related papers out of 28)
- Rémy Belmonte and Martin Vatshelle. Graph Classes with Structured Neighborhoods and Algorithmic Applications
- Marek Cygan, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Ildiko Schlotter. Parameterized Complexity of Eulerian Deletion Problems
- Danny Hermelin, Chien-Chung Huang, Stefan Kratsch and Magnus Wahlström. Parameterized Two-Player Nash Equilibrium
- Daniel Lokshtanov, Matthias Mnich and Saket Saurabh. Planar k-Path in Subexponential Time and Polynomial Space
- Manuel Sorge, René Van Bevern, Rolf Niedermeier and Mathias Weller. From Few Components to an Eulerian Graph by Adding Arcs
ICALP 2011, Zürich, Switzerland (7 FPT-related papers out of 114)
- Andrei Bulatov and Dániel Marx: Constraint satisfaction parameterized by solution size.
- Daniel Lokshtanov and Dániel Marx: Clustering with Local Restrictions.
- Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk: Subset Feedback Vertex Set is Fixed Parameter Tractable
- Danny Hermelin, Matthias Mnich, Erik Jan Van Leeuwen and Gerhard J. Woeginger: Domination when the Stars Are Out
- Isolde Adler, Stavros Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos: Tight Bounds for Linkages in Planar Graphs.
- Olaf Beyersdorff, Nicola Galesi, Massimo Lauria and Alexander Razborov: Parameterized Bounded-Depth Frege is Not Optimal.
TAMC 2011, Tokyo, Japan (5 FPT-related papers out of 51)
- Andre Berger, Alexander Grigoriev and Ruben van der Zwaan: How to Cut a Graph into Many Pieces
- Benjamin Hellouin de Menibus and Takeaki Uno: Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo and Jianer Chen: An Improved Kernel for Planar Connected Dominating Set
- Remy Belmonte, Pinar Heggernes and Pim Van 't Hof: Edge Contractions in Subclasses of Chordal Graphs
- Alexander Langer, Peter Rossmanith and Somnath Sikdar: Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
STOC 2011, San Jose, California (5 FPT-related papers out of 84)
- Nicolas Bousquet, Jean Daligault, Stéphan Thomassé: Multicut is FPT.
- Dániel Marx, Igor Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset.
- Ken-ichi Kawarabayashi and Paul Wollan: A simpler algorithm and shorter proof for the graph minor decomposition.
- Erik Demaine, Mohammad Hajiaghayi and Ken-ichi Kawarabayashi: Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications.
- Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx and Paul Wollan: Finding topological subgraphs is fixed-parameter tractable
SOFSEM 2011, Novy Smokovec, Slovakia (2 FPT-related papers out of 47)
- Nadja Betzler, Robert Bredereck, Rolf Niedermeier, Johannes Uhlmann: On Making a Distinguished Vertex Minimum Degree by Vertex Deletion.
- Christian Komusiewicz, Johannes Uhlmann: Alternative Parameterizations for Cluster Editing.
SODA 2011, San Francisco, CA (4 FPT-related papers out of 133)
- Jeff Erickson and Amir Nayyeri: Shortest Non-Crossing Walks in the Plane
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh: Bidimensionality and EPTAS
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh: Slightly Superexponential Parameterized Problems
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh: Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal
STACS 2011, Dortmund, Germany (5 FPT-related papers out of 54)
- Robert Ganian, Petr Hlineny and Jan Obdrzalek: Clique-width: When Hard Does Not Mean Impossible
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip and Saket Saurabh: Hitting forbidden minors: Approximation and Kernelization
- Hans L. Bodlaender, Bart M.P. Jansen and Stefan Kratsch: Cross-Composition: A New Technique for Kernelization Lower Bounds
- Hans L. Bodlaender and Bart M.P. Jansen: Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter
- Christian Knauer, Hans Raj Tiwary and Daniel Werner: On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
2010
ESA 2010, Liverpool, United Kingdom (3 FPT-related papers out of 50)
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Fast Minor Testing in Planar Graphs.
- Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo: All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables.
- Michael Lampis: Algorithmic Meta-theorems for Restrictions of Treewidth.
STACS 2010, Nancy, France (4 FPT-related papers out of 59)
- Rolf Niedermeier: Reflections on Multivariate Algorithmics and Problem Parameterization.
- Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs.
- Frederic Dorn: Planar Subgraph Isomorphism Revisited.
- Dániel Marx, Barry O'Sullivan, Igor Razgon: Treewidth Reduction for Constrained Separation and Bipartization Problems.
ISAAC 2010, Jeju Island, Korea (5 FPT-related papers out of 40)
- Marek Karpinski, Warren Schudy: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament.
- Abhijin Adiga, Rajesh Chitnis, Saket Saurabh: Parameterized Algorithms for Boxicity.
- André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller: On Tractable Cases of Target Set Selection.
- Ljiljana Brankovic, Henning Fernau: Combining Two Worlds: Parameterised Approximation for Vertex Cover.
- David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time.
STOC 2010, Cambridge, MA (5 FPT-related papers out of 78)
- Holger Dell, Dieter van Melkebeek: Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
- Ken-ichi Kawarabayashi and Paul Wollan: A shorter proof of the Graph Minor Algorithm -- The Unique Linkage Theorem
- Ken-ichi Kawarabayashi and Bruce Reed: Odd Cycle Packing
- Daniel Lokshtanov, Jesper Nederlof: Saving Space by Algebraization
- Dániel Marx: Tractable hypergraph properties for constraint satisfaction and conjunctive queries
SWAT 2010, Bergen, Norway (7 FPT-related papers out of 39)
- Stefan Kratsch, Pascal Schweitzer: Isomorphism for Graphs of Bounded Feedback Vertex Set Number.
- Yixin Cao, Jianer Chen, Yang Liu:: On Feedback Vertex Set New Measure and New Structures.
- Robert Crowston, Gregory Gutin, Mark Jones, Eun Jung Kim, Imre Z. Ruzsa: Systems of Linear Equations over F_2 and Problems Parameterized above Average.
- Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter: Bin Packing with Fixed Number of Bins Revisited.
- Bart Jansen: Polynomial Kernels for Hard Problems on Disk Graphs.
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Faster Parameterized Algorithms for Minor Containment.
- Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing.
ICALP 2010, Track A, Bordeaux, France (3 FPT-related papers out of 60)
- Daniel Král': Decomposition Width of Matroids.
- Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos: Dynamic Programming for Graphs on Surfaces.
- Stefan Kratsch, Magnus Wahlström: Preprocessing of Min Ones Problems: A Dichotomy.
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)
- Leizhen Cai, Boting Yang: Parameterized Complexity of Even/Odd Subgraph Problems.
- Pinar Heggernes, Federico Mancini, Jesper Nederlof, Yngve Villanger: A Parameterized Algorithm for Chordal Sandwich.
- Reinhard Pichler, Stefan Rümmele, Stefan Woltran: Multicut Algorithms via Tree Decompositions.
- Bart Jansen: Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights.
- Daniel Binkele-Raible, Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Peter Rossmanith: A Parameterized Route to Exact Puzzles: Breaking the 2^n-Barrier for Irredundance.
FSTTCS 2010, Chennai, India (5 FPT-related papers out of 38)
- Michael Fellows, Bart Jansen, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh: Determining the Winner of a Dodgson Election is Hard
- Petr Hlineny, Robert Ganian, Jan Obdrzalek: Better algorithms for satisfiability problems for formulas of bounded rank-width
- Vikraman Arvind, Bireswar Das, Johannes Koebler, Seinosuke Toda: Colored Hypergraph Isomorphism is Fixed Parameter Tractable
- Sebastian Ordyniak, Daniel Paulusma, Stefan Szeider: Satisfiability of Acyclic and Almost Acyclic CNF Formulas
- Neeldhara Misra, Geevarghese Philip, Venkatesh Raman and Saket Saurabh: The effect of girth on the kernelization complexity of Connected Dominating Set