The 2-attractor problem is NP-complete

DOI10.4230/LIPICS.STACS.2024.35MaRDI QIDQ6902688zbMATH OpenFDO

Authors Janosch Fuchs, Philip Whittington

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.35

zbMATH Keywords

computational complexitydictionary compressionstring attractors

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A combinatorial view on string attractors
• An upper bound and linear-space queries on the LZ-End parsing
• At the roots of dictionary compression: string attractors
• Budgeted colored matching problems
• Colorful paths in vertex coloring of graphs
• Computing NP-hard repetitiveness measures via MAX-SAT
• Finding colorful paths in temporal graphs
• On some matching problems under the color-spanning model
• Optimal-Time Dictionary-Compressed Indexes
• Sensitivity of string compressors and repetitiveness measures
• String attractors: verification and optimization
• The labeled perfect matching in bipartite graphs
• Towards a definitive measure of repetitiveness
• Tropical matchings in vertex-colored graphs
• Universal compressed text indexing

Cited in

(1)

• Online string attractors. And their relation to the Lempel-Ziv factorization

This page was built for publication: The 2-attractor problem is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902688)