2
$\begingroup$

I have simple algorithmic question, but I can't find any source where this algorithm is explained in details. Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let we apply simultaneously all pairs of row $P_1 \in S_m$ and column $P_2 \in S_n$ permutations to this incidence matrix. Obviously because we have finite ordered set, there exist lexicographically largest value of this matrix.

Question is: what is the best algorithm that allows to find this biggest value?

Example input (Fano plane incidence matrix): Fano plane

Example output:

$$ 1110000 \\ 1001100 \\ 1000011 \\ 0101010 \\ 0100101 \\ 0011001 \\ 0010110 $$

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ This is similar to lexicographically smallest graph canonization, which is known to be NP-hard, but for bipartite graphs. I think there's a good chance it's NP-hard as well $\endgroup$
    – Daniel Weber
    Commented Jul 20 at 2:29
  • $\begingroup$ @DanielWeber Yes, I understand that. Still, graph canonical form (I reimplemented nauty's approach from arxiv.org/abs/1301.1493 Practical graph isomorphism) produces not lexicographically largest incidence matrix. $\endgroup$
    – Ihromant
    Commented Jul 20 at 9:53
  • $\begingroup$ Is this related to Complete graph invariant based on integer programming? $\endgroup$
    – joro
    Commented Jul 20 at 9:55
  • $\begingroup$ It could be related. Still, while looked at your code I spotted that you are iterating over permutations(n). If n>10 it leads to unacceptable running time. Still, nauty runs pretty fast on non-regular graph. I assume that there is (or could be) algorithm which runs with approximately similar time. $\endgroup$
    – Ihromant
    Commented Jul 20 at 10:08
  • $\begingroup$ I am permuting for a toy implementation. The problem can be formulated to integer program, which is faster than permuting, but still of exponential complexity. $\endgroup$
    – joro
    Commented Jul 20 at 10:17

0

Reset to default

You must log in to answer this question.