FPT papers online

This page contains a list of FPT-related papers which have appeared online, such as on the arXiv or on ECCC. They are listed in chronological order. Some papers solving long-standing open problems are highlighted.

- 19th Jun 2017 Victor Lagerkvist, Magnus Wahlström. Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra
- 13th June 2017 Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos. Structured Connectivity Augmentation
- 13th June 2017 Tomasz Kociumaka, Marcin Pilipczuk. Deleting vertices to graphs of bounded genus
- 12th June 2017 Gregory Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi. Kirchoff Matrices and Pfaffians to Design Deterministic Polynomial-Space Parameterized Algorithms
- 10th June 2017 Matthias Bentert, René van Bevern, André Nichterlein, Rolf Niedermeier. Parameterized algorithms for power-efficient connected symmetric wireless sensor networks
- 3rd June 2017 Mehdy Roayaei, MohammadReza Razzazi Inferring protein-protein interaction and protein-DNA interaction directions based on cause-effect pairs in undirected and mixed networks
- 2nd June 2017 Florian Barbero, Christophe Paul, Michał Pilipczuk. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
- 31st May 2017 Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan. Saving Critical Nodes with Firefighters is FPT
- 31st May 2017 Britta Dorn, Ronald de Haan, Ildikó Schlotter. Obtaining a Proportional Allocation by Deleting Items
- 23rd May 2017 N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, Juho Lauri. Algorithms and hardness results for happy coloring problems
- 22nd May 2017 Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- 18th May 2017 Irene Muzi, Michael P. O'Brien, Felix Reidl, Blair D. Sullivan. Being even slightly shallow makes life hard
- 16th May 2017 Oliver Schaudt, Fabian Senger. The Parameterized Complexity of the Equidomination Problem
- 3rd May 2017 Mark Jones, Manuel Lafond, Celine Scornavacca. Consistency of orthology and paralogy constraints in the presence of gene transfers
- 3rd May 2017 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
- 28th April 2017 Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos. Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
- 27th April 2017 Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine. The Parameterized Complexity of Positional Games
- 24th April 2017 Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- 24th April 2017 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
- 21st April 2017 Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström. Path-contractions, edge deletions and connectivity preservation
- 19th April 2017 Zhao An, Qilong Feng, Iyad Kanj, Ge Xia. The Complexity of Tree Partitioning
- 18th April 2017 Hisao Tamaki. Positive-instance driven dynamic programming for treewidth
- 14th April 2017 Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- 13th April 2017 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- 10th April 2017 Nikola Yolov. Minor-matching hypertree width
- 10th April 2017 Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida. Linear-Time FPT Algorithms via Half-Integral Non-returning A-path Packing
- 28th March 2017 Júlio Araújo, Julien Baste, Ignasi Sau. Ruling out FPT algorithms for Weighted Coloring on forests
- 19th March 2017 Yijia Chen, Martin Grohe, Bingkai Lin. The Hardness of Embedding Grids and Walls
- 16th March 2017 Marek Cygan, Lukasz Kowalik, Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decomposition
- 15th March 2017 Nathann Cohen (LRI), Frédéric Havet (COATI, UCA), Dorian Mazauric (UCA, ABS), Ignasi Sau (ALGCO), Rémi Watrigant (UCA, ABS). Complexity Dichotomies for the Minimum F-Overlay Problem
- 9th Match 2017 O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz. On low rank-width colorings
- 8th March 2017 David Eppstein, Denis Kurz. K-Best Solutions of MSO Problems on Tree-Decomposable Graphs
- 8th March 2017 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh. The Half-integral Erdös-Pósa Property for Non-null Cycles
- 7th March 2017 Till Fluschnik, Meike Hatzel, Steffen Härtlein, Hendrik Molter, Henning Seidler. The Minimum Shared Edges Problem on Grid-like Graphs
- 1st March 2017 Dušan Knop, Martin Koutecký, Tomáš Masařík, Tomáš Toufar. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
- 1st March 2017 L. Sunil Chandran, Anita Das, Davis Issac, Erik Jan van Leeuwen. Algorithms and Bounds for Very Strong Rainbow Coloring
- 27th February 2017 Laurent Bulteau. Consensus Patterns parameterized by input string length is W1-hard
- 22nd February 2017 Jakub Gajarský, Petr Hliněný, Martin Koutecký, Shmuel Onn. Parameterized Shifted Combinatorial Optimization
- 21st February 2017 Matthias Bentert, Till Fluschnik, André Nichterlein, Rolf Niedermeier. Parameterized Aspects of Triangle Enumeration
- 21st February 2017 Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, Nimrod Talmon. When can Graph Hyperbolicity be computed in Linear Time?
- 20th February 2017 Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-joung Kwon. An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- 14th February 2017 Iyad Kanj, Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen. Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
- 9th February 2017 Johannes Fichte, Markus Hecher, Michael Morak, Stefan Woltran. Answer Set Solving with Bounded Treewidth Revisited
- 24th January 2017 Mikołaj Bojańczyk, Michał Pilipczuk. Optimizing tree decompositions in MSO
- 24th January 2017 Lars Jaffke, Bart M. P. Jansen. Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- 11th January 2017 Manu Basavaraju, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh. On finding highly connected spanning subgraphs
- 19th December 2016 Pierre Bergé, Jason Crampton, Gregory Gutin, Rémi Watrigant. The Authorization Policy Existence Problem
- 17th December 2016 Robert Ganian, M. S. Ramanujan, Stefan Szeider. Backdoors to Tractable Valued CSP
- 12th December 2016 Gregory Gutin, Felix Reidl, Magnus Wahlström. k-Distinct In- and Out-Branchings in Digraphs
- 6th December 2016 Dániel Marx, Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1−1/d is the best possible exponent for d-dimensional geometric problems
- 29th November 2016 René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý. Fixed-Parameter Algorithms for DAG Partitioning
- 23rd November 2016 Carolin Albrecht, Frank Gurski, Jochen Rethmann, Eda Yilmaz. Knapsack Problems: A Parameterized Point of View
- 23rd November 2016 Akanksha Agrawal, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Simultaneous Feedback Edge Set: A Parameterized Perspective
- 21st November 2016 Stefan Kratsch. A randomized polynomial kernelization for Vertex Cover with a smaller parameter
- 20th November 2016 Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese. Approximation and parameterized algorithms for geometric independent set with shrinking
- 11th November 2016 Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier. Diminishable Parameterized Problems and Strict Polynomial Kernelization
- 6th November 2016 Cornelius Brand, Marc Roth. Parameterized counting of trees, forests and matroid bases
- 3rd November 2016 Karl Bringmann, Allan Grønlund, Kasper Green Larsen. A Dichotomy for Regular Expression Membership Testing
- 3rd November 2016 Katherine Edwards, Irene Muzi, Paul Wollan. Half-integral linkages in highly connected directed graphs
- 3rd November 2016 Wolfgang Fischl, Georg Gottlob, Reinhard Pichler. General and Fractional Hypertree Decompositions: Hard and Easy Cases
- 2nd November 2016 Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh. Below all subsets for Minimal Connected Dominating Set
- 28th October 2016 Hans L. Bodlaender, Tom C. van der Zanden. Improved Lower Bounds for Graph Embedding Problems
- 25th October 2016 Dániel Marx, Marcin Pilipczuk. Subexponential parameterized algorithms for graphs of polynomial growth
- 24th October 2016 Pavel Dvořák, Dušan Knop, Tomáš Toufar. Target Set Selection in Dense Graph Classes
- 23rd October 2016 Eun Jung Kim, O-joung Kwon. A Polynomial Kernel for Distance-Hereditary Vertex Deletion
- 22nd October 2016 M. B. Hastings. Local Maxima and Improved Exact Algorithm for MAX-2-SAT
- 19th October 2016 Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Explicit linear kernels for packing problems
- 19th October 2016 Magnus Wahlström. LP-branching algorithms based on biased graphs
- 15th October 2016 Mithilesh Kumar, Daniel Lokshtanov. A 2ℓk Kernel for ℓ-Component Order Connectivity
- 15th October 2016 Karl Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- 13th October 2016 Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran. Parameterized Complexity of Small Weight Automorphisms
- 11th October 2016 Robert Ganian, M. S. Ramanujan, Stefan Szeider. Combining Treewidth and Backdoors for CSP
- 30th September 2016 Mateus de Oliveira Oliveira. A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
- 30th September 2016 Bart M.P. Jansen, Jules J.H.M. Wulms. Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
- 28th September 2016 George B. Mertzios, André Nichterlein, Rolf Niedermeier. Fine-Grained Algorithm Design for Matching
- 26th September 2016 Marin Bougeret, Ignasi Sau. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- 25th September 2016 Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, Jean-Florent Raymond, Marcin Wrochna. Linear kernels for edge deletion problems to immersion-closed graph classes
- 22nd September 2016 Michał Włodarczyk. Clifford algebras meet tree decompositions
- 18th September 2016 Weidong Luo. A Framework for Solving Turing Kernel (Compression) Lower Bound Problem and Finding Natural Candidate Problems in NP-intermediate
- 16th September 2016 Riccardo Dondi, Florian Sikora. Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis
- 16th September 2016 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh. A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set
- 5th September 2016 Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie, Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- 29th August 2016 Mingyu Xiao, Shaowei Kou. Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- 22nd August 2016 Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs
- 20th August 2016 Mingyu Xiao. Linear Kernels for Separating a Graph into Components of Bounded Size
- 11th August 2016 Jesper Nederlof. Finding Large Set Covers Faster via the Representation Method
- 10th August 2016 Roee David, Karthik C. S., Bundit Laekhanukit. The Curse of Medium Dimension for Geometric Problems in Almost Every Norm
- 9th August 2016 Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang. Parameterized Algorithms for the Maximum Agreement Forest Problem on Multiple Rooted Multifurcating Trees
- 4th August 2016 Yoichi Iwata. Linear-time Kernelization for Feedback Vertex Set
- 2nd August 2016 Darren Strash. On the Power of Simple Reductions for the Maximum Independent Set Problem
- 27th July 2016 Radu Curticapean. Counting matchings with k unmatched vertices in planar graphs
- 26th July 2016 Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin. Finding Detours is Fixed-parameter Tractable
- 26th July 2016 Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski. Complexity of Token Swapping and its Variants
- 26th July 2016 Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat. Approximation and Parameterized Complexity of Minimax Approval Voting
- 21st July 2016 Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff. The Complexity of Drawing Graphs on Few Lines and Few Planes
- 21st July 2016 Serge Gaspers, Edward Lee. Faster Graph Coloring in Polynomial Space
- 19th July 2016 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Spanning Circuits in Regular Matroids
- 18th July 2016 Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Fine-grained complexity of integer programming: The case of bounded branch-width and rank
- 18th July 2016 Euiwoong Lee. Partitioning a Graph into Small Pieces with Applications to Path Transversal
- 15th July 2016 Pedro Montealegre, Ioan Todinca. On Distance-d Independent Set and other problems in graphs with few minimal separators
- 14th July 2016 Esther Ezra, Micha Sharir. The Decision Tree Complexity for k-SUM is at most Nearly Quadratic
- 14th July 2016 Arturs Backurs, Christos Tzamos. Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
- 14th July 2016 Andreas Björklund, Ioannis Koutis. Modular Sieves for Directed Hamiltonian Cycles
- 12th July 2016 Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała. Tight lower bounds for the complexity of multicoloring
- 10th July 2016 Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard Woeginger. Fine-Grained Complexity Analysis of Two Classic TSP Variants
- 5th July 2016 Yuping Ke, Yixin Cao, Xiating Ouyang, Jianxin Wang. Unit Interval Vertex Deletion: Fewer Vertices are Relevant
- 4th July 2016 Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil. Width, depth and space
- 30th June 2016 Bernhard Bliem, Sebastian Ordyniak, Stefan Woltran. Clique-Width and Directed Width Measures for Answer-Set Programming
- 30th June 2016 René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, Ondřej Suchý: Finding Secluded Places of Special Interest in Graphs
- 27th June 2016 Yixin Cao, R. B. Sandeep. Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
- 26th June 2016 Yijia Chen, Joerg Flum. Some lower bounds in parameterized AC0
- 26th June 2016 Dong Yeap Kang, O-joung Kwon, Torstein J.F. Strømme, Jan Arne Telle. Sim-width and induced minors
- 21st June 2016 Martin Fürer. Faster Computation of Path-Width
- 21st June 2016 Cornelius Brand, Holger Dell, Marc Roth. Fine-grained dichotomies for the Tutte plane and Boolean #CSP
- 20th June 2016 Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects
- 17th June 2016 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Bidimensionality and Kernels
- 14th June 2016 V. Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
- 10th June 2016 Christian Komusiewicz, André Nichterlein, Rolf Niedermeier. Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- 10th June 2016 Bart M.P. Jansen, Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials
- 9th June 2016 Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein, Mingxian Zhong. Approximately coloring graphs without long induced paths
- 8th June 2016 Wenjun Li, Yongjie Yang, Jianer Chen, Jianxin Wang. Further Kernelization of Proper Interval Vertex Deletion: New Observations and Refined Analysis
- 27th May 2016 Jason Crampton, Gregory Gutin, Rémi Watrigant. An Approach to Parameterized Resiliency Problems Using Integer Linear Programming
- 10th May 2016 Bart M. P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion
**10th May 2016 Mikołaj Bojańczyk, Michał Pilipczuk. Definability equals recognizability for graphs of bounded treewidth**- 10th May 2016 Riccardo Dondi, Florian Sikora. Parameterized Complexity and Approximation Issues for the Colorful Components Problems
- 9th May 2016 Andreas Emil Feldmann. Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- 3th May 2016 René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, Gerhard J. Woeginger. Precedence-constrained scheduling problems parameterized by partial order width
- 2nd May 2016 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh. A Linear Time Parameterized Algorithm for Node Unique Label Cover
- 20th April 2016 Eduard Eiben, Robert Ganian, O-joung Kwon. A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion
- 19th April 2016 René van Bevern, Christian Komusiewicz, Hendrik Molter, Rolf Niedermeier, Manuel Sorge, Toby Walsh. h-Index Manipulation by Undoing Merges
- 15th April 2016 Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Lossy Kernelization
- 7th April 2016 Jason Crampton, Gregory Gutin, Stéphane Pérennes, Rémi Watrigant. A Multivariate Approach for Checking Resiliency in Access Control
- 7th April 2016 Mojgan Pourhassan, Feng Shi, Frank Neumann. Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover Problem
- 21st March 2016 Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx. Parameterized vertex deletion problems for hereditary graph classes with a block property
- 8th March 2016 Dušan Knop, Martin Koutecký. Scheduling meets n-fold Integer Programming
- 3rd March 2016 René van Bevern, Artem V. Pyatkin. Completing partial schedules for Open Shop with unit processing times and routing
- 2nd March 2016 Fedor V. Fomin, Torstein J. F. Strømme. Vertex Cover Structural Parameterization Revisited
- 26th February 2016 Matthias Mnich, Ildikó Schlotter. Stable Marriage with Covering Constraints: A Complete Computational Trichotomy
- 19th February 2016 Johannes K. Fichte, Arne Meier, Irina Schindler. Strong Backdoors for Default Logic
- 18th February 2016 Arturs Backurs, Nishanth Dikkala, Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles
- 17th February 2016 Łukasz Kowalik, Juho Lauri, Arkadiusz Socała. On the fine-grained complexity of rainbow coloring
- 8th February 2016 Maria Anaya, Olga Anipchenko-Ulaj, Aisha Ashfaq, Joyce Chiu, Mahedi Kaiser, Max Shoji Ohsawa, Megan Owen, Ella Pavlechko, Katherine St. John, Shivam Suleria, Keith Thompson, Corrine Yap. On Determining if Tree-based Networks Contain Fixed Trees
- 8th February 2016 Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan. Metric Dimension of Bounded Tree-length Graphs
- 4th February 2016 Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, Manuel Sorge. The Parameterized Complexity of the Minimum Shared Edges Problem
- 4th February 2016 Jesper Nederlof. A short note on Merlin-Arthur protocols for subset sum
- 3rd February 2016 Andreas Björklund, Petteri Kaski. How proofs are prepared at Camelot
- 19th January 2016 Édouard Bonnet, László Egri, Dániel Marx. Fixed-parameter Approximability of Boolean MinCSPs
- 19th January 2016 Florent Foucaud, Ralf Klasing. Parameterized and approximation complexity of the detection pair problem in graphs
- 19th January 2016 Ryan Williams. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
- 18th January 2016 Sang-il Oum. Rank-width: Algorithmic and structural results
- 11th January 2016 Hans L. Bodlaender, Jesper Nederlof. Subexponential time algorithms for finding small tree and path decompositions
- 2nd January 2016 Mingyu Xiao. On a generalization of Nemhauser and Trotter's local optimization theorem
- 23rd December 2015 Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu. Reduction rules for the maximum parsimony distance on phylogenetic trees
- 16th December 2015 Luerbio Faria, Sulamita Klein, Ignasi Sau, Rubens Sucupira. Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs
- 13th December 2015 René van Bevern, Vincent Froese, Christian Komusiewicz. Parameterizing edge modification problems above lower bounds
- 10th December 2015 Matthias Mnich, Heiko Röglin, Clemens Rösner. New Deterministic Algorithms for Solving Parity Games
- 10th December 2015 Stefano Beretta, Mauro Castelli, Riccardo Dondi. Parameterized Tractability of the Maximum-Duo Preservation String Mapping Problem
- 10th December 2015 Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier. Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
- 8th December 2015 Petr Hliněný, Marek Derňár. Crossing Number is Hard for Kernelization
- 8th December 2015 Eva-Maria C. Hols, Stefan Kratsch. A randomized polynomial kernel for Subset Feedback Vertex Set
- 3rd December 2015 Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy. Hitting Set in hypergraphs of low VC-dimension
- 3rd December 2015 Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge. Exploiting Hidden Structure in Selecting Dimensions that Distinguish Vectors
- 24th November 2015 Pradeesha Ashok, Sudeshna Kolay, Saket Saurabh. Multivariate Complexity Analysis of Geometric Red Blue Set Cover
- 25th November 2015 Radu Curticapean. Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
- 17th November 2015 Christian Komusiewicz. Tight Running Time Lower Bounds for Vertex Deletion Problems
- 17th November 2015 Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs
- 11th November 2015 Shmuel Onn. Unimodular Integer Caratheodory is Fixed Parameter Tractable
- 11th November 2015 Radu Curticapean. Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity
- 5th November 2015 Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- 13th October 2015 Florian Barbero, Gregory Gutin, Mark Jones, Bin Sheng, Anders Yeo. Linear-Vertex Kernel for the Problem of Packing r-Stars into a Graph without Long Induced Paths
- 12th October 2015 Luke Mathieson. Graph Editing Problems with Extended Regularity Constraints
- 6th October 2015 Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective
- 3rd October 2015 Junjie Ye. A Note on Finding Dual Feedback Vertex Set
- 2nd October 2015 Marin Bougeret, Stephane Bessy, Daniel Gonçalves, Cristophe Paul. On independent set on B1-EPG graphs
- 1st October 2015 Piotr Skowron. FPT Approximation Schemes for Maximizing Submodular Functions
- 29th September 2015 N. R. Aravind, R. B. Sandeep, Naveen Sivadasan. Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
- 28th September 2015 Thomas O'Neil. Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability
- 24th September 2015 Bart M.P. Jansen, Astrid Pieterse. Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT
- 24th September 2015 Eunjung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
- 23rd September 2015 Max Bannach, Christoph Stockhusen, Till Tantau. Fast Parallel Fixed-Parameter Algorithms via Color Coding
- 19th September 2015 Yi Fan, Chengqian Li, Zongjie Ma, LjiLjana Brankovic, Vladimir Estivill-Castro, Abdul Sattar. Exploiting Reduction Rules and Data Structures: Local Search for Minimum Vertex Cover in Massive Graphs
- 19th September 2015 Michał Pilipczuk, Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs
- 18th September 2015 Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Lower bounds for approximation schemes for Closest String
- 18th September 2015 Leizhen Cai, Junjie Ye. Finding Two Edge-Disjoint Paths with Length Constraints
- 18th September 2015 Kitty Meeks. Randomised enumeration of small witnesses using a decision oracle
- 18th September 2015 Ashutosh Rai, M. S. Ramanujan, Saket Saurabh. A Parameterized Algorithm for Mixed Cut
- 18th September 2015 Backdoors into Heterogeneous Classes of SAT and CSP. Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, Stanislav Živný
- 17th September 2015 Eunjung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition
- 15th September 2015 Shivam Garg, Geevarghese Philip. Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
- 9th September 2015 Tom C. van der Zanden. Parameterized Complexity of Graph Constraint Logic
- 9th September 2015 Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider. Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility
- 5th September 2015 Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała. Linear kernels for outbranching problems in sparse digraphs
- 3rd September 2015 Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, Renato F. Werneck. Finding Near-Optimal Independent Sets at Scale
- 1st September 2015 Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, Björn Orri Sæmundsson. Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring (Extended Version)
- 1st September 2015 Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk, André Schulz, Darren Strash. On Minimizing Crossings in Storyline Visualizations
- 27th August 2015 Gregory Gutin, Magnus Wahlstrom. Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis
- 27th August 2015 Thiago Braga Marcilon, Rudini Menezes Sampaio. The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results
- 25th August 2015 Per Austrin, Mikko Koivisto, Petteri Kaski, Jesper Nederlof. Dense Subset Sum may be the hardest
- 21st August 2015 Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach, Michal Pilipczuk. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
- 14th August 2015 Andreas Björklund, Petteri Kaski, Łukasz Kowalik. Fast Witness Extraction Using a Decision Oracle
- 12th August 2015 Ronald de Haan. An Overview of Non-Uniform Parameterized Complexity
- 11th August 2015 Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma, Dimitrios M. Thilikos. Editing to a Planar Graph of Given Degrees
- 7th August 2015 René van Bevern, Rolf Niedermeier, Ondřej Suchý. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- 5th August 2015 Vincent Froese, Iyad Kanj, André Nichterlein, Rolf Niedermeier. Finding Points in General Position
- 31st July 2015 R. B. Sandeep, Naveen Sivadasan. Parameterized lower bound and improved kernel for Diamond-free Edge Deletion
- 29th July 2015 Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar. Fast Biclustering by Dual Parameterization
- 27th July 2015 Nader H. Bshouty, Ariel Gabizon. Almost Optimal Cover-Free Families
- 22nd July 2015 N. R. Aravind, R. B. Sandeep, Naveen Sivadasan. Parameterized lower bound and NP-completeness of some H-free Edge Deletion problems
- 21st July 2015 Bart M. P. Jansen. On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT
- 20th July 2015 Eduard Eiben, Robert Ganian, Stefan Szeider. Meta-Kernelization using Well-Structured Modulators
- 20th July 2015 Eduard Eiben, Robert Ganian, Stefan Szeider. Solving Problems on Graphs of High Rank-Width
- 14th July 2015 Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
- 13th July 2015 Maurice Chandoo. Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace
- 13th July 2015 Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin. Polynomial Kernels for Weighted Problems
- 9th July 2015 Robert Ganian, M. S. Ramanujan, Stefan Szeider. Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
- 9th July 2015 Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle. Maximum matching width: new characterizations and a fast algorithm for dominating set
- 8th July 2015 Konstantinos Koiliaris, Chao Xu. A Faster Pseudopolynomial Time Algorithm for Subset Sum
- 8th July 2015 Jisu Jeong, Eun Jung Kim, Sang-il Oum. Constructive algorithm for path-width of matroids
- 8th July 2015 Marcin Pilipczuk, Magnus Wahlström. Directed multicut is W1-hard, even for four terminal pairs
- 8th July 2015 Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna. Edge Bipartization faster than 2k
- 7th July 2015 Vincent Cohen-Addad, Arnaud de Mesmay. A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
- 7th July 2015 Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki. On the pathwidth of almost semicomplete digraphs
- 30th June 2015 Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, David R. Wood. Track Layouts, Layered Path Decompositions, and Leveled Planarity
- 29th June 2015 Eun Jung Kim, O-joung Kwon. A polynomial kernel for Block Graph Vertex Deletion
- 25th June 2015 Canonizing Graphs of Bounded Tree Width in Logspace. Michael Elberfeld, Pascal Schweitzer
- 25th June 2015 Bart M. P. Jansen, Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth and Total Unimodularity
- 24th June 2015 Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos. Algorithmic Aspects of Upper Domination
- 11th June 2015 Rajesh Chitnis, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Saeed Seddighin. A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands
- 10th June 2015 Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau, Rémi Watrigant. Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
- 5th June 2015 Amir Abboud, Virginia Vassilevska Williams, Joshua Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
- 4th June 2015 David Eppstein. Metric Dimension Parameterized by Max Leaf Number
- 4th June 2015 Archontia C. Giannopoulou, George B. Mertzios, Rolf Niedermeier. Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs
- 4th June 2015 Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy. Polynomial-time Algorithm for Isomorphism of Graphs with Clique-width at most 3
- 2nd June 2015 Maise Dantas da Silva, Fábio Protti, Jayme Luiz Szwarcfiter. Parameterized mixed cluster editing via modular decomposition
- 19th May 2015 N. Bourgeois, R. Catellier, T. Denat, V. Th. Paschos. Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the G(n,p) random model
- 7th May 2015 Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon. Colouring graphs with constraints on connectivity
- 7th May 2015 Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova. Kernelization via Sampling with Applications to Dynamic Graph Streams
- 30th April 2015 Sudeshna Kolay, Fahad Panolan. Parameterized Algorithms for Deletion to (r,l)-graphs
- 30th April 2015 Stefan Fafianie, Stefan Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time
- 30th April 2015 Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein. ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- 29th April 2015 Thomas Bosman. A Solution Merging Heuristic for the Steiner Problem in Graphs Using Tree Decompositions
- 23rd April 2015 Martin Lück, Arne Meier. LTL Fragments are Hard for Standard Parameterisations
- 22nd April 2015 Jessica Enright, Kitty Meeks. Deleting edges to restrict the size of an epidemic
- 22nd April 2015 Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, Christophe Paul. FPT Algorithm and Polynomial Kernel for Linear Rank-width One Vertex Deletion
- 21st April 2015 Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau. Parameterized complexity dichotomy for (r,ℓ)-Vertex Deletion
- 21st April 2015 Dániel Marx, Michał Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
- 17th April 2015 Yixin Cao. Unit Interval Editing is Fixed-Parameter Tractable
- 14th April 2015 Jason Crampton, Andrei Gagarin, Gregory Gutin, Mark Jones. On the Workflow Satisfiability Problem with Class-Independent Constraints
- 14th April 2015 Andreas Björklund. Uniquely Coloring Graphs over Path Decompositions
- 11th April 2015 Marek Cygan, Jakub Pachocki, Arkadiusz Socała. The Hardness of Subgraph Isomorphism
- 9th April 2015 D. Cohen, J. Crampton, A. Gagarin, G. Gutin, M. Jones. Algorithms for the workflow satisfiability problem engineered for counting constraints
- 27th March 2015 Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa. Parameterized Complexity of Asynchronous Border Minimization
- 24th March 2015 Meirav Zehavi. Maximization Problems Parameterized Using Their Minimization Versions: The Case of Vertex Cover
- 17th March 2015 Édouard Bonnet, Florian Sikora. The parameterized complexity of Graph Motif relatively to the structure of the input graph
- 13th March 2015 Konstantin Makarychev, Yury Makarychev, Yuan Zhou. Satisfiability of Ordering CSPs Above Average
- 10th March 2015 Rémy Belmonte, Yuya Higashikawa, Naoki Katoh, Yoshio Okamoto. Polynomial-time approximability of the k-Sink Location problem
- 10th March 2015 Jianer Chen, Chao Xu. Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm
- 4th March 2015 Eun Jung Kim, Martin Milanic, Oliver Schaudt. Recognizing k-equistable graphs in FPT time
- 26th February 2015 Luis Pedro Montejano, Ignasi Sau. On the complexity of computing the k-restricted edge-connectivity of a graph
- 26th February 2015 Meirav Zehavi. The k-Leaf Spanning Tree Problem Admits a Klam Value of 39
- 23th February 2015 Jannis Bulian, Anuj Dawar. Fixed-parameter Tractable Distances to Sparse Graph Classes
- 18th February 2015 Petr Kolman, Martin Koutecký. Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
- 17th February 2015 Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.S. Ramanujan, Saket Saurabh. Reconfiguration on sparse graphs
- 16th February 2015 Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post. A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- 13th Feburary 2015 Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems
- 13th Feburary 2015 Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh. Uniform Kernelization Complexity of Hitting Forbidden Minors
- 6th February 2015 Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized Complexity of Superstring Problems
- 3rd February 2015 Glencora Borradaile, Hung Le. Optimal dynamic program for r-domination problems over tree decompositions
- 3rd February 2015 Éric Colin de Verdière. Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
- 30th January 2015 Jason Crampton, Gregory Z. Gutin, Daniel Karapetyan. Valued Workflow Satisfiability Problem
- 30th January 2015 Subhash Khot, Igor Shinkar. On Hardness of Approximating the Parameterized Clique Problem
**28th January 2015 Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams. Quadratic-Time Hardness of LCS and other Sequence Similarity Measures**- 3rd January 2015 Meirav Zehavi. Algorithms for Special Cases of the k-Internal Spanning Tree Problem
- 23rd December 2014 Pål Grønås Drange, Michał Pilipczuk. A Polynomial Kernel for Trivially Perfect Editing
- 17th December 2014 René van Bevern, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Toby Walsh. On Google Scholar H-Index Manipulation by Merging Articles
- 12th December 2014 Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos. The Parameterized Complexity of Graph Cyclability
- 9th December 2014 F. Barbero, G. Gutin, M. Jones, B. Sheng. Parameterized and Approximation Algorithms for Load Coloring Problem
- 4th December 2014 Travis Gagie, Simon J. Puglisi. Searching and Indexing Genomic Databases via Kernelization
- 4th December 2014 Ken-ichi Kawarabayashi, Anastasios Sidiropoulos. Beyond the Euler characteristic: Approximating the genus of general graphs
- 3rd December 2014 Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora. On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
- 2nd December 2014 Yinglei Song. On the Induced Matching Problem in Hamiltonian Bipartite Graphs
- 25th November 2014 Ariel Gabizon, Daniel Lokshtanov, Michal Pilipczuk. Representative sets for multisets
- 25th November 2014 Henning Fernau, Alejandro López-Ortiz, Jazmín Romero. Kernelization Algorithms for Packing Problems Allowing Overlaps
- 21st November 2014 Sigve Hortemo Sæther. Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter
- 17th November 2014 Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Somnath Sikdar. Kernelization and Sparseness: the case of Dominating Set
- 15th November 2014 Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth
- 11th November 2014 Takuya Akiba, Yoichi Iwata. Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
- 4th November 2014 Dániel Marx, Paul Wollan. An exact characterization of tractable demand patterns for maximum disjoint path problems
- 4th November 2014 Yuan Li, Alexander Razborov, Benjamin Rossman. On the AC0 Complexity of Subgraph Isomorphism
- 3rd November 2014 Stefan Kratsch, Manuel Sorge. On Kernelization and Approximation for the Vector Connectivity Problem
- 3rd November 2014 Ronald de Haan, Stefan Szeider. Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
- 2nd November 2014 Igor Razgon. On the read-once property of branching programs and CNFs of bounded treewidth
- 1st November 2014 Feng Shi, Jianer Chen, Qilong Feng, Xiaojun Ding, Jianxin Wang. Algorithms for Maximum Agreement Forest of Multiple General Trees
- 23th October 2014 Nikolaos Fountoulakis, Tobias Friedrich, Danny Hermelin. On the Average-case Complexity of Parameterized Clique
- 20th October 2014 Gregory Gutin, Mark Jones, Magnus Wahlstrom. Structural Parameterizations of the Mixed Chinese Postman Problem
- 19th October 2014 Meirav Zehavi. Solving Parameterized Problems by Mixing Color Coding-Related Techniques
- 15th October 2014 Martin Lück, Arne Meier, Irina Schindler. Parameterized Complexity of CTL: A Generalization of Courcelle's Theorem
- 13th October 2014 Mark Jerrum, Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs
- 8th October 2014 Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: speeding up algorithms for NP-hard problems using FFT
- 4th October 2014 Chandra Chekuri, Julia Chuzhoy. Degree-3 Treewidth Sparsifiers
- 3rd October 2014 Bart M. P. Jansen, Dániel Marx. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- 2nd October 2014 Mateus de Oliveira Oliveira. An Algorithmic Metatheorem for Directed Treewidth
- 1st October 2014 Julia Chuzhoy. Improved Bounds for the Flat Wall Theorem
- 30th September 2014 Yann Disser, Stefan Kratsch, Manuel Sorge. The Minimum Feasible Tileset problem
- 30th September 2014 Friedrich Slivovsky, Stefan Szeider. Model Counting for Formulas of Bounded Clique-Width
- 27th September 2014 Ankit Chauhan, B. V. Raghavendra Rao. Parameterized Analogues of Probabilistic Computation
- 25th September 2014 Gregory Gutin, Stefan Kratsch, Magnus Wahlström. Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
- 24th September 2014 Zoltán Király. Shortest Paths in Nearly Conservative Digraphs
- 17th September 2014 Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh. Finding Even Subgraphs Even Faster
- 12th September 2014 Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau. Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
- 8th September 2014 Sebastian Ordyniak, Alexandru Popa. A Parameterized Study of Maximum Generalized Pattern Matching Problems
- 28th August 2014 Steven Chaplick, Jiří Fiala, Pim van 't Hof, Daniël Paulusma, Marek Tesař. Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
- 27th August 2014 Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos. A linear kernel for planar red-blue dominating set
- 27th August 2014 Michael J. Bannister, David Eppstein. Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
- 26th August 2014 Mingyu Xiao, Hiroshi Nagamochi. Exact Algorithms for Dominating Induced Matching Based on Graph Partition
- 26th August 2014 Constantin Enea, Peter Habermehl, Omar Inverso, Gennaro Parlato. On the Path-Width of Integer Linear Programming
- 22th August 2014 Vikraman Arvind, Gaurav Rattan. Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity
- 7th August 2014 Ann Becker, Reuven Bar-Yehuada, Dan Geiger. Random Algorithms for the Loop Cutset Problem
- 5th August 2014 Hubie Chen, Stefan Mengel. A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
- 3rd August 2014 Gregory Gutin, Viresh Patel. Parameterized TSP: Beating the Average
- 29th July 2014 Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran. Solving Linear Equations Parameterized by Hamming Weight
- 28th July 2014 Robert F. Erbacher, Trent Jaeger, Nirupama Talele, Jason Teutsch. Directed Multicut with linearly ordered terminals
- 26th July 2014 Arkadiusz Socala. Tight lower bound for the channel assignment problem
- 26th July 2014 Assigning channels via the meet-in-the-middle approach. Łukasz Kowalik, Arkadiusz Socała
- 26th July 2014 On Polynomial Kernelization of H-free Edge Deletion. N. R. Aravind, R. B. Sandeep, Naveen Sivadasan
- 22nd July 2014 Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora. Complexity of Grundy coloring and its variants
- 11th July 2014 Radu Curticapean, Dániel Marx. Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
- 8th July 2014 Hadas Shachnai, Meirav Zehavi. FPT Algorithms for Weighted Graphs Can be (Almost) as Efficient as for Unweighted
- 7th July 2014 Henri Perret du Cray, Ignasi Sau. Improved FPT algorithms for weighted independent set in bull-free graphs
- 6th July 2014 Iyad Kanj, Ge Xia. Flip Distance is in FPT time O(n+k⋅ck)
- 6th July 2014 Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song. A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
- 3th July 2014 Igor Razgon. No small nondeterministic read-once branching programs for CNFs of bounded treewidth
- 25th June 2014 Takehiro Ito, Marcin Kamiński, Hirotaka Ono. Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- 19th June 2014 Jannis Bulian, Anuj Dawar. Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
**14th June 2014 Bingkai Lin. The Parameterized Complexity of k-Biclique**- 13th June 2014 Martin Furer, Huiwen Yu. Space Saving by Dynamic Algebraization
- 12th June 2014 Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, Hannes Uppman. Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- 12th June 2014 Serge Gaspers, Stefan Szeider. Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning
- 4th June 2014 Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach. Kernelization lower bound for Permutation Pattern Matching
- 2nd June 2014 Stefan Hougardy, Jannik Silvanus, Jens Vygen. Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
- 30th May 2014 Yixin Cao, Dániel Marx. Chordal Editing is Fixed-Parameter Tractable
- 29th May 2014 Paola Bonizzoni, Anna Paola Carrieri, Gianluca Della Vedova, Gabriella Trucco. Algorithms for the Constrained Perfect Phylogeny with Persistent Characters
- 28th May 2014 Jacob D. Biamonte, Jason Morton, Jacob W. Turner. Tensor Network Contractions for #SAT
- 27th May 2014 Kenya Ueno. Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
- 21st May 2014 Ante Ćustić, Bettina Klinz, Gerhard J. Woeginger. Planar 3-dimensional assignment problems with Monge-like cost arrays
- 17th May 2014 Holger Dell. A simple proof that AND-compression of NP-complete problems is hard
- 13th May 2014 Simone Bova, Robert Ganian, Stefan Szeider. Model Checking Existential Logic on Partially Ordered Sets
- 6th May 2014 Stefan Fafianie, Stefan Kratsch. Streaming Kernelization
- 1st May 2014 Rajesh Chitnis, Graham Cormode, MohammadTaghi Hajaghayi, Morteza Monemizadeh. Parameterized Streaming Algorithms for Vertex Cover
- 30th April 2014 Markus Sortland Dregi, Daniel Lokshtanov. Parameterized Complexity of Bandwidth on Trees
- 30th April 2014 Sigve Hortemo Sæther, Jan Arne Telle. Between Treewidth and Clique-width
- 29th April 2014 Yoichi Iwata, Keigo Oka. Fast Dynamic Graph Algorithms for Parameterized Problems
- 28th April 2014 Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen. Parameterized Complexity Dichotomy for Steiner Multicut
- 22th April 2014 Mateus de Oliveira Oliveira. On the Satisfiability of Quantum Circuits of Small Treewidth
- 16th April 2014 Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- 14th April 2014 Clement Carbonnel, Martin C. Cooper, Emmanuel Hebrard. On Backdoors To Tractable Constraint Languages
- 3rd April 2014 Serge Gaspers, Gregory B. Sorkin. Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets
**3rd April 2014 Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth**- 1st April 2014 Paul Bonsma, Amer E. Mouawad. The Complexity of Bounded Length Graph Recoloring
- 25th March 2014 Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof. On the Computational Complexity of Vertex Integrity
- 25th March 2014 Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma. Colouring Reconfiguration Is Fixed-Parameter Tractable
- 14th March 2014 Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations
- 10th March 2014 Michael Lampis, Kazuhisa Makino, Valia Mitsou, Yushi Uno. Parameterized Edge Hamiltonicity
- 8th March 2014 Olawale Hassan, Iyad Kanj, Daniel Lokshtanov, Ljubomir Perković. On the Ordered List Subgraph Embedding Problems
- 6th March 2014 Yixin Cao. Linear Recognition of Almost (Unit) Interval Graphs
- 6th March 2014 Gregory Gutin, Mark Jones, Bin Sheng. Parameterized Complexity of the k-Arc Chinese Postman Problem
- 1st March 2014 Hadas Shachnai, Meirav Zehavi. Parameterized Algorithms for Graph Partitioning Problems
- 28th February 2014 Alexander Grigoriev, Steven Kelk, Nela Lekic. On low treewidth graphs and supertrees
- 26th February 2014 Sigve Hortemo Sæther, Jan Arne Telle, Martin Vatshelle. Solving MaxSAT and #SAT on structured CNF formulas
- 24th February 2014 Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems
- 20th February 2014 Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman. Vertex Cover Reconfiguration and Beyond
- 19th February 2014 Bart M. P. Jansen. Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
- 17th February 2014 Benjamin A. Burton, William Pettersson. Fixed parameter tractable algorithms in combinatorial topology
- 17th February 2014 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh. Representative Sets of Product Families
- 14th February 2014 Hadas Shachnai, Meirav Zehavi. Faster Computation of Representative Families for Uniform Matroids with Applications
- 13th February 2014 Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk. A subexponential parameterized algorithm for Interval Completion
- 13th February 2014 Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk. A subexponential parameterized algorithm for Proper Interval Completion
- 10th February 2014 Gregory Gutin, Mark Jones, Bin Sheng, Magnus Wahlstrom. Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs
- 8th February 2014 Martin Fürer. A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- 4th February 2014 René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller. Interval scheduling and colorful independent sets
- 24th January 2014 Songjian Lu, Xinghua Lu. An exact algorithm for the weighed mutually exclusive maximum set cover problem
- 18th January 2014 Léon R. Planken, Mathijs M. de Weerdt, Roman P.J. van der Krogt. Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
- 16th January 2014 Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon. Soft Constraints of Difference and Equality
- 11th January 2014 Shiva Kintali. Directed Width Parameters and Circumference of Digraphs
- 11th January 2014 Jiong Guo, Yash Raj Shrestha. Parameterized Complexity of Edge Interdiction Problems
- 25th December 2013 René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý. On the Parameterized Complexity of Computing Balanced Partitions in Graphs
- 17th December 2013 Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, Elad Haramaty. On r-Simple k-Path
- 10th December 2013 Julien Baste, Ignasi Sau The role of planarity in connectivity problems parameterized by treewidth
- 5th December 2013 Ronald de Haan, Stefan Szeider. The Parameterized Complexity of Reasoning Problems Beyond NP
- 5th December 2013 Saeed Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz. Vertex Disjoint Path in Upward Planar Graphs
- 22th November 2013 Janka Chlebíková, Morgan Chopin. The Firefighter Problem: A Structural Analysis
- 20th November 2013 Petr A. Golovach. Editing to a Graph of Given Degrees
- 16th November 2013 Matthias Mnich, Andreas Wiese. Scheduling Meets Fixed-Parameter Tractability
- 16th November 2013 Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger. Largest chordal and interval subgraphs faster than 2^n
- 13th November 2013 Amir Abboud, Kevin Lewi, Ryan Williams. On the parameterized complexity of k-SUM
- 12th November 2013 Zdenek Dvorak, Matthias Mnich. Large Independent Sets in Triangle-Free Planar Graphs
- 11th November 2013 Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Minimum Bisection is fixed parameter tractable
- 11th November 2013 Michael Lampis. Parameterized Approximation Schemes using Graph Widths
- 4th November 2013 Sang-il Oum, Sigve Hortemo Sæther, Martin Vatshelle. Faster Algorithms Parameterized by Clique-width
- 29th October 2013 Christer Baeckstroem, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider. A Complete Parameterized Complexity Analysis of Bounded Planning
- 24th October 2013 Mark Jerrum, Kitty Meeks. Some hard classes of parameterised counting problems
- 22nd October 2013 Leizhen Cai, Chengwei Guo. Contracting Graphs to Split Graphs and Threshold Graphs
- 21st October 2013 Edouard Bonnet, Vangelis Th. Paschos. Parameterized (in)approximability of subset problems
- 21st October 2013 Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma. Parameterized Algorithms for Finding Square Roots
- 12th October 2013 Paweł Rzażewski. Exact Algorithm for Graph Homomorphism and Locally Injective Graph Homomorphism
- 10th October 2013 Magnus Wahlström, Half-integrality, LP-branching and FPT Algorithms
- 10th October 2013 Mohammad T. Hajiaghayi, Rohit Khandekar, Guy Kortsarz. The Foundations of Fixed Parameter Inapproximability
- 9th October 2013 Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabhh, Dimitrios M. Thilikos. Irrelevant Vertices for the Planar Disjoint Paths Problem
- 9th October 2013 Janka Chlebíková, Morgan Chopin. The Firefighter Problem: A Structural Analysis
- 8th October 2013 Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu. Detecting Monomials with k Distinct Variables
- 30th September 2013 Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, Ondrej Suchy. Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) approximation)
- 26th September 2013 Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michał Pilipczuk. Minimizing Rosenthal Potential in Multicast Games
- 25th September 2013 The Computational Complexity of the Game of Set and its Theoretical Applications. Michael Lampis, Valia Mitsou
- 24th September 2013 Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange, Vangelis Th. Paschos. Playing with Parameters: Cross-parameterization in Graphs
- 24th September 2013 Arijit Bishnu, Arijit Ghosh, Subhabrata Paul. Parameterized complexity of k-tuple and liar's domination
- 20th September 2013 Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson. Augmenting graphs to minimize the diameter
- 19th September 2013 Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive, Heribert Vollmer. Parameterized Enumeration with Ordering
- 18th September 2013 Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora. Multiparameterizations for max $k$-set cover and related satisfiability problems
- 17th September 2013 Piotr Skowron, Piotr Faliszewski. Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
- 16th September 2013 Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger. Exploring Subexponential Parameterized Complexity of Completion Problems
- 27th August 2013 Michael J. Bannister, David Eppstein, Joseph A. Simons Fixed parameter tractability of crossing minimization of almost-trees
- 18th August 2013 Igor Razgon. On OBDDs for CNFs of bounded treewidth
- 16th August 2013 Bart M. P. Jansen. On Sparsification for Computing Treewidth
- 15th August 2013 Liang Ding, Abdul Samad, Xingran Xue, Xiuzhen Huang, Liming Cai. Polynomial kernels collapse the W-hierarchy
- 15th August 2013 Rajesh Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz. Fixed-Parameter and Approximation Algorithms: A New Look
- 13th August 2013 Jakub Gajarský, Michael Lampis, Sebastian Ordyniak. Parameterized Algorithms for Modular-Width
- 13th August 2013 Christoph Stockhusen, Till Tantau. Completeness Results for Parameterized Space Classes
- 12th August 2013 Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
- 12th August 2013 Gregory Gutin, Magnus Wahlstrom, Anders Yeo. Parameterized Rural Postman and Conjoining Bipartite Matching Problems
- 11th August 2013 Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, Akira Suzuki. On the Parameterized Complexity of Reconfiguration Problems
- 8th August 2013 Gregory Gutin, Mark Jones. Parameterized Algorithms for Load Coloring Problem
- 8th August 2013 Petr A. Golovach. Editing to a Connected Graph of Given Degrees
- 7th August 2013 Yinglei Song. On the Independent Set and Common Subgraph Problems in Random Graphs
- 7th August 2013 Mark Jerrum, Kitty Meeks. The Parameterised Complexity of Counting Connected Subgraphs
- 2nd August 2013 Gregory Gutin, Gabriele Muciaccia, Anders Yeo. Parameterized Complexity of k-Chinese Postman Problem
- 1st August 2013 Yinglei Song. An Improved Parameterized Algorithm for the Independent Feedback Vertex Set Problem
- 30th July 2013 Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz, Irena Rusu. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications
- 24th July 2013 Christian Knauer, Stefan König, Daniel Werner. Fixed Parameter Complexity and Approximability of Norm Maximization
- 19th July 2013 Michel X. Goemans, Thomas Rothvoss. Polynomiality for Bin Packing with a Constant Number of Item Types
- 18th July 2013 Yoichi Iwata, Keigo Oka, Yuichi Yoshida. Linear-Time FPT Algorithms via Network Flow
- 16th July 2013 Ronald de Haan, Anna Roubíčková, Stefan Szeider. Parameterized Complexity Results for Plan Reuse
- 11th July 2013 Sylvain Guillemot, Dániel Marx. Finding small patterns in permutations in linear time
- 9th July 2013 Avinatan Hassidim, Orgad Keller, Moshe Lewenstein, Liam Roditty. Finding the Minimum-Weight k-Path
- 9th July 2013 Stefan Kratsch, Geevarghese Philip, Saurabh Ray. Point Line Cover: The Easy Kernel is Essentially Tight
- 8th July 2013 Dániel Marx, Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
- 27th June 2013 Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- 23rd June 2013 Hubie Chen, Moritz Müller. The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
- 23rd June 2013 Robert Ganian, Jan Obdržálek. Expanding the expressive power of Monadic Second-Order logic on restricted graph classes
- 18th June 2013 Andreas Björklund, Petteri Kaski, Łukasz Kowalik. Counting thin subgraphs via packings faster than meet-in-the-middle time
- 17th June 2013 Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk. Fast branching algorithm for Cluster Vertex Deletion
- 17th June 2013 Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk. Computing Tree-depth Faster Than $2^{n}$
- 16th June 2013 David Cohen, Jason Crampton, Gregory Gutin, Mark Jones. Pattern-Based Plan Construction for the Workflow Satisfiability Problem
- 15th June 2013 Shenshi Chen, Zhixiang Chen. Faster Deterministic Algorithms for Packing, Matching and $t$-Dominating Set Problems
- 13th June 2013 Yixin Cao. An Efficient Branching Algorithm for Interval Completion
- 12th June 2013 Prachi Goyal, Vikram Kamat, Neeldhara Misra. On the Parameterized Complexity of the Maximum Edge Coloring Problem
- 11th June 2013 Yixin Cao. A note on small cuts for a terminal
- 10th June 2013 Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization
- 31st May 2013 Stefan Fafianie, Hans L. Bodlaender, Jesper Nederlof. Speeding-up Dynamic Programming with Representative Sets - An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions
- 28th May 2013 Chandra Chekuri, Julia Chuzhoy. Polynomial Bounds for the Grid-Minor Theorem
- 21st May 2013 Marek Cygan, Fabrizio Grandoni, Danny Hermelin. Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- 16th May 2013 On Structural Parameterizations for the 2-Club Problem. Sepp Hartung, Christian Komusiewicz, André Nichterlein, Ondrej Suchý
- 14th May 2013 Michael R. Fellows, Bart M. P. Jansen. FPT is Characterized by Useful Obstruction Sets
- 13th May 2013 Sylvain Guillemot, Dániel Marx. A faster FPT algorithm for Bipartite Contraction
- 3rd May 2013 Laurent Bulteau, Christian Komusiewicz. Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable
- 2nd May 2013 Johannes Klaus Fichte, Stefan Szeider. Backdoors to Normality for Disjunctive Logic Programs
- 2nd May 2013 Chris Whidden, Robert G. Beiko, Norbert Zeh. Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees
- 2nd May 2013 Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger. TREEWIDTH and PATHWIDTH parameterized by vertex cover
- 23rd April 2013 Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen. On the parameterized complexity of cutting a few vertices from a graph
- 23rd April 2013 Hans Bodlaender, Pål G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk. A O(c^k n) 5-Approximation Algorithm for Treewidth
- 22nd April 2013 Jaroslaw Blasiok, Marcin Kaminski. Chain minors are FPT
- 22nd April 2013 Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
- 22nd April 2013 Andreas Pfandler, Stefan Rümmele, Stefan Szeider. Backdoors to Abduction
- 21st April 2013 Long Circuits and Large Euler Subgraphs. Fedor V. Fomin, Petr A. Golovach
- 20th April 2013 Michael J. Bannister, Sergio Cabello, David Eppstein. Parameterized Complexity of 1-Planarity
- 19th April 2013 Ronald de Haan, Iyad Kanj, Stefan Szeider. Local Backbones
- 19th April 2013 Marijn J. H. Heule, Stefan Szeider. A SAT Approach to Clique-Width
- 19th April 2013 Neeldhara Misra, Sebastian Ordyniak, Venkatesh Raman, Stefan Szeider. Upper and Lower Bounds for Weak Backdoor Set Detection
- 16th April 2013 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh. Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- 15th April 2013 Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
- 12th April 2013 Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu. Algorithms for Cut Problems on Trees
- 10th April 2013 Yongjie Yang, Jiong Guo. Exact Algorithms for Weighted and Unweighted Borda Manipulation Problems
- 8th April 2013 Chandra Chekuri, Anastasios Sidiropoulos. Approximation algorithms for Euler genus and related problems
- 7th April 2013 Iyad Kanj, Stefan Szeider. On the Subexponential Time Complexity of CSP
- 4th April 2013 Chandra Chekuri, Julia Chuzhoy. Large-Treewidth Graph Decompositions and Applications
- 31st March 2013 Panos Giannopoulos, Christian Knauer. Finding a largest empty convex subset in space is W[1-hard]
- 30th March 2013 Krishnendu Chatterjee, Jakub Ł\kacki. Faster Algorithms for Markov Decision Processes with Low Treewidth
- 28th March 2013 Benjamin A. Burton, Thomas Lewiner, João Paixão, Jonathan Spreer. Parameterized Complexity of Discrete Morse Theory
- 27th March 2013 Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora. Parameterized Approximability of Maximizing the Spread of Influence in Networks
- 27th March 2013 Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano, M. Milanic, Ugo Vaccaro. Latency-Bounded Target Set Selection in Social Networks
- 27th March 2013 Bang Ye Wu, Li-Hsuan Chen. Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
- 18th March 2013 Mateus de Oliveira Oliveira. Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
- 7th March 2013 Robert Ganian, Friedrich Slivovsky, Stefan Szeider. Meta-Kernelization with Structural Parameters
- 7th March 2013 R.Krithika, N.S.Narayanaswamy. Another Disjoint Compression Algorithm for OCT
- 7th March 2013 N.S. Narayanaswamy, R. Subashini. $d$-COS-R is FPT via Interval Deletion
- 4th March 2013 Per Austrin, Petteri Kaski, Mikko Koivisto, Jussi Määttä. Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
- 3rd March 2013 Shenshi Chen. Monomial Testing and Applications
- 27th February 2013 Jakub Gajarsky, Petr Hlineny, Jan Obdrzalek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, Somnath Sikdar. Kernelization Using Structural Parameters on Sparse Graph Classes
- 26th February 2013 Shenshi Chen, Yaqing Chen, Quanhai Yang. Towards Randomized Testing of $q$-Monomials in Multivariate Polynomials
- 18th February 2013 Michael Lampis. Model Checking Lower Bounds for Simple Graphs
- 15th February 2013 Marek Cygan, Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree
- 14th February 2013 Stefan Kratsch. On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- 14th February 2013 Stefan Kratsch. On Polynomial Kernels for Sparse Integer Linear Programs
- 12th February 2013 Dariusz Dereniowski, Wieslaw Kubiak, Yori Zwols. Minimum length path decompositions
- 8th February 2012 Serge Gaspers, Victor Naroditskiy, Nina Narodytska, Toby Walsh. Possible and Necessary Winner Problem in Social Polls
- 30th January 2013 Fedor V. Fomin, Michał Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
- 30th January 2013 Andreas Björklund, Thore Husfeldt. The Parity of Directed Hamiltonian Cycles
- 16th January 2013 Hasan Abasi, Nader Bshouty. A Simple Algorithm for Undirected Hamiltonicity
- 8th January 2013 Magnus Wahlström. Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
- 3rd January 2013 Vikraman Arvind. The Parameterized Complexity of some Permutation Group Problems
- 31st Dec 2012 R. Crowston, G. Gutin, M. Jones, G. Muciaccia. Maximum Balanced Subgraph Problem Parameterized Above Lower Bound
- 1st Dec 2012 R. Crowston, G. Gutin, M. Jones, V. Raman, S. Saurabh, A. Yeo. Fixed-parameter tractability of satisfying beyond the number of variables
- 1st Dec 2012 R. Crowston, G. Gutin, M. Jones, S. Saurabh, A. Yeo. Parameterized Study of the Test Cover Problem
- 30th Nov 2012 Daniel Apon, William Gasarch, Kevin Lawler. The Complexity of Grid Coloring
- 28th Nov 2012 Bruno Escoffier, EunJung Kim, Vangelis Th. Paschos. Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
**27th Nov 2012 Yixin Cao, Daniel Marx. Interval Deletion is Fixed-Parameter Tractable**- 19th Nov 2012 Arash Rafiey. Single Exponential FPT Algorithm for Interval Vertex Deletion and Interval Completion Problem
- 14th Nov 2012 Martin Cadek, Marek Krcal, Jiri Matousek, Lukas Vokrinek, Uli Wagner. Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
- 9th Nov 2012 Michael Elberfeld, Christoph Stockhusen, Till Tantau. On the Space Complexity of Parameterized Problems
- 7th Nov 2012 Sepp Hartung, André Nichterlein. On the Parameterized and Approximation Hardness of Metric Dimension
- 7th Nov 2012 Marek Cygan, Stefan Kratsch, Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings
**7th Nov 2012 Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time**- 6th Nov 2012 René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond. How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding
- 5th Nov 2012 Valentin Garnero, Ignasi Sau. A linear kernel for planar total dominating set
- 2nd Nov 2012 Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider. Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- 26th Oct 2012 Lane A. Hemaspaandra, Rahman Lavaee, Curtis Menton. Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control
- 16th Oct 2012 J. Crampton, R. Crowston, G. Gutin, M. Jones, M. S. Ramanujan. Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
- 1st Oct 2012 Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondřej Suchý. Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- 30th Sept 2012 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
- 28th Sept 2012 Robert Crowston, Gregory Gutin, Mark Jones, Gabriele Muciaccia, Anders Yeo. Parameterizations of Test Cover with Bounded Test Sizes
- 25th Sept 2012 David Cattanéo, Simon Perdrix. The Parameterized Complexity of Domination-type Problems and Application to Linear Codes
- 31st Aug 2012 Kristan Temme, Pawel Wocjan. Efficient Computation of the Permanent of Block Factorizable Matrices
- 9th Aug 2012 Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, Stefan Szeider. Don't Be Strict in Local Search!
- 9th Aug 2012 Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider. On Finding Optimal Polytrees
- 6th Aug 2012 Marek Cygan, Marcin Pilipczuk. On fixed-parameter algorithms for Split Vertex Deletion
- 30th July 2012 Steven Kelk, Celine Scornavacca. Towards the fixed parameter tractability of constructing minimal phylogenetic networks from arbitrary sets of nonbinary trees
- 24th July 2012 Archontia C. Giannopoulou, Iosif Salem, Dimitris Zoros. Effective Computation of Immersion Obstructions for Unions of Graph Classes
- 24th July 2012 Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondřej Suchý. Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
- 20th July 2012 Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth
- 19th July 2012 Lukasz Kowalik, Marcin Mucha. A 9k kernel for nonseparating independent set in planar graphs
- 19th July 2012 Lukasz Kowalik. Nonblocker in H-minor free graphs: kernelization meets discharging
- 17th July 2012 Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions
- 17th July 2012 Robert Crowston, Gregory Gutin, Mark Jones. Directed Acyclic Subgraph Problem Parameterized above Raman-Saurabh Bound
- 17th July 2012 Yitong Yin, Chihao Zhang. Approximate Counting via Correlation Decay on Planar Graphs
- 3rd July 2012 Andrew M. Sutton, Frank Neumann. A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem
- 3rd July 2012 Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions
- 29th June 2012 Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen. Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
- 26th June 2012 Kernelization Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch. Lower Bounds By Cross-Composition
- 21st June 2012 Andrei A. Bulatov, Dániel Marx. Constraint satisfaction parameterized by solution size
- 21st June 2012 Fedor V. Fomin, Bart M. P. Jansen, Michal Pilipczuk, Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
- 18th June 2012 Parametrized Complexity of Weak Odd Domination Problems. David Cattanéo, Simon Perdrix
- 18th June 2012 Cédric Bentz. A polynomial-time algorithm for planar multicuts with few source-sink pairs
- 15th June 2012 Chiranjit Chakraborty, Rahul Santhanam. Instance Compression for the Polynomial Hierarchy and Beyond
- 31 May 2012 Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx. Minimizing Movement: Fixed-Parameter Tractability
- 7 May 2012 Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
- 4 May 2012 Jason Crampton, Gregory Gutin, Anders Yeo. On the Parameterized Complexity of the Workflow Satisfiability Problem
- 27 April 2012 Serge Gaspers, Stefan Szeider. Strong Backdoors to Bounded Treewidth SAT
- 23 April 2012 Petr A. Golovach, Pim van 't Hof, Daniel Paulusma. Obtaining Planarity by Contracting Few Edges
- 22 April 2012 Fedor V. Fomin, Saket Saurabh, Yngve Villanger. A Polynomial kernel for Proper Interval Vertex Deletion
- 19 April 2012 Fedor Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh. Planar F-Deletion: Approximation and Optimal FPT Algorithms
- 19 April 2012 G. Gutin, G. Muciaccia, A. Yeo. (Non-)existence of Polynomial Kernels for the Test Cover Problem
- 13 April 2012 Reinhard Pichler, Stefan Rümmele, Stefan Szeider, Stefan Woltran. Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough
- 10 April 2012 Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma. Finding vertex-surjective graph homomorphisms
- 6 April 2012 Eun Jung Kim, Christophe Paul, Geevarghese Philip. A single-exponential FPT algorithm for the $K_4$-minor cover problem
- 29 March 2012 Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang. Width-parameterized SAT: time-space tradeoffs
- 27 March 2012 Sergio Cabello, Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard
- 23 March 2012 Barnaby Martin. Parameterized Proof Complexity and W[1].
- 16 March 2012 Anthony Perez. On the kernelization of ranking r-CSP in tournaments
- 15 March 2012 Maise Dantas da Silva, Fábio Protti, Uéverton dos Santos Souza. Revisiting the Complexity of And/Or Graph Solution
- 13 March 2012 Eun Jung Kim, Daniel Goncalves. On Exact Algorithms for Permutation CSP
- 8 March 2012 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Known algorithms for EDGE CLIQUE COVER are probably optimal
- 5 March 2012 Daniel Loksthanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh. Faster Parameterized Algorithms using Linear Programming
- 2 March 2012 Joerg Flum, Moritz Müller. Some definitorial suggestions for parameterized proof complexity
- 29 Feb 2012 Marek Cygan. Deterministic parameterized connected vertex cover
- 26 Feb 2012 Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs
- 20 Feb 2012 Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen. Induced Disjoint Paths in Claw-Free Graphs
- 20 Feb 2012 Serge Gaspers, Stefan Szeider. Strong Backdoors to Nested Satisfiability
- 28 Jan 2012 Pascal Berthomé, Jean-François Lalande, Vincent Levorato. Implementation of exponential and parametrized algorithms in the AGAPE project
- 28 Jan 2012 Abhijin Adiga, Jasine Babu, L. Sunil Chandran. Parameterized and Approximation Algorithms for Boxicity
- 15 Jan 2012 Robert Ganian. Using Neighborhood Diversity to Solve Hard Problems
- 13 Jan 2012 Felix Reidl, Peter Rossmanith, Somnath Sikdar. Linear Kernels on Graphs Excluding Topological Minors
- 3 Jan 2012 Ronald de Haan, Nina Narodytska, Toby Walsh. The RegularGcc Matrix Constraint
- 2 Jan 2012 Wolfgang Dvořák. Technical Note: Exploring Σ^P_2 / Π^P_2-hardness for Argumentation Problems with fixed distance to tractable classes
- 21 Dec 2011 Juan Andrés Montoya and Moritz Müller. Parameterized Random Complexity
- 29 Dec 2011 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. On group feedback vertex set parameterized by the size of the cutset
- 20 Dec 2011 Sebastian Böcker, Quang Bao Anh Bui, Francois Nicolas, Anke Truss. Intractability of the Minimum-Flip Supertree problem and its variants
- 19 Dec 2011 Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger. Subexponential fixed-parameter tractability of cluster editing
- 15 Dec 2011 Robert Crowston, Mark Jones, Matthias Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound
- 14 Dec 2011 Fedor V. Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger. k-Gap Interval Graphs
- 10 Dec 2011 René van Bevern. Towards Optimal and Expressive Kernelization for d-Hitting Set
- 7 Dec 2011 Fedor V. Fomin, Michał Pilipczuk. Jungles, bundles, and fixed parameter tractability
- 5 Dec 2011 Iyad Kanj, Ge Xia. What makes normalized weighted satisfiability tractable
- 3 Dec 2011 Ashwinkumar Badanidiyuru, Robert Kleinberg, Hooyeon Lee. Approximating Low-Dimensional Coverage Problems
- 29 Nov 2011 James Nastos, Yong Gao. Bounded Search Tree Algorithms for Parameterized Cograph Deletion: Efficient Branching Rules by Exploiting Structures of Special Graph Classes
- 24 Nov 2011 Tractability results for the Double-Cut-and-Join circular median problem
**9 Nov 2011 Stefan Kratsch, Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization**- 4 Nov 2011 Martin Grohe, Dániel Marx. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- 2 Nov 2011 Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Clique cover and graph separation: New incompressibility results
- 31 Oct 2011 Chiara Braghin, Riccardo Dondi, Gabriella Trucco, Paola Bonizzoni. The Binary Perfect Phylogeny with Persistent characters
- 31 Oct 2011 Serge Gaspers, Stefan Szeider. Backdoors to Acyclic SAT
- 31 Oct 2011 Serge Gaspers, Stefan Szeider. Backdoors to Satisfaction
- 26 Oct 2011 R. Crowston, G. Gutin, M. Jones, A. Yeo. Parameterized Complexity of Satisfying Almost All Linear Equations over $\mathbb{F}_2$
- 24 Oct 2011 Dániel Marx, Barry O'Sullivan, Igor Razgon. Finding small separators in linear time via treewidth reduction
- 18 Oct 2011 Kitty Meeks, Alexander Scott. The Parameterised Complexity of List Problems on Graphs of Bounded Treewidth
- 10 Oct 2011 Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan. Towards optimal kernel for connected vertex cover in planar graphs
- 5 Oct 2011 Danny Hermelin, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, Xi Wu. Hierarchies of Inefficient Kernelizability
- 4 Oct 2011 Arne Meier, Johannes Schmidt, Michael Thomas, Heribert Vollmer. On the Parameterized Complexity of Default Logic and Autoepistemic Logic
- 3 Oct 2011 Rajesh Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx. Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- 2 Oct 2011 Minghui Jiang, Yong Zhang. Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- 27 Sep 2011 Robert Ganian, Petr Hliněný, Alexander Langer, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar. Lower Bounds on the Complexity of MSO1 Model-Checking
- 22 Sep 2011 Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen. Parameterized Complexity of Firefighting Revisited
- 9 Sep 2011 Marie-Louise Bruner, Martin Lackner. A W1-completeness result for permutation pattern matching
- 9 Sep 2011 Michael Lampis. A kernel of order 2k - c log k for vertex cover
- 24 Aug 2011 G. Gutin, A. Yeo. Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey
- 23 Aug 2011 Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman, Saket Saurabh. Parameterized Complexity of MaxSat Above Average
- 18 Aug 2011 Steven Kelk, Celine Scornavacca. Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
- 12 Aug 2011 Chris Whidden, Robert G. Beiko, Norbert Zeh. Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests
- 10 Aug 2011 Robert Bredereck. Graph and Election Problems Parameterized by Feedback Set Numbers
- 22 Jul 2011 Matthew P. Johnson, Deniz Sarioz. Computing the obstacle number of a plane graph
- 18 Oct 2010 Drew Mellor, Elena Prieto, Luke Mathieson, Pablo Moscato. A Kernelisation Approach for Multiple d-Hitting Set and Its Application in Optimal Multi-Drug Therapeutic Combinations