Hard test generation for augmenting path maximum flow algorithms using genetic algorithms: Revisited

To estimate performance of computer science algorithms reliably, one has to create worst-case execution time tests. For certain algorithms this task can be difficult. To reduce the amount of human effort, authors attempt using search-based optimization techniques, such as genetic algorithms. Our previous paper addressed test generation for several maximum flow algorithms. Genetic algorithms were applied for test generation and showed promising results. However, one of the aspects of maximum flow algorithm implementation was missing in that paper: parallel edges (edges which share source and target vertices) were not merged into one single edge (which is allowed in solving maximum flow problems). In this paper, parallel edge merging is implemented and new results are reported. A surprising fact is shown that fitness functions and choices of genetic operators which were the most efficient in the previous paper are much less efficient in the new setup and vice versa. What is more, the set of maximum flow algorithms, for which significantly better tests are generated, changed completely as well.