Binary prefix coding with unequal letter costs is NP-complete

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

Data Structures and AlgorithmsComputational ComplexityComputational GeometryInformation Theory

Summary

Assigning binary codes to symbols efficiently is important for data compression. When each binary digit has the same cost, we know how to find the best codes quickly. This paper shows that if the costs of zeros and ones vary and are given as part of the input, deciding whether an optimal code exists is very hard (NP-complete). The authors use complex mathematical reductions to prove this problem cannot be solved quickly in general. This settles a long-standing question about how letter costs affect coding complexity.

What this means in practice

  • For data compression engineers: Avoid attempts at exact optimal binary coding with unequal costs since the problem is proven NP-hard, focusing instead on approximate or heuristic methods.
  • For algorithm designers: Use this complexity result to guide the development of efficient coding algorithms by focusing on special cases or approximations when letter costs are unequal.

A theory result. No direct application yet.

Authors

L. Sunil Chandran, Rishikesh Gajjala

Abstract

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.