On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum

Afrouz Jabal Ameli; Faezeh Motiei; Morteza Saghafian

doi:10.1007/978-981-95-7127-7_26

On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum

Afrouz Jabal Ameli
, Faezeh Motiei^*
, Morteza Saghafian

^*Corresponding author for this work

Sub Algorithms and Complexity

Eindhoven University of Technology
Institute of Science and Technology Austria

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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-2n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to 2d in expectation as n approaches infinity.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings
Editors	Emilio Di Giacomo, Debajyoti Mondal
Publisher	Springer
Pages	386-401
Number of pages	16
ISBN (Print)	9789819571260
DOIs	https://doi.org/10.1007/978-981-95-7127-7_26
Publication status	Published - 14 Feb 2026
Event	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026 - Perugia, Italy Duration: 4 Mar 2026 → 6 Mar 2026

Publication series

Name	Lecture Notes in Computer Science
Volume	16444 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026
Country/Territory	Italy
City	Perugia
Period	4/03/26 → 6/03/26

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

Keywords

Approximation Algorithms
Discrete and Computational Geometry
Minimum Spanning Tree
NP-hardness

Access to Document

10.1007/978-981-95-7127-7_26

Cite this

Jabal Ameli, A., Motiei, F., & Saghafian, M. (2026). On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum. In E. Di Giacomo, & D. Mondal (Eds.), WALCOM: Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings (pp. 386-401). (Lecture Notes in Computer Science; Vol. 16444 LNCS). Springer. https://doi.org/10.1007/978-981-95-7127-7_26

Jabal Ameli, Afrouz ; Motiei, Faezeh ; Saghafian, Morteza. / On the MST-Ratio : Theoretical Bounds and Complexity of Finding the Maximum. WALCOM: Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings. editor / Emilio Di Giacomo ; Debajyoti Mondal. Springer, 2026. pp. 386-401 (Lecture Notes in Computer Science).

@inproceedings{97f2f74489004e71b0b77103470c6f8e,

title = "On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum",

abstract = "Given a finite set of red and blue points in Rd, 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-2n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to 2d in expectation as n approaches infinity.",

keywords = "Approximation Algorithms, Discrete and Computational Geometry, Minimum Spanning Tree, NP-hardness",

author = "\{Jabal Ameli\}, Afrouz and Faezeh Motiei and Morteza Saghafian",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.; 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026 ; Conference date: 04-03-2026 Through 06-03-2026",

year = "2026",

month = feb,

day = "14",

doi = "10.1007/978-981-95-7127-7\_26",

language = "English",

isbn = "9789819571260",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "386--401",

editor = "\{Di Giacomo\}, Emilio and Debajyoti Mondal",

booktitle = "WALCOM",

}

Jabal Ameli, A, Motiei, F & Saghafian, M 2026, On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum. in E Di Giacomo & D Mondal (eds), WALCOM: Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings. Lecture Notes in Computer Science, vol. 16444 LNCS, Springer, pp. 386-401, 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, 4/03/26. https://doi.org/10.1007/978-981-95-7127-7_26

On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum. / Jabal Ameli, Afrouz; Motiei, Faezeh; Saghafian, Morteza.
WALCOM: Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings. ed. / Emilio Di Giacomo; Debajyoti Mondal. Springer, 2026. p. 386-401 (Lecture Notes in Computer Science; Vol. 16444 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the MST-Ratio

T2 - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026

AU - Jabal Ameli, Afrouz

AU - Motiei, Faezeh

AU - Saghafian, Morteza

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

PY - 2026/2/14

Y1 - 2026/2/14

N2 - Given a finite set of red and blue points in Rd, 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-2n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to 2d in expectation as n approaches infinity.

AB - Given a finite set of red and blue points in Rd, 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-2n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to 2d in expectation as n approaches infinity.

KW - Approximation Algorithms

KW - Discrete and Computational Geometry

KW - Minimum Spanning Tree

KW - NP-hardness

UR - https://www.scopus.com/pages/publications/105031223265

U2 - 10.1007/978-981-95-7127-7_26

DO - 10.1007/978-981-95-7127-7_26

M3 - Conference contribution

AN - SCOPUS:105031223265

SN - 9789819571260

T3 - Lecture Notes in Computer Science

SP - 386

EP - 401

BT - WALCOM

A2 - Di Giacomo, Emilio

A2 - Mondal, Debajyoti

PB - Springer

Y2 - 4 March 2026 through 6 March 2026

ER -

Jabal Ameli A, Motiei F, Saghafian M. On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum. In Di Giacomo E, Mondal D, editors, WALCOM: Algorithms and Computation - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Proceedings. Springer. 2026. p. 386-401. (Lecture Notes in Computer Science). doi: 10.1007/978-981-95-7127-7_26