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 rRank Vertex Deletion, rRank Edge Deletion and rRank 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 rRank Vertex Deletion and rRank Editing are NP Complete for oriented graphs.
4. The problems rRank Vertex Deletion and rRank 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 2Minimum Volume Packing. 