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.
Note (2026-11-15; read against the paper's full text): the paper's authors, per the arXiv metadata, are Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata and Sebastian Wild, not the three names the essay gives (I found none of them in the paper). Its results also differ from the essay's: it shows that the problem (MINETREX, removing a spanning forest so the remaining graph has minimal indegree entropy) is NP-hard to approximate with additive error better than delta times n for some constant delta, and gives a simple greedy algorithm with additive error at most n over ln 2, which comes from computing a minimum-cost spanning tree with edge costs lg of the target's indegree. The essay's inapproximability factor of (1 - epsilon) ln n, its additive O(log n) guarantee and its appeal to submodularity are not the paper's results; the paper's main application is an ultra-succinct data structure for unlabeled graphs with logarithmic-time navigation.
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.