research
∙
08/29/2023
Approximate Monotone Local Search for Weighted Problems
In a recent work, Esmer et al. describe a simple method - Approximate Mo...
share
research
∙
08/23/2023
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinat...
research
∙
06/27/2023
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
The goal of this paper is to understand how exponential-time approximati...
research
∙
05/26/2023
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
For a well-studied family of domination-type problems, in bounded-treewi...
research
∙
04/14/2023
Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width
Two graphs are homomorphism indistinguishable over a graph class ℱ, deno...
research
∙
01/30/2023
The Iteration Number of the Weisfeiler-Leman Algorithm
We prove new upper and lower bounds on the number of iterations the k-di...
research
∙
11/08/2022
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
A square coloring of a graph G is a coloring of the square G^2 of G, tha...
research
∙
11/08/2022
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
We investigate how efficiently a well-studied family of domination-type ...
research
∙
06/27/2022
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
We generalize the monotone local search approach of Fomin, Gaspers, Loks...
research
∙
06/21/2022
A Study of Weisfeiler-Leman Colorings on Planar Graphs
The Weisfeiler-Leman (WL) algorithm is a combinatorial procedure that co...
research
∙
10/28/2021
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Subexponential parameterized algorithms are known for a wide range of na...
research
∙
06/28/2021
Isomorphism Testing Parameterized by Genus and Beyond
We present an isomorphism test for graphs of Euler genus g running in ti...
research
∙
11/30/2020
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
We give an isomorphism test that runs in time n^polylog(h) on all n-vert...
research
∙
11/02/2020
Recent Advances on the Graph Isomorphism Problem
We give an overview of recent advances on the graph isomorphism problem....
research
∙
04/16/2020
Isomorphism Testing for Graphs Excluding Small Minors
We prove that there is a graph isomorphism test running in time n^polylo...
research
∙
02/17/2020
Hypergraph Isomorphism for Groups with Restricted Composition Factors
We consider the isomorphism problem for hypergraphs taking as input two ...
research
∙
08/14/2019
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
The Weisfeiler-Leman procedure is a widely-used approach for graph isomo...
research
∙
01/29/2019
Canonisation and Definability for Graphs of Bounded Rank Width
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension ...
research
∙
03/19/2018
An improved isomorphism test for bounded-tree-width graphs
We give a new fpt algorithm testing isomorphism of n-vertex graphs of tr...
research
∙
02/13/2018
A Faster Isomorphism Test for Graphs of Small Degree
Luks's algorithm (JCSS 1982) to test isomorphism of bounded degree graph...
research
∙
02/13/2018