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.
References
- 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
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.