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

摘要

Very recently, Thomasse 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 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. (C) 2017 Elsevier B.V. All rights reserved.