FPT papers online (historical record)

31st December 2021 Eduard Eiben, Gregory Gutin, Philip R. Neary, Clément Rambaud, Magnus Wahlström, Anders Yeo. Preference Swaps for the Stable Matching Problem
30th December 2021 Arindam Biswas, Venkatesh Raman, Srinivasa Rao Satti, Saket Saurabh. Space-Efficient FPT Algorithms
25th December 2021 Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen. Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs
22nd December 2021 Ebrahim Ardeshir-Larijani. Parametrized Complexity of Quantum Inspired Algorithms
19th December 2021 Arnab Maiti, Palash Dey. Parameterized Algorithms for Kidney Exchange
19th December 2021 Sayan Bandyapadhyay, Zachary Friggstad, Ramin Mousavi. Parameterized Approximation Algorithms for k-Center Clustering and Variants
16th December 2021 Argyrios Deligkas, Eduard Eiben, George Skretas. Minimizing Reachability Times on Temporal Graphs via Shifting Labels
16th December 2021 Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto, Vinicius F. dos Santos, Jayme L. Szwarcfiter. Disconnected Matchings
13th December 2021 Ameet Gadekar, Bruno Ordozgoiti, Suhas Thejaswi. A parameterized approximation algorithm for k-median with lower-bound constraints
13th December 2021 Sayan Bandyapadhyay, Fedor Fomin, Petr Golovach, William Lochet, Nidhi Purohit, Kirill Simonov. How to Find a Good Explanation for Clustering?
12th December 2021 Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Rolf Niedermeier. Temporal Unit Interval Independent Sets
9th December 2021 Xuandi Ren. A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More
8th December 2021 Antonis Antonopoulos, Aris Pagourtzis, Stavros Petsalakis, Manolis Vasilakis. Faster Algorithms for k-Subset Sum and Variations
7th December 2021 Karthik C. S., Subhash Khot. Almost Polynomial Factor Inapproximability for Parameterized k-Clique
6th December 2021 Yuriy Dementiev, Fedor V. Fomin, Artur Ignatiev. Inconsistent Planning: When in doubt, toss a coin!
6th December 2021 Vincent Froese, Leon Kellerhals, Rolf Niedermeier. Modification-Fair Cluster Editing
6th December 2021 Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, Simon Wietheger. Fixed-Parameter Sensitivity Oracles
28th November 2021 Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang. On Lower Bounds of Approximating Parameterized k-Clique
28th November 2021 Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue. Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
27th November 2021 Jan Derbisz. A polynomial kernel for vertex deletion into bipartite permutation graphs
23rd November 2021 Pål Grønås Drange, Irene Muzi, Felix Reidl. Kernelization and hardness of harmless sets in sparse classes
19th November 2021 Jelle J. Oostveen, Erik Jan van Leeuwen. Streaming Deletion Problems Parameterized by Vertex Cover
17th November 2021 Till Fluschnik, Pascal Kunz. Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring
11th November 2021 Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal, Daniel Vaz. Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
11th November 2021 Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo. A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
11th November 2021 Ameet Gadekar. On the parameterized complexity of Compact Set Packing
11th November 2021 Ajinkya Gaikwad, Soumen Maity. The Harmless Set Problem
10th November 2021 Radovan Červený, Ondřej Suchý. Generating faster algorithms for d-Path Vertex Cover
10th November 2021 Ajinkya Gaikwad, Soumen Maity. Defensive Alliances in Graphs
9th November 2021 Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer. Parameterized complexity of untangling knots
8th November 2021 Clément Dallard, Martin Milanič, Kenny Štorgel. Tree decompositions with bounded independence number and their algorithmic applications
7th November 2021 Zeev Nutov. k disjoint st-paths activation in polynomial time
5th November 2021 Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk, Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures
5th November 2021 Fedor V. Fomin, Tuukka Korhonen. Fast FPT-Approximation of Branchwidth
5th November 2021 Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Directed flow-augmentation
5th November 2021 Zhiyang He, Jason Li. Breaking the n^k Barrier for Minimum k-cut on Simple Graphs
5th November 2021 Vít Jelínek, Michal Opler, Jakub Pekárek. Long paths make pattern-counting hard, and deep trees make it harder
4th November 2021 Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. A Compound Logic for Modification Problems: Big Kingdoms Fall from Within
4th November 2021 Mahdi Belbasi, Martin Fürer. Finding All Leftmost Separators of Size ≤k
3rd November 2021 Chris Aronis. The Algorithmic Complexity of Tree-Clique Width
3rd November 2021 Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen. The Parameterized Complexity of the Survivable Network Design Problem
3rd November 2021 Jacob Focke, Marc Roth. Counting Small Induced Subgraphs with Hereditary Properties
3rd November 2021 Mohsen Alambardar Meybodi, Mohammad Reza Hooshmandasl, Ali Shakiba. W[1-hardness of Outer Connected Dominating set in d-degenerate Graphs]
30th October 2021 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé. Twin-width VI: the lens of contraction sequences
29th October 2021 Ajinkya Gaikwad, Soumen Maity. On Structural Parameterizations of the Offensive Alliance Problem
28th October 2021 Manuel Lafond. Recognizing k-leaf powers in polynomial time, for constant k
28th October 2021 Dániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale. A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
27th October 2021 Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang. Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
27th October 2021 Susobhan Bandopadhyay, Suman Banerjee, Aritra Banik, Venkatesh Raman. Structural Parameterizations of Budgeted Graph Coloring
27th October 2021 Dishant Goyal, Ragesh Jaiswal. Tight FPT Approximation for Constrained k-Center and k-Supplier
25th October 2021 Kim-Manuel Klein, Janina Reuter. Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs
21st October 2021 Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, Ulrike Schmidt-Kraepelin. The popular assignment problem: when cardinality is more important than popularity
18th October 2021 Prashanth Amireddy, Chetan Sai Digumarthi. Diameter constrained Steiner tree and related problems
18th October 2021 Dániel Marx, Govind S. Sankar, Philipp Schepper. Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
17th October 2021 Eurinardo Costa, Nicolas Martins, Rudini Sampaio. Spy game: FPT-algorithm, hardness and graph products
14th October 2021 Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy, K. K. Nisha, Vijayaragunathan Ramamoorthi. Parameterized Complexity of Minimum Membership Dominating Set
12th October 2021 André Schidler, Stefan Szeider. A SAT Approach to Twin-Width
7th October 2021 Till Fluschnik, Klaus Heeger, Danny Hermelin. Polynomial Turing Kernels for Clique with an Optimal Number of Queries
7th October 2021 Or Zamir. Faster algorithm for Unique (k,2)-CSP
6th October 2021 Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk. Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size
6th October 2021 Sugyani Mahapatra, Manikandan Narayanan, N S Narayanaswamy, Vijayaragunathan Ramamoorthi. Parameterized Algorithms for the Steiner Tree Problem on a Directed Hypercube
6th October 2021 Carla Groenland, Jesper Nederlof, Isja Mannens, Krisztina Szilágyi. Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
5th October 2021 Thomas Rothvoss, Moritz Venzin. Approximate CVP in time 20.802n -- now in any norm!
2nd October 2021 Rain Jiang, Kai Jiang, Minghui Jiang. Decomposing a graph into subgraphs with small components
4th October 2021 Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu. Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
27th September 2021 Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos. Filling Crosswords is Very Hard
21st September 2021 Michael Lampis, Valia Mitsou. Fine-grained Meta-Theorems for Vertex Integrity
14th September 2021 Janne H. Korhonen, Amir Nikabadi. Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters
13th September 2021 René van Bevern, Artem M. Kirilin, Daniel A. Skachkov, Pavel V. Smirnov, Oxana Yu. Tsidulko. Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
13th September 2021 Sahab Hajebi, Ramin Javadi. On the Parameterized Complexity of the Acyclic Matching Problem
9th September 2021 Ulrich Bauer, Abhishek Rathod. Parameterized inapproximability of Morse matching
9th September 2021 Huck Bennett, Chris Peikert, Yi Tang. Improved Hardness of BDD and SVP Under Gap-(S)ETH
30th August 2021 Pawel Gawrychowski, Mateusz Rzepecki. Faster Exponential Algorithm for Permutation Pattern Matching
30th August 2021 Pawel Gawrychowski, Mateusz Rzepecki. Faster Exponential Algorithm for Permutation Pattern Matching
29th August 2021 Radu Curticapean, Mingji Xia. Parameterizing the Permanent: Hardness for K8-minor-free graphs
29th August 2021 Sen Huang, Mingyu Xiao, Xiaoyu Chen. Exact algorithms for maximum weighted independent set on sparse graphs
23rd August 2021 Phablo F. S. Moura, Matheus J. Ota, Yoshiko Wakabayashi. Approximation and parameterized algorithms to find balanced connected partitions of graphs
23rd August 2021 Ulrich Bauer, Abhishek Rathod, Meirav Zehavi. The complexity of high-dimensional cuts
22nd August 2021 Ahammed Ullah. Clique Cover of Graphs with Bounded Degeneracy
17th August 2021 Hisao Tamaki. A heuristic for listing almost-clique minimal separators of a graph
10th August 2021 Nello Blaser, Morten Brun, Lars M. Salbu, Erlend Raa Vågset. The Parameterized Complexity of Finding Minimum Bounded Chains
29th July 2021 Bazgan Cristina, Casel Katrin, Cazals Pierre. Dense Graph Partitioning on sparse and dense graphs
26th July 2021 Radovan Červený, Pratibha Choudhary, Ondřej Suchý. On Kernels for d-Path Vertex Cover
26th July 2021 Alexandre Cooper, Stephanie Maaz, Amer E.Mouawad, Naomi Nishimura. Parameterized complexity of reconfiguration of atoms
22nd July 2021 Vikraman Arvind, Roman Nedela, Ilia Ponomarenko, Peter Zeman. Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
20th July 2021 Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov. FPT Approximation for Fair Minimum-Load Clustering
16th July 2021 Julián Mestre, Sergey Pupyrev, Seeun William Umboh. On the Extended TSP Problem
15th July 2021 Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov. Lossy Kernelization of Same-Size Clustering
14th July 2021 Jacob Focke, Dániel Marx, Paweł Rzążewski. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
14th July 2021 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh. ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
13th July 2021 Van Bang Le, Jan Arne Telle. The Perfect Matching Cut Problem Revisited
13th July 2021 Falko Hegerfeld, Stefan Kratsch. Towards exact structural thresholds for parameterized complexity
13th July 2021 Konrad Majewski, Michał Pilipczuk, Marek Sokołowski. Maintaining CMSO2 properties on dynamic structures with bounded feedback vertex number
12th July 2021 Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu. Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
9th July 2021 Pascal Kunz, Till Fluschnik, Rolf Niedermeier, Malte Renken. Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
9th July 2021 Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, Frank Sommer. Preventing Small (s,t)-Cuts by Protecting Edges
8th July 2021 Shinwoo An, Eunjin Oh. Feedback Vertex Set on Geometric Intersection Graphs
6th July 2021 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant. Twin-width and polynomial kernels
6th July 2021 Bart M. P. Jansen, Shivesh K. Roy, Michał Włodarczyk. On the Hardness of Compressing Weights
4th July 2021 Hendrik Molter. The Complexity of Finding Temporal Separators under Waiting Time Constraints
2nd July 2021 Faisal N. Abu-Khzam, Norma Makarem, Maryam Shehab. An Improved Fixed-Parameter Algorithm for 2-Club Cluster Edge Deletion
1st July 2021 Radu Curticapean, Holger Dell, Thore Husfeldt. Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
30th June 2021 Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk. Close relatives (of Feedback Vertex Set), revisited
30th June 2021 Siddharth Gupta, Guy Sa'ar, Meirav Zehavi. Grid Recognition: Classical and Parameterized Computational Perspectives
30th June 2021 Hans L. Bodlaender, Carla Groenland, Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration
28th June 2021 Daniel Neuen. Isomorphism Testing Parameterized by Genus and Beyond
27th June 2021 Fredrik Manne, Geevarghese Philip, Saket Saurabh, Prafullkumar Tale. alpha-approximate Reductions: a Novel Source of Heuristics for Better Approximation Algorithms
22nd June 2021 Isja Mannens, Jesper Nederlof, Céline Swennenhuis, Krisztina Szilágyi. On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
22nd June 2021 Huib Donkers, Bart M.P. Jansen. Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
18th June 2021 Girija Limaye. Envy-freeness and Relaxed Stability for Lower-Quotas: A Parameterized Perspective
15th June 2021 Dishant Goyal, Ragesh Jaiswal. FPT Approximation for Socially Fair Clustering
10th June 2021 Samuel Fiorini, Gwenaël Joret, Stefan Weltge, Yelena Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row
8th June 2021 Bart M.P. Jansen, Jari J.H. de Kroon. FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
1st June 2021 Madison Cooley, Casey S. Greene, Davis Issac, Milton Pividori, Blair D. Sullivan. Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition
31st May 2021 Yasir Mahmood, Jonni Virtema. Parameterised Complexity of Propositional Logic in Team Semantics
31st May 2021 Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, Céline M. F. Swennenhuis. Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
25nd May 2021 Nicolas Maack, Hendrik Molter, Rolf Niedermeier, Malte Renken. On Finding Separators in Temporal Split and Permutation Graphs
22nd May 2021 Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi. Parameterized Complexity of Locally Minimal Defensive Alliances
21st May 2021 Barak Steindl, Meirav Zehavi. Verification of Multi-Layered Assignment Problems
21st May 2021 Dušan Knop, Šimon Schierreich, Ondřej Suchý. Balancing the Spread of Two Opinions in Sparse Social Networks
20th May 2021 Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz. On the Parameterized Complexity of Polytree Learning
20th May 2021 Gabriel Bathie, Nicolas Bousquet, Théo Pierron. (Sub)linear kernels for edge modification problems towards structured graph classes
19th May 2021 Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf. Diversity in Kemeny Rank Aggregation: A Parameterized Approach
19th May 2021 Dániel Marx, Govind S. Sankar, Philipp Schepper. Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
18th May 2021 Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche. Interference-free Walks in Time: Temporally Disjoint Paths
18th May 2021 Maël Dumas, Anthony Perez, Ioan Todinca. A cubic vertex-kernel for Trivially Perfect Editing
18th May 2021 Vincent Froese, Christoph Hertrich, Rolf Niedermeier. The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
14th May 2021 Aleksander Figiel, Leon Kellerhals, Rolf Niedermeier, Matthias Rost, Stefan Schmid, Philipp Zschoche. Optimal Virtual Network Embeddings for Tree Topologies
14th May 2021 Michal Koucký, Vojtěch Rödl, Navid Talebanfard. A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
13th May 2021 Junqiang Peng, Mingyu Xiao. A Fast Algorithm for SAT in Terms of Formula Length
11th May 2021 Karl Bringmann, Jasper Slusallek. Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
11th May 2021 Leon Kellerhals, Malte Renken, Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems
10th May 2021 Ashwin Jacob, Jari J. H. de Kroon, Diptapriyo Majumdar, Venkatesh Raman. Parameterized Complexity of Deletion to Scattered Graph Classes
8th May 2021 Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Kirill Simonov. Parameterized Complexity of Feature Selection for Categorical Data Clustering
7th May 2021 Daniel Karapetyan, Gregory Gutin. Solving the Workflow Satisfiability Problem using General Purpose Solvers
4th May 2021 Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, Karol Węgrzycki. Isolation schemes for problems on decomposable graphs
4th May 2021 Lars Jaffke, O-joung Kwon, Jan Arne Telle. Classes of intersection digraphs with good algorithmic properties
4th May 2021 Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia, Dieter Rautenbach, Ignasi Sau. FPT algorithms for packing k-safe spanning rooted sub(di)graphs
30th April 2021 Michał Dębski, Marta Piecyk, Paweł Rzążewski. Faster 3-coloring of small-diameter graphs
29th April 2021 Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders
29th April 2021 Yixin Cao, Yuping Ke. Improved Kernels for Edge Modification Problems
29th April 2021 Celina M. H. de Figueiredo, Alexsander A. de Melo, Diana Sasaki, Ana Silva. Revising Johnson's table for the 21st century
29th April 2021 Laurent Bulteau, Michael R. Fellows, Christian Komusiewicz, Frances Rosamond. Parameterized String Equations
28th April 2021 Gabriel Istrate, Cosmin Bonchis, Adrian Craciun. Kernelization, Proof Complexity and Social Choice
27th April 2021 Michael Lampis. Minimum Stable Cut and Treewidth
22nd April 2021 Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Elimination Distance to Topological-minor-free Graphs is FPT
20th April 2021 Niclas Boehmer, Robert Bredereck, Dušan Knop, Junjie Luo. Finding Small Multi-Demand Set Covers with Ubiquitous Elements and Large Sets is Fixed-Parameter Tractable
19th April 2021 Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit. Parameterized Complexity of Categorical Clustering with Size Constraints
17th April 2021 Nils Morawietz, Petra Wolf. A Timecop's Chase Around the Table
15th April 2021 Tuukka Korhonen. Single-Exponential Time 2-Approximation Algorithm for Treewidth
7th April 2021 Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos. Parameterized Complexity of Elimination Distance to First-Order Logic Properties
7th April 2021 Nils Jakob Eckstein, Niels Grüttemeier, Christian Komusiewicz, Frank Sommer. Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
5th April 2021 Benjamin Merlin Bumpus, Zoltan A. Kocsis. Spined categories: generalizing tree-width beyond graphs
31st March 2021 Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi. An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
18th March 2021 Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk. Vertex Deletion Parameterized by Elimination Distance and Even Less
11th March 2021 Julien Baste, Ignasi Sau, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. Lower bounds
11th March 2021 Julien Baste, Ignasi Sau, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
9th March 2021 Marco Bressan, Marc Roth. Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications
9th March 2021 Benjamin Merlin Bumpus, Kitty Meeks. Edge exploration of temporal graphs
8th March 2021 Naoto Ohsaka. A Fully Polynomial Parameterized Algorithm for Counting the Number of Reachable Vertices in a Digraph
5th March 2021 Tomohiro Koana, Christian Komusiewicz, Frank Sommer. Essentially Tight Kernels for (Weakly) Closed Graphs
4th March 2021 Charis Papadopoulos, Spyridon Tzimas. Computing Subset Feedback Vertex Set via Leafage
4th March 2021 Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R. B. Sandeep, Sagnik Sen, R. Subashini. On subgraph complementation to H-free graphs
2nd March 2021 Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. k-apices of minor-closed graph classes. II. Parameterized algorithms
2nd March 2021 Öznur Yaşar Diner, Archontia C. Giannopoulou, Giannos Stamoulis, Dimitrios M. Thilikos. Block Elimination Distance
1st March 2021 Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. k-apices of minor-closed graph classes. I. Bounding the obstructions
23rd February 2021 Yasir Mahmood, Arne Meier, Johannes Schmidt. Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework
22nd February 2021 Hendrik Molter, Malte Renken, Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting
19th February 2021 Sushmita Gupta, Pallavi Jain, Fahad, Panolan, Sanjukta Roy, Saket Saurabh. Gerrymandering on graphs: Computational complexity and parameterized algorithms
19th February 2021 Shaohua Li, Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth
13th February 2021 Tuukka Korhonen. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
12th February 2021 Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. A more accurate view of the Flat Wall Theorem
11th February 2021 Ajinkya Gaikwad, Soumen Maity. Edge Deletion to Restrict the Size of an Epidemic
5th February 2021 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé. Twin-width IV: low complexity matrices
4th February 2021 Júlio Araújo, Marin Bougeret, Victor A. Campos, Ignasi Sau. Kernelization of Maximum Minimal Vertex Cover
2nd February 2021 Demian Hespe, Sebastian Lamm, Christian Schorr. Targeted Branching for the Maximum Independent Set Problem
26th January 2021 Rajesh Chitnis. A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
25th January 2021 David Eppstein, Siddharth Gupta, Elham Havvaei. Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes
23rd January 2021 Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi. Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
19th January 2021 Louis Dublois, Michael Lampis, Vangelis Th. Paschos. Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
18th January 2021 N R Aravind, Roopam Saxena. An FPT algorithm for Matching Cut
12th January 2021 Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, Saket Saurabh. Diverse Collections in Matroids and Graphs
11th January 2021 Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
3rd January 2021 Hauke Brinkop, Klaus Jansen, Tim Weißenfels. An optimal FPT algorithm parametrized by treewidth for Weighted-Max-Bisection given a tree decomposition as advice assuming SETH and the hardness of MinConv
28th December 2020 Mingyu Xiao, Hiroshi Nagamochi. Bounded-Degree Cut is Fixed-Parameter Tractable
23rd December 2020 Faisal Abu-Khzam, Sebastian Lamm, Matthias Mnich, Alexander Noe, Christian Schulz, Darren Strash. Recent Advances in Practical Data Reduction
17th December 2020 Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen. Induced Disjoint Paths in AT-free Graphs
16th December 2020 Tuukka Korhonen. Listing Small Minimal Separators of a Graph
14th December 2020 Rim van Wersch, Steven Kelk, Simone Linz, Georgios Stamoulis. Reflections on kernelizing and computing unrooted agreement forests
9th December 2020 Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi. An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
5th December 2020 Soh Kumabe, Takanori Maehara. r-Gathering Problems on Spiders:Hardness, FPT Algorithms, and PTASes
4th December 2020 Jianer Chen, Qin Huang, Iyad Kanj, Ge Xia. Near-Optimal Algorithms for Point-Line Covering Problems
3rd December 2020 Arnab Maiti, Palash Dey. On Parameterized Complexity of Binary Networked Public Goods Game
2nd December 2020 Johannes K. Fichte, Markus Hecher, Florim Hamiti. The Model Counting Competition 2020
2nd December 2020 Hans L. Bodlaender. Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation
30th November 2020 Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk, Marcin Wrochna. Integer Programming and Incidence Treedepth
30th November 2020 Daniel Neuen. Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
30th November 2020 Guilherme C. M. Gomes, Vinicius F. dos Santos. On structural parameterizations of the selective coloring problem
30th November 2020 Palash Dey, Arnab Maiti, Amatya Sharma. On Parameterized Complexity of Liquid Democracy
30th November 2020 Márcia R. Cappelle, Guilherme C. M. Gomes, Vinicius F. dos Santos. Parameterized algorithms for locating-dominating sets
30th November 2020 Nello Blaser, Erlend Raa Vågset. Homology Localization Through the Looking-Glass of Parameterized Complexity Theory
25th November 2020 Bin Sheng. Solving the r-pseudoforest Deletion Problem in Time Independent of r
23rd November 2020 Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, Dušan Knop. Recognizing Proper Tree-Graphs
23rd November 2020 Tuukka Korhonen. Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
23rd November 2020 Marc Roth, Johannes Schmitt, Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
20th November 2020 Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki. Fixed-Parameter Algorithms for Graph Constraint Logic
17th November 2020 Guillaume Ducoffe. Optimal diameter computation within bounded clique-width graphs
16th November 2020 Riccardo Dondi, Florian Sikora. The Longest Run Subsequence Problem: Further Complexity Results
16th November 2020 Jarosław Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michał Włodarczyk. To Close Is Easier Than To Open: Dual Parameterization To k-Median
12th November 2020 Chien-Chung Huang, Justin Ward. FPT-Algorithms for the l-Matchoid Problem with Linear and Submodular Objectives
11th November 2020 Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster. Counting Homomorphic Cycles in Degenerate Graphs
11th November 2020 Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences
9th November 2020 Johannes K. Fichte, Markus Hecher, Andre Schidler. Solving the Steiner Tree Problem with few Terminals
9th November 2020 Katrin Casel, Ziena Elijazyfer, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits. Balanced Crown Decomposition for Connectivity Constraints
8th November 2020 Vsevolod A. Afanasev, René van Bevern, Oxana Yu. Tsidulko. The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
6th November 2020 Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Algorithmic Extensions of Dirac's Theorem
6th November 2020 Karthekeyan Chandrasekaran, Weihang Wang. Fixed Parameter Approximation Scheme for Min-max k-cut
5th November 2020 Till Fluschnik. A Multistage View on 2-Satisfiability
23th October 2020 Ken-ichi Kawarabayashi, Robin Thomas, Paul Wollan. Quickly excluding a non-planar graph
22nd October 2020 Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, Karolina Okrasa. Vertex deletion into bipartite permutation graphs
20th October 2020 Philipp Zschoche. A Faster Parameterized Algorithm for Temporal Matching
16th October 2020 Jesper Nederlof, Karol Węgrzycki. Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
13th October 2020 Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos. Digraph Coloring and Distance to Acyclicity
12th October 2020 Petr A. Golovach, Paloma T. Lima, Charis Papadopoulos. Graph Square Roots of Small Distance from Degree One Graphs
11th October 2020 I. Vinod Reddy. On Structural Parameterizations of Load Coloring
9th October 2020 Édouard Bonnet, Sergio Cabello. The Complexity of Mixed-Connectivity
8th October 2020 Gordon Hoi. An Improved Exact Algorithm for the Exact Satisfiability Problem
7th October 2020 Karolina Okrasa, Paweł Rzążewski. Complexity of the list homomorphism problem in hereditary graph classes
7th October 2020 Mahdi Belbasi, Martin Fürer. An Improvement of Reed's Treewidth Approximation
5th October 2020 Yasuaki Kobayashi, Yu Nakahata. A Note on Exponential-Time Algorithms for Linearwidth
29th September 2020 Robert Bredereck, Klaus Heeger, Dušan Knop, Rolf Niedermeier. Multidimensional Stable Roommates with Master List
28th September 2020 Sitan Chen, Adam R. Klivans, Raghu Meka. Learning Deep ReLU Networks Is Fixed-Parameter Tractable
28th September 2020 Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon. The canonical directed tree decomposition and its applications to the directed disjoint paths problem
28th September 2020 Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs
27th September 2020 Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
26th September 2020 Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, Saket Saurabh. Improved FPT Algorithms for Deletion to Forest-like Structures
25th September 2020 Karthekeyan Chandrasekaran, Chandra Chekuri. Hypergraph k-cut for fixed k in deterministic polynomial time
25th September 2020 Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Tsuyoshi Yagita. Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
24th September 2020 Marta Piecyk, Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
24th September 2020 Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
24th September 2020 Saket Saurabh, Prafullkumar Tale. On the Parameterized Complexity of \textsc{Maximum Degree Contraction} Problem
24th September 2020 Martin Koutecký, Johannes Zink. Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
22nd September 2020 Tesshu Hanaka, Kazuma Kawai, Hirotaka Ono. Computing L(p,1)-Labeling with Combined Parameters
18th September 2020 Benjamin Merlin Bumpus, Kitty Meeks, William Pettersson. Directed branch-width: A directed analogue of tree-width
17th September 2020 Carl Einarson, Gregory Gutin, Bart M. P. Jansen, Diptapriyo Majumdar, Magnus Wahlstrom. p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
17th September 2020 Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski. Sparsification Lower Bounds for List H-Coloring
17th September 2020 Ronny Tredup, Evgeny Erofeev. On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency
13th September 2020 Pranabendu Misra. On Fault Tolerant Feedback Vertex Set
9th September 2020 Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov. Diverse Pairs of Matchings
1st September 2020 Vincent Cohen-Addad, Philip N. Klein, Dániel Marx. On the computational tractability of a geographic clustering problem arising in redistricting
22nd August 2020 Zijian Xu, Vorapong Suppakitpaisarn. On the Size of Minimal Separators for Treedepth Decomposition
22nd August 2020 Pratibha Choudhary, Venkatesh Raman. Structural Parameterizations of Tracking Paths Problem
21st August 2020 Akash Kumar, Mithilesh Kumar. Deletion to Induced Matching
20th August 2020 Nick Brettell, Andrea Munaro, Daniël Paulusma. Solving problems on generalized convex graphs via mim-width
19th August 2020 Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
19th August 2020 Christine T. Cheng, Will Rosenbaum. Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth
19th August 2020 Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg. Parameterized Algorithms for Queue Layouts
18th August 2020 Martin Kučera, Ondřej Suchý. Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
18th August 2020 Dániel Marx. Four short stories on surprising algorithmic uses of treewidth
17th August 2020 Johannes Blum. W[1-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension]
17th August 2020 Bruno Courcelle, Irène Durand, Michael Raskin. A unified algorithm for colouring graphs of bounded clique-width
17th August 2020 Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth
12th August 2020 Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz. Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
8th August 2020 Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi. Parameterized Complexity of (A,ℓ)-Path Packing
7th August 2020 Raphael Yuster. A 2^O(k) n algorithm for k-cycle in minor-closed graph families
28th July 2020 Zhenyu Guo, Mingyu Xiao, Yi Zhou. The Complexity of the Partition Coloring Problem
28th July 2020 Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi. The Satisfactory Partition Problem
28th July 2020 Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon. Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
28th July 2020 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant. Twin-width III: Max Independent Set and Coloring
28th July 2020 Hubie Chen, Georg Gottlob, Matthias Lanzinger, Reinhard Pichler. Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
27th July 2020 Sander Borst, Leo van Iersel, Mark Jones, Steven Kelk. New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
24th July 2020 Matthias Bentert, André Nichterlein, Malte Renken, Philipp Zschoche. Using a geometric lens to find k disjoint shortest paths
24th July 2020 Ronny Tredup, Evgeny Erofeev. On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency (Technical Report)
23rd July 2020 Dishant Goyal, Ragesh Jaiswal, Amit Kumar. FPT Approximation for Constrained Metric k-Median/Means
23rd July 2020 Tomohiro Koana, André Nichterlein. Detecting and Enumerating Small Induced Subgraphs in c-Closed Graphs
23rd July 2020 Marco Bressan. Faster algorithms for sampling connected induced subgraphs
23rd July 2020 Łukasz Kowalik, Konrad Majewski. The Asymmetric Travelling Salesman Problem in Sparse Digraphs
22nd July 2020 Frank Kammer, Andrej Sajenko. FPT-space Graph Kernelizations
21st July 2020 Peter Gartland, Daniel Lokshtanov. Independent Set on C≥k-Free Graphs in Quasi-Polynomial Time
21st July 2020 Or Zamir. Breaking the 2n barrier for 5-coloring and 6-coloring
19th July 2020 Edin Husic, Tim Roughgarden. FPT Algorithms for Finding Dense Subgraphs in c-Closed Graphs
17th July 2020 Peter Gartland, Daniel Lokshtanov. Dominated Minimal Separators are Tame (Nearly All Others are Feral)
17th July 2020 Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Solving hard cut problems via flow-augmentation
17th July 2020 Lu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu, Jianxin Li. Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs
17th July 2020 Yasuaki Kobayashi, Yota Otachi. Parameterized Complexity of Graph Burning
17th July 2020 Hans L. Bodlaender, Marieke van der Wegen. Parameterized Complexity of Scheduling Chains of Jobs with Delays
16th July 2020 Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Węgrzycki. A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
15th July 2020 Victor Campos, Raul Lopes, Ana Karolinna Maia, Ignasi Sau. Adapting the Directed Grid Theorem into an FPT Algorithm
15th July 2020 Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs
15th July 2020 Gordon Hoi, Sanjay Jain, Frank Stephan. A Faster Exact Algorithm to Count X3SAT Solutions
14th July 2020 Simon Hengeveld, Tillmann Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
14th July 2020 J. Bang-Jensen, E. Eiben, G. Gutin, M. Wahlstrom, A. Yeo. Component Order Connectivity in Directed Graphs
12th July 2020 Mathew Francis, Rian Neogi, Venkatesh Raman. Recognizing k-Clique Extendible Orderings
10th July 2020 Lucas Keiler, Carlos Vinicius G. C. Lima, Ana Karolinna Maia, Rudini Sampaio, Ignasi Sau. Target set selection with maximum activation time
9th July 2020 Markus Hecher, Jorge Fandinno. Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard
9th July 2020 Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza. Computing the Largest Bond and the Maximum Connected Cut of a Graph
8th July 2020 Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg. Extending Nearly Complete 1-Planar Drawings in Polynomial Time
8th July 2020 Guilherme C. M. Gomes, Vinicius F. dos Santos, Murilo V. G. da Silva, Jayme L. Szwarcfiter. FPT and kernelization algorithms for the k-in-a-tree problem
8th July 2020 Šimon Schierreich, Ondřej Suchý. Waypoint Routing on Bounded Treewidth Graphs
8th July 2020 Toshiki Saitoh, Ryo Yoshinaka, Hans L. Bodlaender. Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes
6th July 2020 Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, Malte Skambath. Solving Packing Problems with Few Small Items Using Rainbow Matchings
3rd July 2020 Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, Amer E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping
30th June 2020 Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný. Counting Homomorphisms to K4-minor-free Graphs, modulo 2
29th June 2020 Kazuhiro Kurita, Yasuaki Kobayashi. Efficient Enumerations for Minimal Multicuts and Multiway Cuts
28th June 2020 Eduard Eiben, William Lochet. A Polynomial Kernel for Line Graph Deletion
26th June 2020 Aleksander Figiel, Anne-Sophie Himmel, André Nichterlein, Rolf Niedermeier. On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
24th June 2020 Frank Gurski, Dominique Komander, Carolin Rehs. Acyclic coloring of special digraphs
24th June 2020 Fedor V. Fomin, Petr A. Golovach. Kernelization of Whitney Switches
18th June 2020 Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale. On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
18th June 2020 Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski. Parameterized Inapproximability of Independent Set in H-Free Graphs
8th June 2020 Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi. A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
6th June 2020 Arman Boyacı, Tınaz Ekim, Mordechai Shalom. On the Maximum Cardinality Cut Problem in Proper Interval Graphs and Related Graph Classes
2nd June 2020 Johan M. M. van Rooij. Fast Algorithms for Join Operations on Tree Decompositions
2nd June 2020 Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michał Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz. On Dynamic Parameterized k-Path
29th May 2020 Matthias Bentert, Roman Haag, Christian Hofer, Tomohiro Koana, André Nichterlein. Parameterized Complexity of Min-Power Asymmetric Connectivity
24th May 2020 Divesh Aggarwal, Eldon Chung. A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices
23rd May 2020 Marvin Künnemann, Dániel Marx. Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
17th May 2020 Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li. Optimal Bounds for the k-cut Problem
17th May 2020 Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, Meirav Zehavi. On the (Parameterized) Complexity of Almost Stable Marriage
12th May 2020 Neeldhara Misra, Harshil Mittal, Aditi Sethia. Red-Blue Point Separation for Points on a Circle
11th May 2020 Friedrich Eisenbrand, Moritz Venzin. Approximate CVP∞ in time 2^0.802n
11th May 2020 Robert Bredereck, Andrzej Kaczmarczyk, Dušan Knop, Rolf Niedermeier. High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
11th May 2020 Cornelius Brand, Kevin Pratt. An Algorithmic Method of Partial Derivatives
11th May 2020 Leslie Ann Goldberg, John Lapinskas, David Richerby. Faster Exponential-time Algorithms for Approximately Counting Independent Sets
10th May 2020 Lars Jaffke, Paloma T. Lima, Geevarghese Philip. Structural Parameterizations of Clique Coloring
7th May 2020 Neeldhara Misra, Harshil Mittal. Imbalance Parameterized by Twin Cover Revisited
6th May 2020 Kishen N. Gowda, Neeldhara Misra, Vraj Patel. A Parameterized Perspective on Attacking and Defending Elections
5th May 2020 Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström. Many visits TSP revisited
5th May 2020 Robert Bredereck, Till Fluschnik, Andrzej Kaczmarczyk. Multistage Committee Election
4th May 2020 Rian Neogi, M. S. Ramanujan, Saket Saurabh, Roohani Sharma. On the Parameterized Complexity of Deletion to H-free Strong Components
4th May 2020 Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza. Reducing graph transversals via edge contractions
30th April 2020 Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan. A Parameterized Approximation Scheme for Min k-Cut
30th April 2020 Niels Grüttemeier, Christian Komusiewicz. Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
30th April 2020 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant. Twin-width I: tractable FO model checking
28th April 2020 Deepanshu Kush, Benjamin Rossman. Tree-depth and the Formula Complexity of Subgraph Isomorphism
28th April 2020 Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, Philipp Zschoche. As Time Goes By: Reflections on Treewidth for Temporal Graphs
27th April 2020 Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse. Approximate Turing Kernelization for Problems Parameterized by Treewidth
27th April 2020 Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. An FPT-algorithm for recognizing k-apices of minor-closed graph classes
27th April 2020 Marin Bougeret, Bart M. P. Jansen, Ignasi Sau. Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
25th April 2020 Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg. Extending Partial 1-Planar Drawings
24th April 2020 Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
24th April 2020 Dániel Marx, R. B. Sandeep. Incompressibility of H-free edge modification problems: Towards a dichotomy
24th April 2020 Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos. A linear fixed parameter tractable algorithm for connected pathwidth
23rd April 2020 Wolfgang Ost, Christian Schulz, Darren Strash. Engineering Data Reduction for Nested Dissection
21st April 2020 Ryan L. Mann, Luke Mathieson, Catherine Greenhill. On the Parameterised Complexity of Induced Multipartite Graph Parameters
21st April 2020 Yixin Cao. Enumerating Maximal Induced Subgraphs
20th April 2020 Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl. Finding large H-colorable subgraphs in hereditary graph classes
19th April 2020 Bart M.P. Jansen, Jari J.H. de Kroon. Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
17th April 2020 Ignasi Sau, Uéverton S. Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs
16th April 2020 Hans Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniel Paulusma, Erik Jan van Leeuwen. Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
16th April 2020 Martin Grohe, Daniel Neuen, Daniel Wiebking. Isomorphism Testing for Graphs Excluding Small Minors
14th April 2020 Marc Roth, Johannes Schmitt, Philip Wellnitz. Counting Small Induced Subgraphs Satisfying Monotone Properties
13th April 2020 Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
12th April 2020 Flavia Bonomo-Braberman, Julliano R. Nascimento, Fabiano S. Oliveira, Uéverton S. Souza, Jayme L. Szwarcfiter. Linear-time Algorithms for Eliminating Claws in Graphs
10th April 2020 Nick Brettell, Jake Horsfield, Daniel Paulusma. Colouring (sP1+P5)-Free Graphs: a Mim-Width Perspective
5th April 2020 Mark Jones, Steven Kelk, Leen Stougie. Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
1st April 2020 Barak Steindl, Meirav Zehavi. Parameterized Analysis of Assignment Under Multiple Preferences
31st March 2020 Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, Sven Zühlsdorf. Engineering Exact Quasi-Threshold Editing
26th March 2020 Yasuaki Kobayashi. On Structural Parameterizations of Node Kayles
25th March 2020 Yixin Cao, Yuping Ke, Hanchun Yuan. Polynomial Kernels for Paw-free Edge Modification Problems
24th March 2020 Vishnu Veerathu, Yogesh Tripathi. Parameterized Algorithms for Red-Blue Weighted Vertex Cover on Trees
23rd March 2020 Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora. On the complexity of Broadcast Domination and Multipacking in digraphs
17th March 2020 Akanksha Agrawal, Kristine V.K. Knudsen, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons
16th March 2020 Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay. Scheduling Lower Bounds via AND Subset Sum
16th March 2020 Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz. Faster Minimization of Tardy Processing Time on a Single Machine
16th March 2020 Jonas Bamse Andersen, Jørgen Bang-Jensen, Anders Yeo. On the parameterized complexity of 2-partitions
11th March 2020 Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour. Induced subgraphs of bounded treewidth and the container method
11th March 2020 Alexander Göke, Dániel Marx, Matthias Mnich. Hitting Long Directed Cycles is Fixed-Parameter Tractable
11th March 2020 Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li, Martin Nöllenburg. Balanced Independent and Dominating Sets on Colored Interval Graphs
10th March 2020 René van Bevern, Pavel V. Smirnov. Optimal-size problem kernels for d-Hitting Set in linear time and space
10th March 2020 Ivan Bliznets, Danil Sagunov. Maximizing Happiness in Graphs of Bounded Clique-Width
9th March 2020 Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov. b-Coloring Parameterized by Clique-Width
7th March 2020 Andreas Björklund, Petteri Kaski. The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
5th March 2020 Jianer Chen, Ying Guo, Qin Huang. Linear-Time Parameterized Algorithms with Limited Local Resources
5th March 2020 Alexander Göke, Dániel Marx, Matthias Mnich. Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
5th March 2020 Stefan Kratsch, Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge. Optimal Discretization is Fixed-parameter Tractable
4th March 2020 Dušan Knop, Martin Koutecký. Scheduling Kernels via Configuration LP
2nd March 2020 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
28th February 2020 Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone. An optimal algorithm for Bisection for bounded-treewidth graphs
26th February 2020 Markus Bläser, Julian Dörfler, Christian Ikenmeyer. On the complexity of evaluating highest weight vectors
25th February 2020 Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden. Hedonic Seat Arrangement Problems
25th February 2020 Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima. Well-partitioned chordal graphs: obstruction set and disjoint paths
23rd February 2020 Ashwin Jacob, Fahad Panolan, Venkatesh Raman, Vibha Sahlot. Structural Parameterizations with Modulator Oblivion
20th February 2020 Carl Einarson, Felix Reidl. A general kernelization technique for domination and independence problems in sparse classes
20th February 2020 Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
20th February 2020 Magnus Wahlström. On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
19th February 2020 Mikko Koivisto, Antti Röyskö. Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs
19th February 2020 Fedor V. Fomin, Petr A. Golovach. Subexponential parameterized algorithms and kernelization on almost chordal graphs
18th February 2020 Andreas Emil Feldmann, Davis Issac, Ashutosh Rai. Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
18th February 2020 Riccardo Dondi, Danny Hermelin. Computing the k Densest Subgraphs of a Graph
18th February 2020 Fedor V. Fomin, Danil Sagunov, Kirill Simonov. Building large k-cores from sparse graphs
18th February 2020 Eduard Eiben, Fedor V. Fomin, Fahad Panolan, Kirill Simonov. Manipulating Districts to Win Elections: Fine-Grained Complexity
18th February 2020 Jana Cslovjecsek, Friedrich Eisenbrand, Robert Weismantel. N-fold integer programming via LP rounding
18th February 2020 Till Fluschnik, Rolf Niedermeier, Carsten Schubert, Philipp Zschoche. Multistage s-t Path: Confronting Similarity with Dissimilarity
14th February 2020 Rémy Belmonte, Ignasi Sau. On the complexity of finding large odd induced subgraphs and odd colorings
13th February 2020 Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP
12th February 2020 Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon. Complexity Analysis of General and Fractional Hypertree Decompositions
12th February 2020 Tomohiro Koana, Vincent Froese, Rolf Niedermeier. Complexity of Combinatorial Matrix Completion With Diameter Constraints
12th February 2020 Manuel Lafond, Binhai Zhu, Peng Zou. Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms
11th February 2020 Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, Karol Węgrzycki. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
9th February 2020 Bart M.P. Jansen, Michał Włodarczyk. Optimal polynomial-time compression for Boolean Max CSP
4th February 2020 Marcin Pilipczuk, Manuel Sorge. A Double Exponential Lower Bound for the Distinct Vectors Problem
4th February 2020 Eduard Eiben, Daniel Lokshtanov. Removing Connected Obstacles in the Plane is FPT
3rd Feburary 2020 Jakkepalli Pavan Kumar, P. Venkata Subba Reddy, S. Arumugam. Algorithmic Complexity of Secure Connected Domination in Graphs
28th January 2020 Liu Ying. The Complexity of Contracting Planar Tensor Network
24th January 2020 Aritra Banik, Pratibha Choudhary, Venkatesh Raman, Saket Saurabh. Fixed-parameter tractable algorithms for Tracking Shortest Paths
21st January 2020 Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan, Eric Thierry. Faster and Enhanced Inclusion-Minimal Cograph Completion
19th January 2020 Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification
17th January 2020 S. Cliff Liu. Simpler Partial Derandomization of PPSZ for k-SAT
15th January 2020 Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
15th January 2020 Falko Hegerfeld, Stefan Kratsch. Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space
15th January 2020 Felix Reidl, Blair D. Sullivan. A color-avoiding approach to subgraph counting in bounded expansion classes
14th January 2020 Stefan Kratsch, Florian Nelles. Efficient parameterized algorithms for computing all-pairs shortest paths
13th January 2020 Johannes K. Fichte, Markus Hecher, Patrick Thier, Stefan Woltran. Exploiting Database Management Systems and Treewidth for Counting
13th January 2020 Markus Hecher, Michael Morak, Stefan Woltran. Structural Decompositions of Epistemic Logic
11th January 2020 Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora. Grundy Coloring & friends, Half-Graphs, Bicliques
9th January 2020 Pratibha Choudhary, Venkatesh Raman. Improved Kernels for Tracking Path Problems
9th January 2020 Leon Kellerhals, Tomohiro Koana. Parameterized Complexity of Geodetic Set
30th December 2019 László Kozma. Exact exponential algorithms for two poset problems
30th December 2019 Pratyush Dayal, Neeldhara Misra. Deleting to Structured Trees
23rd December 2019 Tuukka Korhonen. Potential Maximal Cliques Parameterized by Edge Clique Cover
22nd December 2019 William Lochet. The shortest disjoint paths problem
19th December 2019 Ernst Althaus, Sarah Ziegler. Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
15th December 2019 Bin Sheng. FPT algorithms for generalized feedback vertex set problems
9th December 2019 Klaus Heeger, Anne-Sophie Himmel, Frank Kammer, Rolf Niedermeier, Malte Renken, Andrej Sajenko. Multistage Problems on a Global Budget
7th December 2019 Cornelius Brand, Martin Koutecký, Sebastian Ordyniak. Parameterized Algorithms for MILPs with Small Treedepth
6th December 2019 Jesper Nederlof, Céline Swennenhuis. Parameterized Complexity of Partial Scheduling
4th December 2019 Geevarghese Philip, Rani M. R., Subashini R. On Computing the Hamiltonian Index of Graphs
30th November 2019 Christian Schulz. Scalable Graph Algorithms
29th November 2019 Robert Ganian, Neha Lodha, Sebastian Ordyniak, Stefan Szeider. SAT-Encodings for Treecut Width and Treedepth
29th November 2019 Rajesh Chitnis, Andreas Emil Feldmann, MohammadTaghi Hajiaghayi, Dániel Marx. Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
27th November 2019 Grzegorz Fabiański. Properties of nowhere dense graph classes related to independent set problem
27th November 2019 Danny Hermelin, Matthias Mnich, Simon Omlor. Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs
21st November 2019 Robert Bredereck, Klaus Heeger, Dušan Knop, Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
20th November 2019 Anupam Gupta, Euiwoong Lee, Jason Li. The Karger-Stein Algorithm is Optimal for k-cut
20th November 2019 Rajesh Chitnis, Graham Cormode. Towards a Theory of Parameterized Streaming Algorithms
20th November 2019 Louis Dublois, Michael Lampis, Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set
13th November 2019 Harry Buhrman, Subhasree Patro, Florian Speelman. The Quantum Strong Exponential-Time Hypothesis
13th November 2019 Marcelo Garlet Milani. A Polynomial Kernel for Funnel Arc Deletion Set
12th November 2019 Julien Baste, Lars Jaffke, Tomáš Masařík, Geevarghese Philip, Günter Rote. FPT Algorithms for Diverse Collections of Hitting Sets
11th November 2019 Jungho Ahn, Eduard Eiben, O-joung Kwon, Sang-il Oum. A polynomial kernel for 3-leaf power deletion
9th November 2019 Eduard Eiben, William Lochet, Saket Saurabh. A Polynomial Kernel for Paw-Free Editing
8th November 2019 Guilherme C. M. Gomes, Matheus R. Guedes, Vinícius F. dos Santos. Structural Parameterizations for Equitable Coloring
8th November 2019 Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita. Reconfiguring k-path vertex covers
6th November 2019 Ariel Kulik, Hadas Shachnai. Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
4th November 2019 Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider. On Clustering Incomplete Data
27th October 2019 Ramin Javadi, Amir Nikabadi. On the Parameterized Complexity of Sparsest Cut and Small-set Expansion Problems
25th October 2019 Pasin Manurangsi. Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
25th October 2019 Palash Dey, Sourav Medya. Manipulating Node Similarity Measures in Network
24th October 2019 Mark Jones, Philippe Gambette, Leo van Iersel, Remie Janssen, Steven Kelk, Fabio Pardi, Celine Scornavacca. Cutting an alignment with Ockham's razor
23rd October 2019 Yang P. Liu, Richard Peng, Mark Sellke. Vertex Sparsifiers for c-Edge Connectivity
23rd October 2019 I.Vinod Reddy. Parameterized Coloring Problems on Threshold Graphs
23rd October 2019 Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz. Mimicking Networks Parameterized by Connectivity
22nd October 2019 Ei Ando. The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length
21st October 2019 Ulrich Bauer, Abhishek Rathod, Jonathan Spreer. Parametrized Complexity of Expansion Height
18th October 2019 Shaohua Li, Marcin Pilipczuk, Manuel Sorge. Cluster Editing parameterized above the size of a modification-disjoint P3 packing is para-NP-hard
16th October 2019 Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto. Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
14th October 2019 Jonas Schmidt, Thomas Schwentick, Nils Vortmeier, Thomas Zeume, Ioannis Kokkinis. Dynamic Complexity Meets Parameterised Algorithms
14th October 2019 Qilong Feng, Shaohua Li, Xiangzhong Meng, Jianxin Wang. An Improved FPT Algorithm for the Flip Distance Problem
12th October 2019 Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos. Improved (In-)Approximability Bounds for d-Scattered Set
8th October 2019 Guillaume Ducoffe, Michel Habib (IRIF), Laurent Viennot (GANG, IRIF, Inria). Fast Diameter Computation within Split Graphs
8th October 2019 Matthias Bentert, Klaus Heeger, Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
7th October 2019 Jason Li. Faster Minimum k-cut of a Simple Graph
4th October 2019 Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
4th October 2019 Stéphane Bessy, Marin Bougeret, Alan D.A. Carneiro, Fábio Protti, Uéverton S. Souza. Width Parameterizations for Knot-free Vertex Deletion on Digraphs
3rd October 2019 Rajesh Chitnis, Andreas Emil Feldmann. FPT Inapproximability of Directed Cut and Connectivity Problems
3rd October 2019 Gordon Hoi, Sanjay Jain, Frank Stephan. A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
2nd October 2019 Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron. Parameterized complexity of edge-coloured and signed graph homomorphism problems
2nd October 2019 Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza. Computing the largest bond of a graph
2nd October 2019 Bergougnoux Benjamin, Charis Papadopoulos, Jan Arne Telle. Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width
2nd October 2019 Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak. Subexponential-time algorithms for finding large induced sparse subgraphs
1st October 2019 Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz. On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
1st October 2019 Matthias Bentert, René van Bevern, Fill Fluschnik, André Nichterlein, Rolf Niedermeier. Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions
1st October 2019 Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths
30th September 2019 Raul Lopes, Ignasi Sau. A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps
26th September 2019 Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden. How does object fatness impact the complexity of packing in d dimensions?
18th September 2019 Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant. When Maximum Stable Set can be solved in FPT time
17th September 2019 Hisao Tamaki. A heuristic use of dynamic programming to upperbound treewidth
16th September 2019 Dušan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, Shmuel Onn. Multitype Integer Monoid Optimization and Applications
13th September 2019 Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, Philipp Zschoche. The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
13th September 2019 Hendrik Molter, Rolf Niedermeier, Malte Renken. Enumerating Isolated Cliques in Temporal Networks
4th September 2019 Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx. Parameterized Intractability of Even Set and Shortest Vector Problem
29th August 2019 Josef Malík, Ondřej Suchý, Tomáš Valla. Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
27th August 2019 Eduard Eiben, Robert Ganian, Thekla Hamm, O-joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
25th August 2019 Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Łukasz Kowalik. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
23rd August 2019 Matthias Hummel, Fabian Klute, Soeren Nickel, Martin Nöllenburg. Maximizing Ink in Partial Edge Drawings of k-plane Graphs
23rd August 2019 Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg. Parameterized Algorithms for Book Embedding Problems
22nd August 2019 V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay. On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
19th August 2019 Demian Hespe, Sebastian Lamm, Christian Schulz, Darren Strash. WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track
17th August 2019 Michele Conforti, Samuel Fiorin, Tony Huynh, Gwenaël Joret, Stefan Weltge. The stable set problem in graphs with bounded genus and bounded odd cycle packing number
15th August 2019 Therese Biedl, Erin Wolf Chambers, David Eppstein, Arnaud De Mesmay, Tim Ophelders. Homotopy height, grid-major height and graph-drawing height
14th August 2019 Emilio Di Giacomo, Giuseppe Liotta, Fabrizio Montecchiani. Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs
13th August 2019 Benjamin Aram Berendsohn, László Kozma, Dániel Marx. Finding and counting permutations via CSPs
12th August 2019 Monika Henzinger, Alexander Noe, Christian Schulz. Shared-Memory Branch-and-Reduce for Multiterminal Cuts
11th August 2019 Guillaume Fertin, Christian Komusiewicz. Graph Motif Problems Parameterized by Dual
9th August 2019 Dekel Tsur. Kernel for Kt-free edge deletion
9th August 2019 Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints
4th August 2019 Sergio Cabello. Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth
3rd August 2019 Dekel Tsur. Faster algorithm for Cograph Deletion
6th August 2019 Mohamed Yosri Sayadi. On the maximum number of minimal connected dominating sets in convex bipartite graphs
29th July 2019 Markus Blaeser, Christian Engels. Parameterized Valiant's Classes
29th July 2019 Robert Ganian, Sebastian Ordyniak, Stefan Szeider. A Join-Based Hybrid Parameter for Constraint Satisfaction
28th July 2019 Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak, Magnus Wahlström. Parameterized Pre-coloring Extension and List Coloring Problems
24th July 2019 Dekel Tsur. An FPT algorithm for orthogonal buttons and scissors
19th July 2019 Dekel Tsur. Cluster deletion revisited
18th July 2019 Édouard Bonnet, Nidhi Purohit. Metric Dimension Parameterized by Treewidth
15th July 2019 Martin Koutecky, Daniel Kral. A row-invariant parameterized algorithm for integer programming
15th July 2019 Michal Wlodarczyk. Inapproximability within W1: the case of Steiner Orientation
14th July 2019 Ivan Bliznets, Danil Sagunov. On Happy Colorings, Cuts, and Structural Parameterizations
12th July 2019 Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis, Dimitrios M. Thilikos. Planar Disjoint Paths in Linear Time
10th July 2019 Holger Dell, John Lapinskas, Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle
9th July 2019 Julien Baste, Ignasi Sau, Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
9th July 2019 Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset. Linear MIM-Width of Trees
9th July 2019 Soh Kumabe, Takanori Maehara. r-Gather Clustering and r-Gathering on Spider: FPT Algorithms and Hardness
8th July 2019 Marc Roth, Philip Wellnitz. Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
8th July 2019 Sean Gonzales, Theresa Migler. The Densest k Subgraph Problem in b-Outerplanar Graphs
5th July 2019 Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos. Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
4th July 2019 Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel, Joanna Tomasik. Fixed-parameter tractability of counting small minimum (S,T)-cuts
28th June 2019 Jason Li, Jesper Nederlof. Detecting Feedback Vertex Sets of Size k in O⋆(2.7k) Time
26th June 2019 Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese. Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
25th June 2019 Ashley Montanaro. Quantum speedup of branch-and-bound algorithms
24th June 2019 Dekel Tsur. Faster branching algorithm for split to block vertex deletion
22nd June 2019 Dekel Tsur. l-path vertex cover is easier than l-hitting set for small l
21st June 2019 Radovan Červený, Ondřej Suchý. Faster FPT Algorithm for 5-Path Vertex Cover
21st June 2019 Carl Einarson, Felix Reidl. Domination above r-independence: does sparseness help?
19th June 2019 Karolina Okrasa, Paweł Rzążewski. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
18th June 2019 Katharina T. Huber, Leo van Iersel, Remie Janssen, Mark Jones, Vincent Moulton, Yukihiro Murakami, Charles Semple. Rooting for phylogenetic networks
13th June 2019 Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh. Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
13th June 2019 Huib Donkers, Bart M.P. Jansen. A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
12th June 2019 Ivan Bliznets, Danil Sagunov. Lower Bounds for the Happy Coloring Problems
5th June 2019 Pooya Ronagh. Quantum Algorithms for Solving Dynamic Programming Problems
3rd June 2019 Till Fluschnik, Rolf Niedermeier, Valentin Rohm, Philipp Zschoche. Multistage Vertex Cover
3rd June 2019 Yasir Mahmood, Arne Meier, Johannes Schmidt. Parameterised Complexity for Abduction
31st May 2019 Bryan O'Gorman. Parameterization of tensor network contraction
29th May 2019 Yoichi Iwata, Yusuke Kobayashi. Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
27th May 2019 Johannes Blum. Hierarchy of Transportation Network Parameters and Hardness Results
26th May 2019 Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, Darren Strash. Engineering Kernelization for Maximum Cut
26th May 2019 Andrea Cali, Igor Razgon. Regular resolution for CNF of bounded incidence treewidth with few long clauses
25th May 2019 Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden. Subgraph Isomorphism on Graph Classes that Exclude a Substructure
16th May 2019 Venkatesan Guruswami, Patrick Lin. Parameterized Inapproximability of Exact Cover and Nearest Codeword
13th May 2019 George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, Philipp Zschoche. Computing Maximum Matchings in Temporal Graphs
10th May 2019 Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Kirill Simonov. Refined Complexity of PCA with Outliers
9th May 2019 Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
8th May 2019 Guilherme C. M. Gomes, Ignasi Sau. Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
7th May 2019 Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki. Equal-Subset-Sum Faster Than the Meet-in-the-Middle
6th May 2019 Akanksha Agrawal, Pradeesha Ashok, Meghana M Reddy, Saket Saurabh, Dolly Yadav. FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding
4th May 2019 Steven Kelk, Simone Linz. New reduction rules for the tree bisection and reconnection distance
3rd May 2019 Max Bannach, Sebastian Berndt. Positive-Instance Driven Dynamic Programming for Graph Searching
1st May 2019 Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno. Reconfiguring Undirected Paths
1st May 2019 Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi. Independent Set Reconfiguration Parameterized by Modular-Width
1st May 2019 Hans L. Bodlaender, Sudeshna Kolay, Astrid Pieterse. Parameterized Complexity of Conflict-free Graph Coloring
25th April 2019 Jesper Nederlof. Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
23rd April 2019 Julian Dörfler, Marc Roth, Johannes Schmitt, Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W1-hardness
19th April 2019 Alessandro Aloisio, Vahan Mkrtchyan. On the fixed-parameter tractability of the maximum 2-edge-colorable subgraph problem
16th April 2019 Clement Carbonnel, Miguel Romero, Stanislav Zivny. Point-width and Max-CSPs
15th April 2019 Jason Crampton, Gregory Gutin, Diptapriyo Majumdar. Bounded and Approximate Strong Satisfiability in Workflows
12th April 2019 Yasir Mahmood, Arne Meier. Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic
10th April 2019 Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki. An FPT Algorithm for Max-Cut Parameterized by Crossing Number
7th April 2019 Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
5th April 2019 Hans L. Bodlaender, Benjamin Burton, Fedor V. Fomin, Alexander Grigoriev. Knot Diagrams of Treewidth Two
5th April 2019 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Reducing Topological Minor Containment to the Unique Linkage Theorem
2nd April 2019 Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, Shmuel Onn. An Algorithmic Theory of Integer Programming
27th March 2019 Johannes K. Fichte, Markus Hecher. Treewidth and Counting Projected Answer Sets
20th March 2019 Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx, Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
19th March 2019 Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, Maurizio Patrignani. Upward Book Embeddings of st-Graphs
18th March 2019 Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond. Diversity in Combinatorial Optimization
14th March 2019 Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, Alexander Nover. Maximum Cut Parameterized by Crossing Number
12th March 2019 Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé. On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
6th March 2019 The Siddharth Gupta, Guy Sa'ar, Meirav Zehavi. Parameterized Complexity of Motion Planning for Snake-Like Robots
28th February 2019 Jouke Witteveen, Ralph Bottesch, Leen Torenvliet. A Hierarchy of Polynomial Kernels
28th February 2019 Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
27th February 2019 Sandip Banerjee, Sujoy Bhore. Algorithm and Hardness results on Liar's Dominating Set and k-tuple Dominating Set
23rd February 2019 Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Slightly Superexponential Parameterized Problems
23rd February 2019 László Kozma. Faster and simpler algorithms for finding large patterns in permutations
22nd February 2019 Fedor V. Fomin, Petr A. Golovach, Kirill Simonov. Parameterized k-Clustering: The distance matters!
21st February 2019 Lin Chen, Daniel Marx. Covering a tree with rooted subtrees
20th February 2019 Max Bannach, Malte Skambath, Till Tantau. Towards Work-Efficient Parallel Parameterized Algorithms
18th February 2019 Gregory Rosenthal. Beating Treewidth for Average-Case Subgraph Isomorphism
14th February 2019 Elli Anastasiadi, Antonis Antonopoulos, Aris Pagourtzis, Stavros Petsalakis. Parameterized Fine-Grained Reductions
13th February 2019 Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, Michael Lampis. New Results on Directed Edge Dominating Set
13th February 2019 Holger Dell, Marc Roth, Philip Wellnitz. Counting Answers to Existential Questions
11th February 2019 Bingkai Lin. A Simple Gap-producing Reduction for the Parameterized Set Cover Problem
7th February 2019 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Going Far From Degeneracy
5th February 2019 Bart M.P. Jansen, László Kozma, Jesper Nederlof. Hamiltonicity below Dirac's condition
29th January 2019 Martin Grohe, Daniel Neuen. Canonisation and Definability for Graphs of Bounded Rank Width
27th January 2019 Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi. Parameterized Complexity of Safe Set
22nd January 2019 Dekel Tsur. Faster parameterized algorithm for Cluster Vertex Deletion
21st January 2019 Mahdi Belbasi, Martin Fürer. A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation
15th January 2019 Yicheng Xu, Yong Zhang, Yifei Zou. A constant parameterized approximation for hard-capacitated k-means
11th January 2019 Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag, Frank Sommer. Destroying Bicolored P3s by Deleting Few Edges
11th January 2019 Eva-Maria C. Hols, Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters
10th January 2019 Max Bannach, Till Tantau. On the Descriptive Complexity of Color Coding
10th January 2019 Dekel Tsur. Faster parameterized algorithm for pumpkin vertex deletion set
8th January 2019 Esther Galby, Paloma T. Lima, Daniël Paulusma, Bernard Ries. On the Parameterized Complexity of k-Edge Colouring
8th January 2019 Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale. Subset Feedback Vertex Set in Chordal and Split Graphs
2nd January 2019 Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma. Clique-Width for Hereditary Graph Classes
1st January 2019 Faisal N. Abu-Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw. On the Parameterized Cluster Editing with Vertex Splitting Problem
29th December 2018 Faisal N. Abu-Khzam, Bachir M. Chahine. A Dynamically Turbo-Charged Greedy Heuristic for Graph Coloring
27th December 2018 Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou. Complexity of Reconfiguration Problems for Constraint Satisfaction
27th December 2018 Dekel Tsur. Above guarantee parameterization for vertex cover on graphs with maximum degree 4
25th December 2018 René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko. On (1+ε)-approximate problem kernels for the Rural Postman Problem
20th December 2018 Julien Baste, Binh-Minh Bui-Xuan, Antoine Roux. Temporal Matching
18th December 2018 Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michał Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebert. Model-Checking on Ordered Structures
17th December 2018 Frank Gurski, Carolin Rehs. Comparing Linear Width Parameters for Directed Graphs
13th December 2018 Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler. Shortest Reconfiguration of Matchings
7th December 2018 Holger Dell, Dániel Marx. Kernelization of Packing Problems
5th December 2018 Dušan Knop, Martin Koutecký, Matthias Mnich. Voting and Bribing in Single-Exponential Time
29th November 2018 Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling. Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs
19th November 2018 Marcin Pilipczuk, Michał Ziobro. Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization
19th November 2018 Wojciech Nadara. Experimental evaluation of kernelization algorithms to Dominating Set
12th November 2018 George B. Mertzios, Hendrik Molter, Viktor Zamaraev. Sliding Window Temporal Graph Coloring
9th November 2018 Lars Jaffke, Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
8th November 2018 Dekel Tsur. An O^*(2.619^k) algorithm for 4-path vertex cover
7th November 2018 Lin Chen, Lei Xu, Shouhuai Xu, Zhimin Gao, Weidong Shi. Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
7th November 2018 Antoine Amarilli, Florent Capelli, Mikaël Monet, Pierre Senellart. Connecting Knowledge Compilation Classes and Width Parameters
6th November 2018 Elena Farahbakhsh Touli, Yusu Wang. FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
25th October 2018 Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, Huashuo Zhang. Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
18th October 2018 Rafael Araujo, Sulamita Klein, Rudini Sampaio, Ueverton S. Souza. FPT algorithms to recognize well covered graphs
16th October 2018 Esther Galby, Andrea Munaro, Bernard Ries. Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
16th October 2018 Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Michał Pilipczuk, Marcin Pilipczuk, Saket Saurabh. Randomized contractions meet lean decompositions
16th October 2018 Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström. Multi-budgeted directed cuts
10th October 2018 Ranveer Singh, Vivek Vijay, RB Bapat. Algorithm for B-partitions, parameterized complexity of the matrix determinant and permanent
10th October 2018 Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs
10th October 2018 Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora. On the Complexity of Solution Extension of Optimization Problems
9th October 2018 Ruhollah Majdoddin. Uniform CSP Parameterized by Solution Size is in W[1]
9th October 2018 Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut. On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs
9th October 2018 Pasin Manurangsi. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
21st September 2018 Eun Jung Kim, Maria Serna, Dimitrios M. Thilikos. Data-compression for Parametrized Counting Problems on Sparse graphs
31st August 2018 V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay. Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
10th August 2018 Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniel Paulusma, Stephane Vialette. Finding a Small Number of Colourful Components
10th August 2018 Robert Ganian, Sebastian Ordyniak. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
19th July 2018 Christian Komusiewicz, André Nichterlein, Rolf Niedermeier, Marten Picker. Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments
18th July 2018 Mark de Berg, Hans L. Bodlaender, Sandor Kisfaludi-Bak, Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP
18th July 2018 Kitty Meeks, Fiona Skerman. The parameterised complexity of computing the maximum modularity of a graph
17th July 2018 Jiehua Chen, Danny Hermelin, Manuel Sorge. On Computing Centroids According to the p-Norms of Hamming Distance Vectors
17th July 2018 Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh. Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
17th July 2018 Kevin Pratt. Faster Algorithms via Waring Decompositions
13th July 2018 Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman. Parameterized Distributed Algorithms
13th July 2018 Matthew Jenssen, Peter Keevash, Will Perkins. Algorithms for #BIS-hard problems on expander graphs
13th July 2018 Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
12th July 2018 Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
12th July 2018 Kyriakos Axiotis, Arturs Backurs, Christos Tzamos. Fast Modular Subset Sum using Linear Sketching
12th July 2018 Eugene F. Dumitrescu, Allison L. Fisher, Timothy D. Goodrich, Travis S. Humble, Blair D. Sullivan, Andrew L. Wright. Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
12th July 2018 V.Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials
5th July 2018 Marc Roth, Johannes Schmitt. Counting Induced Subgraphs: A Topological Approach to #W1-hardness
2nd July 2018 René van Bevern, Oxana Yu. Tsidulko, Philipp Zschoche. Facility location under matroid constraints: fixed-parameter algorithms and applications
27th June 2018 Bas A.M. van Geffen, Bart M.P. Jansen, Arnoud A.W.M. de Kroon, Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
27th June 2018 Bart M.P. Jansen, Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
27th June 2018 Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier. On Coalitional Manipulation for Multiwinner Elections: Shortlisting
26th June 2018 René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for safe convoy routing
26th June 2018 Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter, Marco Morik, Rolf Niedermeier, René Saitenmacher. Listing All Maximal k-Plexes in Temporal Graphs
26th June 2018 Max Bannach, Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions
24th June 2018 Gregory Gutin, Magnus Wahlström, Meirav Zehavi. On r-Simple k-Path and Related Problems Parameterized by k/r
18th May 2018 Karl Bringmann, Thore Husfeldt, Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
18th May 2018 Charis Papadopoulos, Spyridon Tzimas. Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size
17th May 2018 Jessica Enright, Kitty Meeks, George B. Mertzios, Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks
17th May 2018 Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, Ana Silva. Dual parameterization of Weighted Coloring
11th May 2018 Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos. On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
9th May 2018 Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk. Parameterized circuit complexity of model checking first-order logic on sparse structures
4th May 2018 Gregory Gutin, George B. Mertzios, Felix Reidl. Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
2nd May 2018 Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton S. Souza, Rubens Sucupira. Maximum cuts in edge-colored graphs
1st May 2018 Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop. Spectrally Robust Graph Isomorphism
26th April 2018 Stefan Kratsch, Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions
24th April 2018 Bart M. P. Jansen, Astrid Pieterse. Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
11th April 2018 Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen. Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs
11th April 2018 N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare. Bipartitioning Problems on Graphs with Bounded Tree-Width
11th April 2018 Júlio Araújo, Cláudia Linhares Sales, Ignasi Sau, Ana Silva. Weighted proper orientations of trees and graphs of bounded treewidth
29th March 2018 Christine Dahn, Nils M. Kriege, Petra Mutzel. A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
26th March 2018 Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
6th March 2018 William Phan, Christopher Purcell. On the parameterized complexity of manipulating Top Trading Cycles
23rd February 2018 Andreas Emil Feldmann, Daniel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks
16th February 2018 Martin Koutecký, Asaf Levin, Shmuel On. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
16th February 2018 Felix Reidl, Magnus Wahlström. Parameterized Algorithms for Zero Extension and Metric Labelling Problems
6th February 2018 Bart M. P. Jansen, Astrid Pieterse. Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
31st January 2018 Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis. Parameterized Power Vertex Cover
31st January 2018 Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci, Guido Proietti. Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem
31st January 2018 Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge. Efficient Algorithms for Measuring the Funnel-likeness of DAGs
25th January 2018 Ellen Cardinaels, Johan S.H. van Leeuwaarden, Clara Stegehuis. Finding induced subgraphs in scale-free inhomogeneous random graphs
11th January 2018 Rémy Belmonte, Michael Lampis, Valia Mitsou. Parameterized (Approximate) Defective Coloring
10th January 2018 Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra. FPT algorithms for embedding into low complexity graphic metrics
20th December 2017 Daniel Štefankovič, Eric Vigoda, John Wilmes. On Counting Perfect Matchings in General Graphs
18th December 2017 Michael P. O'Brien, Blair D. Sullivan. Experimental Evaluation of Counting Subgraph Isomorphisms in Classes of Bounded Expansion
29th November 2017 Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi. On the Parameterized Complexity of Approximating Dominating Set
23rd October 2017 Anupam Gupta, Euiwoong Lee, Jason Li. An FPT Algorithm Beating 2-Approximation for k-Cut
20th October 2017 Guillaume Fertin, Julien Fradin, Christian Komusiewicz. The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph
20th October 2017 Till Fluschnik, George B. Mertzios, André Nichterlein. Kernelization Lower Bounds for Finding Constant Size Subgraphs
19th October 2017 Michał Karpiński, Krzysztof Piecuch. On vertex coloring without monochromatic triangles
19th October 2017 Lars Jaffke, O-joung Kwon, Jan Arne Telle. A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width
6th October 2017 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Covering vectors by spaces: Regular matroids
4th October 2017 Clemens Hoffmann, Hendrik Molter, Manuel Sorge. The Parameterized Complexity of Centrality Improvement in Networks
29th September 2017 Noam Ravid, Dori Medini, Benny Kimelfeld. Ranked Enumeration of Minimal Triangulations
28th September 2017 Lech Duraj, Marvin Künnemann, Adam Polak. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
28th September 2017 V. Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
27th September 2017 Fedor V. Fomin, Petr A. Golovach, Jean-Florent Raymond. On the tractability of optimization problems on H-graphs
26th September 2017 Igor Razgon. Partial matching width and its application to lower bounds for branching programs
26th September 2017 Ben Strasser. Computing Tree Decompositions with FlowCutter: PACE 2017 Submission
18th September 2017 David Eppstein, Siddharth Gupta. Crossing Patterns in Nonplanar Road Networks
15th September 2017 Mark de Berg, Sándor Kisfaludi-Bak, Gerhard Woeginger. The Dominating Set Problem in Geometric Intersection Graphs
15th September 2017 Daniel Kane, Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas
15th September 2017 Ryan Williams. On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry
14th September 2017 Cédric Bentz. An FPT algorithm for planar multicuts with sources and sinks on the outer face
14th September 2017 Cédric Bentz. Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees
13th September 2017 Damir Hasic, Eric Tannier. Gene tree reconciliation including transfers with replacement is hard and FPT
13th September 2017 Danny Hermelin, Dvir Shabtay, Nimrod Talmon. On The Parameterized Tractability of the Just-In-Time Flow-Shop Scheduling Problem
13th September 2017 Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, Gerhard Woeginger. Scheduling Two Agents on a Single Machine: A Parameterized Analysis of NP-hard
11th September 2017 Tong Qin, Osamu Watanabe. An improvement of the algorithm of Hertli for the unique 3SAT problem
7th September 2017 Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos. Structurally Parameterized d-Scattered Set
7th September 2017 Radu Curticapean, Nathan Lindzey, Jesper Nederlof. A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
6th September 2017 Matthias Mnich, René van Bevern. Parameterized complexity of machine scheduling: 15 open problems
31st August 2017 Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Stefan Schmi. Walking Through Waypoints
31st August 2017 Nodari Sitchinava, Darren Stras. Reconstructing Generalized Staircase Polygons with Uniform Step Length
30th August 2017 Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter. Aligned Drawing of Planar Graphs
28th August 2017 Andrea Calì, Florent Capelli, Igor Razgon. Non-FPT lower bounds for structural restrictions of decision DNNF
25th August 2017 Robert Krauthgamer, Ohad Trabelsi. Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
15th August 2017 Lars Jaffke, O-joung Kwon, Jan Arne Telle. Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width
14th August 2017 Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
11th August 2017 Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof. New Tools and Connections for Exponential-time Approximation
7th August 2017 Karthekeyan Chandrasekaran, Sahand Mozaffari. Odd Multiway Cut in Directed Acyclic Graphs
27th July 2017 Yixin Cao. A Naive Algorithm for Feedback Vertex Set
21st July 2017 Wenjun Li, Jianxin Wang, Yongjie Yang. Improved Kernels and Algorithms for Claw and Diamond Free Edge Deletion Based on Refined Observations
21st July 2017 Andreas Emil Feldmann, Daniel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
17th July 2017 Sushmita Gupta, Saket Saurabh, Meirav Zehavi. On Treewidth and Stable Marriage
17th July 2017 David Coudert (COATI), Guillaume Ducoffe (COATI), Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
16th July 2017 Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi. Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
16th July 2017 Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi. Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
14th July 2017 Viresh Patel, Guus Regts. Computing the number of induced copies of a fixed graph in a bounded degree graph
14th July 2017 Holger Dell, John Lapinskas. Fine-grained reductions from approximate counting to decision
13th July 2017 Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut. Triangle packing in (sparse) tournaments: approximation and kernelization
13th July 2017 Jiehua Chen, Danny Hermelin, Manuel Sorge, Harel Yedidsion. How hard is it to satisfy (almost) all roommates?
12th July 2017 Benjamin Bergougnoux (1), Mamadou Moustapha Kanté (1) ((1) LIMOS). Fast exact algorithms for some connectivity problems parametrized by clique-width
12th July 2017 Bernhard Bliem, Stefan Woltran. Defensive Alliances in Graphs of Bounded Treewidth
11th July 2017 Daniel Lokshtanov, Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs
7th July 2017 Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
6th July 2017 Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
6th July 2017 Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna. On Directed Feedback Vertex Set parameterized by treewidth
4th July 2017 Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, Meirav Zehavi. Packing Cycles Faster Than Erdős-Pósa
2nd July 2017 Josh Alman, Matthias Mnich, Virginia Vassilevska Williams. Dynamic Parameterized Problems and Algorithms
1st July 2017 Rani M R, R Subashini. Fixed-Parameter Tractability of the Simultaneous Consecutive Ones Submatrix & Editing Problems
30th June 2017 Ruhollah Majdoddin. Parameterized Complexity of CSP for Infinite Constraint Languages
29th June 2017 Nicolas Bousquet, Arnaud Mary, Aline Parreau. Token Jumping in minor-closed classes
28th June 2017 Ivan Bliznets, Nikolai Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
28th June 2017 Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan. Lossy Kernels for Connected Dominating Set on Sparse Graphs
28th June 2017 Johannes K. Fichte, Markus Hecher, Michael Morak, Stefan Woltran. DynASP2.5: Dynamic Programming on Tree Decompositions in Action
28th June 2017 Ralph Christian Bottesch. Relativization and Interactive Proof Systems in Parameterized Complexity Theory
28th June 2017 Johannes K. Fichte, Markus Hecher, Irina Schindler. Default Logic and Bounded Treewidth
27th June 2017 Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, Ignasi Sau, Ana Silva. On the complexity of finding internally vertex-disjoint long directed paths
26th June 2017 Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
23rd June 2017 Kyle Kloster, Philipp Kuinke, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan, Andrew van der Poel. A practical fpt algorithm for Flow Decomposition and transcript assembly
22nd June 2017 Arne Leitert, Feodor F. Dragan. Parameterized Approximation Algorithms for some Location Problems in Graphs
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

Earlier papers are listed here, due to size restrictions.

Parameterized Complexity

Did you say NP-hard?

Contents

Editing

Page tags

Add a new page