Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem
It addresses the lack of empirical analysis for the NP-complete mutual-visibility problem, providing incremental insights for researchers in graph theory and optimization.
This paper tackled the mutual-visibility problem by implementing and evaluating three algorithms on synthetic graphs, finding that for smaller graphs, they align with theoretical bounds, but for larger instances, solution sizes diverge from limits, with the Genetic Algorithm performing best among tested methods.
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.