I'll vote with requiring it. It is easy enough to install on any platform supporting CPAN. If you package CPAN-style with ExtUtils::MakeMaker, you can provide a make rule to go get the distribution, or else say,     PREREQ_PM => { Regexp::Common => '2.00' }, in the attrubute list of WriteMakefile() in Makefile.PL.

If you don't expect your users to have system privileges, you can make the installation go into some private library and pepper the code with use lib '/my/private/lib';.

There are, of course, many admins who will refuse all modules beyond core, and even delete as many core ones as they can. There are others who will not install anything their vendor's package mechanism doesn't provide. Them aside, well-stocked perl installation will have a good chance of having it.

After Compline,
Zaxo