  The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial
optimization problem that has been extensively studied by the researchers in
the field of evolutionary computing to theoretically analyze the optimization
performance of evolutionary algorithms. Within the paper, we consider a
constrained version of the problem named 2-Hop (1,2)-Minimum Spanning Tree
problem (abbr. 2H-(1,2)-MSTP) in the context of evolutionary algorithms, which
has been shown to be NP-hard. Following how evolutionary algorithms are applied
to solve the MSTP, we first consider the evolutionary algorithms with search
points in edge-based representation adapted to the 2H-(1,2)-MSTP (including the
(1+1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two
variants). More specifically, we separately investigate the upper bounds on
their expected time (i.e., the expected number of fitness evaluations) to
obtain a $\frac{3}{2}$-approximate solution with respect to different fitness
functions. Inspired by the special structure of 2-hop spanning trees, we also
consider the (1+1) EA with search points in vertex-based representation that
seems not so natural for the problem and give an upper bound on its expected
time to obtain a $\frac{3}{2}$-approximate solution, which is better than the
above mentioned ones.
