Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

Resource allocation in rooted trees for VLSI applications

ABSTRACT

Several optimization problems of modifying the weight of vertices in rooted trees, some of which are special cases of the inverse 1-median problem, are solved. Such problems arise in Very Large Scale Integration (VLSI) design of hardware security circuits, circuit synchronization, and analog-to-digital converters. These problems require assigning costly hardware (demands) to the leaves of rooted trees. One common property of these problems is that a resource allocated to an internal node can be shared by the entire sub-tree emanated at the node. Two types of problems are studied here. (1) A tree node employs an addition operation and the demands at the leaves are obtained by summing the resources allocated to nodes along the root-to-leaf paths. A linear-time bottom-up algorithm is shown to minimize the total resources allocated to tree nodes. (2) A tree’s node employs a multiplication operation and the demands at the leaves are obtained by multiplying the resources allocated to nodes along the root-to-leaf paths. A bottom-up dynamic programming algorithm is shown to minimize the total resources allocated to the tree’s nodes. While the above problems are usually solved by design engineers heuristically, this paper offers optimal solutions that can be easily programmed in CAD tools.     

Treed Regression

Abstract

Given a data set consisting of n observations on p independent variables and a single dependent variable, treed regression creates a binary tree with a simple linear regression function at each of the leaves. Each node of the tree consists of an inequality condition on one of the independent variables. The tree is generated from the training data by a recursive partitioning algorithm. Treed regression models are more parsimonious than CART models because there are fewer splits. Additionally, monotonicity in some or all of the variables can be imposed.     

Complement reducible graphs

In this paper we study the family of graphs which can be reduced to single vertices by recursively complementing all connected subgraphs. It is shown that these graphs can be uniquely represented by a tree where the leaves of the tree correspond to the vertices of the graph. From this tree representation we derive many new structural and algorithmic properties. Furthermore, it is shown that these graphs have arisen independently in various diverse areas of mathematics.     

Structuring causal trees

Models of complex phenomena often consist of hypothetical entities called “hidden causes,” which cannot be observed directly and yet play a major role in understanding those phenomena. This paper examines the computational roles of these constructs, and addresses the question of whether they can be discovered from empirical observations. Causal models are treated as trees of binary random variables where the leaves are accessible to direct observation, and the internal nodes—representing hidden causes—account for interleaf dependencies. In probabilistic terms, every two leaves are conditionally independent given the value of some internal node between them. We show that if the mechanism which drives the visible variables is indeed tree structured, then it is possible to uncover the topology of the tree uniquely by observing pairwise dependencies among the leaves. The entire tree structure, including the strengths of all internal relationships, can be reconstructed in time proportional to n log n, where n is the number of leaves.     

Spanning trees whose reducible stems have a few branch vertices

Czechoslovak Mathematical Journal - Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T. The set of leaves of T is...     

Tree template matching in unranked ordered trees

We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as “donʼt care”, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem for unranked ordered trees to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix bar notation, and then propose a table-driven algorithm to solve it. The proposed algorithm is divided into two phases: the preprocessing and the searching phase. The tree template is preprocessed once, and the searching phase can be applied to many subject trees, without the need of preprocessing the tree template again. Although we prove that the space required for preprocessing is exponential in the size of the tree template in the worst case, we show that for a specific class of tree templates, the space required is linear in the size of the tree template. The time for the searching phase is linear in the size of the subject tree in the worst case. Thus, the algorithm is asymptotically optimal when one needs to search for a given tree template, of constant to logarithmic size, in many subject trees.     

Closest 4-leaf power is fixed-parameter tractable

The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most r edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree—the 4-leaf root—with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we give the first algorithmic result for Closest 4-Leaf Power, showing that Closest 4-Leaf Power is fixed-parameter tractable with respect to the parameter r.     

Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees

. Leaf-labelled trees are widely used to describe evolutionary relationships, particularly in biology. In this setting, extant species label the leaves of the tree, while the internal vertices correspond to ancestral species. Various techniques exist for reconstructing these evolutionary trees from data, and an important problem is to determine how "far apart" two such reconstructed trees are from each other, or indeed from the true historical tree. To investigate this question requires tree metrics, and these can be induced by operations that rearrange trees locally. Here we investigate three such operations: nearest neighbour interchange (NNI), subtree prune and regraft (SPR), and tree bisection and reconnection (TBR). The SPR operation is of particular interest as it can be used to model biological processes such as horizontal gene transfer and recombination. We count the number of unrooted binary trees one SPR from any given unrooted binary tree, as well as providing new upper and lower bounds for the diameter of the adjacency graph of trees under SPR and TBR. We also show that the problem of computing the minimum number of TBR operations required to transform one tree to another can be reduced to a problem whose size is a function just of the distance between the trees (and not of the size of the two trees), and thereby establish that the problem is fixed-parameter tractable.     

Extension Operations on Sets of Leaf-Labeled Trees

A fundamental problem in classification is how to combine collections of trees having overlapping sets of leaves. The requirement that such a collection of trees is realized by at least one parent tree determines uniquely some additional subtrees not in the original collection. We analyze the "rules" that arise in this way by defining a closure operator for sets of trees. In particular we show that there exist rules of arbitrarily high order which cannot be reduced to repeated application of lower-order rules.     

On component-size bounded Steiner trees

A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.     

On the maximum size of minimal definitive quartet sets

In this paper, we investigate a problem concerning quartets; a quartet is a particular kind of tree on four leaves. Loosely speaking, a set of quartets is said to be ‘definitive’ if it completely encapsulates the structure of some larger tree, and ‘minimal’ if it contains no redundant information. Here, we address the question of how large a minimal definitive quartet set on n leaves can be, showing that the maximum size is at least 2n−8 for all n≥4. This is an enjoyable problem to work on, and we present a pretty construction, which employs symmetry.     

Geometry of the Space of Phylogenetic Trees

We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of trees. This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.     

Particle methods for stochastic optimal control problems

When dealing with numerical solution of stochastic optimal control problems, stochastic dynamic programming is the natural framework. In order to try to overcome the so-called curse of dimensionality, the stochastic programming school promoted another approach based on scenario trees which can be seen as the combination of Monte Carlo sampling ideas on the one hand, and of a heuristic technique to handle causality (or nonanticipativeness) constraints on the other hand. However, if one considers that the solution of a stochastic optimal control problem is a feedback law which relates control to state variables, the numerical resolution of the optimization problem over a scenario tree should be completed by a feedback synthesis stage in which, at each time step of the scenario tree, control values at nodes are plotted against corresponding state values to provide a first discrete shape of this feedback law from which a continuous function can be finally inferred. From this point of view, the scenario tree approach faces an important difficulty: at the first time stages (close to the tree root), there are a few nodes (or Monte-Carlo particles), and therefore a relatively scarce amount of information to guess a feedback law, but this information is generally of a good quality (that is, viewed as a set of control value estimates for some particular state values, it has a small variance because the future of those nodes is rich enough); on the contrary, at the final time stages (near the tree leaves), the number of nodes increases but the variance gets large because the future of each node gets poor (and sometimes even deterministic). After this dilemma has been confirmed by numerical experiments, we have tried to derive new variational approaches. First of all, two different formulations of the essential constraint of nonanticipativeness are considered: one is called algebraic and the other one is called functional. Next, in both settings, we obtain optimality conditions for the corresponding optimal control problem. For the numerical resolution of those optimality conditions, an adaptive mesh discretization method is used in the state space in order to provide information for feedback synthesis. This mesh is naturally derived from a bunch of sample noise trajectories which need not to be put into the form of a tree prior to numerical resolution. In particular, an important consequence of this discrepancy with the scenario tree approach is that the same number of nodes (or points) are available from the beginning to the end of the time horizon. And this will be obtained without sacrifying the quality of the results (that is, the variance of the estimates). Results of experiments with a hydro-electric dam production management problem will be presented and will demonstrate the claimed improvements. A more realistic problem will also be presented in order to demonstrate the effectiveness of the method for high dimensional problems.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.     

Global alignment of molecular sequences via ancestral state reconstruction

We consider the trace reconstruction problem on a tree (TRPT): a binary sequence is broadcast through a tree channel where we allow substitutions, deletions, and insertions; we seek to reconstruct the original sequence from the sequences received at the leaves. The TRPT is motivated by the multiple sequence alignment problem in computational biology. We give a simple recursive procedure giving strong reconstruction guarantees at low mutation rates. To our knowledge, this is the first rigorous trace reconstruction result on a tree in the presence of indels.     

Uniform election in trees and polyominoids

Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves until the graph is reduced to a single vertex; the elected one. In Métivier et al. (2003) [7], the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that the expected election duration of this algorithm is O(ln(n)) where n denotes the size of the tree, and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs.In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.