A complexity framework for forbidden subgraphs

Abstract

A common direction in algorithmic graph theory is to investigate the complexity of hard problems restricted to specific classes of graphs. This raises the question of whether large sets of such problems can be explained by common problem conditions. For a set of graphs H, the class of H-subgraph-free graphs is the class of all graphs not containing any graph from H as a subgraph. We present a framework to classify the complexity of certain problems on H-subgraph-free graph classes. In particular,  we give an algorithmic meta-theorem classifying the complexity of problems satisfying a framework of three conditions.