Several linear-time algorithms for automata-based pattern matching rely on failure transitions for efficient back-tracking. Like epsilon transitions, failure transition do not consume input symbols, but unlike them, they may only be taken when no other transition is applicable. At a semantic level, this conveniently models catch-all clauses. Recent work demonstrates that failure transitions allow for compact representation of finite-automata in general. For devices with rich alphabets and dense transition functions in particular, the potential savings are great. In this paper, we prove that three important problems related to the introduction of failure transitions are NP-complete, but that efficient approximation is possible for at least one of them.