On polynomial time complexity of ultrametric versions of certain NP-hard problems

The paper deals with important special cases of the travelling salesman problem and the Steiner tree problem. Both of these problems are NP-hard even in the metric case, i. e., for graphs whose edge cost function meets the triangle inequality. Even more severe restriction is imposed by the strong triangle inequality: $ \forall x, y, z\in X \quad c (x, z) \leq \max \{c (x, y), c (y, z) \}$. The function which meets this inequality is called ultrametric. The analysis of graphs with an ultrametric edge cost function is presented. This analysis leads to an algorithm for building the minimal cost Hamiltonian cycle in time $ O \left(n^ 2 \right)$ where $n$ is the number of vertices. For the Steiner tree problem, it is proven that in the case of an ultrametric edge function, the minimum Steiner tree includes only terminal vertices and thus may also be constructed in polynomial time, as a minimum spanning tree on a subgraph of the original graph.