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