Arrow Research search

Author name cluster

Daniel Neuen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
1 author row

Possible papers

11

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.

Details

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.

Details

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.

Details

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.

Details

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).

Details