Everything is possible depending on how deep you want to go. On the assumption that you don't want to get into hacking your shell, kernel or get into selinux or AppArmour. No, you can't stop people executing foo (via ./foo or otherwise) without changing file system permissions or acls.
On Linux an executable is made executable based on file permissions, and posix acls. If they can execute it then they can execute it, only the executable itself can check if it should be run with the full path. If it's just a simple path problem you could wrap it in a shell and check the $0 argument, but for security this is really just obfuscation and anyone with a clue will get round in seconds.
Otherwise this is handled through acls and user and group executability. However, then you have to manage the user accounts, and file system acls and groups.
Usually files are owned by the admin account so for most user accounts they execute things through the group or other permission.
Remove the execute permission from "other".
chmod o-x /path/to/foo
Move the group membership of foo to a trusted group and make sure group execute permission is set.
chgrp trusted /path/to/foo
chmod g+x /path/to/foo
Now you have to put all the users who should be able to run foo into the trusted group.
for eachUser in a potentially a big long list of user accounts
usermod --append --groups trusted $eachUser
And the management overhead of this is is why traditional Unix permissions suck.
For posix acls you can simply add the user to the file, but without the execute permission. Use getfacl to read the access control list.
for eachUser in a smaller list of restricted users
setfacl -m user:$eachUser:000 /path/to/foo
Because the acl entry is there for the user account, it takes precedence over the default user/group/other file system permissions and the user has no permission on the file. Everyone else will be able to use the file as normally.
Better mathematically though is to put all the restricted accounts into a group, and add the group to the file with no permissions instead of individual users.