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

DOI10.1007/978-3-319-13524-3_24MaRDI QIDQ2946027zbMATH OpenOpenAlexFDO

Authors Henri Cray, Ignasi Sau

Publication date 15 September 2015

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

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

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)

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.

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

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)