Polynomial-time Maximum Independent Set in graphs with bounded induced cycle packing
Polynomial-time Maximum Independent Set in graphs with bounded induced cycle packing
Let be a positive integer, and let an -free graph be a graph containing no induced subgraph from the family .
Polynomial-time independent-set conjecture. is solvable in polynomial time in -free graphs.
The conjecture would extend the known polynomial-time result for graphs of bounded odd cycle packing. The paper proves it in the sparse case and gives a quasi-polynomial-time algorithm in general, but does not establish polynomial-time solvability for arbitrary -free graphs.
Sources & referencesView supporting material
Primary source
Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé and Alexandra Wesolek, “Sparse graphs with bounded induced cycle packing number have logarithmic treewidth”, arXiv:2206.00594 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.