Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that The rank of the sub matrix $M[A, V\setminus A] \leq k$ $|A|\geq |V|/c$, $|V \setminus A|\geq |V|/c$, for some constant $c>1$.where  $M[A, V\setminus A]$ denote the submatrix $(m_{ij};i \in A, j \in V \setminus A)$.Note: Assume that existence of such a subset $A$ is guaranteed. .  
Submatrix of small rank
graph theory;matrices