One of the goals of Fedora 18 is to shrink the size of the Minimal install as much as possible. We are concentrating on keeping this minimal.
Since a minimal install machine does not need to do SELinux policy development, it was decided to remove the selinux-policy-devel package from the minimal install, which is fairly large. But audit2allow was in policycoreutils-python, and required the selinux-policy-devel package. audit2allow needs the interface files in selinux-policy-devel package in order for audit2allow -R to work.
I decided to move the audit2allow script to policycoreutils-devel package, since its main job is to help develop selinux-policy.
If you do not find audit2allow you your system, just
yum install policycoreutils-devel
or
yum install /usr/bin/audit2allow
Note: The latest setroubleshoot-server package requires policycoreutils-devel, so if you have this installed you will get audit2allow for free...