Very recently, Thomass'e, Trotignon and Vuskovic [WG 2014] have given an FPTalgorithm for Weighted Independent Set in bull-free graphs parameterized by theweight of the solution, running in time $2^{O(k^5)} cdot n^9$. In this articlewe improve this running time to $2^{O(k^2)} cdot n^7$. As a byproduct, we alsoimprove 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 atmost $2p-1$ for $p geq 3$, we speed up the running time to $2^{O(k cdotk^{rac{1}{p-1}})} cdot n^7$. As $p$ grows, this running time isasymptotically tight in terms of $k$, since we prove that for each integer $pgeq 3$, Weighted Independent Set cannot be solved in time $2^{o(k)} cdotn^{O(1)}$ in the class of ${bull,C_4,ldots,C_{2p-1}}$-free graphs unless theETH fails.
展开▼
