On co-bicliques
A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G. (A co-biclique is the complement of a biclique.) A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial...