I am looking for an algorithm that can convert from a DFA to an NFA, while at the same time producing the minimum number of states for the NFA. My gut tells me this can be done with around $n$ states, where the DFA has $O(2^n)$ states. That is, I do not care how many transitions there are, only about the number of NFA states. I am not a graph-theorist, but it seems to me that there should be an algorithm based on the relationship between the number of vertices(states) and edges(transitions) based on Euler's equation.
Said in another way, I am not attempting to minimize the NFA, but to use a minimized DFA to construct an NFA that has fewer states than the DFA.
Pseudo-code is most welcome.
By definition, DFA is itself an NFA. So, conversion from DFA to NFA doesn't make much sense. But, you can always convert a DFA to an equivalent DFA with minimum number of states. There are several algorithms for that purpose. The best known time complexity is $O(n\log\log n)$, where $n$ is the number of states in the DFA.