TY - GEN

T1 - The maximum binary tree problem

AU - Chandrasekaran, Karthekeyan

AU - Grigorescu, Elena

AU - Istrate, Gabriel

AU - Kulkarni, Shubhang

AU - Lin, Young San

AU - Zhu, Minshen

N1 - Funding Information:
Funding Karthekeyan Chandrasekaran: Supported by NSF CCF-1814613 and NSF CCF-1907937. Elena Grigorescu: Supported by NSF CCF-1910659 and NSF CCF-1910411. Gabriel Istrate: Supported by a grant of Ministry of Research and Innovation, CNCS - UEFISCDI project number PN-III-P4-ID-PCE-2016-0842, within PNCDI III. Young-San Lin: Supported by NSF CCF-1910659 and NSF CCF-1910411. Minshen Zhu: Supported by NSF CCF-1910659 and NSF CCF-1910411.
Publisher Copyright:
© Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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 variant 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 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(log0.63 n))-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P 6= 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 2kpoly(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.

AB - 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 variant 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 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(log0.63 n))-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P 6= 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 2kpoly(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.

KW - Fixed-parameter tractability

KW - Heapability

KW - Inapproximability

KW - Maximum binary tree

UR - http://www.scopus.com/inward/record.url?scp=85092447305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85092447305&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2020.30

DO - 10.4230/LIPIcs.ESA.2020.30

M3 - Conference contribution

AN - SCOPUS:85092447305

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th Annual European Symposium on Algorithms, ESA 2020

A2 - Grandoni, Fabrizio

A2 - Herman, Grzegorz

A2 - Sanders, Peter

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 28th Annual European Symposium on Algorithms, ESA 2020

Y2 - 7 September 2020 through 9 September 2020

ER -