Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.01076 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909814299295744 |
|---|---|
| author | Stojanović, Vanja Pangeršič, Bor |
| author_facet | Stojanović, Vanja Pangeršič, Bor |
| contents | The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms -- a direct random heuristic, a hypergraph-based approximation, and a genetic algorithm -- on diverse synthetic graph datasets, including those with analytically known $μ(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01076 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem Stojanović, Vanja Pangeršič, Bor Computational Geometry Artificial Intelligence Performance Combinatorics The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms -- a direct random heuristic, a hypergraph-based approximation, and a genetic algorithm -- on diverse synthetic graph datasets, including those with analytically known $μ(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods. |
| title | Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem |
| topic | Computational Geometry Artificial Intelligence Performance Combinatorics |
| url | https://arxiv.org/abs/2507.01076 |