Publications in Scientific Journals:
H. Fleischner, E. Mujuni, D. Paulusma, S. Szeider:
"Covering graphs with few complete bipartite subgraphs";
Theoretical Computer Science,
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)
Created from the Publication Database of the Vienna University of Technology.