89 citations · 484 across the 68 of their papers we have counts for
9 papers · 1 filter
Constraint Solving via Fractional Edge Covers
Martin Grohe, Dániel Marx
Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has…
On the hardness of losing weight
Andrei Krokhin, Dániel Marx
We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, an…
Completely inapproximable monotone and antimonotone parameterized problems
Dániel Marx
We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function $…
Clustering with Local Restrictions
Daniel Lokshtanov, Dániel Marx
We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let be a function on the subsets of vertices of a graph…
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often domin…
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
Andreas Emil Feldmann, Daniel Marx
Given a directed graph and a list of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of that contains a di…