A combinatorial matrix reconstruction problem II

Question

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.

Answer 1

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?