Parameterized complexity of finding subgraphs with hereditary
properties on hereditary graph classes.
D. Eppstein,
E. Havvaei, and
S. Gupta.
arXiv:2101.09918.
Proc. 23rd International Symposium on Fundamentals of Computation
Theory, 2021.
Springer, Lecture
Notes in Comp. Sci. 12867 (2021), pp. 217–229, doi:10.1007/978-3-030-86593-1_15.
We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).
(Blog post: Which induced-subgraph problems are easy, and which are hard?)