Minimum reverse-complement-invariant decycling sets
Statement
Let be a finite nonempty alphabet of size with a fixed-point-free involution , and let . The directed de Bruijn graph has length- words as vertices and one-symbol-shift edges, including loops. Put .
What is the minimum cardinality of a set such that and deleting makes 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 . This entry reports a parity theorem toward the symmetry-constrained problem.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.