We investigate the complexity of finding small branch-and-bound trees using variable disjunctions. We first show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2^(1/5) in time 2^(\delta n) with \delta < 1/5, unless the strong exponential time hypothesis fails. Similarly, for any \varepsilon > 0, no polynomial time 2^{(1/2 - \varepsilon)n}-approximation is possible, unless $\PP = \NP$. We then discuss that finding small branch-and-bound trees generalizes finding short treelike resolution refutations. Therefore, hardness results, in particular non-automatizability results, transfer from this setting. Finally, we show that computing the size of a smallest branch-and-bound tree is #P-hard. Similar results hold for estimating the size of the tree produced by branching rules like most-infeasible branching.
Article
View On the Complexity of Finding Shortest Variable Disjunction Branch-and-Bound Proofs