First step: profile your code (for example with Devel::NYProf) and see where the actual slowness comes from.

From a quick glance it seems that your code is linear in the number of elements in each array, so only minor improvements can be made.

In sub Intersection, if you can assume that $refA and $refB each don't contain a single item twice, you can rewrite the sub to:

sub Intersection {
    my( $refA, $refB ) = @_;

    my %counts;
    ++$counts{ $_ } for @$refA;

    my $intersects = 0;
    $counts{ $_ } and ++$intersects for @$refB;

    return $intersects;
}
[download]