The maximum induced bipartite subgraph problem with edge weights
Cornaz, Denis; Mahjoub, Ali Ridha (2007), The maximum induced bipartite subgraph problem with edge weights, SIAM Journal on Discrete Mathematics, 21, 3, p. 662-675. http://dx.doi.org/10.1137/060650015
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Discrete Mathematics
MetadataShow full item record
Abstract (EN)Given a graph $G=(V,E)$ with nonnegative weights on the edges, the maximum induced bipartite subgraph problem (MIBSP) is to find a maximum weight bipartite subgraph $(W,E[W])$ of $G$. Here $E[W]$ is the edge set induced by $W$. An edge subset $F\subseteq E$ is called independent if there is an induced bipartite subgraph of $G$ whose edge set contains $F$. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets, that is, the dependent sets that are not contained in any other dependent set. Using this, we give an integer linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. Moreover, we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph, and can then be solved in polynomial time. This yields a polynomial-time separation algorithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem. We also discuss some polyhedral consequences.
Subjects / KeywordsSeparation algorithm; Minimal dependent set; Edge weight; induced bipartite subgraph
Showing items related by title and author.
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié