Classical and Approximate kernels for structural parameterizations of some graph parameters[HBNI Th139]

Abstract

In this thesis, we design some classical and lossy kernels for structural parameterizations of some Packing, Covering, and Connectivity problems. Additionally, we provide some hardness results. Cycle Packing in undirected graph asks whether a given graph has k vertex disjoint cycles. We provide two types of relaxations to the disjointness constraint. First one is a global relaxation, where we are asked to provide k cycles such that each vertex of the input graph can appear in at most t of them. In this case, we prove that the larger t grows, the more it is likely for this problem to have a polynomial kernel. The second one is a global relaxation, where we are asked to provide k cycles such that each pair of them share t vertices. In this case, we prove that the problem is NP-hard for t = 1, and provide polynomial kernel for t = 1, and polynomial compression for t ≥ 2. We consider classical kernels for Vertex Cover when paremeterized by deletion distance (k) to a graph of degree at most two. We provide a kernel with O(k 5 ) vertices using Expansion Lemma. We also consider when Vertex Cover is parameterized by deletion distance (k) to a disjoint union of d-vertex cliques. In this case, we prove that Vertex Cover has a kernel with O(k d ) vertices, and prove that a kernel with O(k d−ε ) bits cannot exist unless NP ⊆ coNP/poly. Additionally, we prove that Ver- tex Cover admits a time and size efficient polynomial sized approximate kernelization scheme (PSAKS) when parameterized by deletion distance to a graph in which Vertex Cover admits an EPTAS. We prove that Feedback Vertex Set is FPT, but has no polynomial kernel when parameterized the number of vertices having degree more than three. This answers a question asked in an earlier paper. Additionally, we provide a kernel with O(k 7 ) vertices when Feedback Vertex Set is parameterized by deletion distance (k) to pseudo-forest. We also consider an intermediate parameterization where consider deletion distance (k) to mock-d-forest as a parameter, and provide a kernel with O(k 3d+3 ) vertices. Finally, we prove that Feedback Vertex Set admits a time and size efficient PSAKS when parameterized by deletion distance (k) to a graph class in which Feedback Vertex Set admits an EPTAS. We prove that Connected Vertex Cover is NP-Complete in a graph that has one vertex whose deletion results in a (sub)cubic graph. This is somehow in contrast to the fact that Connected Vertex Cover is polynomial time solvable in (sub)cubic graphs. We also provide a branching algorithm with running time O(4 k n O(1) ) for Connected Vertex Cover when parameterized by the size (k) of a cluster vertex deletion set. Finally we provide time efficient PSAKS for Connected Vertex Cover when parameterized by deletion distance (k) to class of bounded diameter graphs, bounded treewidth graphs, and chordal graphs.