Matrix Editing via Multivariate Lens[HBNI Th126]

DSpace/Manakin Repository

Matrix Editing via Multivariate Lens[HBNI Th126]

Show full item record

Title: Matrix Editing via Multivariate Lens[HBNI Th126]
Author: Syed Mohammad Meesum
Advisor: Saket Saurabh
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2017
Pages: 183p.
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.
URI: http://hdl.handle.net/123456789/413

Files in this item

Files Size Format View
HBNI Th126.pdf 560.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account