On the Realisations of
Finite Metric Spaces by Graphs

SACHA VARONE
Ecole Polytechnique Fédérale de Lausanne
Département de Mathématiques
CH - 1015 Lausanne

The purpose of this work is to give an exact representation of data. More precisely, finite metric spaces are embedded into weighted graphs in such a way that the sum of the weights is minimized.

The applications' area of data representation is very wide: good representations are searched for cost reduction (in seismic tomography), for health purpose (in psychology) or for a better understanding of the evolution (in phylogeny).

How to find a submatrix of order as great as possible which can be represented by a tree? How to partition a distance matrix in such a way that each class of the partition can be represented by a tree and the number of these classes is minimized? The former and the latter problem are both solved in two different ways: by a heuristic applied on a particular graph and by an exact algorithm applied on a specific hypergraph.

We then find, in polynomial time,  a partition of a metric space in such a way that the optimal representations of each of the classes can easily be put together to form an optimal representation of the metric space, leading to divide-and-conquer algorithms.

An extension of the so-called Four Point Condition which characterizes the data representable by weighted trees, is stated: consider a real positive valued matrix with a null diagonal on which the Four Point Condition in its ``light'' form holds, that is to say without the triangle inequality to be necessarily satisfied. Then the Four Point Condition is invariable under the transformation of this matrix into a distance matrix. A topological consideration of this extended characterization is carried out.

We also deal with the problem of the representation by a tree data given by a lower and an upper bound. We point out some difficulties which appear when solving this problem and define it under the form of a cascade of linear programming problems, leading to an exact method to solve it.

Finally, two algorithms, which represent exactly the data by minimal weighted graphs, are proposed. A first algorithm uses a reduction procedure from an initial solution and a second one constructs the solution element by element. Numerical results are done in order to compare the two algorithms.

For further information, please contact Professor Alain Hertz (alain.hertz@epfl.ch).