On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem

Abstract

A lot of heuristic algorithms, such as Evolutionary algorithms (EAs), are used to solve the maximum leaf spanning tree (MLST) problem which is non-deterministic polynomial time hard (NP-hard). However, the performance analysis of EAs on the MLST problem has seldom been studied theoretically. In this paper, we theoretically analyze the performance of the (1+1) EA on the MLST problem. We demonstrate that the (1+1) EA obtains $5$-approximation ratio and 3-approximation ratio on this problem in expected polynomial runtime O(nm²) and O(nm⁴), respectively, where n is the number of nodes and m is the number of edges in a connected undirected graph. Furthermore, we reveal that the (1+1) EA can outperform the local search algorithms on two instances of the MLST problem.

Keywords:

• evolutionary algorithm
• maximum leaf spanning tree
• local search
• approximation algorithms
• performance analysis

2010 AMS Subject Classifications::

• 68W20
• 68Q25
• 90C27
• 90C59

Acknowledgements

The authors thank the anonymous reviewers and the editor for their valuable comments and suggestions that help improve this paper. This work was supported by the National Natural Science Foundation of China under Grants 61170081 and 61472143.