Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe maximum agreement subtree problem
283
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we investigate an extremal problem on binary phylogenetic trees. Given two such trees $T_1$ and $T_2$, both with leaf-set ${1,2,...,n}$, we are interested in the size of the largest subset $S subseteq {1,2,...,n}$ of leaves in a common subtree of $T_1$ and $T_2$. We show that any two binary phylogenetic trees have a common subtree on $Omega(sqrt{log{n}})$ leaves, thus improving on the previously known bound of $Omega(loglog n)$ due to M. Steel and L. Szekely. To achieve this improved bound, we first consider two special cases of the problem: when one of the trees is balanced or a caterpillar, we show that the largest common subtree has $Omega(log n)$ leaves. We then handle the general case by proving and applying a Ramsey-type result: that every binary tree contains either a large balanced subtree or a large caterpillar. We also show that there are constants $c, alpha > 0$ such that, when both trees are balanced, they have a common subtree on $c n^alpha$ leaves. We conjecture that it is possible to take $alpha = 1/2$ in the unrooted case, and both $c = 1$ and $alpha = 1/2$ in the rooted case.
rate research
Read More
A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open question raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order $n$ with maximum mean subtree order must be very close to $n$. Moreover, we show that the maximum mean subtree order is equal to $n - 2log_2 n + O(1)$. For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to $n - log_2 n + O(1)$.
We consider the quantity $P(G)$ associated with a graph $G$ that is defined as the probability that a randomly chosen subtree of $G$ is spanning. Motivated by conjectures due to Chin, Gordon, MacPhee and Vincent on the behaviour of this graph invariant depending on the edge density, we establish first that $P(G)$ is bounded below by a positive constant provided that the minimum degree is bounded below by a linear function in the number of vertices. Thereafter, the focus is shifted to the classical ErdH{o}s-Renyi random graph model $G(n,p)$. It is shown that $P(G)$ converges in probability to $e^{-1/(ep_{infty})}$ if $p to p_{infty} > 0$ and to $0$ if $p to 0$.
Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the local
Given a set of points $P$ and axis-aligned rectangles $mathcal{R}$ in the plane, a point $p in P$ is called emph{exposed} if it lies outside all rectangles in $mathcal{R}$. In the emph{max-exposure problem}, given an integer parameter $k$, we want to delete $k$ rectangles from $mathcal{R}$ so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in $mathcal{R}$ are translates of two fixed rectangles. However, if $mathcal{R}$ only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple $O(k)$ bicriteria approximation algorithm; that is by deleting $O(k^2)$ rectangles, we can expose at least $Omega(1/k)$ of the optimal number of points.
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 $text{P} eq text{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 text{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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
