Improved FPT algorithms for weighted independent set in bull-free graphs |
| |
Authors: | Henri Perret du Cray Ignasi Sau |
| |
Institution: | AlGCo project-team, CNRS, LIRMM, Montpellier, France |
| |
Abstract: | 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 . In this article we improve this running time to . As a byproduct, we also improve the previous Turing-kernel for this problem from to . Furthermore, for the subclass of bull-free graphs without holes of length at most for , we speed up the running time to . As grows, this running time is asymptotically tight in terms of , since we prove that for each integer , Weighted Independent Set cannot be solved in time in the class of -free graphs unless the ETH fails. |
| |
Keywords: | Parameterized complexity Bull-free graphs Independent set Turing-kernel |
本文献已被 ScienceDirect 等数据库收录! |
|