is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

Question

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance!

Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( usually $N$ is a large number, $K$ is a small number). Each row of the matrix contains distinct values, but each column may contain duplicate values. For $i = 1, 2, \cdots, K$, let $m_i$ denote the count of distinct values at $i$-th column and define $\rho := min(m_1, m_2, \cdots, m_K)$. If we can swap any two numbers within each row, how to minimize $\rho$ provided you can perform any number of the given operations(swaps)?

Can this problem be NP-complete in terms of $N$??

For example: in a $4\times3$ matrix $$ \begin{matrix} 1&2 & 3\\ 3&4& 5\\ 4&5& 7\\ 6&7& 8\\ \end{matrix} $$ Since only swaps within a row are allowed, we can swap 1 and 2 in the first row, but cannot swap 1 in the first row with 4 in the second row. I think after performing a few swaps, one optimal solution we can get is $$ \begin{matrix} 1&2 & 3\\ 4&5& 3\\ 4&5& 7\\ 6&8& 7\\ \end{matrix} $$ where $m_1 = 3, m_2=3, m_3 = 2$,
Hence the minimum count of distinct values of all columns is $\rho = 2$.

Answer 1

The first thing we have to do is define a decision version of your problem, like for example:

Is it possible to swap the elements inside the rows of the matrix so that in at least one column the number of distinct elements is less or equal than $\rho$?

Well, the first thing to take into account is that this problem is just asking if we can swap elements inside the rows in order to find a column where the number of distinct elements is less or equal than $\rho$.

We are going to reduce the decision version of 3HITTING SET to the decision version of your problem. 3HITTING SET is an np-complete variant of minimum hitting set where all subsets have only three elements. Hitting set is like the inverse of set cover. In minimum set cover you cover members of the universe with subsets and in miminum hitting set you cover subsets with members of the universe. That means that if an element appears in a subset, that subset is covered by the element. The objective is to find the minimum number of elements inside the universe that are enough to cover all subsets.

A decision version of 3HITTING SET will be:

Is it possible to cover all subsets with at most $\rho$ elements of the universe?

Now with the reduction:

We simply convert each subset of the hitting set problem into a row of your problem. That is we create a matrix $A$ .Then, for each subset $i$ that belongs to the hitting set instance, we create a row $i$ inside the matrix $A$. And then for each element $j$ that belongs to the universe in the hitting set instance being reduced, we create a number inside the matrix, this number will be inside row $A_i$ if the element $j$ that belong to the universe appears inside the subset $i$ in the hitting set instance.

If there is a hitting set of size $\rho$, then we will have a matrix where we can form a column by swapping with at most $\rho$ distinct elements.

The reason for this is that if we can cover the sets of the hitting set instance with $\rho$ elements then we can form a column with $\rho$ or less distinct elements inside the matrix by picking the numbers that were mapped to elements of the universe in the hitting set instance and swapping them inside the rows of the matrix so that they are all in the same column.

For the other direction, that is, for the cases in which there is no minimum hitting set instance with at most $\rho$ distinct elements we have to show that those cases are converted in our reduction into matrices where we can´t form a column with at most $\rho$ elements by swapping numbers inside rows.

If on those instances we could, by swapping numbers inside rows, create a column with at most $\rho$ elements inside the matrix; that would mean that there exists $\rho$ elements that can cover the subsets in the hitting set instance. This is a contradiction

The reason is that we have mapped every element of the universe in the hitting set instance to a different number inside the matrix and also we have mapped every subset into a different row inside the matrix. So if we could form a column with at most $\rho$ distinct elements by swapping elements inside the rows, that will mean that there is at least one of those numbers inside each row. Because each subset of the hitting set instance was mapped to a different row and each element of the universe is mapped to a different number inside the matrix, that will mean that we can cover the subsets with those $\rho$ elements in the hitting set instance.