Polynomial-time Maximum Independent Set in graphs with bounded induced cycle packing

Let kk be a positive integer, and let an Ok\mathcal{O}_k-free graph be a graph containing no induced subgraph from the family Ok\mathcal{O}_k.

Polynomial-time independent-set conjecture. \textscMaximumIndependentSet\textsc{Maximum Independent Set} is solvable in polynomial time in Ok\mathcal{O}_k-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 Ok\mathcal{O}_k-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

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.