Systematized Approaches to the Complexity of Subgraph Problems

J. Inform. Processing 13, 442-448, 1990This is a survey on complexity issues of subgraph problems proved in a systematic way. We deal with vertex-deletion and edge-deletion problems which can be viewed as subgraph problems. General NP-completeness theorems are presernted for these problems. We also present a systematized result which shoaws polynomial time algorithms for these problems restricted to series-parallel graphs. Another problem we consider in this paper is the lelxicographically first maximal subgraph problems which appear in connection with parallel complexity theory