A polynomial Turing-kernel for weighted independent set in bull-free graphs

DOI10.1007/S00453-015-0083-XMaRDI QIDQ521799zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Trotignon, Kristina Vušković, Stéphan Thomassé

Publication date 12 April 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.6205, http://eprints.whiterose.ac.uk/89781/1/bullFreeFptFinal.pdf

zbMATH Keywords

kernelFPT algorithmstable setbull-free graphTuring-kernel

Mathematics Subject Classification ID

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

Abstract: The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size $k$, when $k$ is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size $k$. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size $O(k^5)$. As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

Recommendations

• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• Improved FPT algorithms for weighted independent set in bull-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A graph polynomial for independent sets of bipartite graphs
• A graph polynomial for independent sets of bipartite graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Algorithmic results of independent \(k\)-domination on weighted graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs

Cites work

• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A completeness theory for polynomial (Turing) kernelization
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A survey of the algorithmic aspects of modular decomposition
• Algorithm Theory - SWAT 2004
• Algorithms for some \(H\)-join decompositions
• Geometric algorithms and combinatorial optimization
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Independent set in \(P_5\)-free graphs in polynomial time
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• On problems without polynomial kernels
• On the Chromatic Number of Subgraphs of a Given Graph
• On the density of families of sets
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Recognizing Berge graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strong perfect graph theorem
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• The structure of bull-free graphs II and III -- a summary
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(16)

• Improved FPT algorithms for weighted independent set in bull-free graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Polynomial Turing compressions for some graph problems parameterized by modular-width
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Alternative parameterizations of \textsc{Metric Dimension}
• Parameterized complexity of independent set in H-free graphs
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• On some FPT problems without polynomial Turing compressions
• Parameterized complexity of independent set in \(H\)-free graphs
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

This page was built for publication: A polynomial Turing-kernel 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 Q521799)