Approximating minimum biclique cover and partition

Sandy Heydrich

MPI, Host: Rob van Stee

26th February 2015 (Thursday), 10:00 in ADR LG26


We consider the problem of covering (or partitioning) the edges of a bipartite graph with complete bipartite graphs (bicliques). Both problems are NP-hard and polynomial time algorithms for several special graph classes were found. However, no non-trivial approximation algorithms (below an approximation factor of n) for the problem on general graphs were known so far. The best known inapproximability result by Gruber and Holzer states that it is NP-hard to approximate both problems within n^{1/3-epsilon} or m^{1/5-epsilon} for all epsilon>0. We improve this to n^{1-epsilon} and m^{1/2-epsilon} via a reduction from graph coloring. Moreover, we give the first non-trivial approximation algorithms, achieving an approximation factor of n/sqrt(log n) for biclique cover and n/log log n for biclique partition.

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc
E: MSc

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom


DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.