89 citations · 484 across the 68 of their papers we have counts for
6 papers · 1 filter
On the computational tractability of a geographic clustering problem arising in redistricting
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
Redistricting is the problem of dividing a state into a number of regions, called districts. Voters in each district elect a representative. The primary criteria are: each dist…
Four short stories on surprising algorithmic uses of treewidth
Dániel Marx
This article briefly describes four algorithmic problems where the notion of treewidth is very useful. Even though the problems themselves have nothing to do with treewidth, it tur…
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
Marvin Künnemann, Dániel Marx
To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean con…
Incompressibility of H-free edge modification problems: Towards a dichotomy
Dániel Marx, R. B. Sandeep
Given a graph and an integer , the -free Edge Editing problem is to find whether there exists at most pairs of vertices in such that changing the adjacency of the…
Hitting Long Directed Cycles is Fixed-Parameter Tractable
Alexander Göke, Dániel Marx, Matthias Mnich
In the Directed Long Cycle Hitting Set} problem we are given a directed graph , and the task is to find a set of at most vertices/arcs such that has no cycle of le…
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
Alexander Göke, Dániel Marx, Matthias Mnich
The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph~ and seeks a smallest vertex set~ that hits all cycles in . This is one of Karp's 21 $\math…