The Effect of Graph Structure on Greedy, Simulated Annealing, and Lotka–Volterra Methods

Abstract

The maximum-independent-set problem is a fundamental graph problem with applications in situations where one wants to select as many mutually compatible objects as possible, such as non-conflicting tasks or choices. This problem is computationally difficult to solve exactly on large graphs. This motivates the use of heuristic algorithms. However, heuristic performance can depend strongly on the structure of the input graph, so it is not enough to ask which algorithm performs best on average. It is also important to understand when and why a heuristic fails.

This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.

The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.

The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.

Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle.