5
$\begingroup$

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:

  1. 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.
  2. 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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Have you checked whether a greedy algorithm works? (Always choose a pair to combine that reduces the number of #'s by as little as possible.) Seems like too much to hope for, but you could check (using random testing). $\endgroup$ – D.W.♦ Aug 3 '16 at 5:09
  • $\begingroup$ It's a special case of minimum hitting set. $\endgroup$ – Yuval Filmus Aug 3 '16 at 8:41
  • $\begingroup$ @YuvalFilmus, can you elaborate on how to formulate this as a polynomial-sized instance of minimum hitting set? Here we're not given the final tuples in advance, and it seems like (even after seeing the inputs) there may be exponentially many candidates for which tuples could appear in the output. But probably I'm overlooking some nice insight? $\endgroup$ – D.W.♦ Aug 3 '16 at 19:34
  • $\begingroup$ @D.W. Right, it's "implicit" minimum hitting set. $\endgroup$ – Yuval Filmus Aug 3 '16 at 21:58
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

It seems to me this is the minimum set cover problem. https://en.wikipedia.org/wiki/Set_cover_problem

where the universe to cover is the union of the elements of each of the tuples. It is known to be NP-Complete so there aren't known algorithms to solve it in polynomial time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ As I wrote, I don't see how this can be the set cover problem, although it is related. For example, consider {(1,2,#),(#,2,3)}. I do not need both tuples to cover the universe {1,2,3}; the correct answer is instead to combine both tuples into a new one (1,2,3). Also, order matters, so e.g. {(1,2),(2,1)} cannot be simplified. $\endgroup$ – imallett Aug 3 '16 at 18:56
  • 1
    $\begingroup$ Can you clarify the relationship? How do you plan to reduce from minimum set cover to this problem? I'm not immediately seeing the equivalence, so it would help if you could edit your answer to clarify $\endgroup$ – D.W.♦ Aug 3 '16 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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