New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth

Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon

We study the tractability of the maximum independent set problem from the viewpoint of graph width parameters, with the goal of defining a width parameter that is as general as pos…