research
∙
08/29/2023
Approximate Monotone Local Search for Weighted Problems
In a recent work, Esmer et al. describe a simple method - Approximate Mo...
share
research
∙
06/27/2023
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
The goal of this paper is to understand how exponential-time approximati...
research
∙
05/26/2023
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
For a well-studied family of domination-type problems, in bounded-treewi...
research
∙
05/12/2023
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
We consider the well-studied Robust (k, z)-Clustering problem, which gen...
research
∙
04/06/2023
Parameterized Approximation Schemes for Clustering with General Norm Objectives
This paper considers the well-studied algorithmic regime of designing a ...
research
∙
11/08/2022
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
A square coloring of a graph G is a coloring of the square G^2 of G, tha...
research
∙
11/08/2022
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
We investigate how efficiently a well-studied family of domination-type ...
research
∙
10/19/2022
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
The goal of this paper is to investigate a family of optimization proble...
research
∙
09/04/2022
Computing Generalized Convolutions Faster Than Brute Force
In this paper, we consider a general notion of convolution. Let D be a f...
research
∙
08/11/2022
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
In the Directed Steiner Network problem, the input is a directed graph G...
research
∙
08/04/2022
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
The leafage of a chordal graph G is the minimum integer l such that G ca...
research
∙
06/27/2022
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
We generalize the monotone local search approach of Fomin, Gaspers, Loks...
research
∙
05/20/2022
Parameterized Complexity of Weighted Multicut in Trees
The Edge Multicut problem is a classical cut problem where given an undi...
research
∙
03/15/2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
The Dynamic Time Warping (DTW) distance is a popular measure of similari...
research
∙
03/15/2022
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
Conditional lower bounds based on P≠ NP, the Exponential-Time Hypothesis...
research
∙
10/28/2021
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Subexponential parameterized algorithms are known for a wide range of na...
research
∙
10/18/2021
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
In the general AntiFactor problem, a graph G is given with a set X_v⊆ℕ o...
research
∙
07/14/2021
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
The goal of this work is to give precise bounds on the counting complexi...
research
∙
05/19/2021
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
For the General Factor problem we are given an undirected graph G and fo...
research
∙
09/01/2020
On the computational tractability of a geographic clustering problem arising in redistricting
Redistricting is the problem of dividing a state into a number k of regi...
research
∙
08/18/2020
Four short stories on surprising algorithmic uses of treewidth
This article briefly describes four algorithmic problems where the notio...
research
∙
05/23/2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
To study the question under which circumstances small solutions can be f...
research
∙
04/24/2020
Incompressibility of H-free edge modification problems: Towards a dichotomy
Given a graph G and an integer k, the H-free Edge Editing problem is to ...
research
∙
03/11/2020
Hitting Long Directed Cycles is Fixed-Parameter Tractable
In the Directed Long Cycle Hitting Set problem we are given a directed g...
research
∙
03/05/2020
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
The Directed Feedback Vertex Set (DFVS) problem takes as input a directe...
research
∙
11/29/2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertex-weighted directed graph G...
research
∙
09/26/2019
How does object fatness impact the complexity of packing in d dimensions?
Packing is a classical problem where one is given a set of subsets of Eu...
research
∙
09/04/2019
Parameterized Intractability of Even Set and Shortest Vector Problem
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
08/13/2019
Finding and counting permutations via CSPs
Permutation patterns and pattern avoidance have been intensively studied...
research
∙
03/20/2019
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponentia...
research
∙
02/23/2019
Slightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms ...
research
∙
02/21/2019
Covering a tree with rooted subtrees
We consider the multiple traveling salesman problem on a weighted tree. ...
research
∙
12/07/2018
Kernelization of Packing Problems
Kernelization algorithms are polynomial-time reductions from a problem t...
research
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
04/11/2018
Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
In algorithmic graph theory, a classic open question is to determine the...
research
∙
03/28/2018
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
03/28/2018
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
02/23/2018
The Parameterized Hardness of the k-Center Problem in Transportation Networks
In this paper we study the hardness of the k-Center problem on inputs th...
research
∙
11/13/2017
Constraint Solving via Fractional Edge Covers
Many important combinatorial problems can be modeled as constraint satis...
research
∙
11/10/2017
On the hardness of losing weight
We study the complexity of local search for the Boolean constraint satis...
research
∙
11/10/2017
Completely inapproximable monotone and antimonotone parameterized problems
We prove that weighted circuit satisfiability for monotone or antimonoto...
research
∙
11/10/2017
Clustering with Local Restrictions
We study a family of graph clustering problems where each cluster has to...
research
∙
11/10/2017
Size bounds and query plans for relational joins
Relational joins are at the core of relational algebra, which in turn is...
research
∙
01/16/2014