Document Open Access Logo

Reconstruction of Trees from Jumbled and Weighted Subtrees

Authors Dénes Bartha, Peter Burcsi, Zsuzsanna Lipták

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.10.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Dénes Bartha
Peter Burcsi
Zsuzsanna Lipták

Cite As Get BibTex

Dénes Bartha, Peter Burcsi, and Zsuzsanna Lipták. Reconstruction of Trees from Jumbled and Weighted Subtrees. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.10

Abstract

Let T be an edge-labeled graph, where the labels are from a finite alphabet Sigma. For a subtree U of T the Parikh vector of U is a vector of length |Sigma| which specifies the multiplicity of each label in U. We ask when T can be reconstructed from the multiset of Parikh vectors of all its subtrees, or all of its paths, or all of its maximal paths. We consider the analogous problems for weighted trees. We show how several well-known reconstruction problems on labeled strings, weighted strings and point sets on a line can be included in this framework. We present reconstruction algorithms and non-reconstructibility results, and extend the polynomial method, previously applied to jumbled strings [Acharya et al., SIAM J. on Discr. Math, 2015] and weighted strings [Bansal et al., CPM 2004], to deal with general trees and special tree classes.

Subject Classification

Keywords
  • trees
  • paths
  • Parikh vectors
  • reconstruction problems
  • homometric sets
  • polynomial method
  • jumbled strings
  • weighted strings

Metrics

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

References

  1. Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, Alon Orlitsky, and Shengjun Pan. Quadratic-backtracking algorithm for string reconstruction from substring compositions. In 2014 IEEE Int. Symp. on Information Theory (ISIT 2014), pages 1296-1300, 2014. URL: http://dx.doi.org/10.1109/ISIT.2014.6875042.
  2. Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, Alon Orlitsky, and Shengjun Pan. String reconstruction from substring compositions. SIAM J. Discrete Math., 29(3):1340-1371, 2015. URL: http://dx.doi.org/10.1137/140962486.
  3. Tatsuya Akutsu, Daiji Fukagawa, Jesper Jansson, and Kunihiko Sadakane. Inferring a graph from path frequency. Discrete Applied Mathematics, 160(10-11):1416-1428, 2012. URL: http://dx.doi.org/10.1016/j.dam.2012.02.002.
  4. Amihood Amir, Ayelet Butman, and Ely Porat. On the relationship between histogram indexing and block-mass indexing. Philosophical Transactions of The Royal Society A: Mathematical Physical and Engineering Sciences, 372(2016), 2014. URL: http://dx.doi.org/10.1098/rsta.2013.0132.
  5. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In 41st Int. Coll. on Automata, Languages, and Programming (ICALP 2014), volume 8572 of Lecture Notes in Computer Science, pages 114-125. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_10.
  6. Maria Axenovich and Lale Özkahya. On homometric sets in graphs. Electronic Notes in Discrete Mathematics, 38:83-86, 2011. URL: http://dx.doi.org/10.1016/j.endm.2011.09.014.
  7. Golnaz Badkobeh, Gabriele Fici, Steve Kroon, and Zsuzsanna Lipták. Binary Jumbled String Matching for Highly Run-Length Compressible Texts. Information Processing Letters, 113:604-608, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.05.007.
  8. Nikhil Bansal, Mark Cieliebak, and Zsuzsanna Lipták. Efficient algorithms for finding submasses in weighted strings. In Proc. of the 15th Ann. Symp. on Combinatorial Pattern Matching (CPM 2004), volume 3109 of Lecture Notes in Computer Science, pages 194-204. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27801-6_14.
  9. Dénes Bartha and Péter Burcsi. Reconstructibility of trees from subtree size frequencies. Stud. Univ. Babeş-Bolyai Math., 59:435-442, 2014. Google Scholar
  10. Peter B. Borwein. Computational excursions in analysis and number theory. CMS books in mathematics. Springer, New York, Berlin, Heidelberg, 2002. Google Scholar
  11. Péter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Algorithms for Jumbled Pattern Matching in Strings. Int. Journal of Foundations of Computer Science, 23:357-374, 2012. URL: http://dx.doi.org/10.1142/S0129054112400175.
  12. Péter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems, 50:35-51, 2012. URL: http://dx.doi.org/10.1007/s00224-011-9344-5.
  13. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proc. of 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 31-40, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
  14. Ferdinando Cicalese, Travis Gagie, Emanuele Giaquinta, Eduardo Sany Laber, Zsuzsanna Lipták, Romeo Rizzi, and Alexandru I. Tomescu. Indexes for jumbled pattern matching in strings, trees and graphs. In 20th Int. Symp. on String Processing and Information Retrieval (SPIRE 2013), volume 8214 of Lecture Notes in Computer Science, pages 56-63. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-02432-5_10.
  15. Ferdinando Cicalese, Eduardo Sany Laber, Oren Weimann, and Raphael Yuster. Approximating the maximum consecutive subsums of a sequence. Theoret. Comput. Sci., 525:130-137, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2013.05.032.
  16. Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme J. Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. CUP, 1998. Google Scholar
  17. Stephane Durocher, Robert Fraser, Travis Gagie, Debajyoti Mondal, Matthew Skala, and Sharma V. Thankachan. Indexed geometric jumbled pattern matching. In Proc. of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), volume 8486 of Lecture Notes in Computer Science, pages 110-119. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07566-2_12.
  18. Tomás Feder and Rajeev Motwani. On the graph turnpike problem. Inf. Process. Lett., 109(14):774-776, 2009. URL: http://dx.doi.org/10.1016/j.ipl.2009.03.024.
  19. Radoslav Fulek and Slobodan Mitrovic. Homometric sets in trees. Eur. J. Comb., 35:256-263, 2014. URL: http://dx.doi.org/10.1016/j.ejc.2013.06.008.
  20. Travis Gagie, Danny Hermelin, Gad M. Landau, and Oren Weimann. Binary jumbled pattern matching on trees and tree-like structures. Algorithmica, 73(3):571-588, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9957-6.
  21. Emanuele Giaquinta and Szymon Grabowski. New algorithms for binary jumbled pattern matching. Inf. Process. Lett., 113(14-16):538-542, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.04.013.
  22. Danny Hermelin, Gad M. Landau, Yuri Rabinovich, and Oren Weimann. Binary jumbled pattern matching via all-pairs shortest paths. CoRR, abs/1401.2065, 2014. URL: http://arxiv.org/abs/1401.2065.
  23. Ross Honsberger. In Polya’s Footsteps: Miscellaneous Problems and Essays (Dolciani Mathematical Expositions). The Mathematical Association of America, October 1997. Google Scholar
  24. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Efficient indexes for jumbled pattern matching with constant-sized alphabet. In 21st Annual European Symposium on Algorithms (ESA 2013), volume 8125 of Lecture Notes in Computer Science, pages 625-636. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_53.
  25. Eduardo Laber, Wilfredo Bardales, and Ferdinando Cicalese. On lower bounds for the maximum consecutive subsums problem and the (min,+)-convolution. In Proceedings of the 2013 IEEE Int. Symp. on Information Theory (ISIT 2013). IEEE, 2014. Google Scholar
  26. Vincent Lacroix, Cristina G. Fernandes, and Marie-France Sagot. Motif search in graphs: Application to metabolic networks. IEEE/ACM Trans. Comput. Biology Bioinform., 3(4):360-368, 2006. URL: http://dx.doi.org/10.1109/TCBB.2006.55.
  27. Lap-Kei Lee, Moshe Lewenstein, and Qin Zhang. Parikh matching in the streaming model. In 19th Int. Symp. on String Processing and Information Retrieval (SPIRE 2012), volume 7608 of Lecture Notes in Computer Science, pages 336-341. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34109-0_35.
  28. Paul Lemke, Steven S. Skiena, and Warren D. Smith. Discrete and Computational Geometry: The Goodman-Pollack Festschrift, chapter Reconstructing Sets From Interpoint Distances, pages 597-631. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. URL: http://dx.doi.org/10.1007/978-3-642-55566-4_27.
  29. Tanaeem M. Moosa and M. Sohel Rahman. Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discr. Algorithms, 10:5-9, 2012. URL: http://dx.doi.org/10.1016/j.jda.2011.08.003.
  30. N. Saitou and M. Nei. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol, 4(4):406-425, 1987. Google Scholar
  31. Svetoslav Savchev and Titu Andreescu. Mathematical Miniatures, volume 43 of Anneli Lax New Mathematical Library. The Mathematical Association of America, 2003. Google Scholar
  32. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. URL: http://dx.doi.org/10.1145/322217.322225.
  33. J. L. Selfridge and E. G. Straus. On the determination of numbers by their sums of a fixed order. Pacific J. Math., 8(4):847-856, 1958. Google Scholar
  34. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of Symbolic and Algebraic Computation (EUROSAM'79), volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. 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 About DROPS Imprint Privacy Contact