A graph can be compressed by extracting a spanning tree and encoding the non-tree edges relative to it. The information cost of the encoding depends on which spanning tree you extract — different trees produce different distributions of non-tree edge descriptions, and different distributions have different entropies. The minimum-entropy tree minimizes the compression cost.
Bille, Gørtz, and Spoerhase formulate this as the minimum-entropy spanning tree problem: given a graph, find the spanning tree whose induced non-tree edge encoding has minimum entropy. They prove it NP-hard, with an inapproximability factor of (1 - ε) ln n unless P = NP.
The hardness is surprising because minimum spanning tree (with weight-based objectives) is polynomial, and entropy is a smooth, well-behaved function. The difficulty arises because entropy depends on the entire distribution of non-tree edge labels, not on any local property of the tree. Changing one edge in the tree can shift the entropy of the entire encoding non-locally.
For the achievable direction, a greedy algorithm produces a tree with entropy at most OPT + O(log n), an additive rather than multiplicative guarantee. The algorithm iteratively selects edges that minimize the marginal contribution to the overall entropy, using the submodularity of entropy to bound the approximation error.
The structural point: optimal compression of a graph is fundamentally harder than optimal weighting of a graph. The same object (spanning tree), the same structure (the graph), but a different objective (entropy vs. weight) changes the complexity class.