Optimal system of loops on an orientable surface (Q1773896)

Let \(M\) be a compact orientable surface with empty boundary; as it is well-known, a \textit{(fundamental) system of loops} for \(M\) is a collection of simple loops on \(M\) with a common point \(v_{0}\), pairwise disjoint except at \(v_{0}\), which cut \(M\) into a topological disk (for details, see [\textit{J. Stillwell}, Classical topology and combinatorial group theory. Graduate Texts in Mathematics, 72, Springer-Verlag (1980; Zbl 0453.57001)], chapter 1.4). The present paper takes into account the case of an orientable \textit{combinatorial} surface \(M\) whose edges have positive weights, and faces the problem of searching for \textit{optimal} (i.e. \textit{shortest}, with respect to the given weights) systems of loops homotopic to a given one. The authors describe an iterative procedure yielding such an optimal system and prove that it is made of loops which are shortest simple ones in their homotopy classes. Note that, in case of uniform weights, the corresponding algorithm turns out to have polynomial running time; it might be interesting to compare this fact with the NP-hardness of computing a shortest polynomial scheme for a combinatorial surface (see \textit{J. Erickson} and \textit{S. Har-Peled}, Discrete Comput. Geom. 31 (1), 37--59 (2004; Zbl 1060.68129)]).