Memetic Search for Identifying Critical Nodes in Sparse Graphs.

Area of Science:

• Graph theory
• Combinatorial optimization
• Computer science

Background:

• Critical node problems (CNPs) are essential for analyzing graph robustness and network resilience.
• These problems are computationally complex, requiring efficient algorithms for practical applications.
• Existing methods often struggle with scalability and finding optimal solutions.

Purpose of the Study:

• To develop and evaluate an effective memetic algorithm for solving the classic critical node problem (CNP).
• To assess the algorithm's performance on benchmark instances and compare it with existing methods.
• To investigate the algorithm's applicability to variants like the cardinality-constrained CNP.

Main Methods:

• A memetic algorithm integrating a double backbone-based crossover operator for offspring generation.
• A component-based neighborhood search for refining solutions to local optima.
• A rank-based pool updating strategy to maintain population diversity and quality.

Main Results:

• The proposed algorithm established 24 new upper bounds on 42 benchmark instances.
• It matched 15 previously best-known solutions, demonstrating significant performance improvements.
• The algorithm proved effective for the cardinality-constrained CNP variant.

Conclusions:

• The developed memetic algorithm offers a powerful and efficient approach to solving critical node problems.
• The study highlights the effectiveness of combining specific operators and strategies for complex graph optimization.
• The findings contribute to advancing computational methods for network analysis and optimization.