---
OA_place: repository
OA_type: green
_id: '21410'
abstract:
- lang: eng
  text: 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.
acknowledgement: "A. J. Ameli—Supported by the project COALESCE (ERC grant no. 853234).\r\nM.
  Saghafian—Partially supported by the European Research Council (ERC), grant no.
  788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z
  342-N31."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Afrouz
  full_name: Jabal Ameli, Afrouz
  last_name: Jabal Ameli
- first_name: Faezeh
  full_name: Motiei, Faezeh
  last_name: Motiei
- first_name: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
citation:
  ama: '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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: A. Jabal Ameli, F. Motiei, M. Saghafian, in:, 20th International Conference
    and Workshops on Algorithms and Computation, Springer Nature, 2026, pp. 386–401.
conference:
  end_date: 2026-03-06
  location: Perugia, Italy
  name: 'WALCOM: International Conference and Workshops on Algorithms and Computation'
  start_date: 2026-03-04
date_created: 2026-03-08T23:01:45Z
date_published: 2026-02-14T00:00:00Z
date_updated: 2026-03-09T10:25:41Z
day: '14'
department:
- _id: HeEd
doi: 10.1007/978-981-95-7127-7_26
ec_funded: 1
external_id:
  arxiv:
  - '2409.11079'
intvolume: '     16444'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2409.11079
month: '02'
oa: 1
oa_version: Preprint
page: 386-401
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
publication: 20th International Conference and Workshops on Algorithms and Computation
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9789819571260'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'On the MST-ratio: Theoretical bounds and complexity of finding the maximum'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16444
year: '2026'
...