On the complexity of the identifiable subgraph problem, revisited

摘要

A bipartite graph G = (L, R; E) with at least one edge is said to be identifiable if for every vertex v is an element of L, the subgraph induced by its non-neighbors has a matching of cardinality |L| - 1. An l-subgraph of G is an induced subgraph of G obtained by deleting from it some vertices in L together with all their neighbors. The IDENTIFIABLE SUBGRAPH problem is the problem of determining whether a given bipartite graph contains an identifiable l-subgraph. The MIN- and MAX-IDENTIFIABLE SUBGRAPH problems are defined similarly, taking into account a given upper, resp. lower bound on the number of vertices from L in an identifiable l-subgraph.