Matrix Editing via Multivariate Lens[HBNI Th126]

Abstract

In this thesis we design algorithms for the matrix rigidity problem and its variants and study their hardness in the framework of parameterized complexity. The rigidity of a matrix is a classical concept in Computational Complexity Theory, but their parameterized complexity is relatively unexplored. The thesis also studies the problem of above guarantee compression of the classical vertex cover problem above maximum matching using the notion of matroids. We also initiate the study of Volume Packing and Strip Packing problems in the framework of parameterized complexity. In particular we obtain the following results.

1. The problems r-Rank Vertex Deletion, r-Rank Edge Deletion and r-Rank Editing are NP Complete for undirected graphs. 2. All the problems mentioned above admit a polynomial kernel and are FPT parameterized by number of edits for undirected graphs. 3. The problems r-Rank Vertex Deletion and r-Rank Editing are NP Complete for oriented graphs. 4. The problems r-Rank Vertex Deletion and r-Rank Editing for oriented graphs admit a polynomial kernel and are FPT parameterized by the number of edits. 5. The problems Real Matrix Rigidity and FF Matrix Rigidity are FPT parameterized by target rank and the number of edits. 6. The problems Real Matrix Rigidity and FF Matrix Rigidity are W[1] Hard with respect to number of edits. 7. We provide an alternate and conceptually simpler randomized polynomial size compression for Vertex Cover Above LP. 8. A single exponential FPT algorithm for 2-Minimum Volume Packing.