Loading [MathJax]/jax/output/HTML-CSS/jax.js

Lito Goldmann ; Leon Kellerhals ; Tomohiro Koana - Structural Parameterizations of the Biclique-Free Vertex Deletion Problem

dmtcs:13018 - Discrete Mathematics & Theoretical Computer Science, November 15, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.13018
Structural Parameterizations of the Biclique-Free Vertex Deletion ProblemArticle

Authors: Lito Goldmann ; Leon Kellerhals ; Tomohiro Koana

    In this work, we study the Biclique-Free Vertex Deletion problem: Given a graph G and integers k and ij, 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 i2. In contrast, we find that it is W[1]-hard for the treedepth for any integer i1. Finally, we show that Biclique-Free Vertex Deletion has a polynomial kernel for every i1 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.


    Volume: vol. 26:3
    Section: Discrete Algorithms
    Published on: November 15, 2024
    Accepted on: August 30, 2024
    Submitted on: February 7, 2024
    Keywords: Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 175 times.
    This article's PDF has been downloaded 206 times.