{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:52:27Z","timestamp":1753894347725,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Discrete Algorithms","license":[{"start":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T00:00:00Z","timestamp":1731628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this work, we study the Biclique-Free Vertex Deletion problem: Given a\ngraph $G$ and integers $k$ and $i \\le j$, find a set of at most $k$ vertices\nthat intersects every (not necessarily induced) biclique $K_{i, j}$ in $G$.\nThis is a natural generalization of the Bounded-Degree Deletion problem,\nwherein one asks whether there is a set of at most $k$ vertices whose deletion\nresults in a graph of a given maximum degree $r$. The two problems coincide\nwhen $i = 1$ and $j = r + 1$. We show that Biclique-Free Vertex Deletion is\nfixed-parameter tractable with respect to $k + d$ for the degeneracy $d$ by\ndeveloping a $2^{O(d k^2)} \\cdot n^{O(1)}$-time algorithm. We also show that it\ncan be solved in $2^{O(f k)} \\cdot n^{O(1)}$ time for the feedback vertex\nnumber $f$ when $i \\ge 2$. In contrast, we find that it is W[1]-hard for the\ntreedepth for any integer $i \\ge 1$. Finally, we show that Biclique-Free Vertex\nDeletion has a polynomial kernel for every $i \\ge 1$ when parameterized by the\nfeedback edge number. Previously, for this parameter, its fixed-parameter\ntractability for $i = 1$ was known (Betzler et al., 2012) but the existence of\npolynomial kernel was open.<\/jats:p>","DOI":"10.46298\/dmtcs.13018","type":"journal-article","created":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T20:20:09Z","timestamp":1731702009000},"source":"Crossref","is-referenced-by-count":0,"title":["Structural Parameterizations of the Biclique-Free Vertex Deletion Problem"],"prefix":"10.46298","volume":"vol. 26:3","author":[{"given":"Lito","family":"Goldmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leon","family":"Kellerhals","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"Koana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,11,15]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/14245\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/14245\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T20:20:09Z","timestamp":1731702009000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dmtcs.episciences.org\/13018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,15]]},"references-count":0,"journal-issue":{"issue":"Discrete Algorithms","published-online":{"date-parts":[[2024,11,15]]}},"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.46298\/dmtcs.13018","relation":{"has-preprint":[{"id-type":"arxiv","id":"2308.00501v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2308.00501v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2308.00501","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2308.00501","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2024,11,15]]},"article-number":"13018"}}