While preparing for final exam, I encountered a (target) problem where you have $M$ lines and $L$ points and you want to answer if it's possible to cover them all using $K$ disks of unit radius (decision problem).

I would like to reduce the Disk Covering Problem to the problem at hand to show that the problem is NP-hard. Is my logic valid if I construct an instance of the target problem with no lines, meaning to set $M=0$, and reduce an arbitrary instance of the disk covering problem to it? or does setting $M=0$ invalidate the reduction?

  • $\begingroup$ Can you define Disk Covering Problem you want to reduce from (which needs to be NP-Hard)? What are the instances of this problem? What are the yes-instances or the measure you want to optimize (which should depend on the instance)? $\endgroup$
    – Steven
    Commented Dec 4, 2023 at 19:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.