Groupe d’études et de recherche en analyse des décisions

# The Metric Cutpoint Partition Problem

## Alain Hertz et Sacha Varone

Let $G = (V,E,w)$ be a graph with vertex and edge sets $V$ and $E$, respectively, and $w:E\rightarrow R^+$ a function which assigns a positive weight or length to each edge of $G$. $G$ is called a realization of a finite metric space $(M, d)$, with $M = \{1, \ldots, n\}$ if and only if $\{1, \ldots, n} \subseteq V$ and $d(i, j)$ is equal to the length of the shortest chain linking $i$ and $j$ in $G$ $\forall i,j=1, \ldots, n$. A realization $G$ of $(M, d)$, is said optimal if the sum of its weights is minimal among all the realizations of $(M, d)$. A cutpoint in a graph $G$ is a vertex whose removal strictly increases the number of connected component of $G$. The Metric Cutpoint Partition Problem is to determine if a finite metric space $(M, d)$ has an optimal realization containing a cutpoint. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of $(M, d)$ from optimal realizations of subspaces that do not contain any cutpoint.

, 20 pages