Transaction selection is NP-hard, but the software isn't trying to find the ideal fee; just one that is cheap enough. That's why they use variations of Dijkstra and A*, and not these algorithms themselves. In LND, for instance, you can check yourself how optimized it is, comparably to a simple Dijkstra algorithm implementation: https://github.com/lightningnetwork/lnd/blob/master/routing/pathfind.go#L494-L504.

But, I don't understand why you focus on routing algorithm being NP-hard, and ignore mining which is NP-hard itself. The typical way to resolve this, is just to select a "good enouch solution" rather finding the optimal. This is why you can find cases of blocks which could include higher paying transactions instead. System works pretty fine after all.