Minimize a DFA with don't care transitions

I think this problem is NP-hard (more on that in a bit). This is what I'd try.

1. (Optional) Preprocess the input via the usual minimization algorithm with accept/reject/don't care as separate outcomes. (Since don't care is not equivalent to accept or reject, we get the Myhill–Nerode equivalence relation back, allowing a variant of the usual algorithm.)

2. Generate a conflict graph as follows. Start with all edges between accepting and rejecting states. Take the closure where we iteratively add edges q₁—q₂ such that there exists a symbol s for which there exists an edge σ(q₁, s)—σ(q₂, s).

3. Color this graph with as few colors as possible. (Or approximate.) Lots and lots of coloring algorithms out there. PartialCol is a good starting point.

4. Merge each color class into a single node. This potentially makes the new transition function multi-valued, but we can choose arbitrarily.

With access to an alphabet of arbitrary size, it seems easy enough to make this reduction to coloring run the other way, proving NP-hardness. The open question for me is whether having a fixed-size alphabet constrains the conflict graph in such a way as to make the resulting coloring instance easier somehow. Alas, I don't have time to research this.