Two robots moving geodesically on a tree (Q2163648)

In the present paper TC\((-)\) denotes the topological complexity introduced by \textit{M. Farber} [Discrete Comput. Geom. 29, No. 2, 211--221 (2003; Zbl 1038.68130)]. The invariant \(\text{GC}(X,g)\) means the geodesic complexity of a metric space \((X,g)\), see [\textit{D. Recio-Mitter}, J. Appl. Comput. Topol. 5, No. 1, 141--178 (2021; Zbl 1485.53050)]. Note that the authors use the reduced versions. For a graph \(G\) with path metric \(d\), \(F_\epsilon(G,2)\) denotes the ordered two-point \(\epsilon\)-configuration space consisting of the pairs \((a_1,a_2)\in G\times G\) for which \(d(a_1,a_2)\geq\epsilon\) and \(C(G,2)\) is the unordered two-point configuration space of \(G\). Writing \(a=(a_1,a_2)\) and \(b=(b_1,b_2)\) for points \(a,b\in G\times G\), the \(\ell_1\) and \(\ell_2\) metrics on \(G\times G\) are defined by \(\ell_1(a,b)=|d(a_1,b_1)+d(a_2,b_2)|\) and \(\ell_2(a,b)=\sqrt{d^2(a_1,b_1)+d^2(a_2,b_2)}\). The authors study the geodesic complexities \(\text{GC}(F_\epsilon(G,2),\ell_1)\), \(\text{GC}(F_\epsilon(G,2),\ell_2)\) and \(\text{GC}(C(G,2),\ell_1)\) for certain graphs \(G\). Specifically, they show the following statements. \textbf{Theorem 1}. Let \(G\) be a star graph, with \(k\geq 3\) edges emanating from a single vertex. Then \begin{itemize} \item[(1)] If \(k=3\), \(\text{GC}(F_\epsilon(G,2),\ell_i)=\text{TC}(F_\epsilon(G,2))=1\) for \(i\in\{1,2\}\). \item[(2)] If \(k\geq 4\), \(\text{GC}(F_\epsilon(G,2),\ell_i)=\text{TC}(F_\epsilon(G,2))=2\) for \(i\in\{1,2\}\). \end{itemize} \textbf{Theorem 2}. Let \(G\) be a tree. Then \begin{itemize} \item[(1)] If \(G\) is homeomorphic to an interval, then \(\text{GC}(C(G,2),\ell_1)=\text{TC}(C(G,2))=0\). \item[(2)] If \(G\) is the Y-graph, \(\text{GC}(C(G,2),\ell_1)=\text{TC}(C(G,2))=1\). \item[(3)] Otherwise, \(\text{GC}(C(G,2),\ell_1)=\text{TC}(C(G,2))=2\). \end{itemize}