3
$\begingroup$

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:

$A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\}^{m\times m}$, so that $B=QAP$

In other words two matrices are equivalent, if they are equal up to permutation of rows and columns.

A canonisation function for $\sim$ is any function $N$ on the set of all boolean matrices with $N(A)\in \{0,1\}^{m\times n}$ for all $m,n\geq 1$ and $A\in \{0,1\}^{m\times n}$ with the following two properties:

  1. $N(A)\sim A$ for every $A$
  2. $A\sim B \Leftrightarrow N(A)=N(B)$ for all $A,B\in\{0,1\}^{m\times n}$

Now i want to find a canonisation function for $\sim$ that is most efficiently computable. One possible canonisation function is the function $\mathrm{MaxLex}$ which maps every matrix $A$ to the lexicographically largest $B$ that is equivalent to $A$.

For this i first define a linear order on bitvectors as follows: For $b,c\in\{0,1\}^k$

$b<_{llex} c$ iff: the number of ones in $c$ is larger than in $b$ or ($b$ and $c$ have the same number of ones and $b(i)>c(i)$ for the first index $i$ with $b(i)\neq c(i)$)

Then a lexicographic order $<_{lex}$ on matrices of equal dimension is defined as follows:

$A<_{lex}B$ iff $w_A<_{llex}w_B$

where $w_X=X(1,-)X(2,-)\ldots X(m,-)\in\{0,1\}^{mn}$ denotes the bit vector that results from the concatenation of the rows $X(i,-)$ of $X$.

Then $\mathrm{MaxLex}(A):=\max_{<_{lex}} \{ B : A\sim B\}$

I have found a simple recursive algorithm that computes $\mathrm{MaxLex}$, which has however a worst case runtime of $\mathcal{O}(m!)$.

Now my questions are:

  1. Is there a more efficient algorithm that computes $\mathrm{MaxLex}$ than my $\mathcal{O}(m!)$ algorithm?
  2. Is there a polynomial time algorithm that computes $\mathrm{MaxLex}$
  3. Is there a canonisation function for $\sim$ that is computable in polynomial time?
  4. Is anything known about the computational complexity of this problem?

I am thankful for any tips, pointers or comments. I have already googled this problem but couldn't find anything. The only thing i found which resembles this is the decision problem of whether a boolean matrix is equivalent to a triangle matrix, which according to this posting is in NP, but not known to be NP-hard nor in P.

$\endgroup$
5
$\begingroup$

This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, in particular, it doesn't matter whether the $P$ and $Q$ are restricted to satisfy $P=Q^{-1}$ or not, as asked in a comment above).

In particular, there is a canonization procedure that takes only $2^{\tilde{O}(\sqrt{n})}$ time (much better than $n! \sim 2^{\Theta(n \log n)}$), by Babai-Luks 1983, though in practice I'd recommend just using nauty.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I have to think about this. Do you know if the triangulization problem or equivalently two processor scheduling problem which was asked about here is also GI-hard or is this still unknown? $\endgroup$ – 0123456789 Apr 6 '16 at 22:39
1
$\begingroup$

This kind of problem has been studied, e.g. in the exploitation of symmetries in model-checking and in satisfaction constraint problems.

The short answer is that it is $NP$-hard.

I suggest this draft by Junttila as a starting point: A note on the computational complexity of a string orbit problem. It addresses the complexity question (in the subcase of vectors), and references important related work.

$\endgroup$
  • $\begingroup$ Wow, thanks for the link. I have read the draft, but it only proves that the general problems Constructive String Orbit (CSO), where the group that acts on the strings is part of the input and could be any group is $FP^{NP}$ complete and the same for the decision problem variant CSO(D) which is NP complete because Max-Clique can be reduced to it. The group that is used in the proof isn't the same as mine. It applies the same permutation of row and column, whereas in my group rows and columns can be permuted independently from each other. Does that make a difference? $\endgroup$ – 0123456789 Apr 6 '16 at 15:45
0
$\begingroup$

$O(p!)$ where $p$ is the largest prime less than or equal to $n$. https://oeis.org/A186202

MAXLEX is equivalent to MAX-CLIQUE if you read the entries starting at the upper left and read them in an increasing frontier (and put 1's down the main diagonal).

$\endgroup$
  • $\begingroup$ Cool. Although p would be at least n/2 then, because there is always a prime between n and 2n. Do you have a link to the algorithm? $\endgroup$ – 0123456789 Apr 6 '16 at 7:16
  • $\begingroup$ Test one non-trivial member of each prime period permutation in parallel. $\endgroup$ – Chad Brewbaker Apr 6 '16 at 12:39

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.