NP-hardness of Circuit Distance for polygons
NP-hardness of Circuit Distance for polygons
Let be a polytope defined by a matrix and a vector , let and be vertices of , and let . A circuit walk is a walk from to whose steps follow circuit directions of . The conjectured decision problem asks whether there is a circuit walk from to of length at most .
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
Sign in to submit a solution.
No solutions have been posted yet.