Agarwal, Akanksha ; Saurabh, Saket ; Tale, Prafullkumar (2019) On the Parameterized Complexity of Contraction to Generalization of Trees Theory of Computing Systems, 63 (3). pp. 587-614. ISSN 1432-4350
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s00224-018-9892-z
Related URL: http://dx.doi.org/10.1007/s00224-018-9892-z
Abstract
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⊆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 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ℓ be the family of graphs such that each graph in Tℓ can be made into a tree by deleting at most ℓ edges. Thus, the problem we study is Tℓ-Contraction. We design an FPT algorithm for Tℓ-Contraction running in time O((2(√ℓ))O(k+ℓ)⋅nO(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ℓ-Contraction of size O([k(k+2ℓ)](⌈α/α−1⌉+1)).
Item Type: | Article |
---|---|
Source: | Copyright of this article belongs to Springer-Verlag. |
ID Code: | 123374 |
Deposited On: | 15 Sep 2021 11:01 |
Last Modified: | 15 Sep 2021 11:01 |
Repository Staff Only: item control page