89 citations · 484 across the 68 of their papers we have counts for
10 papers · 1 filter
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Dániel Marx, Daniel Neuen +1
A square coloring of a graph is a coloring of the square of , that is, a coloring of the vertices of such that any two vertices that are at distance at most in…
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…
Computing Generalized Convolutions Faster Than Brute Force
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be…
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx +1
In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgr…
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Esther Galby, Daniel Marx, Philipp Schepper +2
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameter…