4 citations · 6 across the 9 of their papers we have counts for
18 papers
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfmann, Dani Dorfman, Simon Döring +5
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for…
The Classical Weisfeiler-Leman Algorithm Stabilizes in Rounds
Simon Döring, Daniel Neuen
The classical Weisfeiler-Leman algorithm (also known as the -dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuris…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
Daniel Neuen, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., and admit the same number of…
Treedepth Inapproximability and Exponential ETH Lower Bound
Édouard Bonnet, Daniel Neuen, Marek Sokołowski
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a -time exact algorith…
Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
Radu Curticapean, Simon Döring, Daniel Neuen
We consider the parameterized problem IndSub for fixed graph properties : Given a graph and an integer , this problem asks to count the number of induced -ver…
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Can You Link Up With Treewidth?
Radu Curticapean, Simon Döring, Daniel Neuen +1
In a fundamental paper in parameterized complexity theory, Marx [ToC '10] constructed -vertex graphs of maximum degree such that time algorithms for d…
Counting Small Induced Subgraphs: Hardness via Fourier Analysis
Radu Curticapean, Daniel Neuen
For a fixed graph property and integer , consider the problem of counting the induced -vertex subgraphs satisfying in an input graph . This problem can be s…
Approximate Monotone Local Search for Weighted Problems
Baris Can Esmer, Ariel Kulik, Daniel Marx +2
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algor…
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width
Daniel Neuen
Two graphs are homomorphism indistinguishable over a graph class , denoted by , if for al…
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…
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J. ACM 2019], by establishing a connection between parameterized approximation and expon…
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Dániel Marx, Pranabendu Misra, Daniel Neuen +1
Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this pa…
Isomorphism Testing Parameterized by Genus and Beyond
Daniel Neuen
We give an isomorphism test for graphs of Euler genus running in time . Our algorithm provides the first explicit upper bound on the dependence on $g…