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.
2012
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 (9 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
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)
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
