Quasi-median graphs are a tool commonly used by evolutionary biologists to visualise the evolution of molecular sequences. As with any graph, a quasi-median graph can contain cut vertices, that is, vertices whose removal disconnect the graph. These v
ertices induce a decomposition of the graph into blocks, that is, maximal subgraphs which do not contain any cut vertices. Here we show that the special structure of quasi-median graphs can be used to compute their blocks without having to compute the whole graph. In particular we present an algorithm that, for a collection of $n$ aligned sequences of length $m$, can compute the blocks of the associated quasi-median graph together with the information required to correctly connect these blocks together in run time $mathcal O(n^2m^2)$, independent of the size of the sequence alphabet. Our primary motivation for presenting this algorithm is the fact that the quasi-median graph associated to a sequence alignment must contain all most parsimonious trees for the alignment, and therefore precomputing the blocks of the graph has the potential to help speed up any method for computing such trees.
A k-dissimilarity D on a finite set X, |X| >= k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edge-weighted trees T with leaf-set X: Given a subset Y of X of size k, D(Y) is defined to be the total
length of the smallest subtree of T with leaf-set Y . In case k = 2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called 4-point condition. However, in case k > 2 Pachter and Speyer recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k >= 3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2k-element subset of X arises from some tree, and that 2k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition.
An important problem that commonly arises in areas such as internet traffic-flow analysis, phylogenetics and electrical circuit design, is to find a representation of any given metric $D$ on a finite set by an edge-weighted graph, such that the total
edge length of the graph is minimum over all such graphs. Such a graph is called an optimal realization and finding such realizations is known to be NP-hard. Recently Varone presented a heuristic greedy algorithm for computing optimal realizations. Here we present an alternative heuristic that exploits the relationship between realizations of the metric $D$ and its so-called tight span $T_D$. The tight span $T_D$ is a canonical polytopal complex that can be associated to $D$, and our approach explores parts of $T_D$ for realizations in a way that is similar to the classical simplex algorithm. We also provide computational results illustrating the performance of our approach for different types of metrics, including $l_1$-distances and two-decomposable metrics for which it is provably possible to find optimal realizations in their tight spans.
A realisation of a metric $d$ on a finite set $X$ is a weighted graph $(G,w)$ whose vertex set contains $X$ such that the shortest-path distance between elements of $X$ considered as vertices in $G$ is equal to $d$. Such a realisation $(G,w)$ is call
ed optimal if the sum of its edge weights is minimal over all such realisations. Optimal realisations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. In [Adv. in Math. 53, 1984, 321-402] A.~Dress showed that the optimal realisations of a metric $d$ are closely related to a certain polytopal complex that can be canonically associated to $d$ called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of $d$ must always contain an optimal realisation as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally=decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realisations of two-dimensional totally-decomposable metrics.
Tight-spans of metrics were first introduced by Isbell in 1964 and rediscovered and studied by others, most notably by Dress, who gave them this name. Subsequently, it was found that tight-spans could be defined for more general maps, such as directe
d metrics and distances, and more recently for diversities. In this paper, we show that all of these tight-spans as well as some related constructions can be defined in terms of point configurations. This provides a useful way in which to study these objects in a unified and systematic way. We also show that by using point configurations we can recover results concerning one-dimensional tight-spans for all of the maps we consider, as well as extend these and other results to more general maps such as symmetric and unsymmetric maps.
A k-dissimilarity map on a finite set X is a function D : X choose k rightarrow R assigning a real value to each subset of X with cardinality k, k geq 2. Such functions, also sometimes known as k-way dissimilarities, k-way distances, or k-semimetrics
, are of interest in many areas of mathematics, computer science and classification theory, especially 2-dissimilarity maps (or distances) which are a generalisation of metrics. In this paper, we show how regular subdivisions of the kth hypersimplex can be used to obtain a canonical decomposition of a k-dissimilarity map into the sum of simpler k-dissimilarity maps arising from bipartitions or splits of X. In the special case k = 2, this is nothing other than the well-known split decomposition of a distance due to Bandelt and Dress [Adv. Math. 92 (1992), 47-105], a decomposition that is commonly to construct phylogenetic trees and networks. Furthermore, we characterise those sets of splits that may occur in the resulting decompositions of k-dissimilarity maps. As a corollary, we also give a new proof of a theorem of Pachter and Speyer [Appl. Math. Lett. 17 (2004), 615-621] for recovering k-dissimilarity maps from trees.
We study efficient combinatorial algorithms to produce the Hasse diagram of the poset of bounded faces of an unbounded polyhedron, given vertex-facet incidences. We also discuss the special case of simple polyhedra and present computational results.
The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well stud
ied, there is not much known about the facets of the secondary polytope. The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.
