## Abstract

In this paper, we consider the minimum biclique cover and minimum biclique partition problems on bipartite graphs. In the minimum biclique cover problem, we are given an input bipartite graph G=(V,E), and our goal is to compute the minimum number of complete bipartite subgraphs that cover all edges of G. This problem, besides its correspondence to a well-studied notion of bipartite dimension in graph theory, has applications in many other research areas such as artificial intelligence, computer security, automata theory, and biology. Since it is NP-hard, past research has focused on approximation algorithms, fixed parameter tractability, and special graph classes that admit polynomial time exact algorithms. For the minimum biclique partition problem, we are interested in a biclique cover that covers each edge exactly once. We revisit the problems from approximation algorithms' perspectives and give nearly tight lower and upper bound results. We first show that both problems are NP-hard to approximate to within a factor of n ^{1-ε} (where n is the number of vertices in the input graph). Using a stronger complexity assumption, the hardness becomes, ω̄ (n)where ω̄(·)idhides lower order terms. Then we show that approximation factors of the form n/(logn) ^{γ} for some γ>0 can be obtained. Our hardness results have many consequences: (i) ω̄(n) hardnesses for computing the Boolean rank and non-negative integer rank of an n-by-n matrix (ii) hardness for minimizing the number of states in a deterministic finite automaton (DFA), given an n-state DFA as input, and (iii) ω̄ (√n)hardness for computing minimum NFA from a truth table of size n. These results settle some of the most basic problems in the area of regular language optimization.

Original language | English |
---|---|

Title of host publication | Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 235-246 |

Number of pages | 12 |

Volume | 8737 LNCS |

ISBN (Print) | 9783662447765 |

DOIs | |

Publication status | Published - 2014 |

MoE publication type | A4 Article in a conference publication |

Event | European Symposium on Algorithms - Wroclaw, Poland Duration: 8 Sep 2014 → 10 Sep 2014 Conference number: 22 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8737 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | European Symposium on Algorithms |
---|---|

Abbreviated title | ESA |

Country | Poland |

City | Wroclaw |

Period | 08/09/2014 → 10/09/2014 |