Even directed circuit in oriented matroids

Status open high confidence

Problem 1.4 asks for a decision procedure for the existence of an even directed circuit in a general oriented matroid. The source paper (published in Combinatorial Theory 2022) shows via Theorem 1.6 that the problem is polynomially equivalent to recognising non-even oriented regular matroids, and provides a forbidden-minor characterisation for non-even oriented bond matroids; however, the general problem for arbitrary oriented matroids is shown to require super-polynomially many signed-circuit oracle calls, leaving its exact computational complexity open. No subsequent paper resolving Problem 1.4 in full generality was found in a targeted web search.

Reviewer notes. The paper itself (Combinatorial Theory, vol. 2 no. 1, 2022) already provides partial resolution: for regular oriented matroids the problem reduces to non-even recognition, and odd directed circuits are detectable in polynomial time. For general oriented matroids the signed-circuit oracle lower bound rules out a polynomial oracle algorithm. The open question is whether a poly-time algorithm exists when the matroid is given by an explicit representation rather than an oracle. No follow-up found after five web calls.

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