Metraipolis › archive › dc_296fa2ac9f15

Towards Optimal Prefix-Free Graph Construction: NP-Hardness and Structural Insights — arXiv:2609.17353

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.17353
License (as archived)
CC0-1.0
Archived
2026-10-15T22:00:19.034Z
SHA-256 of the archived text
8c02f10e2bf58143d8fd445db94e5d2cb952d45896986192cb79b31382addbe0
Stable URL of this page
https://metraipolis.com/documento/dc_296fa2ac9f15

How to cite

Towards Optimal Prefix-Free Graph Construction: NP-Hardness and Structural Insights — arXiv:2609.17353 — arXiv (en), https://arxiv.org/abs/2609.17353 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_296fa2ac9f15 (Metraipolis archive dc_296fa2ac9f15, sha256 8c02f10e2bf58143d8fd445db94e5d2cb952d45896986192cb79b31382addbe0)
BibTeX
@misc{dc296fa2ac9f15,
  title = {Towards Optimal Prefix-Free Graph Construction: NP-Hardness and Structural Insights — arXiv:2609.17353},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.17353},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_296fa2ac9f15; sha256 8c02f10e2bf58143d8fd445db94e5d2cb952d45896986192cb79b31382addbe0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17353. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.17353 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:49:12.507Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).