Document Open Access Logo

The Maximum Binary Tree Problem

Authors Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.30.pdf
  • Filesize: 0.62 MB
  • 22 pages

Document Identifiers

Author Details

Karthekeyan Chandrasekaran
  • Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA
Elena Grigorescu
  • Purdue University, West Lafayette, IN, USA
Gabriel Istrate
  • West University of Timişoara, Romania
  • e-Austria Research Institute, Timişoara, Romania
Shubhang Kulkarni
  • Purdue University, West Lafayette, IN, USA
Young-San Lin
  • Purdue University, West Lafayette, IN, USA
Minshen Zhu
  • Purdue University, West Lafayette, IN, USA

Funding

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

Cite AsGet BibTex

Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu. The Maximum Binary Tree Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.30

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 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(log^0.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 ≠ 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • maximum binary tree
  • heapability
  • inapproximability
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Louigi Addario-Berry, Ketan Dalal, and Bruce A Reed. Degree constrained subgraphs. Electronic Notes in Discrete Mathematics, 19:257-263, 2005. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  3. Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, and Saket Saurabh. Degree-constrained subgraph problems: Hardness and approximation results. In Approximation and Online Algorithms, pages 29-42, 2009. Google Scholar
  4. Omid Amini, Ignasi Sau, and Saket Saurabh. Parameterized complexity of the smallest degree-constrained subgraph problem. In Parameterized and Exact Computation, pages 13-29, 2008. Google Scholar
  5. Per Austrin, Ryan O’Donnell, and John Wright. A new point of NP-hardness for 2-to-1 Label-Cover. In Proceedings of the 15th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX '12, pages 1-12, 2012. Google Scholar
  6. János Balogh, Cosmin Bonchiş, Diana Diniş, Gabriel Istrate, and Ioan Todinca. On the heapability of finite partial orders. Discrete Mathematics and Theoretical Computer Science, 22(1):paper # 17, 2020. Google Scholar
  7. Nikhil Bansal, Rohit Khandekar, and Viswanath Nagarajan. Additive guarantees for degree-bounded directed network design. SIAM J. Comput., 39(4):1413-1431, October 2009. Google Scholar
  8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences, 87:119-139, 2017. Google Scholar
  9. Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna. Approximating longest directed paths and cycles. In Automata, Languages and Programming, pages 222-233, 2004. Google Scholar
  10. John Byers, Brent Heeringa, Michael Mitzenmacher, and Georgios Zervas. Heapable sequences and subseqeuences. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, ANALCO '11, pages 33-44, 2011. Google Scholar
  11. Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu. The maximum binary tree problem. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.07915.
  12. Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar. A push–relabel approximation algorithm for approximating the minimum-degree mst problem and its generalization to matroids. Theoretical Computer Science, 410(44):4489-4503, 2009. Google Scholar
  13. Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar. What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. Algorithmica, 55(1):157-189, September 2009. Google Scholar
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  15. Paul Erdös, Ralph J Faudree, CC Rousseau, and RH Schelp. Subgraphs of minimal degree k. Discrete Math, 85(1):53-58, 1990. Google Scholar
  16. Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409-423, 1994. URL: https://doi.org/10.1006/jagm.1994.1042.
  17. Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 448-456, 1983. Google Scholar
  18. Michael Garey and David Johnson. Computers and Intractability. W. H. Freeman and Company, 1979. Google Scholar
  19. Michel X. Goemans. Minimum bounded degree spanning trees. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS '06, pages 273-282, 2006. Google Scholar
  20. Venkatesan Guruswami and Ali Kemal Sinop. Improved inapproximability results for maximum k-colorable subgraph. Theory of Computing, 9:413-435, 2013. Google Scholar
  21. Gabriel Istrate and Cosmin Bonchiş. Heapability, interactive particle systems, partial orders: Results and open problems. In Proceedings of DCFS'2016, 18th International Conference on Descriptional Complexity of Formal Systems, pages 18-28. Springer, 2016. Google Scholar
  22. David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18(1):82-98, 1997. Google Scholar
  23. Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. On some network design problems with degree constraints. Journal of Computer and System Sciences, 79(5):725-736, 2013. Google Scholar
  24. Ton Kloks, Dieter Kratsch, and Haiko Müller. Bandwidth of chain graphs. Information Processing Letters, 68(6):313-315, 1998. Google Scholar
  25. Jochen Könemann and R. Ravi. A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J. Comput., 31(6):1783-1793, June 2002. Google Scholar
  26. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In International Colloquium on Automata, Languages, and Programming, ICALP '08, pages 575-586, 2008. Google Scholar
  27. Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. In International Colloquium on Automata, Languages, and Programming, ICALP '09, pages 653-664, 2009. Google Scholar
  28. Jochen Könemann and R. Ravi. Primal-dual meets local search: Approximating msts with nonuniform degree bounds. SIAM Journal on Computing, 34(3):763-773, 2005. Google Scholar
  29. Lap Chi Lau, Joseph (Seffi) Naor, Mohammad Salavatipour, and Mohit Singh. Survivable network design with degree or order constraints. SIAM Journal on Computing, 39(3):1062-1087, 2009. Google Scholar
  30. Jaclyn Porfilio. A combinatorial characterization of heapability. Master’s thesis, Williams College, 2015. Google Scholar
  31. R. Ravi, Madhav Marathe, S. S. Ravi, Daniel Rosenkrantz, and Harry B. Hunt III. Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica, 31(1):58-78, September 2001. Google Scholar
  32. Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM, 62(1):1-19, March 2015. Google Scholar
  33. Jacqueline Smith. Minimum degree spanning trees on bipartite permutation graphs. Master’s thesis, University of Alberta, 2011. Google Scholar
  34. Jeremy Spinrad, Andreas Brandstädt, and Lorna Stewart. Bipartite permutation graphs. Discrete Applied Mathematics, 18(3):279-292, 1987. Google Scholar
  35. Ryuhei Uehara and Yushi Uno. Efficient algorithms for the longest path problem. In Proceedings of the 15th International Conference on Algorithms and Computation, ISAAC '04, pages 871-883, 2004. Google Scholar
  36. Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letters, 109(6):315-318, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact