Comment 76 for bug 959037

> (Another minor problem with your proposal as you phrased it is the following. The existence of /etc/init.d/dnsmasq does not entail that the dnsmasq is installed. The package could have been removed and not purged.)

Correct, but then I wonder what prevents dnsmasq from running even if it's removed (not purged), since its executable is provided by dnsmasq-base, which _is_ installed.
But anyway the same logic that prevents it from running can be reused by NM to detect if dnsmasq will indeed start.