Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs

DOI10.1007/978-3-319-13524-3_24zbMATH Open1456.68066arXiv1407.1706OpenAlexW1678437030MaRDI QIDQ2946027

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: Very recently, Thomass'e, Trotignon and Vuskovic [WG 2014] 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})} c d o t n^{9}

. In this article we improve this running time to

2^{O (k^{2})} c d o t 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

2 p - 1

for

p g e q 3

, we speed up the running time to

2^{O (k c d o t k^{f r a c 1 p - 1})} c d o t n^{7}

. As

p

grows, this running time is asymptotically tight in terms of

k

, since we prove that for each integer

p g e q 3

, Weighted Independent Set cannot be solved in time

2^{o (k)} c d o t n^{O (1)}

in the class of

b u l l, C_{4}, l d o t s, C_{2 p - 1}

-free graphs unless the ETH fails.

Full work available at URL: https://arxiv.org/abs/1407.1706

zbMATH Keywords

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

Mathematics Subject Classification ID

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