<p>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 <em>rankwidth</em> of a graph. You can find more information in <a href="http://mathsci.kaist.ac.kr/~sangil/pdf/2008exp.pdf" rel="nofollow">this paper</a>, <a href="http://arxiv.org/abs/1503.00190" rel="nofollow">this paper</a> or <a href="http://mathsci.kaist.ac.kr/~sangil/pdf/2007partition-esa.pdf" rel="nofollow">especially this paper</a></p>

<p>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.</p>

CC BY-SA 3.0
2015-11-17T06:55:48.847Z
2015-11-17T06:55:48.847Z
Joe Bebel
<p>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...)</p>

CC BY-SA 3.0
2015-11-23T16:26:46.383Z
2015-11-23T16:26:46.383Z
Thomas S
<p>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 </p>

<ol>
<li><p>The rank of the sub matrix $M[A, V\setminus A] \leq k$ </p></li>
<li><p>$|A|\geq |V|/c$, $|V \setminus A|\geq |V|/c$, for some constant $c&gt;1$.</p></li>
</ol>

<p>where  $M[A, V\setminus A]$ denote the submatrix $(m_{ij};i \in A, j \in V \setminus A)$.</p>

<p>Note: Assume that existence of such a subset $A$ is guaranteed. .  </p>

CC BY-SA 3.0
2015-11-16T17:53:23.007Z
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
CC BY-SA 3.0
2015-11-16T17:57:51.807Z
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
CC BY-SA 4.0
2020-02-25T11:51:00.703Z
Is $k$ a constant? Is a running time of $O(n^{f(k)})$ allowed?
SamiD
CC BY-SA 4.0
2020-02-25T12:13:23.980Z
Even for $k=0$ you are looking for a submatrix not containing any diagonal elements that consists of all zeros (because the rank of the submatrix has to be zero). Thus in the complement of the graph you are searching for a bipartite clique of linear size -- which is $\mathsf{NP}$-hard, I presume. If you replace $n/c$ by $K$ then there is an obvious $n^{K}$ algorithm Just guess the at most $k\times k$ full-rank matrix and a disjoint $(K-k)\times (K-k)$ matrix of rank $0$ making sure that you never guess the same row and column in either guess.
SamiD
CC BY-SA 4.0
2020-02-27T07:11:16.877Z
Ah! I see now taht this is already an answer by @ThomasS
SamiD
<graph-theory><matrices>
Submatrix of small rank
Kumar
# Submatrix of small rank

(Asked by: username_0 on 2015-11-16)

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

**Tags:** graph-theory, matrices
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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$.  
> **username_2**: Is $k$ a constant? Is a running time of $O(n^{f(k)})$ allowed?  
> **username_2**: Even for $k=0$ you are looking for a submatrix not containing any diagonal elements that consists of all zeros (because the rank of the submatrix has to be zero). Thus in the complement of the graph you are searching for a bipartite clique of linear size -- which is $\mathsf{NP}$-hard, I presume. If you replace $n/c$ by $K$ then there is an obvious $n^{K}$ algorithm Just guess the at most $k\times k$ full-rank matrix and a disjoint $(K-k)\times (K-k)$ matrix of rank $0$ making sure that you never guess the same row and column in either guess.  
> **username_2**: Ah! I see now taht this is already an answer by @ThomasS  

---

## 2 answers

### Answer by username_3 on 2015-11-17. Score: 2

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](http://mathsci.kaist.ac.kr/~sangil/pdf/2008exp.pdf), [this paper](http://arxiv.org/abs/1503.00190) or [especially this paper](http://mathsci.kaist.ac.kr/~sangil/pdf/2007partition-esa.pdf)

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.


---

### Answer by username_4 on 2015-11-23. Score: 0

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...)


---

