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

DOI10.1007/s00453-015-0083-xzbMath1364.68233arXiv1310.6205OpenAlexW1617257399WikidataQ59889903 ScholiaQ59889903MaRDI QIDQ521799

Kristina Vušković, Nicolas Trotignon, Steé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

zbMATH Keywords

stable setkernelFPT algorithmbull-free graphTuring-kernel

Mathematics Subject Classification ID

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

Related Items (13)

Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , 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

Cites Work

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• A survey of the algorithmic aspects of modular decomposition
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Turing kernelization for finding long paths and cycles in restricted graph classes
• 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
• On problems without polynomial kernels
• Geometric algorithms and combinatorial optimization
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Recognizing Berge graphs
• On the density of families of sets
• A Completeness Theory for Polynomial (Turing) Kernelization
• Algorithms for Some H-Join Decompositions
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• On the Chromatic Number of Subgraphs of a Given Graph
• Algorithm Theory - SWAT 2004
• Independent Set in P₅-Free Graphs in Polynomial Time
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial Turing-kernel for weighted independent set in bull-free graphs