A set of problems which has attracted considerable interest recently is the set of node-deletion problems. The general node-deletion problem can be stated as follows: Given a graph, find the minimum number of nodes whose deletion results in a subgraph satisfying property r. In (LY) this problem was shown to be NP-complete for a large class of properties (the class of properties that are hereditary on induced subgraphs) using a small number of reduction schemes from the node cover problem. Since the node cover problem becomes polynomial on bipartite graphs, it might be hoped that this is the case with other node-deletion problems too. In this paper we characterize those properties for which the bipartite restriction of the node-deletion problem is polynomial and those for which it remains NP-complete. Similar results follow for analogous problems on other structures such as families of sets, hypergraphs and 0,1 matrices. For example, in the case of matrices, our result states that ifM is a class of 0,1 matrices which is closed under permutation and deletion of rows and columns, then finding the largest submatrix inM of a matrix is polynomial if the matrices ofM have bounded rank and NP-complete otherwise. 1. Introduction. A common approach when faced with an NP-complete problem (C), (K), (GJ) is to restrict its input domain with the hope that the problem may become solvable in polynomial time under the restriction. In fact it turns out that sometimes this is the case" for example, the node-cover problem, NP-complete on general graphs (K), can be solved efficiently when restricted to bipartite graphs. (This follows from K6nig's theorem that the node covering number of a bipartite graph equals the number of edges in a maximum matching, and moreover a minimum node cover can be found efficiently from a maximum matching when the graph is bipartite--see, for example, (La).) In other cases, however, the node cover problem continues to be NP-complete under restriction; for example the node cover problem on planar graphs (GJS). Much work has been done recently (KD), (LY), (LDL) on a class of problems, called the node-deletion (or maximum subgraph) problems. The general node-deletion problem can be stated as follows: Given a graph (or digraph) G, find a set of nodes of minimum cardinality, whose deletion results in a graph or digraph satisfying a property r. Several of the known NP-complete problems, such as the node cover, the max clique, the feedback-node set (K), as well as some polynomial problems, such as the connectivity of a graph (E), IT), can be formulated in an obvious way as node-deletion problems, by specifying appropriately the property r.