6
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ Graph isomorphism. The matrix is its adjacency matrix. (But then we assume the permutations on both row and column are kept the same.) $\endgroup$ Apr 16 '14 at 10:25
  • $\begingroup$ @HendrikJan: ok (it is GI-complete), but usually the adjacency matrix is a square matrix; are you aware of cases in which the problem is referenced with another short name (without calling it GI) ? (in other domains/contexts) $\endgroup$
    – Vor
    Apr 16 '14 at 10:35
  • 1
    $\begingroup$ @HendrikJan, Wait, why is this graph isomorphism? Graph isomorphism imposes the requirement that the row & column isomorphisms are the same; Vor's problem has no such requirement. So it sounds like your own comment shows that this is not the same as GI (at least, if it is the same, the reason is non-obvious). Am I missing something? $\endgroup$
    – D.W.
    Apr 18 '14 at 0:23
  • 1
    $\begingroup$ @D.W. You have a point there. I will have a look at the construction proposed by Vor. $\endgroup$ Apr 19 '14 at 9:46
  • 1
    $\begingroup$ @D.W.: now that I'm reading your comment more carefully, it seems that you're right; it seems that my problem is equivalent to hypergraph isomorphism. Obviously it is GI complete: it is enough to use an incidence matrix in which the columns represent nodes, and the rows represent the edges (every row contains exactly two 1s). The reverse direction is similar: transform the incidence matrix of the hypergraph to a graph and attach to every hyperedge an unique structure (e.g. a $K_n$). $\endgroup$
    – Vor
    Apr 19 '14 at 10:18
2
$\begingroup$

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.

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