Add 'your program' to the users sudo list, hence giving him/her the possibility to sudo your program (check man visudo, or the documentation of your distributions sudo implementation).
If you use a distribution that hasn't disabled the UID bit, you can use that. You set root as owner of 'your program' and set the UID bit. Which make the program run under the owners identity always. (Doesn't work with scripts, though.) If security is important, this is not an option.
$ chown root your_program
$ chmod +s your_program