Did you try adding
UserName ALL= NOPASSWD: /sbin/reboot
As the last line of their /etc/sudoers files? (replacing UserName with their actual user name, of course.)
That should grant them root access to only the /sbin/reboot command (add more commands using comma delimiting).
Then they just run $ sudo reboot
If you want to require they enter their own password before rebooting, use the line
UserName ALL=/sbin/reboot
Instead.
Use of sudo is recorded in /var/log/secure, if I recall correctly.