NP-hardness of square root for planar graphs

Conjecture 1.3 · arXiv:2205.12764

arXiv Conjecture high confidence— first stated 2023-07-13

Authors: Zdeněk Dvořák, Benjamin Moore, Abhiruk Lahiri

Status open high confidence

Conjecture 1.3 from arXiv:2205.12764 asserts that the H-square-root problem is NP-complete when H is the class of planar graphs. The source paper proves NP-hardness for the broader class of 6-apex graphs (a proper minor-closed class below planar in the bounded-expansion hierarchy), and the conjecture asks whether apex vertices are truly necessary. No follow-up paper resolving or making partial progress on the planar case was found in indexed literature as of May 2026.

Reviewer notes. No follow-up found after 5 web calls. The conjecture is recent (2023) and no resolution was found; open with high confidence. The paper arXiv:2211.02699 ('Characterizing and recognizing exact-distance squares of graphs') appeared in a citation API response but is unrelated to this conjecture.

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

Conjecture. The $\mathcal{H}$-square-root problem is NP-complete for the class $\mathcal{H}$ of planar graphs.

Context

The authors prove NP-completeness of the H-square-root problem for the class of 6-apex graphs (a proper minor-closed class), and note that 6-apex graphs lie at the bottom of the bounded-expansion hierarchy. They ask whether apex vertices are truly necessary or whether planarity alone already makes the problem hard, and state they believe the latter is the case.

Source paper

Square roots of nearly planar graphs
Zdeněk Dvořák, Benjamin Moore, Abhiruk Lahiri · 2023-07-13
https://arxiv.org/abs/2205.12764 PDF source