Fleischner, H. and Mujuni, E. and Paulusma, Daniel and Szeider, S. (2009) 'Covering graphs with few complete bipartite subgraphs.', Theoretical computer science., 410 (21-23). pp. 2045-2053.
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.
|Keywords:||Bicliques, Parameterized complexity, Covering and partitioning problems.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.tcs.2008.12.059|
|Record Created:||14 Oct 2009 10:20|
|Last Modified:||02 Apr 2013 16:53|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|