Alladi Ramakrishnan Hall

Matrix Editing via Multivariate Lens

Syed Mohammad Meesum

In the thesis we consider problems having the following template for
some fixed integer r --

Input: A matrix M over some field F and an integer k.
Parameter: k
Question: Can we alter k entries in M such that rank becomes at most r ?

1) We first consider the special cases when the matrix M is either a
symmetric matrix or an antisymmetric 0-1 matrix. These choices of M
correspond to the adjacency matrices of undirected graph and oriented
graphs respectively. The question which we ask there is, whether it is
possible to delete/edit at most k edges in a graph such that the rank of
the adjacency matrix becomes at most r.
We also consider a similar question when we are allowed to delete vertices.
We proved that these problems are NP-complete, FPT wrt k and admit
polynomial kernels.

2) Generally, we studied the question for an arbitrary matrix over a given
field F. In this general form the problem corresponds to the decision
version of the classical matrix rigidity problem. We considered the
parameter to be r+k. We showed that this problem is FPT wrt r+k. We also
show that this problem is W[1] hard with respect to k.

In the talk I will also discuss, among other things, about the various
details of the more general problem (2) and will present an FPT algorithm
for solving it.In the thesis we consider problems having the following template for
some fixed integer r --

Input: A matrix M over some field F and an integer k.
Parameter: k
Question: Can we alter k entries in M such that rank becomes at most r ?

1) We first consider the special cases when the matrix M is either a
symmetric matrix or an antisymmetric 0-1 matrix. These choices of M
correspond to the adjacency matrices of undirected graph and oriented
graphs respectively. The question which we ask there is, whether it is
possible to delete/edit at most k edges in a graph such that the rank of
the adjacency matrix becomes at most r.
We also consider a similar question when we are allowed to delete vertices.
We proved that these problems are NP-complete, FPT wrt k and admit
polynomial kernels.

2) Generally, we studied the question for an arbitrary matrix over a given
field F. In this general form the problem corresponds to the decision
version of the classical matrix rigidity problem. We considered the
parameter to be r+k. We showed that this problem is FPT wrt r+k. We also
show that this problem is W[1] hard with respect to k.

In the talk I will also discuss, among other things, about the various
details of the more general problem (2) and will present an FPT algorithm
for solving it.