The Biclique Cover Problem and the Modified Galois Lattice

Hideaki OTSUKI  Tomio HIRATA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.3   pp.497-502
Publication Date: 2015/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014FCP0019
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
biqlique cover,  Galois lattice,  domino-free,  

Full Text: PDF(417.1KB)>>
Buy this Article




Summary: 
The minimum biclique cover problem is known to be NP-hard for general bipartite graphs. It can be solved in polynomial time for C4-free bipartite graphs, bipartite distance hereditary graphs and bipartite domino-free graphs. In this paper, we define the modified Galois lattice Gm(B) for a bipartite graph B and introduce the redundant parameter R(B). We show that R(B)=0 if and only if B is domino-free. Furthermore, for an input graph such that R(B)=1, we show that the minimum biclique cover problem can be solved in polynomial time.