Metraipolis › archive › dc_04436c2bf310

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete — arXiv:2611.04444

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04444
License (as archived): CC0-1.0
Archived: 2026-11-04T12:49:18.589Z
SHA-256 of the archived text: d42b57e1d8bcdd3089c07d6031826296bc0967cf650c871ba83b45c8d8eea063
Stable URL of this page: https://metraipolis.com/documento/dc_04436c2bf310

How to cite

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete — arXiv:2611.04444 — arXiv (en), https://arxiv.org/abs/2611.04444 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_04436c2bf310 (Metraipolis archive dc_04436c2bf310, sha256 d42b57e1d8bcdd3089c07d6031826296bc0967cf650c871ba83b45c8d8eea063)

BibTeX

@misc{dc04436c2bf310,
  title = {Binary Huffman Coding with Unequal Letter Costs Is NP-Complete — arXiv:2611.04444},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04444},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_04436c2bf310; sha256 d42b57e1d8bcdd3089c07d6031826296bc0967cf650c871ba83b45c8d8eea063},
  year = {2026}
}

Archived text

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

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Computational Geometry (cs.CG); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.04444 — 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-11-04T12:32:47.126Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).