Improved FPT algorithms for weighted independent set in bull-free graphs. (English) Zbl 1456.68066

Cray, Henri; Sau, Ignasi

Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8894, 282-293 (2014).

Summary: Very recently, S. Thomassé et al. [Lect. Notes Comput. Sci. 8747, 408–419 (2014; Zbl 1364.68232)] 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(k^5)} \cdot n^9\). In this article we improve this running time to \(2^{O(k^2)} \cdot 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 \geq 3\), we speed up the running time to \(2^{O(k \cdot k^{\frac{1}{p-1}})} \cdot n^7\). As \(p\) grows, this running time is asymptotically tight in terms of \(k\), since we prove that for each integer \(p \geq 3\), Weighted Independent Set cannot be solved in time \(2^{o(k)} \cdot n^{O(1)}\) in the class of \(\{\mathrm{bull},C_4,\ldots,C_{2p-1}\}\)-free graphs unless the ETH fails.
For the entire collection see [Zbl 1318.68014].

MSC:

68Q27	Parameterized complexity, tractability and kernelization
05C15	Coloring of graphs and hypergraphs
05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85	Graph algorithms (graph-theoretic aspects)
68W40	Analysis of algorithms

Keywords:

parameterized complexity; FPT algorithm; bull-free graphs; independent set; Turing-kernel

Citations:

Zbl 1364.68232