On the complexity of the identifiable subgraph problem, revisited

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.