Skip to content
Preprint

Deterministic $n^{O(\log n)}$ Graph Isomorphism Algorithm via Inherited Decompositions

Nov 2026 · 0 citations
Computer Science

TL;DR

This is the first proof of such a worst-case bound for general graphs isomorphism, and improves the explicit cubic logarithmic exponent in the analysis of the corrected Luks--Babai algorithm.

Abstract

We give a deterministic $n^{O(\log d)}$-time algorithm for isomorphism of graphs with $n$ vertices and maximum degree $d$. Since $d<n$, this is an $n^{O(\log n)}$-time algorithm for graph isomorphism. To our knowledge, this is the first proof of such a worst-case bound for general graphs. It improves the explicit cubic logarithmic exponent in the analysis of the corrected Luks--Babai algorithm. For graphs of maximum degree $d$, the best previous bound known to us, due to Grohe, Neuen, and Schweitzer, is $n^{O((\log d)^c)}$ for an absolute constant $c$. The algorithm uses the local-certificate and color-refinement steps of Babai's quasipolynomial algorithm, but retains the decomposition of each recursive instance when it solves an auxiliary coloring problem. There are two reasons for retaining this information. First, a local test can make progress without removing many vertices: it can eliminate a layer of permutation symmetry. A logarithmic bound on the total weight of these layers allows tests of constant size. Second, the auxiliary bipartite graphs arising in the symmetry-breaking step can be represented inside the current instance, after retaining a row decomposition when necessary. These recursive calls inherit the progress already made. Two further observations give the dependence on the degree. The recursive calls made by a local test check disjoint parts of the instance, so together they cost about as much as one call on the whole instance. And for graphs of maximum degree $d$, each large symmetric action that the algorithm must break acts on at most $d$ points. We present the algorithm through colorings, partitions, and bipartite graphs, and collect the permutation-group ingredients in one appendix. The result extends to string isomorphism and returns one isomorphism and generators for the full automorphism group.

View source

Similar papers

Preprint Nov 2026

Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ space

We present an algorithm that, given read-only access to the adjacency matrix of an $n$-vertex graph $G$, computes the number of $6$-cliques in $G$ using $O(n^{5.97})$ time and $O(\log n)$ space. We achieve this by exploiting a decomposition of an equality indicator function underlying, among others, the refutations of...

Afrouz Jabal Ameli, Niklas Mohrin, Jesper Nederlof · 0 citations
Preprint Oct 2026

Fast Distributed $(\Delta + 1)$-Edge Coloring in Bipartite Graphs

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(\Delta + 1)$-edge coloring can be solved deterministically in $O(f(\Delta) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(\Delta + 1)$-edge coloring on bip...

Yann Bourreau, Sebastian Brandt, Ananth Narayanan · 0 citations
Preprint Oct 2026

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA'27). To achieve this result, we introduce a new algorithmic framework for finding a large indepe...

Kaisei Deguchi, K. Kawarabayashi, Hirotaka Yoneda et al. · 0 citations
Preprint Nov 2026

Minimum-Cost $k$-Arborescence Packing in $\tilde O(km+k^4 n)$ Time

We give a deterministic, strongly polynomial algorithm running in $\tilde{O}(km+k^4n)$ time that finds $k$ arc-disjoint arborescences of minimum total cost in a directed multigraph with $n$ vertices and $m$ arcs. This significantly improves upon the state of the art for $k \ge 2$ with $k=n^{o(1)}$: the prior fastest we...

Zhaienhe Zhou · 0 citations
Preprint Oct 2026

A quasi-polynomial $\chi$-bound for $P_6$-free graphs

In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $\chi(G)\le \omega(G)^{c\log_2\omega(G)}$ for $c=45/\log_2(4/3)<109$. The best previous bound was exponential in $\omega(G)$. Our result is the first quasi-polynomial bound for $P_6$-free graphs and generalizes the bound for $P_5$-fre...

Shen-Wei Huang, Yi-Dong Zhou, Yuwen Zhou · 0 citations
Preprint Oct 2026

The chromatic number of a random graph with $o(n^{3/2})$ edges

Let $G(n,m)$ be the Erdos-Renyi random graph with $n$ vertices and $m$ edges and let $\delta>0$. Alon and Krivelevich [Combinatorica 1997] proved that for any sequence $m\leq n^{3/2-\delta}$ there \emph{exists} an integer sequence $q=q(n)$ such that the chromatic number of $G(n,m)$ equals either $q$ or $q+1$ with proba...

Amin Coja-Oghlan, M. Isaev, Mih-Yun Kang et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.