Papers for

software developers building tree-optimization tools

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Balanced mobiles problem is strongly NP-complete to solve optimally

Strong NP-Completeness of Unrestricted Balanced Mobiles

Abstract: A mobile is a rooted full binary tree whose leaves carry positive integer weights. The imbalance of an internal node is the absolute difference between the total weights of its two child subtrees, and the cost of the mobile is the sum of these imbalances. In the unrestricted \emph{Balanced Mobiles} problem, only the multiset of leaf weights is given: both the tree topology and the placement of the weights must be chosen so as to minimize the cost. The computational complexity of this unrestricted variant has remained open, although the variant with a prescribed topology is strongly NP-hard. We close this gap by proving that the decision version of unrestricted Balanced Mobiles is strongly NP-complete. Our reduction from Numerical 3-Dimensional Matching with Distinct Integers uses three widely separated numerical scales. Tight telescoping bounds force every threshold-achieving mobile into a canonical hierarchy, after which pairwise distinctness of the source integers collapses the hierarchy to single triples from which a valid numerical matching can be recovered.

Mon 21 SeptComputational Complexity
The gist
This paper looks at a problem where you have to build a special kind of tree with weighted leaves to minimize imbalance between parts of the tree. The authors prove that deciding whether you can build such a tree with an imbalance below a certain threshold is very hard computationally (strongly NP-complete). They do this by linking the problem to a known difficult puzzle about matching numbers in triples. This result closes an open question about the problem’s difficulty when you can choose both the tree shape and leaf placement.
Open → 2609.24654v1