  LZ-End is a variant of the well-known Lempel-Ziv parsing family such that
each phrase of the parsing has a previous occurrence, with the additional
constraint that the previous occurrence must end at the end of a previous
phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is
determined greedily from left to right, as the longest factor that satisfies
the above constraint~[Kreft & Navarro, 2010]. In this work, we consider an
optimal LZ-End parsing that has the minimum number of phrases in such parsings.
We show that a decision version of computing the optimal LZ-End parsing is
NP-complete by showing a reduction from the vertex cover problem. Moreover, we
give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach
for computing various NP-hard repetitiveness measures recently presented by
[Bannai et al., 2022]. We also consider the approximation ratio of the size of
greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a
lower bound of the ratio which asymptotically approaches $2$.
