Paper Info
Title
The Biclique Partitioning Polytope
Abstract
Given a bipartite graph G = (V-1, V-2, E), a biclique of G is a complete bipartite subgraph of G, and a biclique partitioning of G is a set A subset of E such that the bipartite graph G' = (V-1, V-2, A) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = (V-1, V-2, E) with edge weights w(e) is an element of R for all e is an element of E (thus, negative weights are allowed), finding a biclique partitioning A subset of E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P-nm of the complete bipartite graph K-nm (i.e., P-nm is the convex hull of the incidence vectors of the biclique partitionings of K-nm). In this paper we develop such a polyhedral study and show that ladder, bellows, and grid inequalities induce facets of P-nm. Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.dam.2021.05.023
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
Biclique partitioning, Polyhedral combinatorics, Facet-inducing inequalities
Journal
301
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Gilberto Farias de Sousa Filho1134.07
Teobaldo Bulhões200.34
Lucídio dos Anjos Formiga Cabral3658.50
Luiz Satoru Ochi447434.62
Fábio Protti535746.14
Rian G. S. Pinheiro6314.72