Balanced mobiles problem is strongly NP-complete to solve optimally
Strong NP-Completeness of Unrestricted Balanced Mobiles
Computational Complexity
Summary
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.
What this means in practice
- •For algorithm designers: Know that optimally balancing mobiles without fixed structure is computationally infeasible, guiding heuristic or approximate methods.
- •For software developers building tree-optimization tools: Understand inherent complexity limits when designing tools to minimize imbalance in weighted binary trees without preset structure.
A theory result. No direct application yet.
Authors
Andrei Popa, Alexandru Popa
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.