FPT papers online

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

• 4th October 2024 Tomohiro Koana, Nidhi Purohit, Kirill Simonov. Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
• 3rd October 2024 Radu Curticapean, Simon Döring, Daniel Neuen, Jiaheng Wang. Can You Link Up With Treewidth?
• 1st October 2024 Shmuel Onn. Circuit and Graver Walks and Linear and Integer Programming
• 1st October 2024 Lena Carta, Lukas Drexler, Annika Hennes, Clemens Rösner, Melanie Schmidt. FPT Approximations for Fair k-Min-Sum-Radii
• 30th September 2024 Andreas Grigorjew, Wanchote Jiamjitrak, Brendan Mumey, Alexandru I. Tomescu. Parameterised Approximation and Complexity of Minimum Flow Decompositions
• 28th September 2024 Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, Meirav Zehavi. Exact Algorithms for Clustered Planarity with Linear Saturators
• 27th September 2024 Florent Foucaud, Clara Marcille, R. B. Sandeep, Sagnik Sen, S Taruni. Algorithms and complexity for monitoring edge-geodetic sets in graphs
• 27th September 2024 David Mestel, Steven Chaplick, Steven Kelk, Ruben Meuwese. Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
• 27th September 2024 Ronak Bhadra, Raghunath Tewari. Deciding Reachability in a Directed Graph given its Path Decomposition
• 25th September 2024 Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, Sebastian Siebertz. Kernelization Complexity of Solution Discovery Problems
• 21st September 2024 Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi. A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
• 20th September 2024 Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, Chanho Song. Dynamic parameterized problems on unit disk graphs
• 20th September 2024 Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, Johannes Schmitt. Parameterised Holant Problems
• 20th September 2024 Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz. Parameterized Local Search for Max c-Cut
• 19th September 2024 Kyungjin Cho, Eunjin Oh. Mimicking Networks for Constrained Multicuts in Hypergraphs
• 13th September 2024 Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos. Vertex identification to a forest
• 12th September 2024 Jan Gutleben, Arne Meier. A SUBSET-SUM Characterisation of the A-Hierarchy
• 12th September 2024 Marvin Künnemann, Mirza Redzic. Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
• 10th September 2024 Daniel Carter. On the joint embedding property for cographs and trees
• 8th September 2024 Arnold Filtser, Ameet Gadekar. FPT approximations for Capacitated Sum of Radii and Diameters
• 7th September 2024 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi. Subexponential Parameterized Algorithms for Hitting Subgraphs
• 6th September 2024 Klaus Jansen, Alexandra Lassota, Malte Tutas, Adrian Vetta. FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
• 6th September 2024 Klaus Jansen, Kai Kahler, Lis Pirotton, Malte Tutas. Improving the Parameter Dependency for High-Multiplicity Scheduling on Uniform Machines
• 5th September 2024 Raul Lopes, Ignasi Sau. Constant congestion linkages in polynomially strong digraphs in polynomial time
• 5th September 2024 Lars Rohwedder, Karol Węgrzycki. Space-Efficient Algorithm for Integer Programming with Few Constraints
• 5th September 2024 Lars Rohwedder, Karol Węgrzycki. Fine-Grained Equivalence for Problems Related to Integer Linear Programming
• 5th September 2024 Michał Włodarczyk. Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1-hard]
• 5th September 2024 Michał Włodarczyk. Does Subset Sum Admit Short Proofs?
• 4th September 2024 Thomas Depian, Simon D. Fink, Robert Ganian, Martin Nöllenburg. The Parameterized Complexity of Extending Stack Layouts
• 3rd September 2024 Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista. Quantum Algorithms for One-Sided Crossing Minimization
• 30th August 2024 Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, Ruben F. A. Verhaegh. Preprocessing to Reduce the Search Space for Odd Cycle Transversal
• 30th August 2024 Glenn Sun, Yihong Zhang, Haobin Ni. E-Graphs as Circuits, and Optimal Extraction via Treewidth
• 28th August 2024 Batya Kenig, Dan Shlomo Mizrahi. Enumeration of Minimal Hitting Sets Parameterized by Treewidth
• 27th August 2024 Davi de Andrade, Júlio Araújo, Laure Morelle, Ignasi Sau, Ana Silva. On the parameterized complexity of computing good edge-labelings
• 27th August 2024 Václav Blažej, M. S. Ramanujan, Peter Strulo, Sushmita Gupta. On Controlling Knockout Tournaments Without Perfect Information
• 25th August 2024 Václav Blažej, Satyabrata Jana, M. S. Ramanujan, Peter Strulo. On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
• 24th August 2024 Matthias Bentert, Fedor V. Fomin, Fanny Hauser, Saket Saurabh. The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
• 23rd August 2024 Matthias Kaul, Matthias Mnich, Hendrik Molter. Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
• 23rd August 2024 Peter Jonsson, Victor Lagerkvist, George Osipov. CSPs with Few Alien Constraints
• 20th August 2024 Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Arne Meier. Rejection in Abstract Argumentation: Harder Than Acceptance?
• 20th August 2024 Valentin Zech, Niclas Boehmer, Edith Elkind, Nicholas Teh. Multiwinner Temporal Voting with Aversion to Change
• 18th August 2024 Shinwoo Ahn, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee, Eunjin Oh, Hyeonjun Shin. Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
• 18th August 2024 Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak. Unbreakable Decomposition in Close-to-Linear Time
• 15th August 2024 Ishay Haviv, Dror Rabinovich. Kernelization for Orthogonality Dimension
• 15th August 2024 Faisal N. Abu-Khzam, Lucas Isenmann. Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
• 11th August 2024 Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, Sheng-Lung Peng. The complexity of strong conflict-free vertex-connection k-colorability
• 8th August 2024 Daniel W. Cranston, Moritz Mühlenthaler, Benjamin Peyrille. A simple quadratic kernel for Token Jumping on surfaces
• 7th August 2024 Tatsuya Terao, Ryuhei Mori. Parameterized Quantum Query Algorithms for Graph Problems
• 7th August 2024 Rajesh Chitnis, Samuel Thomas, Anthony Wirth. Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
• 7th August 2024 Andreas Björklund, Thore Husfeldt. Finding longer cycles via shortest colourful cycle
• 28th July 2024 Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan. On the geometry of k-SAT solutions: what more can PPZ and Schöning's algorithms do?
• 25th July 2024 Tim Randolph, Karol Węgrzycki. Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
• 22nd July 2024 Jakub Balabán, Robert Ganian, Mathis Rocton. Twin-Width Meets Feedback Edges and Vertex Integrity
• 22nd July 2024 Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, Stefan Szeider. Explaining Decisions in ML Models: a Parameterized Complexity Analysis
• 19th July 2024 Sangam Balchandar Reddy, Anjeneya Swami Kare. Algorithms for Minimum Membership Dominating Set Problem
• 17th July 2024 Barış Can Esmer, Ariel Kulik. Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
• 17th July 2024 Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, Ziena Zeif. Optimal Padded Decomposition For Bounded Treewidth Graphs
• 15th July 2024 Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider. From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
• 12th July 2024 Michael Lampis. Circuits and Backdoors: Five Shades of the SETH
• 12th July 2024 Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht. Obstructions to Erdős-Pósa Dualities for Minors
• 12th July 2024 Manuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober, Michał T. Seweryn, Stefan Weltge, Yelena Yuditsky. Integer programs with nearly totally unimodular matrices: the cographic case
• 12th July 2024 Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl. Tree Independence Number IV. Even-hole-free Graphs
• 12th July 2024 Philip Cervenjak, Junhao Gan, Seeun William Umboh, Anthony Wirth. Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
• 12th July 2024 Karthik C. S., Euiwoong Lee, Pasin Manurangsi. On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
• 11th July 2024 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center
• 11th July 2024 Evripidis Bampis, Bruno Escoffier, Michalis Xefteris. Improved FPT Approximation for Non-metric TSP
• 9th July 2024 Radu Curticapean, Daniel Neuen. Counting Small Induced Subgraphs: Hardness via Fourier Analysis
• 9th July 2024 Simon Döring, Dániel Marx, Philip Wellnitz. From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
• 7th July 2024 Divesh Aggarwal, Antoine Joux, Miklos Santha, Karol Węgrzycki. Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
• 3rd July 2024 Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins, Vinicius F. dos Santos. Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
• 2nd July 2024 Stefan Kratsch, Van Bang Le. On polynomial kernelization for Stable Cutset
• 1st July 2024 Jonas Lill, Kalina Petrova, Simon Weber. Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
• 1st July 2024 Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond. Kick the cliques
• 30th June 2024 Therese Biedl, Prosenjit Bose, Karthik Murali. A Parameterized Algorithm for Vertex and Edge Connectivity of Embedded Graphs
• 28th June 2024 Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane, Matthias Bentert, Pål Grønås Drange, Felix Reidl, Alan Kuntz, Blair D. Sullivan. Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
• 28th June 2024 Bart M.P. Jansen, Céline M.F. Swennenhuis. Steiner Tree Parameterized by Multiway Cut and Even Less
• 27th June 2024 Petr Hliněný, Liana Khazaliya. Crossing Number is NP-hard for Constant Path-width (and Tree-width)
• 27th June 2024 Arnaud Casteigts, Nils Morawietz, Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
• 27th June 2024 Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, Saket Saurabh. Cuts in Graphs with Matroid Constraints
• 26th June 2024 Max Bannach, Florian Chudigiewitsch, Till Tantau. On the Descriptive Complexity of Vertex Deletion Problems
• 26th June 2024 Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
• 25th June 2024 Shinwoo An, Eunjin Oh, Jie Xue. Sparse Outerstring Graphs Have Logarithmic Treewidth
• 21st June 2024 Venkatesan Guruswami, Rhea Jain. Exponential Time Approximation for Coloring 3-Colorable Graphs
• 18th June 2024 Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad. Parameterized Shortest Path Reconfiguration
• 17th June 2024 Édouard Bonnet. Treewidth Inapproximability and Tight ETH Lower Bound
• 16th June 2024 Yuxi Liu, Mingyu Xiao. Solving Co-Path/Cycle Packing Faster than $3^k$
• 11th June 2024 M. A. Shalu, V. K. Kirubakaran. Open Packing in Graphs: Bounds and Complexity
• 3rd June 2024 N. R. Aravind, Roopam Saxena. The Parameterized Complexity of Terminal Monitoring Set
• 3rd June 2024 Palash Dey, Ashlesha Hota, Sudeshna Kolay, Sipra Singh. Knapsack with Vertex Cover, Set Cover, and Hitting Set
• 31st May 2024 Karolina Drabik, Tomáš Masařík. Finding Diverse Solutions Parameterized by Cliquewidth
• 31st May 2024 Marko Lalovic. Exact Algorithms for MaxCut on Split Graphs
• 29th May 2024 Matthias Bentert, Leon Kellerhals, Rolf Niedermeier. The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
• 27th May 2024 Christian Komusiewicz, Jannik Schestag. Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
• 24th May 2024 Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh. When far is better: The Chamberlin-Courant approach to obnoxious committee selection
• 24th May 2024 Yota Otachi, Akira Suzuki, Yuma Tamura. Finding Induced Subgraphs from Graphs with Small Mim-Width
• 22nd May 2024 Édouard Bonnet. Sparse Induced Subgraphs of Large Treewidth
• 20th May 2024 Artem Kaznatcheev. Local search for valued constraint satisfaction parameterized by treedepth
• 19th May 2024 Jason Yang. Fixed-parameter tractability of canonical polyadic decomposition over finite fields
• 17th May 2024 Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman. Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
• 13th May 2024 David Coudert, Mónika Csikós, Guillaume Ducoffe, Laurent Viennot. Practical Computation of Graph VC-Dimension
• 11th May 2024 Hao Sun, A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
• 8th May 2024 Aizhong Zhou, Fengbo Wang, Jiong Guo. Committee Elections with Candidate Attribute Constraints
• 8th May 2024 Aizhong Zhou, Fengbo Wang, Jiong Guo. Controlling Borda Elections by Adding or Deleting either Votes or Candidates: Complete and Top-Truncated Votes
• 7th May 2024 George Osipov, Marcin Pilipczuk, Magnus Wahlström, Parameterized Complexity of MinCSP over the Point Algebra
• 6th May 2024 Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca. Distributed Model Checking on Graphs of Bounded Treedepth
• 5th May 2024 Mihail Stoian. TSP Escapes the O(2^n n^2) Curse
• 5th May 2024 Hitoshi Murakami, Yutaro Yamaguchi. An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
• 3rd May 2024 Katrin Casel, Tobias Friedrich, Aikaterini Niklanovits, Kirill Simonov, Ziena Zeif. Combining Crown Structures for Vulnerability Measures
• 3rd May 2024 Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, Graph Parameters, Universal Obstructions, and WQO
• 2nd May 2024 Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Metric Dimension and Geodetic Set Parameterized by Vertex Cover
• 2nd May 2024 Leo van Iersel, Mark Jones, Jannik Schestag, Celine Scornavacca, Mathias Weller. Maximizing Network Phylogenetic Diversity
• 1st May 2024 Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl. Tree independence number II. Three-path-configurations
• 30th April 2024 Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, Irene Muzi. Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
• 30th April 2024 Jessica Enright, Samuel D. Hand, Laura Larios-Jones, Kitty Meeks. Structural Parameters for Dense Temporal Graphs
• 29th April 2024 Václav Blažej, Dušan Knop, Jan Pokorný, Šimon Schierreich. Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
• 29th April 2024 Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, Martin Strehler. Graph Search Trees and the Intermezzo Problem
• 29th April 2024 Mihail Stoian. Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT
• 27th April 2024 Giorgos Kritikakis, Ioannis G Tollis. Parameterized Linear Time Transitive Closure
• 27th April 2024 Ryoma Norose, Yutaro Yamaguchi. Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
• 26th April 2024 Klaus Jansen, Kai Kahler, Esther Zwanger. Exact and Approximate High-Multiplicity Scheduling on Identical Machines
• 25th April 2024 Robert Ganian, Hung P. Hoang, Simon Wietheger. Parameterized Complexity of Efficient Sortation
• 25th April 2024 Boris Klemz, Marie Diana Sieper. Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
• 25th April 2024 Marin Bougeret, Bart M. P. Jansen, Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
• 25th April 2024 Jesse Beisegel, Fabienne Ratajczak, Robert Scheffler. Computing Hamiltonian Paths with Partial Order Restrictions
• 24th April 2024 Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More
• 24th April 2024 Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
• 23rd April 2024 Michael Lampis, Manolis Vasilakis. Parameterized Maximum Node-Disjoint Paths
• 23rd April 2024 Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C Nandy, Krishna Priya K M, Bodhayan Roy, Sasanka Roy, Abhishek Sahu. Minimum Consistent Subset in Trees and Interval Graphs
• 22nd April 2024 Klaus Heeger, Hendrik Molter. Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
• 22nd April 2024 Robert Ganian, Haiko Mueller, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki. A Tight Subexponential-time Algorithm for Two-Page Book Embedding
• 19th April 2024 Anna Zych-Pawlewicz, Marek Żochowski. Dynamic Parameterized Feedback Problems in Tournaments
• 16th April 2024 Michael Kiran Huber. How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
• 16th April 2024 Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Martin Milanič, Peter Muršič, Robert Scheffler. The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
• 15th April 2024 Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity. Kernelization Algorithms for the Eigenvalue Deletion Problems
• 15th April 2024 Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, Alexander Wolff. Eliminating Crossings in Ordered Graphs
• 15th April 2024 Bart M. P. Jansen, Ruben F. A. Verhaegh. Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
• 15th April 2024 Ambroise Baril, Miguel Couceiro, Victor Lagerkvist. The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
• 14th April 2024 Carlos V.G.C. Lima, Thiago Marcilon, Pedro Paulo de Medeiros. On the complexity of some cycle convexity parameters
• 13th April 2024 Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu. Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• 12th April 2024 Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez. Destroying Densest Subgraphs is Hard
• 11th April 2024 Naonori Kakimura, Ildikó Schlotter. Parameterized Complexity of Submodular Minimization under Uncertainty
• 8​th ​A​pril 2024​ ​Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang​. Combinatorial Correlation Clustering​
• 7​th ​A​pril 2024​ ​Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, Kevin Pratt​. Chromatic number in $1.9999^n$ time? Fast deterministic set partitioning under the asymptotic rank conjecture​
• 6​th ​A​pril 2024​ ​Chao Yang, Zhujun Zhang​. Undecidability of tiling the plane with a fixed number of Wang bars​
• 5th April 2024 Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Saket Saurabh. Stability in Graphs with Matroid Constraints
• 5th April 2024 Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis. Minor Containment and Disjoint Paths in almost-linear time
• 5​th April 2024 ​Petr Hliněný​. Note on k-Planar and Min-k-Planar Drawings of Graphs​
• ​5​th April ​2024 Henry Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov​. Inapproximability of Maximum Diameter Clustering for Few Clusters​
• ​5​th April 2024​ ​Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang​. An Improved Pseudopolynomial Time Algorithm for Subset Sum​
• 5​th Apr​il 2024​ ​Henry Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov​. Inapproximability of Maximum Diameter Clustering for Few Clusters​
• 4th April 2024 J. Mark Keil, Debajyoti Mondal. The Maximum Clique Problem in a Disk Graph Made Easy
• 4th April 2024 Friedrich Eisenbrand, Lars Rohwedder, Karol Węgrzycki. Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
• 3rd Apr​il 2024​ ​Klaus Heeger, Danny Hermelin, Michael L. Pinedo, Dvir Shabtay​. Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard​
• 3​rd Apr​il 2024​ ​Alexander Firbas, Alexander Dobler, Fabian Holzer, Jakob Schafellner, Manuel Sorge, Anaïs Villedieu, Monika Wißmann​. The Complexity of Cluster Vertex Splitting and Company​
• ​3rd Apr​il 2024​ ​Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny​. Elimination distance to bounded degree on planar graphs​
• 1​st Apr​il 2024​ ​Till Fluschnik, Leon Kellerhals​. ​Placing Green Bridges Optimally, with a Multivariate Analysis​
• 1​st Apr​il 2024​ ​Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé​. Twin-width and permutations​
• 31st Mar 2024​ ​Omar Al - Khazali​ An Algebraic Approach to the Longest Path Problem​
• 30th March 2024 Jan Derbisz, Tomasz Krawczyk. Circular-arc graphs and the Helly property
• 28th March 2024 Ce Jin, Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums
• 27th March 2024 George B. Mertzios, Hendrik Molter, Paul G. Spirakis. Realizing temporal transportation trees
• 27th March 2024 Yixin Cao, Jingyi Liu, Jianxin Wang. Minimum sum vertex cover: kernelization and parameterized algorithms
• 26th March 2024 Juhi Chaudhary, Hendrik Molter, Meirav Zehavi. Parameterized Analysis of Bribery in Challenge the Champ Tournaments
• 24th March 2024 Kleitos Papadopoulos. A Novel exact algorithm for economic lot-sizing with piecewise linear production costs
• 24th March 2024 Kilian Grage, Klaus Jansen. Convolution and Knapsack in Higher Dimensions
• 21st March 2024 Mark Jones, Jannik Schestag. Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
• 19th March 2024 Niels Holtgrefe, Leo van Iersel, Mark Jones. Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
• 18th March 2024 Shinwoo An, Eunjin Oh. ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
• 13th March 2024 Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak. Approximating Small Sparse Cuts
• 12th March 2024 Jakob Greilhuber, Philipp Schepper, Philip Wellnitz. Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs
• 12th March 2024 Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
• 12th March 2024 Michael Lampis. The Primal Pathwidth SETH
• 11th March 2024 Marta Piecyk. C2k+1-coloring of bounded-diameter graphs
• 11th March 2024 P. S. Ardra, R. Krithika, Saket Saurabh, Roohani Sharma. Balanced Substructures in Bicolored Graphs
• 10th March 2024 Pasin Manurangsi. Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
• 10th March 2024 R. Krithika, V. K. Kutty Malu, Prafullkumar Tale. Revisiting Path Contraction and Cycle Contraction
• 9th March 2024 Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective
• 7th March 2024 Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing. Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
• 6th March 2024 Jayakrishnan Madathil, Kitty Meeks. Parameterized Algorithms for Balanced Cluster Edge Modification Problems
• 6th March 2024 Prafullkumar Tale. Double Exponential Lower Bound for Telephone Broadcast
• 4th March 2024 Matthias Bentert, Klaus Heeger, Tomohiro Koana. Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
• 1st March 2024 Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Mark Siggers, Siani Smith. Graph Homomorphism, Monotone Classes and Bounded Pathwidth
• 28th February 2024 Caroline Brosse, Alessio Conte, Vincent Limouzy, Giulia Punzi, Davide Rucci. Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
• 27th February 2024 Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin. Tight Lower Bounds for Block-Structured Integer Programs
• 26th February 2024 Katarzyna Kowalska, Michał Pilipczuk. Parameterized and approximation algorithms for coverings points with segments in the plane
• 26th February 2024 Jelle J. Oostveen, Daniël Paulusma, Erik Jan van Leeuwen. The Complexity of Diameter on H-free graphs
• 24th February 2024 Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, Kenny Štorgel. Tree decompositions meet induced matchings: beyond Max Weight Independent Set
• 23rd February 2024 Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, Frank Sommer. On the Complexity of Community-aware Network Sparsification
• 23rd February 2024 Majid Behbahani, Mina Dalirrooyfard, Elaheh Fata, Yuriy Nevmyvaka. Graph Partitioning With Limited Moves
• 23rd February 2024 Matthias Bentert, Fedor V. Fomin, Petr A. Golovach. Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
• 22nd February 2024 Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Węgrzycki. Hitting Meets Packing: How Hard Can it Be?
• 22nd February 2024 Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno. Parameterized Complexity of Finding Dissimilar Shortest Paths
• 21st February 2024 Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer. Edge-Disjoint Paths in Eulerian Digraphs
• 20th February 2024 Till Fluschnik, Leon Kellerhals, Malte Renken. Locally Rainbow Paths
• 20th February 2024 Tatiana Belova, Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin. Improved Space Bounds for Subset Sum
• 19th February 2024 Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin, Viktor Zamaraev. Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
• 19th February 2024 Tuukka Korhonen, Marek Sokołowski. Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
• 18th February 2024 Tomohiro Koana, Magnus Wahlström. Faster algorithms on linear delta-matroids
• 18th February 2024 Moritz Lichter, Simon Raßmann, Pascal Schweitzer. Computational complexity of the Weisfeiler-Leman dimension
• 17th February 2024 Clément Dallard, Matjaž Krnc, O-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel, Sebastian Wiederrecht. Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
• 16th February 2024 Tesshu Hanaka, Noleen Köhler, Michael Lampis. Core Stability in Additively Separable Hedonic Games of Low Treewidth
• 15th February 2024 Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, Blair D. Sullivan. Correlation Clustering with Vertex Splitting
• 15th February 2024 Katie Clinch, Serge Gaspers, Abdallah Saffidine, Tiankuang Zhang. A Piecewise Approach for the Analysis of Exact Algorithms
• 15th February 2024 Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited
• 15th February 2024 Andreas Emil Feldmann, Michael Lampis. Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
• 15th February 2024 Shuangle Li, Bingkai Lin, Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
• 14th February 2024 Tim Seppelt. An Algorithmic Meta Theorem for Homomorphism Indistinguishability
• 13th February 2024 Konrad Majewski, Michał Pilipczuk, Anna Zych-Pawlewicz. Parameterized dynamic data structure for Split Completion
• 13th February 2024 Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, Prafullkumar Tale. Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
• 12th February 2024 Narek Bojikian, Stefan Kratsch. Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
• 11th February 2024 Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
• 9th February 2024 Kristina Asimi, Libor Barto, Victor Dalmau. The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
• 9th February 2024 Sushmita Gupta, M. S. Ramanujan, Peter Strulo. An Exercise in Tournament Design: When Some Matches Must Be Scheduled
• 5th February 2024 Hans L. Bodlaender, Krisztina Szilágyi. XNLP-hardness of Parameterized Problems on Planar Graphs XNLP-hardness of Parameterized Problems on Planar Graphs
• 2nd February 2024 Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, Alexander Wiedemann. Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model
• 29th January 2024 Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis, Szymon Toruńczyk. Elementary first-order model checking for sparse graphs
• 29th January 2024 Alexander Firbas, Manuel Sorge. On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
• 24th January 2024 Amir Abboud, Nick Fischer, Yarin Shechter. Faster Combinatorial k-Clique Algorithms
• 17th January 2024 Daniel W. Cranston. Token Jumping in Planar Graphs has Linear Sized Kernels
• 15th January 2024 Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov. Fixed-parameter debordering of Waring rank
• 12th January 2024 Ragesh Jaiswal, Amit Kumar, Jatin Yadav. FPT Approximation for Capacitated Sum of Radii
• 10th January 2024 Shubhada Aute, Fahad Panolan. Parameterized Algorithms for Minimum Sum Vertex Cover
• 3rd January 2024 Klaus Heeger, Danny Hermelin. Minimizing the Weighted Number of Tardy Jobs is W[1-hard]
• 29th December 2023 Vidya Sagar Sharma. Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
• 22nd December 2023 Max Bannach, Markus Hecher. Structure-Guided Automated Reasoning
• 22nd December 2023 Nick Fischer, Marvin Künnemann, Mirza Redzic. The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties
• 19th December 2023 Bingkai Lin, Huairui Chu. FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
• 18th December 2023 Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx. Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
• 17th December 2023 Martin Milanič, Irena Penev, Nevena Pivač, Kristina Vušković. Bisimplicial separators
• 15th December 2023 Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler. Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology
• 14th December 2023 Mahabba El Sahili, Faisal N. Abu-Khzam. A Linear Kernel for Planar Vector Domination
• 14th December 2023 Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou. On the complexity of list H-packing for sparse graph classes
• 13th December 2023 Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen, Tomáš Masařík. Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor
• 12th December 2023 Eduard Eiben, Robert Ganian, Thekla Hamm, Viktoriia Korchemna. A Structural Complexity Analysis of Synchronous Dynamical Systems
• 12th December 2023 Robert Ganian, Thekla Hamm, Dušan Knop, Sanjukta Roy, Šimon Schierreich, Ondřej Suchý. Maximizing Social Welfare in Score-Based Social Distance Games
• 12th December 2023 Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider. Finding a Cluster in Incomplete Data
• 12th December 2023 Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider. The Computational Complexity of Concise Hypersphere Classification
• 12th December 2023 Eduard Eiben, Robert Ganian, Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning
• 11th December 2023 Ivan Bliznets, Jesper Nederlof, Krisztina Szilágyi. Parameterized Algorithms for Covering by Arithmetic Progressions
• 11th December 2023 Jesper Nederlof, Krisztina Szilágyi. Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
• 6th December 2023 Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
• 6th December 2023 Jesper Nederlof, Céline M. F. Swennenhuis, Karol Węgrzycki. A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
• 4th December 2023 Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue. Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
• 4th December 2023 Martin Grohe, Daniel Neuen. Isomorphism for Tournaments of Small Twin Width
• 30th November 2023 Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, Szymon Toruńczyk. First-Order Model Checking on Monadically Stable Graph Classes
• 28th November 2023 Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu. **Parameterized Inapproximability Hypothesis under ETH**
• 16th November 2023 Mariana Escalante, Martín Matamala, Iván Rapaport, Paola Tolomei, Luis Miguel Torres. The Minimum Clique Routing Problem on Cycles
• 15th November 2023 Simon Döring, Dániel Marx, Philip Wellnitz. Counting Small Induced Subgraphs with Edge-monotone Properties
• 14th November 2023 Serge Gaspers, Jerry Zirui Li. Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems
• 10th November 2023 Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi. Structural Parameterizations of Vertex Integrity
• 10th November 2023 Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton Souza. Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
• 8th November 2023 Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum, Daniël Paulusma. Computing pivot-minors
• 7th November 2023 Shinwoo An, Kyungjin Cho, Eunjin Oh. Faster Algorithms for Cycle Hitting Problems on Disk Graphs
• 6th November 2023 Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita, Yuto Okada, Yota Otachi. Dichotomies for Tree Minor Containment with Structural Parameters
• 5th November 2023 Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan. Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
• 5th November 2023 Kevin Pratt. A stronger connection between the asymptotic rank conjecture and the set cover conjecture
• 4th November 2023 Jeremy T. Fineman. Single-Source Shortest Paths with Negative Real Weights in O~(mn8/9) Time
• 3rd November 2023 Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh. A First Order Method for Linear Programming Parameterized by Circuit Imbalance
• 3rd November 2023 Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk, Adam Polak. Parameterized algorithms for block-structured integer programs with large entries
• 2nd November 2023 Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza. On Conflict-Free Cuts: Algorithms and Complexity
• 1st November 2023 Sylvain Guillemot. Parameterized covering in semi-ladder-free hypergraphs
• 31st October 2023 Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, K. S. Thejaswini. Simple and tight complexity lower bounds for solving Rabin games
• 31st October 2023 Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk, Marek Sokołowski. Fully dynamic approximation schemes on planar and apex-minor-free graphs
• 26th October 2023 Venkatesan Guruswami, Xuandi Ren, Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP
• 24th October 2023 Linear MIM-width of the Square of Trees. Svein Høgemo
• 20th October 2023 D. Gribanov, D. Malyshev, P. Pardalos. Faster Integer Points Counting in Parametric Polyhedra
• 18th October 2023 Andreas Björklund, Petteri Kaski. The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
• 18th October 2023 Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, George Karypis, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Christian Schulz, Roohani Sharma, Darren Strash, Blair D. Sullivan, Bora Uçar, Albert-Jan Yzelman. Open Problems in (Hyper)Graph Decomposition
• 14th October 2023 Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Tree Containment Above Minimum Degree is FPT
• 14th October 2023 Jan Böker, Louis Härtel, Nina Runde, Tim Seppelt, Christoph Standke. The Complexity of Homomorphism Reconstructibility
• 12th October 2023 Jakub Balabán, Robert Ganian, Mathis Rocton. Computing Twin-Width Parameterized by the Feedback Edge Number
• 9th October 2023 Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, Erik Jan van Leeuwen. The Parameterised Complexity of Integer Multicommodity Flow
• 9th October 2023 George Osipov, Marcin Pilipczuk. Directed Symmetric Multicut is W1-hard
• 9th October 2023 Tesshu Hanaka, Yasuaki Kobayashi. Finding a Minimum Spanning Tree with a Small Non-Terminal Set
• 9th October 2023 Siddharth Gupta, Guy Sa'ar, Meirav Zehavi. Collective Graph Exploration Parameterized by Vertex Cover
• 9th October 2023 Siddharth Gupta, Guy Sa'ar, Meirav Zehavi. Drawn Tree Decomposition: New Approach for Graph Drawing Problems
• 6th October 2023 Bart M. P. Jansen, Shivesh K. Roy. On the Parameterized Complexity of Multiway Near-Separator
• 6th October 2023 Bart M.P. Jansen, Bart van der Steenhoven. Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions
• 6th October 2023 Vidya Sagar Sharma. A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
• 5th October 2023 Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, Saket Saurabh. FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
• 3rd October 2023 Lukas Drexler, Jan Höckendorff, Joshua Könen, Kevin Schewior. Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs
• 2nd October 2023 Harmender Gahlawat, Meirav Zehavi. Parameterized Complexity of Incomplete Connected Fair Division
• 2nd October 2023 Max Bannach, Florian Chudigiewitsch, Till Tantau. Existential Second-Order Logic Over Graphs: Parameterized Complexity
• 1st October 2023 Neeldhara Misra, Harshil Mittal, Saket Saurabh, Dhara Thakkar. On the Complexity of the Eigenvalue Deletion Problem
• 29th September 2023 Benjamin Bergougnoux, Oscar Defrain, Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems
• 29th September 2023 Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number
• 29th September 2023 Matthias Lanzinger, Igor Razgon. FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
• 29th September 2023 Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski. Max Weight Independent Set in sparse graphs with no long claws
• 28th September 2023 Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, Meirav Zehavi. Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
• 28th September 2023 Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman. QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
• 27th September 2023 Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi. Sidestepping Barriers for Dominating Set in Parameterized Complexity
• 27th September 2023 Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov. st-Planar Edge Completion Problem is Fixed-Parameter Tractable
• 27th September 2023 Baitian Li. Computing Permanents and Counting Hamiltonian Cycles Faster
• 24th September 2023 Cornelius Brand, Viktoriia Korchemna, Michael Skotnica, Kirill Simonov. Counting Vanishing Matrix-Vector Products
• 20th September 2023 Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk. Single-Exponential FPT Algorithms for Enumerating Secluded F-Free Subgraphs and Deleting to Scattered Graph Classes
• 18th September 2023 Juhi Chaudhary, Hendrik Molter, Meirav Zehavi. How to Make Knockout Tournaments More Popular?
• 15th September 2023 Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov. On Induced Versions of Menger's Theorem on Sparse Graphs
• 15th September 2023 Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos. Dynamic programming on bipartite tree decompositions
• 13th September 2023 Henning Fernau, Kevin Mann. Perfect Roman Domination and Unique Response Roman Domination
• 10th September 2023 Sushmita Gupta, Pallavi Jain, Saket Saurabh. How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach
• 9th September 2023 Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang. Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming
• 8th September 2023 Susobhan Bandopadhyay, Suman Banerjee, Diptapriyo Majumdar, Fahad Panolan. Shortest Path with Positive Disjunctive Constraints -- a Parameterized Perspective
• 7th September 2023 Koustav De, Harshil Mittal, Palash Dey, Neeldhara Misra. Parameterized Aspects of Distinct Kemeny Rank Aggregation
• 3rd September 2023 Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov. Upward and Orthogonal Planarity are W[1-hard Parameterized by Treewidth]
• 3rd September 2023 Virginia Aardevol Martinez, Steven Chaplick, Steven Kelk, Ruben Meuwese, Matus Mihalak, Georgios Stamoulis. Relaxed Agreement Forests
• 1st September 2023 Alexander Firbas, Alexander Dobler, Fabian Holzer, Jakob Schafellner, Manuel Sorge, Anaïs Villedieu, Monika Wißmann. The Complexity of Cluster Vertex Splitting and Company
• 31st August 2023 Zimo Sheng, Mingyu Xiao. A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering
• 30th August 2023 Jona Dirks, Enna Gerhard, Mario Grobler, Amer E. Mouawad, Sebastian Siebertz. Data reduction for directed feedback vertex set on graphs without long induced cycles
• 29th August 2023 Walter Didimo, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Stephen Kobourov, Marie Diana Sieper. Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem
• 29th August 2023 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Tomohiro Koana. FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
• 29th August 2023 Baris Can Esmer, Ariel Kulik, Daniel Marx, Daniel Neuen, Roohani Sharma. Approximate Monotone Local Search for Weighted Problems
• 28th August 2023 Sally Dong, Guanghao Ye. Faster Min-Cost Flow on Bounded Treewidth Graphs
• 27th August 2023 Yuxi Liu, Mingyu Xiao. An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
• 25th August 2023 Walter Didimo, Emilio Di Giacomo, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali. On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity
• 24th August 2023 Klaus Heeger, Danny Hermelin, Matthias Mnich, Dvir Shabtay. No Polynomial Kernels for Knapsack
• 22nd August 2023 Robert Ganian, Liana Khazaliya, Kirill Simonov. Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
• 22nd August 2023 Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter. Parameterized Complexity of Simultaneous Planarity
• 21st August 2023 Cornelius Brand, Robert Ganian, Sebastian Röder, Florian Schager. Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
• 21st August 2023 Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan. Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
• 17th August 2023 Pål Grønås Drange, Patrick Greaves, Irene Muzi, Felix Reidl. Computing complexity measures of degenerate graphs
• 12th August 2023 François Sellier. Parameterized Matroid-Constrained Maximum Coverage
• 11th August 2023 Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi. Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
• 11th August 2023 Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stephan Thomasse, Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems
• 9th August 2023 Tuukka Korhonen, Daniel Lokshtanov. Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
• 6th August 2023 Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé. Factoring Pattern-Free Permutations into Separable ones
• 4th August 2023 Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi. Kernelization of Counting Problems
• 3rd August 2023 Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi. Meta-theorems for Parameterized Streaming Algorithms
• 3rd August 2023 Andreas Björklund, Petteri Kaski, Jesper Nederlof. Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
• 2nd August 2023 Lawqueen Kanesh, Diptapriyo Majumdar, M. S. Ramanujan. Polynomial-delay Enumeration Kernelizations for Cuts of Bounded Degree
• 1st August 2023 Lito Goldmann, Leon Kellerhals, Tomohiro Koana. Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
• 26th July 2023 Narek Bojikian, Stefan Kratsch. A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
• 22nd July 2023 Steven Kelk, Ruben Meuwese. Agreement forests of caterpillar trees: complexity, kernelization and branching
• 21st July 2023 Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov. Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
• 20th July 2023 Michal Pilipczuk (MIMUW), Mathieu Mari (MIMUW, IDEAS NCBR), Timothe Picavet (ENS de Lyon). A parameterized approximation scheme for the 2D-Knapsack problem with wide items
• 20th July 2023 R. Krithika, V. K. Kutty Malu, Roohani Sharma, Prafullkumar Tale. Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
• 18th July 2023 P-matchings Parameterized by Treewidth
• 17th July 2023 Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, Saket Saurabh. Fixed-Parameter Algorithms for Fair Hitting Set Problems
• 16th July 2023 Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
• 15th July 2023 Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, Tom C. van der Zanden. Minimum Separator Reconfiguration
• 14th July 2023 Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Turán's Theorem Through Algorithmic Lens
• 14th July 2023 Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Sparse induced subgraphs in P_6-free graphs
• 13th July 2023 Michał Włodarczyk, Meirav Zehavi. Planar Disjoint Paths, Treewidth, and Kernels
• 11th July 2023 Robert Ganian, Thekla Hamm, Dušan Knop, Sanjukta Roy, Šimon Schierreich, Ondřej Suchý. Maximizing Social Welfare in Score-Based Social Distance Games
• 11th July 2023 Juhi Chaudhary, Meirav Zehavi. Parameterized Results on Acyclic Matchings with Implications for Related Problems
• 10th July 2023 Vera Chekan, Stefan Kratsch. Tight Algorithmic Applications of Clique-Width Generalizations
• 10th July 2023 Foivos Fioravantes, Nikolaos Melissinos, Theofilos Triommatis. Parameterised distance to local irregularity
• 9th July 2023 Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai. Budgeted Matroid Maximization: a Parameterized Viewpoint
• 7th July 2023 Christian Komusiewicz, Jannik Schestag. A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
• 5th July 2023 Stefan Kratsch, Pascal Kunz. Approximate Turing kernelization and lower bounds for domination problems
• 5th July 2023 Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza. Exact and Parameterized Algorithms for the Independent Cutset Problem
• 5th July 2023 Manuel Lafond, Weidong Luo. Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
• 4th July 2023 Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, Marek Sokołowski. Sparse Graphs of Twin-width 2 Have Bounded Tree-width
• 4th July 2023 Jan Dreier, Daniel Mock, Peter Rossmanith. Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
• 4th July 2023 Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu. Faster Detours in Undirected Graphs
• 3rd July 2023 Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, Ly Orgo. Polynomial-time Approximation of Independent Set Parameterized by Treewidth
• 3rd July 2023 Hisao Tamaki. A contraction-recursive algorithm for treewidth
• 3rd July 2023 Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
• 3rd July 2023 Arindam Biswas, Johannes Meintrup. Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time
• 3rd July 2023 Riccardo Dondi, Manuel Lafond. An FTP Algorithm for Temporal Graph Untangling
• 1st July 2023 Łukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski. Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
• 1st July 2023 Emmanuel Sam, Benjamin Bergougnoux, Petr A. Golovach, Nello Blaser. Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
• 30th June 2023 Anthony Hevia, Benjamin Kallus, Summer McClintic, Samantha Reisner, Darren Strash, Johnathan Wilso. Solving Edge Clique Cover Exactly via Synergistic Data Reduction
• 30th June 2023 Michael Levet, Nicholas Sieger. Logarithmic Weisfeiler--Leman Identifies All Graphs of Bounded Rank Width
• 30th June 2023 Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond. Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments
• 29th June 2023 Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk. 5-Approximation for H-Treewidth Essentially as Fast as H-Deletion Parameterized by Solution Size
• 29th June 2023 Maël Dumas, Anthony Perez. An improved kernelization algorithm for Trivially Perfect Editing
• 28th June 2023 Victor Campos, Jonas Costa, Raul Lopes, Ignasi Sau. New Menger-like dualities in digraphs and applications to half-integral linkages
• 27th June 2023 Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma. Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
• 26th June 2023 Michaela Borzechowski, Patrick Schnider, Simon Weber. An FPT Algorithm for Splitting a Necklace Among Two Thieves
• 26th June 2023 Eva Michelle Deltl, Till Fluschnik, Robert Bredereck. Algorithmics of Egalitarian versus Equitable Sequences of Committees
• 23rd June 2023 Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao. A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap
• 22nd June 2023 Manuel Lafond, Weidong Luo. Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters
• 20th June 2023 David Eppstein. A Parameterized Algorithm for Flat Folding
• 19th June 2023 David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams. Quasipolynomiality of the Smallest Missing Induced Subgraph
• 16th June 2023 Thomas Bläsius, Max Göttlicher. An Efficient Algorithm for Power Dominating Set
• 12th June 2023 David C. Kutner, Laura Larios-Jones. Temporal Reachability Dominating Sets: contagion in temporal graphs
• 8th June 2023 Vedangi Bengali, Nate Veldt. Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
• 7th June 2023 Christian Komusiewicz, Pascal Kunz, Frank Sommer, Manuel Sorge. On Computing Optimal Tree Ensembles
• 7th June 2023 Marc Hellmuth, Guillaume E. Scholz. Linear Time Algorithms for NP-hard Problems restricted to GaTEx Graphs
• 7th June 2023 Chien-Chung Huang, François Sellier. Matroid-Constrained Vertex Cover
• 6th June 2023 Magnus Wahlström. Representative set statements for delta-matroids and the Mader delta-matroid
• 5th June 2023 Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli. On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
• 2nd June 2023 Fedor V. Fomin, Pierre Fraigniaud, Petr A. Golovach. Parameterized Complexity of Broadcasting in Graphs
• 30th May 2023 Johannes K. Fichte, Markus Hecher, Michael Morak, Patrick Thier, Stefan Woltran. Solving Projected Model Counting by Utilizing Treewidth and its Limits
• 26th May 2023 Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz. Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
• 26th May 2023 Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier. Can You Solve Closest String Faster than Exhaustive Search?
• 25th May 2023 Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski. Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
• 25th May 2023 Leif Eriksson, Victor Lagerkvist. Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning
• 23th May 2023 Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma. Parameterized Complexity Classification for Interval Constraints
• 19th May 2023 Édouard Bonnet, Julien Duron. Stretch-width
• 18th May 2023 George Osipov, Magnus Wahlström. Parameterized Complexity of Equality MinCSP
• 12th May 2023 Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase. Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
• 12th May 2023 Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi, Hiroomi Nochide, Yota Otachi. Minimum Consistent Subset for Trees Revisited
• 11th May 2023 Valentin Bartier, Oscar Defrain, Fionn Mc Inerney. Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree
• 5th May 2023 Michal Wlodarczyk. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
• 4th May 2023 Jorke M. de Vlas. On the parameterized complexity of the Perfect Phylogeny problem
• 3rd May 2023 Fedor F. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Approximating Long Cycle Above Dirac's Guarantee
• 3rd May 2023 Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Giannos Stamoulis. Computing paths of large rank in planar frameworks deterministically
• 3rd May 2023 Jan Dreier, Robert Ganian, Thekla Hamm. Approximate Evaluation of Quantitative Second Order Queries
• 2nd May 2023 Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniel Paulusma, Siani Smith, Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
• 2nd May 2023 Rajni Dabas, Neelima Gupta, Tanmay Inamdar. FPT Approximations for Capacitated/Fair Clustering with Outliers
• 2nd May 2023 Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen. Two-sets cut-uncut on planar graphs
• 1st May 2023 Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
• 29th April 2023 Ragesh Jaiswal, Amit Kumar. Clustering What Matters in Constrained Settings
• 28th April 2023 Michael Lampis, Manolis Vasilakis. Structural Parameterizations for Two Bounded Degree Problems Revisited
• 27th April 2023 Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, Sebastian Siebertz. On Solution Discovery via Reconfiguration
• 27th April 2023 Cornelius Brand, Robert Ganian, Kirill Simonov. A Parameterized Theory of PAC Learning
• 26th April 2023 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi. Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs
• 15th April 2023 Yijia Chen, Yi Feng, Bundit Laekhanukit, Yanlin Liu. Simple Combinatorial Construction of the k^o(1)-Lower Bound for Approximating the Parameterized k-Clique
• 14th April 2023 Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michał Pilipczuk. Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
• 14th April 2023 Thai Bui. Finding A Path Of Length k: An Expository
• 6th April 2023 Sriram Bhyravarapu, Satyabrata Jana, Lawqueen Kanesh, Saket Saurabh, Shaily Verma. Parameterized algorithms for Eccentricity Shortest Path Problem
• 6th April 2023 Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase. Parameterized Approximation Schemes for Clustering with General Norm Objectives
• 6th April 2023 Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang. Improved Hardness of Approximating k-Clique under ETH
• 4th April 2023 Eduard Eiben, Tomohiro Koana, Magnus Wahlström. Determinantal Sieving
• 4th April 2023 Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, Marek Sokołowski. Dynamic treewidth
• 29th March 2023 Therese Biedl, David Eppstein, Torsten Ueckerdt. On the complexity of embedding in graph products
• 29th March 2023 Vincent Froese, Christoph Hertrich. Training Neural Networks is NP-Hard in Fixed Dimension
• 23rd March 2023 Giovanna K. Conrado, Amir K. Goharshady, Harshit J. Motwani, Sergei Novozhilov. Parameterized Algorithms for Topological Indices in Chemistry
• 22nd March 2023 Shmuel Onn. Degree Sequence Optimization in Bounded Treewidth
• 21st March 2023 Argyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith, George Skretas. Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source
• 20th March 2023 Ajaykrishnan E S, Soumen Maity, Abhishek Sahu, Saket Saurabh. An Improved Exact Algorithm for Knot-Free Vertex Deletion
• 19th March 2023 Nicolas Bousquet, Quentin Deschamps, Aline Parreau. Metric dimension parameterized by treewidth in chordal graphs
• 18th March 2023 Ambroise Baril, Antoine Castillon, Nacim Oijid. On the Parameterized Complexity of Relaxations of Clique
• 17th March 2023 Sergio Cabello, David Gajser. Connectivity with uncertainty regions given as line segments
• 14th March 2023 Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz. Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process
• 14th March 2023 Sayan Bandyapadhyay, William Lochet, Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
• 13th March 2023 V P Abidha, Pradeesha Ashok, Avi Tomar, Dolly Yadav. Coloring a Dominating Set Without Conflicts: q-Subset Square Coloring
• 7th March 2023 Jessica Enright, Kitty Meeks, William Pettersson, John Sylvester. Cops and Robbers on Multi-Layer Graphs
• 5th March 2023 Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman. Expansion Lemma -- Variations and Applications to Polynomial-Time Preprocessing
• 4th March 2023 George Manoussakis. Efficient maximal cliques enumeration in weakly closed graphs
• 2nd March 2023 Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs
• 28th February 2023 Jakob Baumann, Matthias Pfretzschner, Ignaz Rutter. Parameterized Complexity of Vertex Splitting to Pathwidth at most 1
• 27th February 2023 Falko Hegerfeld, Stefan Kratsch. Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
• 27th February 2023 Lucas Meijer. 3-Coloring in Time O(1.3217^n)
• 27th February 2023 Dipayan Chakraborty, R. B. Sandeep. Contracting edges to destroy a pattern: A complexity study
• 22nd February 2023 Henning Fernau, Kevin Mann. Hitting the Romans
• 21st February 2023 Steven Chaplick, Steven Kelk, Ruben Meuwese, Matus Mihalak, Georgios Stamoulis. Snakes and Ladders: a Treewidth Story
• 21st February 2023 Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon. New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
• 20th February 2023 Emmanuel Arrighi, Fedor V. Fomin, Petr Golovach, Petra Wolf. Kernelizing Temporal Exploration Problems
• 19th February 2023 Yefim Dinitz, Solomon Eyal Shimony. On Existence of Must-Include Paths and Cycles in Undirected Graphs
• 19th February 2023 Michael Lampis, Nikolaos Melissinos, Manolis Vasilakis. Parameterized Max Min Feedback Vertex Set
• 18th February 2023 Huairui Chu. A Tight Lower Bound for Compact Set Packing
• 17th Feburary 2023 Thomas Bläsius, Maximilian Katzmann, Marcus Wilhelm. Partitioning the Bags of a Tree Decomposition Into Cliques
• 17th February 2023 Nina Klobas, George B. Mertzios, Hendrik Molter, Paul G. Spirakis. Realizing temporal graphs from fastest travel times
• 14th February 2023 Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda. Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
• 9th February 2023 Daniel Cocks. t-sails and sparse hereditary classes of unbounded tree-width
• 9th February 2023 Yeonsu Chang, O-joung Kwon, Myounghwan Lee. A new width parameter of graphs based on edge cuts: α-edge-crossing width
• 7th February 2023 Jan Dreier, Nikolas Mählmann, Sebastian Siebertz. First-Order Model Checking on Structurally Sparse Graph Classes
• 7th February 2023 Falko Hegerfeld, Stefan Kratsch. Tight algorithms for connectivity problems parameterized by clique-width
• 1st February 2023 Symon Toruńczyk. Flip-width: Cops and Robber on dense graphs
• 1st February 2023 Juha Kontinen, Yasir Mahmood, Arne Meier, Heribert Vollmer. Parameterized Complexity of Weighted Team Definability
• 1st February 2023 Roman Erhardt, Kathrin Hanauer, Nils Kriege, Christian Schulz, Darren Strash. Improved Exact and Heuristic Algorithms for Maximum Weight Clique
• 1st February 2023 Leon Kellerhals, Tomohiro Koana, Pascal Kunz, Rolf Niedermeier. Parameterized Algorithms for Colored Clustering
• 30th January 2023 Julien Baste. The Leafed Induced Subtree in chordal and bounded treewidth graphs
• 25th January 2023 Pascal Kunz, Hendrik Molter, Meirav Zehavi. In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
• 17th January 2023 Zhao Song, Tianyi Zhou. Faster Sinkhorn's Algorithm with Small Treewidth
• 15th January 2023 Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi. Long Directed Detours: Reduction to 2-Disjoint Paths
• 10th January 2023 Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar, Kirill Simonov. Proportionally Fair Matching with Multiple Groups
• 4th January 2023 Leslie Ann Goldberg, Marc Roth. Parameterised and Fine-grained Subgraph Counting, modulo 2
• 2nd January 2023 Klaus Heeger, André Nichterlein, Rolf Niedermeier. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
• 30th December 2022 Christophe Crespelle, Rémi Pellerin, Stéphan Thomassé. A quasi-quadratic vertex Kernel for Cograph edge editing
• 28th December 2022 Tomohiro Koana. Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
• 27th December 2022 Igor Razgon. FPT algoritms providing constant ratio approximation of hypertree width parameters for hypergraphs of bounded rank
• 23rd December 2022 Narek Bojikian, Vera Chekan, Falko Hegerfeld, Stefan Kratsch. Tight Bounds for Connectivity Problems Parameterized by Cutwidth
• 22nd December 2022 Henning Fernau, Florent Foucaud, Kevin Mann, Utkarsh Padariya, Rajath Rao K.N. Parameterizing Path Partitions
• 15th December 2022 Manuel Caceres. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
• 14th December 2022 Aleksander Figiel, Tomohiro Koana, André Nichterlein, Niklas Wünsche. Correlating Theory and Practice in Finding Clubs and Plexes
• 9th December 2022 Tian Bai, Mingyu Xiao. Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs
• 7th December 2022 Ildikó Schlotter. Recognizing when a preference system is close to admitting a master list
• 3rd December 2022 Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki. Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
• 3rd December 2022 Thomas Erlebach, Jakob T. Spooner. Parameterized temporal exploration problems
• 1st December 2022 Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue. Clustering What Matters: Optimal Approximation for Clustering with Outliers
• 1st December 2022 Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan. An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
• 22nd November 2022 Sriram Bhyravarapu, I. Vinod Reddy. On Structural Parameterizations of Star Coloring
• 17th November 2022 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi. (Re)packing Equal Disks into Rectangle
• 17th November 2022 Manuel Caceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu. Minimum Path Cover in Parameterized Linear Time
• 15th November 2022 Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing, Tuomo Lehtilä. The RED-BLUE SEPARATION problem on graphs
• 15th November 2022 Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro. Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms
• 14th November 2022 Tuukka Korhonen, Daniel Lokshtanov. An Improved Parameterized Algorithm for Treewidth
• 13th November 2022 Ernesto Parra Inza, Frank Angel Hernández Mira, José María Sigarreta Almira, Nodari Vakhania. Exact and Approximation Algorithms for the Domination Problem
• 13th November 2022 Tomohiro Koana, André Nichterlein, Niklas Wünsche. Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
• 11th November 2022 Yuzhou Gu, Zhao Song. A Faster Small Treewidth SDP Solver
• 11th November 2022 Rafael Kiesel, André Schidler. A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets
• 11th November 2022 Yijia Chen, Moritz Müller, Keita Yokoyama. A parameterized halting problem, Δ0 truth and the MRDP theorem
• 10th November 2022 Michael J. Bremner, Zhengfeng Ji, Xingjian Li, Luke Mathieson, Mauro E.S. Morales. Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
• 8th November 2022 Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek. Computing Square Colorings on Bounded-Treewidth and Planar Graphs
• 8th November 2022 Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz. Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
• 7th November 2022 Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k^2 and Linear in n
• 7th November 2022 Pradeesha Ashok, Rajath Rao, Avi Tomar. Polynomial Kernels for Generalized Domination Problems
• 4th November 2022 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi. A Framework for Approximation Schemes on Disk Graphs
• 3rd November 2022 Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos. Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
• 3rd November 2022 Danish Kashaev, Guido Schäfer. A Round and Bipartize Approximation Algorithm for Vertex Cover
• 3rd November 2022 Marco Bressan, Matthias Lanzinger, Marc Roth. The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
• 1st November 2022 Elise Deen, Leo van Iersel, Remie Janssen, Mark Jones, Yuki Murakami, Norbert Zeh. A Near-Linear Kernel for Two-Parsimony Distance
• 31st October 2022 Aritra Banik, Prahlad Narasimhan Kasthurirangan, Venkatesh Raman. Dominator Coloring Parameterized by Cluster Vertex Deletion Number
• 26th October 2022 Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
• 19th October 2022 Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski. List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• 18th October 2022 Michael Lampis. First Order Logic on Pathwidth Revisited Again
• 13th October 2022 Andre Schidler, Robert Ganian, Manuel Sorge, Stefan Szeider. Threshold Treewidth and Hypertree Width
• 13th October 2022 Gabriel L. Duarte, Uéverton S. Souza. On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy
• 13th October 2022 Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov. The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
• 7th October 2022 Markus Hecher. Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?
• 5th October 2022 Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, Gaurav Viramgami. Romeo and Juliet Meeting in Forest Like Regions
• 5th October 2022 Laure Morelle, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. Faster parameterized algorithms for modification problems to minor-closed classes
• 5th October 2022 Benjamin Bergougnoux, Tuukka Korhonen, Jesper Nederlof. Tight Lower Bounds for Problems Parameterized by Rank-width
• 30th September 2022 Leif Eriksson, Victor Lagerkvist. A Multivariate Complexity Analysis of Qualitative Reasoning Problems
• 28th September 2022 Stefan Kratsch, Florian Nelles. Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width
• 27th September 2022 Haohong Li, Ge Xia. An O(3.82k) Time FPT Algorithm for Convex Flip Distance
• 26th September 2022 Naoto Ohsaka. On the Parameterized Intractability of Determinant Maximization
• 25th September 2022 Martin Milanič, Paweł Rzążewski. Tree decompositions with bounded independence number: beyond independent sets
• 24th September 2022 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé. Twin-width V: linear minors, modular counting, and matrix multiplication
• 20th September 2022 Michael Skotnica. VEST is W[2-hard]
• 19th September 2022 François Dross, Krzysztof Fleszar, Karol Węgrzycki, Anna Zych-Pawlewicz. Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
• 19th September 2022 N.R. Aravind, Roopam Saxena. Parameterized Complexity of Path Set Packing
• 16th September 2022 Lars Jaffke, Paloma T. Lima, Roohani Sharma. b-Coloring Parameterized by Pathwidth is XNLP-complete
• 14th September 2022 Zeev Nutov. Parameterized algorithms for node connectivity augmentation problems
• 12th September 2022 Akanksha Agrawal, Soumita Hait, Amer E. Mouawad. On finding short reconfiguration sequences between independent sets
• 7th September 2022 Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth. Counting Subgraphs in Somewhere Dense Graphs
• 5th September 2022 Mina Dalirrooyfard, Virginia Vassilevska Williams. Induced Cycles and Paths Are Harder Than You Think
• 5th September 2022 Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza-Cadena, Matthias Mnich. Resolving Infeasibility of Linear Systems: A Parameterized Approach
• 4th September 2022 Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force
• 1st September 2022 Andreas Emil Feldmann, Tung Anh Vu. Generalized k-Center: Distinguishing Doubling and Highway Dimension
• 31st August 2022 Louis Carpentier, Jorik Jooken, Jan Goedgebeur. A heuristic algorithm for the maximum happy vertices problem using tree decompositions
• 31st August 2022 Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström. On weighted graph separation problems and flow-augmentation
• 30th August 2022 Johannes Blum, Yann Disser, Andreas Feldmann, Siddharth Gupta, Anna Zych-Pawlewicz. On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
• 30th August 2022 Vincent Cohen-Addad, Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering
• 30th August 2022 Tom C. van der Zanden, Hans L. Bodlaender, Herbert J.M. Hamers. Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs
• 26th August 2022 Ahammed Ullah. Computing Clique Cover with Structural Parameterization
• 26th August 2022 Hans L. Bodlaender. The Parameterized Complexity Binary CSP for Graphs with a Small Vertex Cover and Related Results
• 24th August 2022 Markus Hecher. Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract
• 21st August 2022 Hengzhao Ma, Jianzhong Li, Xiangyu Gao, Tianpeng Gao. Turing Machines with Two-level Memory: A Deep Look into the Input/Output Complexity
• 18th August 2022 Eduard Eiben, Clément Rambaud, Magnus Wahlström. On the parameterized complexity of symmetric directed multicut
• 16th August 2022 Łukasz Bożyk, Michał Pilipczuk. Polynomial kernel for immersion hitting in tournaments
• 14th August 2022 Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, Saket Saurabh. Exact Exponential Algorithms for Clustering Problems
• 11th August 2022 Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx, Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
• 10th August 2022 Faisal N. Abu-Khzam, Henning Fernau, Kevin Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
• 6th August 2022 Ajinkya Gaikwad, Soumen Maity, Saket Saurabh. Parameterized Algorithms for Locally Minimal Defensive Alliance
• 5th August 2022 Ajinkya Gaikwad, Soumen Maity. Offensive Alliances in Graphs
• 4th August 2022 Esther Galby, Daniel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale. Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• 4th August 2022 Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström. Almost Consistent Systems of Linear Equations
• 4th August 2022 Ajinkya Gaikwad, Soumen Maity. Parameterized Complexity of Upper Edge Domination
• 3rd August 2022 Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, Shuvam Kant Tripathi. Maximum Minimal Feedback Vertex Set: A Parameterized Perspective
• 3rd August 2022 Carlos V.G.C. Lima, Vinicius F. dos Santos, João H.G. Sousa, Sebastián A. Urrutia. On the Computational Complexity of the Strong Geodetic Recognition Problem
• 1st August 2022 Alex Meiburg. Reduction Rules and ILP Are All You Need: Minimal Directed Feedback Vertex Set
• 25th July 2022 Gregory Gutin, Matthias Mnich. A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
• 20th July 2022 Nicolas El Maalouly, Raphael Steiner, Lasse Wulf. Exact Matching: Correct Parity and FPT Parameterized by Independence Number
• 20th July 2022 Tesshu Hanaka. Computing Densest k-Subgraph with Structural Parameters
• 20th July 2022 Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Martin Milanič. Computing Tree Decompositions with Small Independence Number
• 18th July 2022 Pengcheng Zhu, Shenggen Zheng, Lihua Wei, Xueyun Cheng, Zhijin Guan, Shiguang Feng. The Complexity of Quantum Circuit Mapping with Fixed Parameters
• 18th July 2022 René van Bevern, Daniel A. Skachkov. A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
• 15th July 2022 Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov, Giannos Stamoulis. Fixed-Parameter Tractability of Maximum Colored Path and Beyond
• 15th July 2022 Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Ueverton S. Souza. A tight quasi-polynomial bound for Global Label Min-Cut
• 15th July 2022 Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge. Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
• 15th July 2022 Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
• 14th July 2022 Ambroise Baril, Miguel Couceiro, Victor Lagerkvist. Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
• 14th July 2022 Yosuke Mizutani, Blair D. Sullivan. Improved Parameterized Complexity of Happy Set Problems
• 14th July 2022 Jungho Ahn, Jinha Kim, O-joung Kwon. Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• 14th July 2022 Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht. Kernelization for Graph Packing Problems via Rainbow Matching
• 13th July 2022 Benjamin Merlin Bumpus, Zoltan Kocsis, Jade Edenstar Master. Structured Decompositions: Structural and Algorithmic Compositionality
• 11th July 2022 Dimitrios M. Thilikos, Sebastian Wiederrecht. Killing a Vortex
• 11th July 2022 Jelle J. Oostveen, Erik Jan van Leeuwen. Parameterized Complexity of Streaming Diameter and Connectivity Problems
• 3rd July 2022 Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi. Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
• 3rd July 2022 Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
• 1st July 2022 Benjamin Merlin Bumpus, Bart M.P. Jansen, Jari J.H. de Kroon. Search-Space Reduction via Essential Vertices
• 30th June 2022 Clément Dallard, Martin Milanič, Kenny Štorgel. Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• 30th June 2022 Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• 30th June 2022 Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca. On graphs coverable by k shortest paths
• 30th June 2022 Robert Ganian, Viktoriia Korchemna. Slim Tree-Cut Width
• 29th June 2022 Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, Alessandra Tappini. Recognizing Map Graphs of Bounded Treewidth
• 29th June 2022 Aleksander Figiel, Vincent Froese, André Nichterlein, Rolf Niedermeier. There and Back Again: On Applying Data Reduction Rules by Undoing Others
• 27th June 2022 Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
• 27th June 2022 Deniz Ağaoğlu Çağırıcı, Peter Zeman. Recognition and Isomorphism of Proper U-graphs in FPT-time
• 26th June 2022 Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Dvir Shabtay. Hardness of Interval Scheduling on Unrelated Machines
• 23rd June 2022 Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur. Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
• 23rd June 2022 Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk. On the Complexity of Problems on Tree-structured Graphs
• 21st June 2022 Tomoyuki Yamakami. Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis
• 20th June 2022 Hans L. Bodlaender, Carla Groenland, Hugo Jacob. List Colouring Trees in Logarithmic Space
• 20th June 2022 Huib Donkers, Bart M.P. Jansen, Jari J.H. de Kroon. Finding k-Secluded Trees Faster
• 16th June 2022 Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk. Twin-width and types
• 15th June 2022 Shweta Jain, Yo Mizutani, Blair Sullivan. Faster Decomposition of Weighted Graphs into Cliques using Fisher's Inequality
• 14th June 2022 Hans Bodlaender, Nils Donselaar, Johan Kwisthout. Parameterized Complexity Results for Bayesian Inference
• 14th June 2022 Niclas Boehmer, Tomohiro Koana. The Complexity of Finding Fair Many-to-One Matchings
• 9th June 2022 Steven Kelk, Simone Linz, Ruben Meuwese. Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics
• 9th June 2022 David Dekker, Bart M. P. Jansen. Kernelization for Feedback Vertex Set via Elimination Distance to a Forest
• 3rd June 2022 Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, Stefan Szeider. Weighted Model Counting with Twin-Width
• 2nd June 2022 Max Bannach, Malte Skambath, Till Tantau. On the Parallel Parameterized Complexity of MaxSAT Variants
• 1st June 2022 Robert Ganian, Eun Jung Kim, Stefan Szeider. Algorithmic Applications of Tree-Cut Width
• 1st June 2022 Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• 25th May 2022 Marcelo P. L. Benedito, Lucas P. Melo, Lehilton L. C. Pedrosa. A parameterized approximation algorithm for the Multiple Allocation k-Hub Center
• 23rd May 2022 Mateus de Oliveira Oliveira, Farhad Vadiee. From Width-Based Model Checking to Width-Based Automated Theorem Proving
• 22nd May 2022 Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli, Alessandra Tappini. On the Parameterized Complexity of the s-Club Cluster Edge Deletion Problem
• 16th May 2022 David G. Harris, N. S. Narayanaswamy. A faster algorithm for Vertex Cover parameterized by solution size
• 16th May 2022 Alexander S. Kulikov, Ivan Mihajlin. Polynomial formulations as a barrier for reduction-based hardness proofs
• 13th May 2022 Andrew Fraser, Brian Lavallee, Blair D. Sullivan. Gerrymandering Trees: Parameterized Hardness
• 10th May 2022 Todd Wareham. Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach
• 10th May 2022 Todd Wareham, Marieke Sweers. Exploring Viable Algorithmic Options for Automatically Creating and Reconfiguring Component-based Software Systems: A Computational Complexity Approach (Full Version)
• 10th May 2022 Todd Wareham, Andrew Vardy. Environmental Sensing Options for Robot Teams: A Computational Complexity Perspective
• 5th May 2022 Wojciech Nadara, Michał Pilipczuk, Marcin Smulewicz. Computing treedepth in polynomial space and linear fpt time
• 2nd May 2022 Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, Uéverton S. Souza. Taming graphs with no large creatures and skinny ladders
• 2nd May 2022 Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz. Token sliding on graphs of girth five
• 2nd May 2022 Antoine Amarilli, Mikaël Monet. Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
• 1st May 2022 Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, Anna Zych-Pawlewicz. Dynamic data structures for parameterized string problems
• 29th April 2022 Faisal Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, Kevin Mann. Enumerating Connected Dominating Sets
• 28th April 2022 Max Bannach, Pamela Fleischmann, Malte Skambath. MaxSAT with Absolute Value Functions: A Parameterized Perspective
• 22nd April 2022 Josh Alman, Dean Hirsch. Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
• 22nd April 2022 Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, Sebastian Siebertz. A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems
• 21st April 2022 Niclas Boehmer, Klaus Heeger. Adapting Stable Matchings to Forced and Forbidden Pairs
• 20th April 2022 Ishay Haviv. A Fixed-Parameter Algorithm for the Schrijver Problem
• 14th April 2022 Ishay Haviv. A Fixed-Parameter Algorithm for the Kneser Problem
• 12th April 2022 Valentin Bartier, Nicolas Bousquet, Amer E. Mouawad. Galactic Token Sliding
• 12th April 2022 Pierre Bergé, Anthony Busson, Carl Feghali, Rémi Watrigant. 1-Extendability of independent sets
• 11th April 2022 Thekla Hamm, Nina Klobas, George B. Mertzios, Paul G. Spirakis. The Complexity of Temporal Vertex Cover in Small-Degree Graphs
• 6th April 2022 Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz. Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings
• 29th March 2022 Philipp Zschoche. Restless Temporal Path Parameterized Above Lower Bounds
• 29th March 2022 Carolina Lucía Gonzalez, Felix Mann. On d-stable locally checkable problems on bounded mim-width graphs
• 25th March 2022 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa. Independent set reconfiguration on directed graphs
• 24th March 2022 Tuukka Korhonen. Grid Induced Minor Theorem for Graphs of Small Degree
• 18th March 2022 Jeroen L.G. Schols. Kernelization for Treewidth-2 Vertex Deletion
• 16th March 2022 Rajesh Chitnis, Nitin Saurabh. Tight Lower Bounds for Approximate & Exact k-Center in Rd
• 15th March 2022 Dániel Marx. Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
• 15th March 2022 Michael J. Bremner, Zhengfeng Ji, Ryan L. Mann, Luke Mathieson, Mauro E.S. Morales, Alexis T.E. Shaw. Quantum Parameterized Complexity
• 14th March 2022 Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz, Frank Sommer, Petra Wolf. Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs
• 11th March 2022 Leon Kellerhals, Tomohiro Koana, Pascal Kunz. Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
• 10th March 2022 Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, Kirill Simonov. Parameterized Algorithms for Upward Planarity
• 9th March 2022 Kei Kimura, Kotaro Nakayama. Neighborhood persistency of the linear optimization relaxation of integer linear optimization
• 9th March 2022 Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski. Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
• 7th March 2022 David Fischer, Julian Golak, Matthias Mnich. Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
• 7th March 2022 Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen. Few Induced Disjoint Paths for H-Free Graphs
• 6th March 2022 Narmina Baghirova, Carolina Lucía Gonzalez, David Schindl. Locally checkable problems in bounded clique-width graphs
• 3rd March 2022 Hauke Brinkop, Klaus Jansen. High Multiplicity Scheduling on Uniform Machines in FPT-Time
• 28th February 2022 Cornelius Brand, Esra Ceylan, Christian Hatschka, Robert Ganian, Viktoriia Korchemna. Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
• 27th February 2022 Benjamin Bergougnoux, Jan Dreier, Lars Jaffke. A logic-based algorithmic meta-theorem for mim-width
• 25th February 2022 Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk. Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
• 25th February 2022 Samuel Hand, Jessica Enright, Kitty Meeks. Making Life More Confusing for Firefighters
• 24th February 2022 Soeren Nickel, Martin Nöllenburg, Manuel Sorge, Anaïs Villedieu, Hsiang-Yun Wu, Jules Wulms. Planarizing Graphs and their Drawings by Vertex Splitting
• 24th February 2022 Jessica Enright, Kitty Meeks, Hendrik Molter. Counting Temporal Paths
• 24th February 2022 Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Saket Saurabh. Parameterized Complexity of Graph Partitioning into Connected Clusters
• 24th Febuary 2022 Nicolas El Maalouly, Raphael Steiner. Exact Matching in Graphs of Bounded Independence Number
• 24th February 2022 Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondřej Suchý, Tomáš Valla. Polynomial Kernels for Tracking Shortest Paths
• 20th February 2022 Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi. Finding shortest non-separating and non-disconnecting paths
• 20th February 2022 Steven Kelk, Simone Linz, Ruben Meuwese. Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
• 17th February 2022 Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski. Computing list homomorphisms in geometric intersection graphs
• 17th February 2022 Tatsuya Gima, Yota Otachi. Extended MSO Model Checking via Small Vertex Integrity
• 17th February 2022 Eric Angel, Sébastien Morais, Damien Regnault. A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graph with Bounded Tree-width
• 16th February 2022 Jan Dreier, Sebastian Ordyniak, Stefan Szeider. SAT Backdoors: Depth Beats Size
• 16th February 2022 Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman. The Parameterized Complexity of Quantum Verification
• 16th February 2022 Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs. Quantum speedups for treewidth
• 15th February 2022 Hisao Tamaki. Heuristic computation of exact treewidth
• 14th February 2022 Tesshu Hanaka, Michael Lampis. Hedonic Games and Treewidth Revisited
• 14th February 2022 Danny Hermelin, Hendrik Molter, Dvir Shabtay. Single Machine Weighted Number of Tardy Jobs Minimization With Small Weights
• 14th February 2022 Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen. Problems hard for treewidth but easy for stable gonality
• 9th February 2022 Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang. Constant Approximating Parameterized k-SetCover is W[2-hard]
• 7th February 2022 Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions
• 7th February 2022 Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov. Longest Cycle above Erdős-Gallai Bound
• 6th February 2022 Ying Liu. The Exponential-Time Complexity of the complex weighted #CSP
• 4th February 2022 Bart M. P. Jansen, Michał Włodarczyk. Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
• 4th February 2022 Ajinkya Gaikwad, Soumen Maity. Globally Minimal Defensive Alliances: A Parameterized Perspective
• 3rd February 2022 Niclas Boehmer, Robert Bredereck, Klaus Heeger, Dušan Knop, Junjie Luo. Multivariate Algorithmics for Eliminating Envy by Donating Goods
• 2nd February 2022 Cristiano Bocci, Chiara Capresi, Kitty Meeks, John Sylvester. A New Temporal Interpretation of Cluster Editing
• 2nd February 2022 Yixin Cao, Jianxin Wang, Hanchun Yuan. Modification Problems toward Proper (Helly) Circular-arc Graphs
• 31st January 2022 Maël Dumas, Anthony Perez, Mathis Rocton, Ioan Todinca. Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• 31st January 2022 Hans L. Bodlaender, Carla Groenland, Hugo Jacob. XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
• 30th January 2022 Bin Sheng, Gregory Gutin. Solving Routing Problems via Important Cuts
• 28th January 2022 Vikraman Arvind, Ilia Ponomarenko, Grigory Ryabov. Isomorphism testing of k-spanning tournaments is Fixed Parameter Tractable
• 27th January 2022 Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler, Sebastian Ordyniak, Daniël Paulusma. An Algorithmic Framework for Locally Constrained Homomorphisms
• 24th January 2022 Hugo Jacob, Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• 22nd January 2022 Dmitry Gribanov, Dmitry Malyshev. Faster ILP Algorithms for Problems with Sparse Matrices and Their Applications to Multipacking and Multicover Problems in Graphs and Hypergraphs
• 21st January 2022 Till Tantau. On the Satisfaction Probability of k-CNF Formulas
• 18th January 2022 Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith. The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
• 14th January 2022 Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer. The Parameterized Complexity of s-Club with Triangle and Seed Constraints
• 14th January 2022 Tomohiro Koana, Christian Komusiewicz, André Nichterlein, Frank Sommer. Covering Many (or Few) Edges with k Vertices in Sparse Graphs
• 14th January 2022 Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, Malte Renken. Delay-Robust Routes in Temporal Graphs
• 12th January 2022 Weidong Luo. Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
• 11th January 2022 Fahad Panolan, Hannane Yaghoubizade. Partial Vertex Cover on Graphs of Bounded Degeneracy
• 10th January 2022 Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman. Deletion to Scattered Graph Classes II -- Improved FPT Algorithms for Deletion to Pairs of Graph Classes
• 10th January 2022 Gordon Hoi, Ammar Fathin Sabili, Frank Stephan. An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
• 10th January 2022 Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, Saket Saurabh. Detours in Directed Graphs
• 6th January 2022 Igor Razgon. The splitting power of branching programs of bounded repetition and CNFs of bounded width
• 6th January 2022 Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi. Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
• 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

Earlier papers are listed here, due to page-size limitations