Is Prüfer Code encoding always a bad idea?

Real world problems are often of a complexity that renders deterministic approaches intractable. In the area of applied optimization, heuristics can offer a viable alternative. While potentially forfeiting on finding the most optimal solution, these techniques return good solutions in a short time. To do so, a suitable modelling of the problem as well as an efficient mapping of the problem’s solutions into a so-called solution space is required. Since it is very common to represent solutions as graphs, algorithms that efficiently map graphs into a heuristic-friendly solutions-space are of general interest to community. For a special type of graph, namely trees (i.e., undirected, connected and acyclic graphs such as Cayley in Phil Mag 13:172–176 (1857) [13]) Prüfer Code (Prüfer in Archiv der Mathematik und Physik 27:742–744 (1918) [43]) (PC) offers a bijective encoding process that comes at a low complexity (algorithms of Θ(n)-complexity are known Micikevičius et al. in Linear-time algorithms for encoding trees as sequences of node labels (2007) [37]) and facilitates mapping to n-2 dimensional Euclidean space. However, this encoding does not preserve properties such as e.g., locality and has therefore been shown to be sub-optimal for entire classes of problems (Gottlieb et al. in Prüfer numbers: a poor representation of spanning trees for evolutionary search (2001) [24]). We argue that Prüfer Code does preserve some characterizing properties (e.g., degree of branching and branching vertices) and that these are sufficiently relevant for certain types of problems to motivate encoding them in PC. We present our investigations and provide an example problem where PC encoding worked very well.