Résumé
Very recently, Thomasse, Trotignon and Vuskovic [WG 2014] have given an FPT algorithm for WEIGHTED INDEPENDENT SET in bull-free graphs parameterized by the weight of the solution, running in time 2(O(k5)).n(9). In this article we improve this running time to 2(O(k2)).n(7). As a byproduct, we also improve the previous Turing-kernel for this problem from O(k(5)) to O(k(2)). Furthermore, for the subclass of bull-free graphs without holes of length at most 2p - 1 for p >= 3, we speed up the running time to 2(O(k.k1/p-1)) . n(7). As p grows, this running time is asymptotically tight in terms of k, since we prove that for each integer p >= 3, WEIGHTED INDEPENDENT SET cannot be solved in time 2(o(k)) . n(O(1)) in the class of {bull, C-4,..., C2p-1}-free graphs unless the ETH fails.