  A $k$-attractor is a combinatorial object unifying dictionary-based
compression. It allows to compare the repetitiveness measures of different
dictionary compressors such as Lempel-Ziv 77, the Burrows-Wheeler transform,
straight line programs and macro schemes. For a string $T \in \Sigma^n$, the
$k$-attractor is defined as a set of positions $\Gamma \subseteq [1,n]$, such
that every distinct substring of length at most $k$ is covered by at least one
of the selected positions. Thus, if a substring occurs multiple times in $T$,
one position suffices to cover it. A 1-attractor is easily computed in linear
time, while Kempa and Prezza [STOC 2018] have shown that for $k \geq 3$, it is
NP-complete to compute the smallest $k$-attractor by a reduction from $k$-set
cover.
  The main result of this paper answers the open question for the complexity of
the 2-attractor problem, showing that the problem remains NP-complete. Kempa
and Prezza's proof for $k \geq 3$ also reduces the 2-attractor problem to the
2-set cover problem, which is equivalent to edge cover, but that does not fully
capture the complexity of the 2-attractor problem. For this reason, we extend
edge cover by a color function on the edges, yielding the colorful edge cover
problem. Any edge cover must then satisfy the additional constraint that each
color is represented. This extension raises the complexity such that colorful
edge cover becomes NP-complete while also more precisely modeling the
2-attractor problem. We obtain a reduction showing $k$-attractor to be
NP-complete and APX-hard for any $k \geq 2$.
