Daniel Neuen

SODA Conference 2025 Conference Paper

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

• Radu Curticapean
• Daniel Neuen

SODA Conference 2024 Conference Paper

Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations

• Baris Can Esmer
• Ariel Kulik
• Dániel Marx
• Daniel Neuen
• Roohani Sharma

FOCS Conference 2023 Conference Paper

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements

• Martin Grohe
• Moritz Lichter
• Daniel Neuen
• Pascal Schweitzer

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai’s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the k-tuples of vertices of a graph. Since Fürer’s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. We answer this question affirmatively, establishing an $\Omega\left(n^{k / 2}\right)$-lower bound for all k.

SODA Conference 2023 Conference Paper

Computing Square Colorings on Bounded-Treewidth and Planar Graphs

• Akanksha Agrawal 0001
• Dániel Marx
• Daniel Neuen
• Jasper Slusallek

A square coloring of a graph G is a coloring of the square G 2 of G, that is, a coloring of the vertices of G such that any two vertices that are at distance at most 2 in G receive different colors. We investigate the complexity of finding a square coloring with a given number of q colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time for graphs of treewidth at most tw. The somewhat unusual exponent 2 tw in the running time is essentially optimal: we show that for any ε > 0, there is no algorithm with running time f (tw)n (2-ε) tw unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number q ≥ 4 of colors. Our main algorithmic result is showing that the problem (when the number of colors q is part of the input) can be solved in subexponential time on planar graphs. The result follows from the combination of two algorithms. If the number q of colors is small (≤ n 1/3 ), then we can exploit a treewidth bound on the square of the graph to solve the problem in time. If the number of colors is large (≥ n 1/3 ), then an algorithm based on protrusion decompositions and building on our result for the bounded- treewidth case solves the problem in time. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 04458. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

SODA Conference 2023 Conference Paper

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

• Jacob Focke
• Dániel Marx
• Fionn Mc Inerney
• Daniel Neuen
• Govind S. Sankar
• Philipp Schepper
• Philip Wellnitz

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 of a graph G is a set S of vertices such that | N ( u ) ∩ S | ∈ σ for every u ∈ S, and | N ( v ) ∩ S | ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value c σ, ρ such that there is an algorithm that counts (σ, ρ)-sets in time c tw σ, ρ · n O(1) (if a tree decomposition of width tw is given in the input). Let s top denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; r top is defined analogously for ρ. Surprisingly, c σ, ρ is often significantly smaller than the natural bound s top + r top + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining c σ, ρ, we say that (σ, ρ) is m -structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • c σ, ρ = s top + r top +2 if (σ, ρ) is not m-structured for any m ≥ 2 • c σ, ρ = max{ s top, r top } + 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and s top = r top is even, and • c σ, ρ = max{ s top, r top } + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time c tw σ, ρ · n O(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3 tw · n O(1) algorithm of van Rooij to 2 tw · n O(1). Despite the unusually delicate definition of c σ, ρ, we show that our algorithms are most likely optimal, i. e. , for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a ( c σ, ρ — ε) tw · n O(1) - algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https: //arxiv. org/abs/2211. 04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

SODA Conference 2022 Conference Paper

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs

• Dániel Marx
• Pranabendu Misra
• Daniel Neuen
• Prafullkumar Tale

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 paper is to introduce a framework for obtaining time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node U nique L abel C over problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, O dd C ycle T ransversal, S ubset F eedback V ertex S et, G roup F eedback V ertex S et, S ubset G roup F eedback V ertex S et, V ertex M ultiway C ut, and C omponent O rder C onnectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain time (randomized) algorithms for V ertex M ultiway C ut, G roup F eedback V ertex S et, and S ubset F eedback V ertex S et. Our algorithms are designed with possible generalization to H -minor free graphs in mind. To obtain the same time algorithms on H -minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

SODA Conference 2022 Conference Paper

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

• Daniel Neuen

We give an isomorphism test that runs in time n polylog( h ) on all n -vertex graphs excluding some h -vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n polylog( n ) (Babai, STOC 2016) and n f ( h ) for some function f (Grohe and Marx, SIAM J. Comp. , 2015). Our result also unifies and extends previous isomorphism tests for graphs of maximum degree d running in time n polylog( d ) (FOCS 2018) and for graphs of Hadwiger number h running in time n polylog( h ) (FOCS 2020).

FOCS Conference 2020 Conference Paper

Isomorphism Testing for Graphs Excluding Small Minors

• Martin Grohe
• Daniel Wiebking
• Daniel Neuen

We prove that there is a graph isomorphism test running in time n polylog(h) on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were n poly(h) (Ponomarenko, 1988) and n polylog(n) (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.

MFCS Conference 2019 Conference Paper

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

• Sandra Kiefer
• Daniel Neuen

The Weisfeiler-Leman procedure is a widely-used approach for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into bi- and triconnected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its triconnected components. Thus, the dimension of the algorithm needed to distinguish two given graphs is at most the dimension required to distinguish the corresponding decompositions into 3-connected components (assuming dimension at least 2). This result implies that for k >= 2, the k-dimensional algorithm distinguishes k-separators, i. e. , k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

FOCS Conference 2018 Conference Paper

A Faster Isomorphism Test for Graphs of Small Degree

• Martin Grohe
• Daniel Neuen
• Pascal Schweitzer

In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^O((log d)^c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d log d).

STOC Conference 2018 Conference Paper

An exponential lower bound for individualization-refinement algorithms for graph isomorphism

• Daniel Neuen
• Pascal Schweitzer

The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question what the running time of individualization-refinement algorithms is. For all we know some of the algorithms could have polynomial running time. In this work we give a negative answer to this question and construct a family of graphs on which algorithms based on the individualization-refinement paradigm require exponential time. Contrary to a previous construction of Miyazaki, that only applies to a specific implementation within the individualization-refinement framework, our construction is immune to changing the cell selector, the refinement operator, the invariant that is used, or adding various heuristic invariants to the algorithm. In fact, our graphs also provide exponential lower bounds in the case when the k -dimensional Weisfeiler-Leman algorithm is used to replace the the 1-dimensional Weisfeiler-Leman algorithm (often called color refinement) that is normally used. Finally, the arguments even work when the entire automorphism group of the inputs is initially provided to the algorithm. The arguments apply to isomorphism testing algorithms as well as canonization algorithms within the framework.