Skip to main content

Research Repository

Advanced Search

Covering graphs with few complete bipartite subgraphs

Fleischner, H.; Mujuni, E.; Paulusma, D.; Szeider, S.

Authors

H. Fleischner

E. Mujuni

S. Szeider



Abstract

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them 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 two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P=NP.

Citation

Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059

Journal Article Type Article
Publication Date May 1, 2009
Deposit Date Oct 14, 2009
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 410
Issue 21-23
Pages 2045-2053
DOI https://doi.org/10.1016/j.tcs.2008.12.059
Keywords Bicliques, Parameterized complexity, Covering and partitioning problems.
Public URL https://durham-repository.worktribe.com/output/1547640