  Indexing a set of strings for prefix search or membership queries is a
fundamental task with many applications such as information retrieval or
database systems. A classic abstract data type for modelling such an index is a
trie. Due to the fundamental nature of this problem, it has sparked much
interest, leading to a variety of trie implementations with different
characteristics. A trie implementation that has been well-used in practice is
the double-array (trie) consisting of merely two integer arrays. While a
traversal takes constant time per node visit, the needed space consumption in
computer words can be as large as the product of the number of nodes and the
alphabet size. Despite that several heuristics have been proposed on lowering
the space requirements, we are unaware of any theoretical guarantees.
  In this paper, we study the decision problem whether there exists a
double-array of a given size. To this end, we first draw a connection to the
sparse matrix compression problem, which makes our problem NP-complete for
alphabet sizes linear to the number of nodes. We further propose a reduction
from the restricted directed Hamiltonian path problem, leading to
NP-completeness even for logarithmic-sized alphabets.
