The minimum list for a AD Trust is:
53 TCP/UDP DNS
88 TCP/UDP Kerberos
389 TCP/UDP LDAP
445 TCP SMB
636 TCP LDAP (SSL)
You can tighten that up a bit by configuring Kerberos for TCP only.
And if you're crazy you could use HOSTS files instead of DNS.
References: Pber's Blog and MS KB 179442
As for which computers need to be able to access the above: The computer verifying the authentication of the trusted user must be able to directly contact both it's own DC and the Trusted DC.
For example: Bob from Alpha (domain) is trying to log in to a workstation that's in Omega (domain). That workstation will check with it's own DCs to get the relevant trust information. Then the workstation will contact a DC from Alpha, verify the user, and login.
Another stickier example: Bob is using his workstation in the Alpha domain. Bob logs into a web service that runs on the Omega domain, but does not use Kerberos to authenticate. The web server in Omega is going to do the authentication, so it needs access like the workstation in the previous example.
The last one I don't actually remember the "answer" to - exactly like the previous, but using Kerberized authentication. I believe the Omega web server still needs access just the same, but it's been too long and I don't have a lab to test that in quickly. I should dig into this one of these days and write a blog article.