Cheap and Secure Web Hosting Provider : See Now

[Solved]: Matrix equality up to row/column permutations problem name

, , No Comments
Problem Detail: 

Sorry for the trivial question; has the following decision problem an "official" (possibly short) name?

Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same up to row and column permutations.

(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)

Asked By : Vor

Answered By : Vor

After a few observation in the comments (thanks to Hendrik Jan, Yuval Filmus, and D.W), I post an extended comment as an answer.

It seems (unless I'm missing something) that the problem is equivalent to Hypergraph isomorphism (HI):

  • to prove that it is equivalent to HI, it is enough to use incidence matrices: every column represents a node of the hypergraph, every row represents an hyperedge (the $1$s are placed on the columns corresponding to the nodes of the hyperedge).

The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?

(if nobody post another answer in a few days I'll temporarily accept mine).

Additional stuff:

  • for proving that it is GI-complete it is enough to consider the incidence matrix of the source graphs $G_1, G_2$;

  • the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H_1, H_2$, transform them to graphs: every column becomes a node $c_i$, every row becomes a node $r_i$; an edge $(c_i,r_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\{c_{i_1},...,c_{i_m}\}$ that represents an hyperedge to preserve hyperedge mapping.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23850

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback