# 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

1. The rank of the sub matrix $M[A, V\setminus A] \leq k$

2. $|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. .

• Assume we take $A=\emptyset$ (or any $A$ smaller than $k$). Doesn't it satisfy the rank request? do you have further constraints on the size of $A$? – R B Nov 16 '15 at 17:53
• Sorry I forgot to mention it. size of $A$ is at least some constant fraction of $|V|$. i.e., $|A| > |V|/c$ for $c>1$. – Kumar Nov 16 '15 at 17:57

## 2 Answers

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.

This looks rather NP-hard (i.e., as it is obviously in NP, NP-complete) to me: Already the case $k=1$ looks hard (and interesting!). It asks for a large submatrix for which a vector $v$ exists such that all columns are either zero or $v$. The subgraph induced by $A$ thus has sets $B$ and $C$ such that (1) the nodes of $B$ have no outgoing edges (in $A$) and (2) all other nodes in $A-B$ have outgoing edges exactly to $C$. This looks like a "linear combination" of Clique and Independent set: $B=\emptyset, C=A$ yields a clique, $C=\emptyset,B=A$ and independent set. I do not know whether this has been studied before. (This is rather a comment, but it was too long...)