Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time 2O(k5)⋅n9. In this article we improve this running time to 2O(k2)⋅n7. As a byproduct, we also improve the previous Turing-kernel for this problem from O(k5) to O(k2). 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 2O(k⋅k1p−1)⋅n7. 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 2o(k)⋅nO(1) in the class of {bull,C4,…,C2p−1}-free graphs unless the ETH fails.