Some problems similar to the minimization of immersions
also appear in the literature.
However, to our best knowledge, no straightforward reduction exists
from one of these problems to the minimization of immersions. The
first problem is the minimization of non-deterministic finite
automata with limited non-determinism. Whereas the minimization of
arbitrary non-deterministic finite
automata is PSPACE-complete, it becomes NP-complete for automata
that have a fixed number of initial states, and are otherwise
deterministic [1]}. Further NP-completeness results for
minimization of automata with small degree of ambiguity are provided
in [2]}. A seemingly close problem from computational biology is the shortest common superstring problem,
which asks for the shortest string containing each string from a given
set as factor. This problem is known to be NP-complete [3]}.
