As you've stated, the only real way to get at them is going underground? So what works?
What about snakes? Import a ton of badgers, but they dig pretty good size holes too, don't they?
Seems to me snakes would be the answer, since they can easily move underground, populate at a pace that is close to dogs(?).
Back on topic, but does a large population of coyotes, or even a reasonable one, seriously impact dog populations?
And what about pigs? They seem to be the worst, since they are smart, eat a lot, breed like crazy, can be vicious, and are sweeping the US?
Coyotes go after pigs?