Summary
The paper shows that finding the largest group of points in a network with no connections between them (called a maximum independent set) remains a very hard problem even in networks that exclude a certain kind of planar substructure. Specifically, the authors prove this is true even when the network does not have any induced minors that look like a 5 by 5 grid. This result disproves earlier guesses that the problem would become easier in such restricted networks.
What this means in practice
- •For algorithm designers: Avoid assuming Max Independent Set is easier in graphs excluding certain planar induced minors, guiding search for tractable graph classes.
- •For network analysts: Recognize that large independent group identification remains computationally difficult even when networks exclude complex planar patterns, affecting network design analysis.
A theory result. No direct application yet.
Authors
Édouard Bonnet, Yeonsu Chang
Abstract
We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.