89 citations · 484 across the 68 of their papers we have counts for
4 papers · 1 filter
Interval Deletion is Fixed-Parameter Tractable
Yixin Cao, Dániel Marx
We study the minimum \emph{interval deletion} problem, which asks for the removal of a set of at most vertices to make a graph of vertices into an interval graph. We presen…
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Holger Dell, Thore Husfeldt, Dániel Marx +2
We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n))…
Constraint satisfaction parameterized by solution size
Andrei A. Bulatov, Dániel Marx
In the constraint satisfaction problem (CSP) corresponding to a constraint language (i.e., a set of relations) , the goal is to find an assignment of values to variables so that…
Minimizing Movement: Fixed-Parameter Tractability
Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx
We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve…