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

DOI10.1007/S00453-015-0083-XzbMATH Open1364.68233arXiv1310.6205OpenAlexW1617257399WikidataQ59889903 ScholiaQ59889903MaRDI QIDQ521799FDOQ521799

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

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• On the density of families of sets
• Geometric algorithms and combinatorial optimization
• Title not available (Why is that?)
• On problems without polynomial kernels
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• A New Algorithm for Generating All the Maximal Independent Sets
• Independent set in \(P_5\)-free graphs in polynomial time
• 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
• The strong perfect graph theorem
• Recognizing Berge graphs
• Title not available (Why is that?)
• A completeness theory for polynomial (Turing) kernelization
• On the Chromatic Number of Subgraphs of a Given Graph
• A survey of the algorithmic aspects of modular decomposition
• Algorithm Theory - SWAT 2004
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• 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
• Algorithms for some \(H\)-join decompositions
• Title not available (Why is that?)
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Improved FPT algorithms for weighted independent set in bull-free graphs

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
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• 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}
• 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
• Parameterized complexity of independent set in H-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)