NP-hardness of Circuit Distance for polytopes
Conjecture 21 · arXiv:2510.01916
Status open high confidence
Conjecture 21 from arXiv:2510.01916 posits that Circuit Distance (the non-monotone variant) is NP-hard for polygons. The paper's main result (Theorem 1) already establishes NP-hardness for the monotone variant, and the authors remark that their proof techniques seem likely to extend to the non-monotone setting. No follow-up paper resolving this conjecture was found in a wide web search; the conjecture is very recent (October 2025) and remains open.
Reviewer notes. The paper proves NP-hardness of Monotone Circuit Distance for polygons (Theorem 1) and conjectures the same holds for the non-monotone Circuit Distance problem (Conjecture 21). The conjecture is recent (≤ 1 year) and a wide search found no resolution; open with high confidence. A related ScienceDirect paper 'On the hardness of short and sign-compatible circuit walks' (pii/S0166218X25000678) may be relevant background work but returned HTTP 403 and could not be verified.
Context
The authors focus on monotone circuit walks as most directly relevant to circuit augmentation schemes, but note the non-monotone variant is natural too. The Circuit Distance problem asks whether there is a circuit walk from $\mathbf{s}$ to $\mathbf{t}$ of length at most $k$ in a polytope $P=\{\mathbf{x}\in\mathbb{R}^{n}\colon Ax\leq\mathbf{b}\}$. The authors remark that their proof techniques seem likely to extend to this non-monotone setting.
Notes. Polygons are 2-dimensional polytopes; in this case circuit directions coincide with edge directions (as noted in Observation 9 of the paper).
Source paper
Short circuit walks in fixed dimension
Alexander E. Black, Christian Nöbel, Raphael Steiner · 2025-10-02
https://arxiv.org/abs/2510.01916