H. Fleischner
Covering graphs with few complete bipartite subgraphs
Fleischner, H.; Mujuni, E.; Paulusma, D.; Szeider, S.
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 |
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article