Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910662478790656 |
|---|---|
| author | Lafond, Manuel |
| author_facet | Lafond, Manuel |
| contents | Given a bipartite graph $G$, the \textsc{Bicluster Editing} problem asks for the minimum number of edges to insert or delete in $G$ so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter $k$, which is the number of allowed modified edges. We first show that one can obtain a kernel with $4.5k$ vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time $O^*(2.581^k)$. Our algorithm has the advantage of being conceptually simple and should be easy to implement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_13123 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing Lafond, Manuel Data Structures and Algorithms Given a bipartite graph $G$, the \textsc{Bicluster Editing} problem asks for the minimum number of edges to insert or delete in $G$ so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter $k$, which is the number of allowed modified edges. We first show that one can obtain a kernel with $4.5k$ vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time $O^*(2.581^k)$. Our algorithm has the advantage of being conceptually simple and should be easy to implement. |
| title | Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.13123 |