Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908764143091712 |
|---|---|
| author | Krithika, R. Malu, V. K. Kutty Sharma, Roohani Tale, Prafullkumar |
| author_facet | Krithika, R. Malu, V. K. Kutty Sharma, Roohani Tale, Prafullkumar |
| contents | In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) under standard complexity-theoretic assumptions. We also give faster FPT algorithms for contraction to restricted bicliques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_10607 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction Krithika, R. Malu, V. K. Kutty Sharma, Roohani Tale, Prafullkumar Data Structures and Algorithms Computational Complexity F.2.2 In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) under standard complexity-theoretic assumptions. We also give faster FPT algorithms for contraction to restricted bicliques. |
| title | Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction |
| topic | Data Structures and Algorithms Computational Complexity F.2.2 |
| url | https://arxiv.org/abs/2307.10607 |