2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – R B Nov 16 '15 at 17:53
  • $\begingroup$ 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$. $\endgroup$ – Kumar Nov 16 '15 at 17:57
2
+50
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.