On co-bicliques

Cornaz, Denis 

RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 295-304

Résumé

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\subseteq E$ is an independent of $G$ if there is a co-biclique $B$ such that $F\subseteq 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 time for any nonnegative cost vector $x\in {\mathbb{Q}}_{+}^E$. Based on this, we obtain a branch-and-cut algorithm for the maximum co-biclique problem which is, given a weight vector $w\in {\mathbb{Q}}_{+}^E$, to find a co-biclique $B$ of $G$ maximizing $w\left(B\right)={\sum }_{e\in B}{w}_e$.

Détail

DOI : 10.1051/ro:2007020

Classification : 05C15, 90C09
Keywords: co-bicyclique, signed graph, branch-and-cut