1
$\begingroup$

For a positive integer $n$, let an $n$-shuffle be a multiset $S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each $S_i$ is a multiset of $n$ numbers containing the number $d_i$. A realization of the shuffle is a symmetric $n\times n$ matrix $M$ whose shuffle $S(M)$ is constructed as in A combinatorial matrix reconstruction problem to which this question is a followup. Clearly, a matrix is defined by its shuffle only up to symmetric permutations.

I am looking for an algorithm that finds for a given shuffle some realization if it is unique up to symmetric permutations, or reports that this is impossible. For the case when the $S_i$ are disjoint sets, an algorithm is described in McKay's answer to my earlier question, and a class of counterexamples with multiple not permutation equivalent realizations is given. In between there is much room for improvement....

Unless the problem can be shown to be NP-hard I am looking for an approach different from reduction to an NP-hard problem. Most likely, the problem belongs to the complexity class of graph isomorphism. Like in graph isomorphism, the majority of problems can be solved easily by a simple backtracking search based on McKay's observation, but more regular problems are harder.

$\endgroup$

1 Answer 1

1
$\begingroup$

Since we look for a matrix up to a symmetric permutation, we can fix the order of rows and assume that $S$ is a list and $S_i$ represents the elements of $i$-th row of $M$. Then, we can put the diagonal elements $d_i$ at positions $M_{ii}$ and define $S'_i := S_i\setminus \{d_i\}$.

Our goal is find a placement of the elements of each $S'_i$ at the non-diagonal positions of the $i$-th row of $M$. Below I describe an ILP approach to this problem.

Let $T_i$ the set of distinct elements corresponding to multiset $S'_i$ and $m_{is}$ be the multiplicity of $s$ in $S'_i$. Then let $x_{ijt}\in\{0,1\}$ for $i,j\in[n]$, $i\ne j$, and $t\in T_i$ be an indicator variable for the equality $M_{ij}=t$. The ILP problem can be posed as follows: $$\begin{cases} \sum_{t\in T_i} t x_{ijt} = \sum_{t\in T_j} t x_{jit} \qquad (1\leq i<j\leq n),\\ \sum_{t\in T_i} x_{ijt} = 1 \qquad (i,j\in [n],\ i\ne j),\\ \sum_{j=1\atop j\ne i}^n x_{ijt} = m_{it}\qquad (i\in[n],\ t\in T_i). \end{cases} $$ There is no objective function here, so any feasible solution will do the job. However, an objective function can be used to quickly check if there exist more than one solution by solving the problem with a linear objective function with random coefficients and then with the same function but negated (and to repeat this multiple times with different choices of coefficients). It should catch different solutions (if they exist) with high probability.

P.S. There is a somewhat related NP-complete problem: Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

$\endgroup$
4
  • $\begingroup$ To explicitly disallow a given binary solution, you can use a no-good cut, as in my answer here. $\endgroup$
    – RobPratt
    Aug 30, 2022 at 19:26
  • $\begingroup$ Since ILP is NP-hard, this approach would be appropriate if the problem can be shown to be NP-hard. But this is unlikely; the problem should be easier, perhaps of the complexity class of graph isomorphism. Your approach also needs graph isomorphism for postprocessing since if there are multiple solutions of your ILP one still needs to check whether they are permutation equivalent. $\endgroup$ Aug 31, 2022 at 15:26
  • $\begingroup$ @ArnoldNeumaier: On the contrary, I think your problem is quite likely NP-complete. I gave a link to a simpler problem, which is proved to be NP-complete. Perhaps, that one can be reduced to yours but I did not check. As for ILP, it's often can be solved quite fast in practice for moderate instances with state-of-art solvers like Gurobi or CPLEX. $\endgroup$ Aug 31, 2022 at 15:39
  • $\begingroup$ I'd be quite interested in a proof on NP-completeness. $\endgroup$ Aug 31, 2022 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.