Arboral satisfaction: Recognition and LP approximation

We study two basic problems about arboral satisfaction. First, we develop two nontrivial algorithms to test whether a given point set is arborally satisfied. In 2D, both of our algorithms run in O(nlog⁡n) time, and one of them achieves O(n) runtime if the points are presorted; we also show a matching Ω(nlog⁡n) lower bound in the algebraic decision tree model. In d dimensions, our algorithm runs in O(dnlog⁡n+nlogd−1⁡n) time. Second, we study a natural integer linear programming formulation of finding the minimum-size arborally satisfied superset of a given 2D point set, which is equivalent to finding offline dynamically optimal binary search trees. Unfortunately, we conclude that the linear programming relaxation has large integrality gap, making it unlikely to find an approximation algorithm via this approach.