On the complexity of the identifiable subgraph problem

A bipartite graph G=(L,R;E)G=(L,R;E) with at least one edge is said to be identifiable   if for every vertex v∈Lv∈L, the subgraph induced by its non-neighbors has a matching of cardinality |L|−1|L|−1. This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications. An ℓℓ-subgraph   of a bipartite graph G=(L,R;E)G=(L,R;E) is an induced subgraph of GG obtained by deleting from it some vertices in LL together with all their neighbors. The Identifiable Subgraph problem is the problem of determining whether a given bipartite graph G=(L,R;E)G=(L,R;E) contains an identifiable ℓℓ-subgraph. While the problem of finding a smallest   set J⊆LJ⊆L that induces an identifiable ℓℓ-subgraph of GG is NP-hard and also APX-hard, the complexity of the identifiable subgraph problem is still open.In this paper, we introduce and study the kk-bounded Identifiable Subgraph problem. This is the variant of the Identifiable Subgraph problem in which the input bipartite graphs G=(L,R;E)G=(L,R;E) are restricted to have the maximum degree of vertices in RR bounded by kk. We show that for k≥3k≥3, the kk-bounded Identifiable Subgraph problem is as hard as the general case, while it becomes solvable in linear time for k≤2k≤2. Our proof is based on the notion of strongly cyclic graphs  , that is, multigraphs with at least one edge such that for every vertex vv, no connected component of the graph obtained by deleting vv is a tree. We show that a bipartite graph G=(L,R;E)G=(L,R;E) with maximum degree of vertices in RR bounded by 22 is a no instance to the Identifiable Subgraph problem if and only if a multigraph naturally associated to it does not contain any strongly cyclic subgraph, and characterize such graphs in terms of finitely many minimal forbidden topological minors.