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
Type
Article accepté pour publication ou publiéDate
2007Journal name
SIAM Journal on Discrete MathematicsVolume
21Number
3Publisher
SIAM
Pages
662-675
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
Separation algorithm; Minimal dependent set; Edge weight; induced bipartite subgraphRelated items
Showing items related by title and author.
-
Fouilhoux, Pierre; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
-
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004) 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é
-
Mahjoub, Ali Ridha; Cornaz, Denis (2009) Communication / Conférence