Time complexity analysis of evolutionary algorithms for 2-hop (1, 2)-minimum spanning tree problem

Feng Shi, Frank Neumann, Jianxin Wang

Abstract

The 2-Hop (1, 2)-Minimum Spanning Tree Problem (2H-(1,2)-MSTP) is an NP-hard optimization problem with significant applications in network design, particularly where signal delay must be minimized. This paper investigates the performance of various evolutionary algorithms (EAs), including the (1+1) EA and multi-objective variants like GSEMO, on this problem. Through rigorous time complexity analysis, we demonstrate that the choice of solution representation—edge-based versus vertex-based—is critical to algorithmic efficiency. Specifically, a vertex-based representation allows the (1+1) EA to achieve a 3/2-approximation in $O(n^4)$ time, significantly outperforming edge-based approaches. Furthermore, multi-objective strategies are shown to facilitate the search process by bridging infeasible and optimal solution spaces.

Introduction

Minimum Spanning Tree (MST) problems are fundamental in combinatorial optimization. While the standard MST problem is solvable in polynomial time using algorithms like Prim's or Kruskal's, real-world constraints often introduce NP-hardness. One such constraint is the "hop constraint," which limits the number of edges between a root node and any other node in the tree to minimize latency. The 2-Hop (1, 2)-Minimum Spanning Tree Problem (2H-(1,2)-MSTP) restricts the tree depth to 2 and edge weights to 1 or 2. This paper provides a theoretical analysis of how evolutionary algorithms navigate the search space of this NP-hard problem.

Problem Formulation

In the 2H-(1,2)-MSTP, we are given a complete graph $G = (V, E)$ with a root node $r \in V$. Each edge $e \in E$ has a weight $w(e) \in \{1, 2\}$. The goal is to find a spanning tree $T$ rooted at $r$ such that the distance from $r$ to any vertex $v$ is at most 2 hops, and the total weight of the edges in $T$ is minimized. The restriction to weights 1 and 2 makes the problem a specific class of NP-hard problems often used to study approximation performance in theoretical computer science.

Algorithms and Representations

The study evaluates several evolutionary strategies using expected time complexity analysis:

  1. (1+1) EA: A baseline local search algorithm that maintains a single individual and uses mutation to find improvements.
  2. GSEMO (Global Simple Evolutionary Multi-Objective Optimizer): A population-based algorithm that treats the problem as having multiple objectives, such as minimizing cost while managing the number of edges.
  3. GSEMO-1 and GSEMO-2: Specialized multi-objective variants designed to manage population size and improve the efficiency of edge-swapping operations.

A key contribution of this work is the comparison of two representation schemes:

  • Edge-based Representation: Solutions are encoded as bit-strings of length $m$ (number of edges). This representation often requires complex repair mechanisms or heavy penalties for infeasible solutions (e.g., cycles or depth > 2).
  • Vertex-based Representation: Solutions are encoded as bit-strings of length $n-1$, where each bit indicates whether a vertex is a direct child of the root. This representation is mathematically powerful because every bit-string inherently represents a valid 2-hop tree, eliminating the need to penalize infeasible solutions.

Theoretical Analysis and Results

The analysis focuses on the expected number of fitness evaluations required to reach a 3/2-approximation of the optimal solution. The results highlight a dramatic difference in complexity based on the chosen representation.

Comparison of expected time complexities for different algorithms and representations.

As shown in the table above, the (1+1) EA using an edge-based representation requires $O(m^6n)$ time to achieve a 3/2-approximation. In contrast, the same algorithm using a vertex-based representation achieves the same approximation ratio in only $O(n^4)$ time. Given that $m \approx n^2$, this represents a massive reduction in computational effort.

The analysis also reveals the "swap bottleneck" in edge-based representations. Improving a solution often requires flipping two specific bits simultaneously (a swap), which has a low probability ($1/m^2$) in standard mutation. Multi-objective algorithms like GSEMO-2 mitigate this by allowing the population to include slightly infeasible solutions that serve as "stepping stones" to better feasible ones, reducing the complexity to $O(m^4n)$ in the edge-based case.

Conclusion

This research underscores the importance of problem representation in the design of evolutionary algorithms for constrained optimization. By adopting a vertex-based representation that naturally incorporates the 2-hop constraint, the search space is effectively pruned, leading to exponential speedups. Additionally, multi-objective approaches prove beneficial in navigating complex landscapes where local optima or infeasible regions hinder simple greedy searches. Future work will explore extending these findings to $k$-hop constraints and more diverse weight distributions.

Summary updated

BibTeX
@article{shi2021time,
  author = {Feng Shi and Frank Neumann and Jianxin Wang},
  title = {{Time complexity analysis of evolutionary algorithms for 2-hop (1, 2)-minimum spanning tree problem}},
  journal = {Theoretical Computer Science},
  year = {2021},
  doi = {10.1016/j.tcs.2021.09.003},
}
Figure