Systematized Approaches to the Complexity of Subgraph Problems

This is a survey of issues related to the complexity of subgraph problems proved in a systematic way. It deals with vertex deletion and edge deletion problems that can be viewed as subgraph problems. General NP-completeness theorems for these problems are presented, as well as a systematized result that shows polynomial time algorithms for these problems restricted to series-parallel graphs. Another problem considered in this paper is the lexicographically first maximal subgraph problems that appear in connection with parallel complexity theory.