The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

DOI10.1016/S0166-218X(99)00160-2MaRDI QIDQ1962070zbMATH OpenFDO

Authors Meei Pyng Ng, Nicholas Wormald, Mike Steel

Publication date 10 April 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00160-2

zbMATH Keywords

leaf-labelled treesubtree

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Review text

It is known that the following question is NP-complete: Given a set of trees with leaves labelled from the set \(L\), does there exist a tree \(T\) with leaves labelled by \(L\) such that each of the given trees is homeomorphic to a subtree of \(T\)? If all trees have one label in common the question is solvable in polynomial time. The authors prove, however, that the problem is NP-complete even if it is known that each given tree contains \(x\) or \(y\), where \(x\) and \(y\) are two given labels. Some related complexity results are proved, too.

Recommendations

• The complexity of reconstructing trees from qualitative characters and subtrees
• On the complexity of constructing evolutionary trees
• Finding a maximum compatible tree is NP-hard for sequences and trees
• Convex tree realizations of partitions
• Extension operations on sets of leaf-labelled trees

Cites work

• An efficient algorithm for supertrees
• scientific article; zbMATH DE number 871930 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Reconstruction of rooted trees from subtrees
• The complexity of reconstructing trees from qualitative characters and subtrees

Cited in

(6)

• Determining the consistency of partial tree descriptions
• Convex tree realizations of partitions
• The complexity of reconstructing trees from qualitative characters and subtrees
• The reducts of the homogeneous binary branching C-relation
• Solving infinite-domain CSPs using the patchwork property
• Recognising the overlap graphs of subtrees of restricted trees is hard

This page was built for publication: The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962070)