Nearly tight approximability results for minimum biclique cover and partition

Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, Andreas Karrenbauer

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

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 languageEnglish
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages235-246
Number of pages12
Volume8737 LNCS
ISBN (Print)9783662447765
DOIs
Publication statusPublished - 2014
MoE publication typeA4 Article in a conference publication
EventEuropean Symposium on Algorithms - Wroclaw, Poland
Duration: 8 Sep 201410 Sep 2014
Conference number: 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceEuropean Symposium on Algorithms
Abbreviated titleESA
CountryPoland
CityWroclaw
Period08/09/201410/09/2014

Fingerprint Dive into the research topics of 'Nearly tight approximability results for minimum biclique cover and partition'. Together they form a unique fingerprint.

Cite this