7 papers · 1 filter
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…
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…
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…
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…