Node-Deletion Problems on Bipartite Graphs 论文

详细信息

发表期刊/会议

SIAM Journal on Computing

发表日期

1981-05-01

发表年份

1981

摘要

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 $\pi $. 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 if M is a class of 0,1 matrices which is closed under permutation and deletion of rows and columns, then finding the largest submatrix in M of a matrix is polynomial if the matrices of M have bounded rank and NP-complete otherwise.