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.
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
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search