Treewidth of display graphs: bounds, brambles and applications
From MaRDI portal
Publication:5233142
DOI10.7155/JGAA.00508zbMATH Open1419.05187arXiv1809.00907OpenAlexW2972917334MaRDI QIDQ5233142FDOQ5233142
Author name not available (Why is that?)
Publication date: 16 September 2019
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1809.00907
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
Applications of graph theory (05C90) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Title not available (Why is that?)
- Phylogeny. Discrete and random processes in evolution
- Title not available (Why is that?)
- Subtree transfer operations and their induced metrics on evolutionary trees
- Graph searching and a min-max theorem for tree-width
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Vertex and tree arboricities of graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Parameterized Algorithms
- Locating a tree in a phylogenetic network
- On the vertex-arboricity of planar graphs
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Phylogenetic incongruence through the lens of monadic second order logic
- On Low Treewidth Graphs and Supertrees
- Transforming phylogenetic networks: moving beyond tree space
- Compatibility of unrooted phylogenetic trees is FPT
- Treewidth computations. I: Upper bounds
- On compatibility and incompatibility of collections of unrooted phylogenetic trees
- Graph triangulations and the compatibility of unrooted phylogenetic trees
- Tree-based unrooted phylogenetic networks
- Treewidth computations. II. Lower bounds
- Reconstructing a phylogenetic level-1 network from quartets
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
- Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
- Fast compatibility testing for rooted phylogenetic trees
- An improved isomorphism test for bounded-tree-width graphs
- Computing tree width: from theory to practice and back
- Treewidth distance on phylogenetic trees
- Bounds for phylogenetic network space metrics
- Exploring the tiers of rooted phylogenetic network space using tail moves
- On Computing the Maximum Parsimony Score of a Phylogenetic Network
Cited In (5)
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- 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
- Snakes and Ladders: A Treewidth Story
Uses Software
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)
