Superlinear lower bound for map isomorphism

Open subproblem: conditional superlinear lower bound · arXiv:2008.01616

arXiv Informal medium confidence— first stated 2021-01-07

Authors: Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman

Status open high confidence

No follow-up paper proving a conditional superlinear lower bound for map isomorphism or simultaneous conjugation was found. The best known lower bounds remain the communication complexity bound of Omega(dn log n) for d>1 and the decision tree search-version bound of Omega(n log n), both mentioned in the source paper itself; a conditional lower bound ruling out O(n polylog n) algorithms is still open. The paper was subsequently published as Kawarabayashi et al., ACM Transactions on Algorithms (2024, doi:10.1145/3686798), with the open problem presumably unchanged.

Reviewer notes. The open problem is a conditional complexity lower bound (e.g. under SETH or ETH) that would rule out O(n polylog n) algorithms for map isomorphism or simultaneous conjugation. The algorithmic side has progressed (subquadratic algorithm for simultaneous conjugacy, arXiv:2007.05870, J. Graph Theory 2022), but no matching lower bound result was found in the indexed literature as of May 2026. The published journal version of the source paper (ACM ToA, doi:10.1145/3686798) returned HTTP 403 and could not be verified for any updated open-problem discussion.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. An interesting open subproblem is to prove a conditional ``truly superlinear'' lower bound for any of the mentioned problems (map isomorphism, simultaneous conjugation).

Context

Some progress has been made: the communication complexity of the simultaneous conjugation problem is $\Omega(dn\log n)$ for $d>1$, and under the decision tree model the search version has lower bound $\Omega(n\log n)$. A conditional lower bound ruling out, e.g., $O(n\,\mathrm{polylog}\,n)$ algorithms remains open.

Notes. Stated in prose without a labelled environment; full paper text is truncated so further items in later sections may be missing.

Source paper

Automorphism groups of maps in linear time
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman · 2021-01-07
https://arxiv.org/abs/2008.01616 PDF source