Abstract
In this work, we study the Biclique-Free Vertex Deletion problem: Given a graph G and integers k and i ≤ j, find a set of at most k vertices that intersects every (not necessarily induced) biclique Ki,j in G. This is a natural generalization of the Bounded-Degree Deletion problem, wherein one asks whether there is a set of at most k vertices whose deletion results in a graph of a given maximum degree r. The two problems coincide when i = 1 and j = r+1. We show that Biclique-Free Vertex Deletion is fixed-parameter tractable with respect to k + d for the degeneracy d by developing a 2O(dk2) · nO(1)-time algorithm. We also show that it can be solved in 2O(fk) · nO(1) time for the feedback vertex number f when i ≥ 2. In contrast, we find that it is W[1]-hard for the treedepth for any integer i ≥ 1. Finally, we show that Biclique-Free Vertex Deletion has a polynomial kernel for every i ≥ 1 when parameterized by the feedback edge number. Previously, for this parameter, its fixed-parameter tractability for i = 1 was known (Betzler et al., 2012) but the existence of polynomial kernel was open.
Original language | English |
---|---|
Article number | #4 |
Journal | Discrete Mathematics and Theoretical Computer Science |
Volume | 26 |
Issue number | 3 |
DOIs | |
Publication status | Published - 15 Nov 2024 |
Bibliographical note
Publisher Copyright:© 2024 by the author(s)
Keywords
- Biclique-free graphs
- Fixed-parameter tractability
- Kernelization
- Structural graph parameterizations