Distinct Row Matrix Completion Decision Problem

Definition

Distinct Row Matrix Completion Decision Problem

Given a matrix $M\in \{0,1,?{\}}^{n\times m}$ and an integer $p$, this decision problem asks whether we can replace all $?$s by $0$ or $1$ so the completed matrix has at most $p$ distinct rows.

Complexity

Constant number of incomplete users

Suppose only $u_0$ has missing entries. We can scan the other $n-1$ users and ask: Does some row agree with $u_0$ on every known entry? If yes, we can fill the ? entries so that $u_0$ becomes identical to that row. If no such row exists, $u_0$ cannot be merged with any existing row, so the missing entries can be filled arbitrarily.

Comparing $u_0$ with one row requires checking up to $m$ entries, so scanning all rows takes $O(nm)$ running time, i.e., polynomial running time.

If more than one user has missing entries, the incomplete users can potentially be completed so that they become equal to each other, not just to an already complete user.

Consider the case where there are only constantly many incomplete users, say $k$.

1. If an incomplete user can be completed to equal an already complete row, we can merge it with that row.
2. For the remaining incomplete users, we try all possible ways of grouping them into identical completed rows.

A group of incomplete users is feasible exactly when their known entries never conflict. That is, for every column, we must never have one user with known value $0$ and another user with known value $1$. If there is no such conflict, the ? entries can be filled so that all users in the group become the same row.

For example,

$$(1,?,0,?),(1,1,?,0),(?,1,0,0)$$

can all be completed to

$$(1,1,0,0),$$

so they form one distinct row.

In contrast,

$$(1,?,0),(0,1,?)$$

cannot be grouped because their first entries conflict.

Thus, we can brute-force over all partitions of the $k$ incomplete users and check whether every group is feasible. Since $k$ is constant, the number of possible groupings depends only on $k$, not on $n$ or $m$.

Therefore,

$$k=O(1)⟹\text{brute-force over all groupings of the incomplete users is polynomial.}$$

Hence, Distinct Row Matrix Completion is polynomial-time solvable when only constantly many rows contain missing entries

Input-dependent number of incomplete users

If the number $k$ of incomplete users is part of the input, then $k$ may grow with $n$. Consequently, brute-forcing all possible partitions of the incomplete users is no longer guaranteed to run in polynomial time.

In fact, Distinct Row Matrix Completion is NP-complete, even if the matrix is almost complete: each row and each column may contain at most $3$ missing entries.

Importantly,

$$\text{at most }3\text{ missing entries per row}$$

does not imply that only constantly many rows are incomplete. We may still have $\Theta (n)$ incomplete rows, each containing only a few ? entries.

Membership in NP is straightforward: a completed matrix is a certificate. Given such a completion, we can check in polynomial time that

1. every ? was replaced by $0$ or $1$ while all originally known entries remain unchanged, and
2. the completed matrix contains at most $p$ distinct rows.

NP-hardness is obtained by a reduction from a special version of 3-Coloring.

Thus,

$$\begin{array}{rl}k=O(1)& ⟹\text{polynomial-time solvable},\\ k\text{ input-dependent}& ⟹\text{NP-complete in general}.\end{array}$$

The problem remains NP-complete even under the strong restriction that every row and every column contains at most $3$ missing entries