2017/08/02 by Akanksha Agrawal, Saket Saurabh, Agrawal, Akanksha +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1708.00622
openalex publication_date 2017/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a family of graphs cal F, the \F-Contraction problem takes\nas an input a graph G and an integer k, and the goal is to decide if there\nexists S \⊆ E(G) of size at most k such that G/S belongs to cal\nF. Here, G/S is the graph obtained from G by contracting all the edges in\nS. Heggernes et al.~[Algorithmica (2014)] were the first to study edge\ncontraction problems in the realm of Parameterized Complexity. They studied\n cal F-Contraction when cal F is a simple family of graphs such as trees\nand paths. In this paper, we study the \F-Contraction problem, where\n cal F generalizes the family of trees. In particular, we define this\ngeneralization in a "parameterized way". Let mathbbT_\ℓ be the family of\ngraphs such that each graph in mathbbT_\ℓ can be made into a tree by\ndeleting at most \ℓ edges. Thus, the problem we study is\n mathbbT_\ℓ-Contraction. We design an FPT algorithm for\n mathbbT_\ℓ-Contraction running in time\n\O((2\√(\ℓ))\O(k + \ℓ) \⋅ n\O(1)).\nFurthermore, we show that the problem does not admit a polynomial kernel when\nparameterized by k. Inspired by the negative result for the kernelization, we\ndesign a lossy kernel for mathbbT_\ℓ-Contraction of size \n\O([k(k + 2\ℓ)] ^( lceil \(\α)/(\α-1) rceil + 1)).\n