Treewidth of display graphs: bounds, brambles and applications
From MaRDI portal
(Redirected from Publication:5233142)
Abstract: Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or networks. The treewidth of such graphs is bounded as a function of many common dissimilarity measures between phylogenetic trees and this has been leveraged in fixed parameter tractability results. Here we further elucidate the properties of display graphs and their interaction with treewidth. We show that it is NP-hard to recognize display graphs, but that display graphs of bounded treewidth can be recognized in linear time. Next we show that if a phylogenetic network displays (i.e. topologically embeds) a phylogenetic tree, the treewidth of their display graph is bounded by a function of the treewidth of the original network (and also by various other parameters). In fact, using a bramble argument we show that this treewidth bound is sharp up to an additive term of 1. We leverage this bound to give an FPT algorithm, parameterized by treewidth, for determining whether a network displays a tree, which is an intensively-studied problem in the field. We conclude with a discussion on the future use of display graphs and treewidth in phylogenetics.
Recommendations
- scientific article; zbMATH DE number 1982177
- Layout of Graphs with Bounded Tree-Width
- A managed Bayesian risk approach for decision making alternatives
- Tree-Width and Optimization in Bounded Degree Graphs
- Treewidth: Characterizations, Applications, and Computations
- scientific article; zbMATH DE number 772777
- scientific article; zbMATH DE number 932194
- Surprising Applications of Treewidth Bounds for Planar Graphs
- Computational aspects of treewidth for graph
- scientific article; zbMATH DE number 7310078
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- An improved isomorphism test for bounded-tree-width graphs
- Bounds for phylogenetic network space metrics
- Compatibility of unrooted phylogenetic trees is FPT
- Computing tree width: from theory to practice and back
- Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
- Easy problems for tree-decomposable graphs
- Exploring the tiers of rooted phylogenetic network space using tail moves
- Fast compatibility testing for rooted phylogenetic trees
- Graph searching and a min-max theorem for tree-width
- Graph theory
- Graph triangulations and the compatibility of unrooted phylogenetic trees
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Locating a tree in a phylogenetic network
- On compatibility and incompatibility of collections of unrooted phylogenetic trees
- On computing the maximum parsimony score of a phylogenetic network
- On low treewidth graphs and supertrees
- On the fixed parameter tractability of agreement-based phylogenetic distances
- On the vertex-arboricity of planar graphs
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Parameterized algorithms
- Phylogenetic incongruence through the lens of monadic second order logic
- Phylogeny. Discrete and random processes in evolution
- Reconstructing a phylogenetic level-1 network from quartets
- Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
- Subtree transfer operations and their induced metrics on evolutionary trees
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Transforming phylogenetic networks: moving beyond tree space
- Tree-based unrooted phylogenetic networks
- Treewidth computations. I: Upper bounds
- Treewidth computations. II. Lower bounds
- Treewidth distance on phylogenetic trees
- Vertex and tree arboricities of graphs
Cited in
(8)- Treewidth distance on phylogenetic trees
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Phylogenetic incongruence through the lens of monadic second order logic
- Snakes and Ladders: A Treewidth Story
- Embedding phylogenetic trees in networks of low treewidth
- Composing dynamic programming tree-decomposition-based algorithms
- Counting Cherry reduction sequences in phylogenetic tree-child networks is counting linear extensions
- Embedding phylogenetic trees in networks of low treewidth
This page was built for publication: Treewidth of display graphs: bounds, brambles and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233142)
