Symbolic Regression for Approximating Graph Geodetic Number

Abstract

Graph properties are certain attributes that could make the structure of the graph understandable. Occasionally, standard methods cannot work properly for calculating exact values of graph properties due to their huge computational complexity, especially for real-world graphs. In contrast, heuristics and metaheuristics are alternatives proved their ability to provide sufficient solutions in a reasonable time. Although in some cases, even heuristics are not efficient enough, where they need some not easily obtainable global information of the graph. The problem thus should be dealt in completely different way by trying to find features that related to the property and based on these data build a formula which can approximate the graph property. In this work, symbolic regression with an evolutionary algorithm called Cartesian Genetic Programming has been used to derive formulas capable to approximate the graph geodetic number which measures the minimal-cardinality set of vertices, such that all shortest paths between its elements cover every vertex of the graph. Finding the exact value of the geodetic number is known to be NP-hard for general graphs. The obtained formulas are tested on random and real-world graphs. It is demonstrated how various graph properties as training data can lead to diverse formulas with different accuracy. It is also investigated which training data are really related to each property.