Chandrasekaran, Karthekeyan ;
Grigorescu, Elena ;
Istrate, Gabriel ;
Kulkarni, Shubhang ;
Lin, YoungSan ;
Zhu, Minshen
The Maximum Binary Tree Problem
Abstract
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 maximumsized binary tree in a given graph. MBT is a natural variant of the wellstudied longest path problem, since both can be viewed as finding a maximumsized 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 exp(O(log n/ log log n))approximation algorithm under the exponential time hypothesis, where n is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient exp(O(log^0.63 n))approximation under the exponential time hypothesis. Our inapproximability results rely on selfimproving reductions and structural properties of binary trees. We also show constantfactor inapproximability assuming P ≠ NP.
In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on n vertices contains a binary tree of size k in 2^k poly(n) time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO 2011, which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs.
BibTeX  Entry
@InProceedings{chandrasekaran_et_al:LIPIcs:2020:12896,
author = {Karthekeyan Chandrasekaran and Elena Grigorescu and Gabriel Istrate and Shubhang Kulkarni and YoungSan Lin and Minshen Zhu},
title = {{The Maximum Binary Tree Problem}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {30:130:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12896},
URN = {urn:nbn:de:0030drops128967},
doi = {10.4230/LIPIcs.ESA.2020.30},
annote = {Keywords: maximum binary tree, heapability, inapproximability, fixedparameter tractability}
}
26.08.2020
Keywords: 

maximum binary tree, heapability, inapproximability, fixedparameter tractability 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 