Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.

Given graph and set of color lists I'd like to delete a small number of nodes to break a large number of frustrated cycles.

Is anything known about this problem, especially from algorithmic point of view?

Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.

Given graph and set of color lists I'd like to delete a small number of vertices to break a large number of frustrated cycles.

Is anything known about this problem, especially from algorithmic point of view?