Provable Speedups from Linkage Learning in Evolutionary Algorithms for Graph Optimisation

Graph ordering problems, such as the NP-hard Feedback Arc Set (FAS) problem, are commonly attacked with evolutionary algorithms and greedy reinsertion heuristics. These methods search in permutation spaces and are guided solely by the objective value. As a result, they expose the immediate precedence constraints of the graph but leave transitive structure hidden. We show that this constitutes a genuine obstruction to efficient search. To this end, we show that even for a simple special case of FAS, namely to compute a topological ordering of a graph, an evolutionary algorithm (RLS) needs weakly exponential time. Building on linkage learning mechanisms developed for binary spaces, we transfer this machinery to permutation spaces and prove that it learns arcs of the underlying graph and never reports false ones. We then design a mutation operator that employs the learned arcs to identify sets of elements that are jumped together, thereby handling transitive structure implicitly. Equipping RLS with this operator, we show that learning and search reinforce each other: in every non-optimal step, the algorithm improves the fitness or enables the detection of a new arc with probability at least $1/n^2$. Hence, the improved algorithm orders any DAG in expected polynomial time without having to recover the entire graph. This exponential speedup demonstrates the usefulness of the enhanced operator in settings with hidden transitive structure. Experiments on instances with progressively removed transitivity information confirm this gap and indicate that the same operator remains effective on cyclic FAS instances.