Submatrix of small rank 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&gt;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. .
Essentially, you are asking for a graph "separator" of a certain kind, and while this doesn't answer your question directly, your question is likely related to the notion of the rankwidth of a graph. You can find more information in this paper, this paper or especially this paper

Note that the notion of rankwidth uses "rank over the finite field $\mathbb{F}_2$", which may or may not be the field you were asking about.