NP-hardness of Circuit Distance for polygons

From papers

Let P={xRn ⁣:Axb}P = \{\mathbf{x}\in \mathbb{R}^n\colon A\mathbf{x}\leq \mathbf{b}\} be a polytope defined by a matrix AQm×nA\in \mathbb{Q}^{m\times n} and a vector bQm\mathbf{b}\in \mathbb{Q}^m, let s\mathbf{s} and t\mathbf{t} be vertices of PP, and let kZ0k\in \mathbb{Z}_{\geq 0}. A circuit walk is a walk from s\mathbf{s} to t\mathbf{t} whose steps follow circuit directions of PP. The conjectured decision problem asks whether there is a circuit walk from s\mathbf{s} to t\mathbf{t} of length at most kk.

Circuit Distance conjecture. The Circuit Distance problem is NP-hard for polygons.

The paper notes that the proof techniques for monotone circuit walks seem likely to extend to the undirected setting but require technical innovation; the claimed NP-hardness for polygons therefore remains open in the supplied source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alexander E. Black, Christian Nöbel and Raphael Steiner, “Short circuit walks in fixed dimension”, arXiv:2510.01916 (2025).

Solutions 0

No solutions have been posted yet.