My first try at golf:

sub b {  
    $M = scalar keys %t;
    $m = $M *= $M;
    foreach  ( keys %t ) {
        $r = c( $_ );
        ($m,$n) = ($r, $_) if ($r < $m );
    }
    $n;
}

sub c {
    @s=@_;
    %b  = ( $s[0] => $b=$sum=0 );
    while ( @s > 0 ) {
        $b ++;
        @s = grep {  ! exists( $b{$_}  ) } 
             map { @{$t{$_}} } @s;
        @b{ @s } = ($b) x scalar(@s);
        $sum += $b * scalar(@s); 
        return $M if $sum >  $m         
    }
    $sum;    
}
[download]

works for graphs too, I think.

Update: I can write that down in 196:

sub b{$M=$m=@_*@_;for(keys %t){$r=c($_);($m,$n)=($r,$_)if($r<$m)}$n}su
+b c{%b=($_[0]=>$b=$sum=1);while(@_){$b++;@_=grep{!$b{$_}}map{@{$t{$_}
+}}@_;@b{@_}=($b)x@_;$sum+=$b*@_;return$M if$sum>$m}$sum}
[download]

slower but shorter: down to 177:

sub b{$M=$m=@_*@_;for(keys %t){$r=c($_);($m,$n)=($r,$_)if($r<$m)}$n}su
+b c{%b=($_[0]=>$b=$sum=1);while(@_){$b++;@_=grep{!$b{$_}}map{@{$t{$_}
+}}@_;@b{@_}=($b)x@_;$sum+=$b*@_}$sum}
[download]

I never new how hard obfuscation is! </code>

--
Brigitte    'I never met a chocolate I didnt like'    Jellinek
http://www.horus.com/~bjelli/         http://perlwelt.horus.at

sub bacon {
  (%g,%d)=@_;for$k(keys%g){($i,@l,%v)=(0,$k);{!$v{$_}++and$d{$k}+=$i f
+or@l;$i++;(@l=map{grep!$v{$_},@{$g{$_}}}@l)&&redo}}(sort{$d{$a}<=>$d{
+$b}}keys%d)[0]
}
[download]

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

sub b {
$a=@_*@_;for(@_){%t=@_;$t=@r=$_;$t+=%t while@r=map@{delete$t{$_}},@r;$
+a=$t,$b=$_ if!ref&&$t<$a}$b
}
[download]

Update: Thanks to MeowChow for crawling through that thoroughly fetid blob of code and discovering that I need to say $t+=keys%t instead of $t+=%t. And here I thought I was being so clever.

Interestingly, this causes both my 5.6 Win32 ActiveState Perl and my 5.6.1 Linux to segfault, but appears to work under 5.00503. Hmmm....

update: I think this is a garbage-collection issue, stemming from your deletion of a hash key will simultaneously dereferencing it. Ingenious, and dangerous.

update2: Err, that wasn't the problem, the problem was that my test hash was already %t, so it was getting reset inside the sub, and I ran into this.

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

sub bacon {
  my%t=@_;(sort{@{$t{$b}}<=>@{$t{$a}}}keys%t)[0]
}
[download]

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

This problem shouldn't be NP-complete. A well-rounded algorithm is going to be, I believe, O(N^2) or O(N^3). However, the golf solution will probably be NP.

---

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Sorry to ask but my curiosity is too big...
What is NP (or NP-complete) ?
Thanks.

BobiOne KenoBi ;)

BTW, if mathematicians measure theis distance from number from Erdös, and musicians from Elvis, who can be used by Perl Programmers as 0?