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. We show that the IDENTIFIABLE SUBGRAPH and MAX-IDENTIFIABLE SUBGRAPH problems are polynomially solvable, thereby answering the question about the complexity of these two problems posed by Fritzilas et al. in 2013. We also complement a known APX-hardness result for the MIN-IDENTIFIABLE SUBGRAPH problem by showing that two parameterized variants of the problem are W[1]-hard. (C) 2017 Elsevier B.V. All rights reserved.