3
$\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
  • $\begingroup$ Is $k$ a constant? Is a running time of $O(n^{f(k)})$ allowed? $\endgroup$ – SamiD Feb 25 at 11:51
  • $\begingroup$ 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. $\endgroup$ – SamiD Feb 25 at 12:13
  • $\begingroup$ Ah! I see now taht this is already an answer by @ThomasS $\endgroup$ – SamiD Feb 27 at 7:11
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.

| cite | improve this answer | |
$\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...)

| cite | improve this answer | |
$\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.