89 citations · 484 across the 68 of their papers we have counts for
16 papers · 1 filter
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -set o…
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer, Jacob Focke, Dániel Marx +1
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict t…
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
Dániel Marx
Conditional lower bounds based on , the Exponential-Time Hypothesis (ETH), or similar complexity assumptions can provide very useful information about what type of algori…
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
Dániel Marx, Govind S. Sankar, Philipp Schepper
In the general AntiFactor problem, a graph is given with a set of forbidden degrees for every vertex and the task is to find a set of edges su…
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke, Dániel Marx, Paweł Rzążewski
The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given grap…
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper
For the General Factor problem we are given an undirected graph and for each vertex a finite set of non-negative integers. The task is to decide if there is a…