Gartland and Lokshtanov's induced-minor-free graph algorithm conjecture

Less than 1 year old · traced to

Let HH be a planar graph. For a fixed integer rr and fixed CMSO2_2 formula ψ\psi, (tw⁡≤r,ψ)(\operatorname{tw} \leq r,\psi)-MWIS is the problem of finding a maximum-weight vertex set inducing a graph of treewidth at most rr that satisfies ψ\psi, or reporting that no such set exists. Also, lcol⁡(3)\operatorname{lcol}(3) denotes the relevant 3-color list-colouring problem. A graph is HH-induced-minor-free if it does not contain HH as an induced minor.

Gartland and Lokshtanov's conjecture. For every fixed rr and CMSO2_2 formula ψ\psi, (tw⁡≤r,ψ)(\operatorname{tw} \leq r,\psi)-MWIS and lcol⁡(3)\operatorname{lcol}(3) can be solved in polynomial time in HH-induced-minor-free graphs.

This conjecture extends polynomial-time algorithmic results from graphs excluding linear forests to induced-minor-free graphs for planar forbidden graphs. Its status is not established in the supplied text.

References

Primary source

Amir Nikabadi and Paweł Rzążewski, “Induced packing treewidth”, arXiv:2607.07595 (2026).

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.