conference paper published yes Afrouz Jabal Ameli author Faezeh Motiei author Morteza Saghafian author f86f7148-b140-11ec-9577-95435b8df824 HeEd department WALCOM: International Conference and Workshops on Algorithms and Computation Alpha Shape Theory Extended project Mathematics, Computer Science project Given a finite set of red and blue points in R^d, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points, divided by the length of the Euclidean minimum spanning tree of their union. The MST-ratio has recently gained attention due to its direct interpretation in topological models for studying point sets with applications in spatial biology. The maximum MST-ratio of a point set is the maximum MST-ratio over all proper colorings of its points by red and blue. We prove that finding the maximum MST-ratio of a given point set is NP-hard when the dimension is part of the input. Moreover, we present a quadratic-time 3-approximation algorithm for this problem. As part of the proof, we show that in any metric space, the maximum MST-ratio is smaller than 3. Furthermore, we study the average MST-ratio over all colorings of a set of n points. We show that this average is always at least n-2/n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to (math formular) in expectation as n approaches infinity. Springer Nature2026Perugia, Italy eng 0302-9743 1611-3349 9789819571260 2409.1107910.1007/978-981-95-7127-7_26 16444386-401 Jabal Ameli A, Motiei F, Saghafian M. On the MST-ratio: Theoretical bounds and complexity of finding the maximum. In: <i>20th International Conference and Workshops on Algorithms and Computation</i>. Vol 16444. Springer Nature; 2026:386-401. doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_26">10.1007/978-981-95-7127-7_26</a> A. Jabal Ameli, F. Motiei, M. Saghafian, in:, 20th International Conference and Workshops on Algorithms and Computation, Springer Nature, 2026, pp. 386–401. Jabal Ameli A, Motiei F, Saghafian M. 2026. On the MST-ratio: Theoretical bounds and complexity of finding the maximum. 20th International Conference and Workshops on Algorithms and Computation. WALCOM: International Conference and Workshops on Algorithms and Computation, LNCS, vol. 16444, 386–401. A. Jabal Ameli, F. Motiei, and M. Saghafian, “On the MST-ratio: Theoretical bounds and complexity of finding the maximum,” in <i>20th International Conference and Workshops on Algorithms and Computation</i>, Perugia, Italy, 2026, vol. 16444, pp. 386–401. Jabal Ameli, A., Motiei, F., &#38; Saghafian, M. (2026). On the MST-ratio: Theoretical bounds and complexity of finding the maximum. In <i>20th International Conference and Workshops on Algorithms and Computation</i> (Vol. 16444, pp. 386–401). Perugia, Italy: Springer Nature. <a href="https://doi.org/10.1007/978-981-95-7127-7_26">https://doi.org/10.1007/978-981-95-7127-7_26</a> Jabal Ameli, Afrouz, Faezeh Motiei, and Morteza Saghafian. “On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum.” In <i>20th International Conference and Workshops on Algorithms and Computation</i>, 16444:386–401. Springer Nature, 2026. <a href="https://doi.org/10.1007/978-981-95-7127-7_26">https://doi.org/10.1007/978-981-95-7127-7_26</a>. Jabal Ameli, Afrouz, et al. “On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum.” <i>20th International Conference and Workshops on Algorithms and Computation</i>, vol. 16444, Springer Nature, 2026, pp. 386–401, doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_26">10.1007/978-981-95-7127-7_26</a>. 214102026-03-08T23:01:45Z2026-03-09T10:25:41Z