2026-07-20T11:02:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8544 2024-03-06T10:41:28Z ddc:004 open_access

On the Parameterized Complexity of Contraction to Generalization of Trees Agrawal, Akanksha Saurabh, Saket Tale, Prafullkumar Graph Contraction Fixed Parameter Tractability Graph Algorithms Generalization of Trees For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S \subseteq E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al.[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied \cal F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let T_\ell be the family of graphs such that each graph in T_\ell can be made into a tree by deleting at most \ell edges. Thus, the problem we study is T_\ell-Contraction. We design an FPT algorithm for T_\ell-Contraction running in time O((\ncol)^{O(k + \ell)} * n^{O(1)}). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T_\ell-Contraction of size O([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha-1}\rceil + 1)}}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Saket Saurabh and Prafullkumar Tale 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.1 urn:nbn:de:0030-drops-85446 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.1 eng https://creativecommons.org/licenses/by/3.0/legalcode