Minimum reverse-complement-invariant decycling sets

Let $\Sigma$ be a finite nonempty alphabet of size $q$ with a fixed-point-free involution $a\mapsto\bar a$ , and let $k\ge2$ . The directed de Bruijn graph $B(q,k)$ has length- $k$ words as vertices and one-symbol-shift edges, including loops. Put $\rho(a_1\cdots a_k)=\bar a_k\cdots\bar a_1$ .

What is the minimum cardinality $\tau_{\rm RC}(q,k)$ of a set $M\subseteq\Sigma^k$ such that $\rho(M)=M$ and deleting $M$ makes $B(q,k)$ acyclic?

This is the minimum-size symmetric-decycling problem described as open by Marçais, Elder and Kingsford (2024), Section 6. Section 5.1 also identifies the lack of constructions of symmetric ordinary minimum decycling sets. The classical minimum without symmetry is $N_q(k)=\frac1k\sum_{d\mid k}\varphi(d)q^{k/d}$ . This entry reports a parity theorem toward the symmetry-constrained problem.

Result: Proved(see note)
Status: Partial result
AI contribution: AI-assisted
Method: Argument
Field: de Bruijn graphs; unavoidable sets; reverse-complement symmetry
Posed by: Guillaume Marçais, C. S. Elder and Carl Kingsford, k-nonical space: sketching with reverse complements (2024), Section 6; see also Section 5.1
Year posed: 2024
Years open: 2y
Solved: 2026-08
Model: GPT-5.6 Sol; GPT-5 Pro
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Significance: 12 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1 claims, for every finite nonempty alphabet with a fixed-point-free complement and every $k\ge2$ ,
$\tau_{\rm RC}(q,k)=N_q(k)\quad\Longleftrightarrow\quad k\text{ is even}.$
For odd $k\ge3$ , Theorem 3.1 gives $\tau_{\rm RC}(q,k)\ge N_q(k)+q$ , hence an excess of at least two for binary words and four for DNA. For even orders, Sections 6-8 provide a weighted construction and a direct spectral selector; integer weights permit exact polynomial-bit membership testing for a single word. The case $k=2$ is handled separately.

This completely classifies attainability of the ordinary minimum and partially answers the external symmetric-minimum question. It does not determine the general exact odd optimum, prove a packing-covering equality, give quantitative residual-path/window bounds, or establish biological performance. The classical ordinary minimum itself is prior work.

What the AI did

The author reports using GPT-5.6 Sol and GPT-5 Pro through ChatGPT. The manuscript and public authorship disclosure describe substantial AI assistance with candidate proof arguments, symbolic identities, construction and verification code, adversarial checks and exposition. The author selected the research problem, directed the work and is responsible for the claims and final manuscript. The model names are author-supplied; the public disclosure does not identify model versions or assign individual lemmas to models. AI-assisted reflects the documented material assistance without asserting that AI discovered the central proof. Agreement between distinct implementations and author-side AI reviews is not independent specialist verification.

Verification

The posed question was read at source. Marcais, Elder and Kingsford, "k-nonical space: sketching with reverse complements", Bioinformatics 40(11), Section 6: "Being a symmetric decycling set is a strong condition that is still not well understood theoretically (e.g. the minimum size of a symmetric decycling set is unknown)." That is the quantity this paper bounds, and the submitter's quotation of it is accurate.

The mathematics was not checked here. The public 15-page manuscript carries analytical proofs, LaTeX source and an exact binary replay using only the standard library; the author's audit of 12 September records an anonymous clone matching all 50 reviewed files and a finite panel over binary $k=2,4,6,8,10,12$ with 612 legal firings and 14 mutations rejected. A finite panel does not establish the uniform $q$ -ary theorem, and no independent specialist endorsement or formal proof is supplied. Partial because the question is answered for half its cases: every even order is settled exactly, and odd orders get a lower bound rather than the optimum.

Sources

Submitted by Oleksiy Babanskyy on 12 Sep 2026

Minimum reverse-complement-invariant decycling sets

What was actually shown

What the AI did

Verification

Sources

Discussion