Edge cover by bipartite subgraphs
Marie-Christine Plateau, Leo Liberti, Laurent Alfandari · 2007
k≤m Ek and m is minimum. Two related and reasonably well-studied problems are the Minimum Biclique Cover (MBC), where Hk are required to be bicliques (i.e. complete bipartite subgraphs) [4,3,2,1] and the Minimum Cut Cover (MCC), where Hk are cutsets, namely not required to be connected. Both problems are NP-hard. To the best of our knowledge, whether the MBGC is NP-hard or not is currently unknown. Let G = (V,E) be an undirected graph. For v ∈ V , we denote by δ(v) the set of vertices u such that {v, u} ∈ E, and by δ(v) the set of edges e ∈ E adjacent to v. With respect to a set of edges F ⊂ E, δF (v) is the set of vertices adjacent to v using edges in F , and δF (v) is the set of edges e ∈ F adjacent to v.