[Back]


Publications in Scientific Journals:

H. Fleischner, E. Mujuni, D. Paulusma, S. Szeider:
"Covering graphs with few complete bipartite subgraphs";
Theoretical Computer Science, 410 (2009), 21-23; 2045 - 2053.



English 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 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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.tcs.2008.12.059


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