Title: Covering Graphs with Few Complete Bipartite Subgraphs
Abstract: Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the given graph can be covered with at most k bicliques (complete bipartite subgraphs); the biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques. Both problems are known to be NP-complete even if the given graph is bipartite. In this paper we investigate these two problems in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first problem is fixed-parameter tractable, while the second one is not fixed-parameter tractable unless P=NP.
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot