b'D\xc3\xa1niel Marx'

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...

0 Fateme Abbasi, et al. ∙

research

∙ 04/06/2023

Parameterized Approximation Schemes for Clustering with General Norm Objectives

This paper considers the well-studied algorithmic regime of designing a ...

0 Fateme Abbasi, et al. ∙

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...

0 Akanksha Agrawal, et al. ∙

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 ...

0 Jacob Focke, et al. ∙

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...

0 Barış Can Esmer, et al. ∙

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...

0 Barış Can Esmer, et al. ∙

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...

0 Esther Galby, et al. ∙

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...

0 Esther Galby, et al. ∙

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...

0 Barış Can Esmer, et al. ∙

research

∙ 05/20/2022

Parameterized Complexity of Weighted Multicut in Trees

The Edge Multicut problem is a classical cut problem where given an undi...

0 Esther Galby, et al. ∙

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...

0 Karl Bringmann, et al. ∙

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...

0 Dániel Marx, et al. ∙

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...

0 Dániel Marx, et al. ∙

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...

0 Dániel Marx, et al. ∙

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...

0 Jacob Focke, et al. ∙

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...

0 Dániel Marx, et al. ∙

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...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 08/18/2020

Four short stories on surprising algorithmic uses of treewidth

This article briefly describes four algorithmic problems where the notio...

0 Dániel Marx, et al. ∙

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...

0 Marvin Künnemann, et al. ∙

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 ...

0 Dániel Marx, et al. ∙

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...

0 Alexander Göke, et al. ∙

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...

0 Alexander Göke, et al. ∙

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...

0 Rajesh Chitnis, et al. ∙

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...

0 Sándor Kisfaludi-Bak, et al. ∙

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...

0 Arnab Bhattacharyya, et al. ∙

research

∙ 08/13/2019

Finding and counting permutations via CSPs

Permutation patterns and pattern avoidance have been intensively studied...

0 Benjamin Aram Berendsohn, et al. ∙

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...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 02/23/2019

Slightly Superexponential Parameterized Problems

A central problem in parameterized algorithms is to obtain algorithms ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 02/21/2019

Covering a tree with rooted subtrees

We consider the multiple traveling salesman problem on a weighted tree. ...

0 Lin Chen, et al. ∙

research

∙ 12/07/2018

Kernelization of Packing Problems

Kernelization algorithms are polynomial-time reductions from a problem t...

0 Holger Dell, et al. ∙

research

∙ 10/16/2018

Multi-budgeted directed cuts

We study multi-budgeted variants of the classic minimum cut problem and ...

0 Stefan Kratsch, et al. ∙

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...

0 Gábor Bacsó, et al. ∙

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...

0 Mark de Berg, et al. ∙

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...

0 Mark de Berg, et al. ∙

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...

0 Andreas Emil Feldmann, et al. ∙

research

∙ 11/13/2017

Constraint Solving via Fractional Edge Covers

Many important combinatorial problems can be modeled as constraint satis...

0 Martin Grohe, et al. ∙

research

∙ 11/10/2017

On the hardness of losing weight

We study the complexity of local search for the Boolean constraint satis...

0 Andrei Krokhin, et al. ∙

research

∙ 11/10/2017

Completely inapproximable monotone and antimonotone parameterized problems

We prove that weighted circuit satisfiability for monotone or antimonoto...

0 Dániel Marx, et al. ∙

research

∙ 11/10/2017

Clustering with Local Restrictions

We study a family of graph clustering problems where each cluster has to...

0 Daniel Lokshtanov, et al. ∙

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...

0 Albert Atserias, et al. ∙

research

∙ 01/16/2014

Soft Constraints of Difference and Equality

In many combinatorial problems one may need to model the diversity or si...

0 Emmanuel Hébrard, et al. ∙

Dániel Marx

Featured Co-authors