The Maximum Binary Tree Problem
share
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural generalization of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient (-O(log n/ loglog n))-approximation algorithm under the exponential time hypothesis. In undirected graphs, we show that MBT has no efficient (-O(log^0.63n))-approximation under the exponential time hypothesis. Our hardness results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P≠NP. Furthermore, motivated by the longest heapable subsequence problem (introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO '11), which is equivalent to MBT in permutation DAGs, we study MBT in restricted graph families. We show that MBT admits efficient algorithms in two graph families: bipartite permutation graphs and bounded treewidth graphs.
READ FULL TEXT