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

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

Authors: Henri Cray, Ignasi Sau 

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)}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 $pgeq3$, we speed up the running time to $2^{O(kcdot{k}^{frac1p-1})}cdot{n}^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $pgeq3$, Weighted Independent Set cannot be solved in time $2^{o(k)}cdot{n}^{O(1)}$ in the class of $bull,C_4,ldots,C_{2p-1}$-free graphs unless the ETH fails.

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

Recommendations

• Improved FPT algorithms for weighted independent set in bull-free graphs
• An improved FPT algorithm for independent feedback vertex set
• An improved FPT algorithm for independent feedback vertex set
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Efficient computation of tolerances in the weighted independent set problem for some classes of graphs
• scientific article; zbMATH DE number 4064507
• An algorithm for finding a maximum weighted independent set in an arbitrary graph

zbMATH Keywords

FPT algorithmindependent setparameterized complexityTuring-kernelbull-free graphs

Mathematics Subject Classification ID

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

Cited In (3)

• Improved FPT algorithms for weighted independent set in bull-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs

This page was built for publication: Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946027)