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

"Covering graphs with few complete bipartite subgraphs";

Theoretical Computer Science,410(2009), 21-23; 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 NPcomplete 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 fixedparameter tractable, while the latter two problems are not fixed-parameter tractable unless P D NP.

http://dx.doi.org/10.1016/j.tcs.2008.12.059

Created from the Publication Database of the Vienna University of Technology.