Find a Minimal Set of Combined Tuples

Suppose I have a set of n ordered tuples, all of the same, fixed dimension. The tuples' values are integers, with #s indicating an integer I don't care about. For example:


{ (1,2,5), (4,2,3), (1,2,#), (#,2,3) }

Tuples can be combined so long as they don't disagree about anything. For example, (1,2,#) and (#,2,3) can be combined into (1,2,3). Therefore, we can simplify the above set by combining the last two elements:


{ (1,2,5), (4,2,3), (1,2,3) }

The goal is to simplify the set as much as possible. We can't simplify from here any more, but by simplifying in a different way, we could have done better by combining the 1st with the 3rd and the 2nd with the 4th (hence, this problem is not convex):


{ (1,2,5), (4,2,3) }

My question:

• Is this a well-known problem by a different name? (E.g., give a reduction from some NP-complete problem, perhaps?) It's related to the set-cover problem, but somewhat different since elements can be combined and not everything need be chosen.

• What algorithms can I use to solve this, even approximately? Speed is important; I solved a similar, simpler problem in expected O(n); equivalent performance would be ideal.

Call tuples containing at least one # "free tuples" (vs. "complete tuples"). Observation: WLOG every tuple is free: combining a free tuple with a complete tuple or a complete tuple with a complete tuple is never suboptimal, so we can preprocess all such combinations first, then remove all complete tuples--since by construction, nothing can combine with them.

I am not aware of whether this problem has a name or not, but it can be shown that it is NP-complete by reduction from the maximum independent subset problem:

Given an undirected graph of $N$ vertices and $M$ edges, we can map the nodes to a set of $M$-tuples $\{x_1,...,x_n\}$ such that any two tuples are "compatible" if and only if the corresponding nodes do not share an edge:

• Given $i$-th undirected edge $\{a,b\}$ with $ a\leq b$ we set $x_{a}[i]$ to 1 and $x_{b}[i]$ to 2.

• Any element that remains unset by the previous rule is set to #.

Now:

-
For each pair of nodes that share an edge, the corresponding tuples will not be compatible because they have different values in the position corresponding to the edge.

-
For each pair of nodes that do not share an edge, for each position in the tuples at least one of them has # assigned in that position. Hence,they will be compatible.

By definition:

-
An independent subset of the graph is such that it does not contain two nodes that share an edge.

-
A compatible subset of tuples is such that it does not contain two tuples that are not compatible.

Hence a subset of nodes is independent if and only if the corresponding subset of tuples is compatible. Then, the size of the maximum independent set in the original graph is equal to the size of the maximum set of compatible tuples.

StackExchange Computer Science Q#61232, answer score: 3