Maximizing merges with restrictions

Question

Note: The input to this problem has type List[List[List[Pair[int, int]]]]. Since it's tricky to visualize that, I'll use terminology from the original problem, which comes from the optimization of data pipelines. The graph structure in the original problem is not relevant.

Consider k collections of nodes. Every node has some data attached to it, which will be a list of pairs of integers (e.g.: node u has data [(1, 2), (3, 3)]). We'll select one node from each of the k collections, and try to perform merge operations on this selection.

Two nodes can be merged if there is no conflict between their data. Two pairs (a, b) and (c, d) conflict iff a == c and b != d. There is initially no conflict between any two pairs in a list. After merging, the lists are concatenated, and the selection reduces in size by 1.

The score of a selection is the smallest we can make it after performing any sequence of merges. I'm looking for a subquadratic (in input size) algorithm, but anything polynomial is a good place to start.

Some observations, to assist with solving this problem: can_merge is symmetric but not transitive - [(1, 1)] can be merged with [(2, 1)], and [(2, 1)] can be merged with [(1, 2)], but transitivity fails. Greedy attempts seem to fail because of this property. Thinking of this as clique-finding doesn't really help - the graph induced by the relation can_merge can be quadratic in size, and even if we're only aiming for quadratic, clique-finding and then some kind of subset cover isn't going to be polynomial it seems.

In practice, it's the case that the number of pairs given in the input is approximately equal to the number of nodes, up to a small constant multiple. Also, the number of unique second values for any given first value across all pairs shouldn't be very large - sqrt(input size) would be a good bound.

Answer 1

The problem is NP-hard, by reduction from graph coloring, so you should not expect any polynomial-time algorithm.

Here's a reduction. Consider an undirected graph $G$. Associate to each node/vertex $v$ a list of pairs $(e,v)$, one for each edge $e$ incident on $v$. Now we can treat this as an instance of your problem (ignore the graph structure; we obtain a list of pairs for each node). Any solution to your problem corresponds to a valid coloring of this graph: all nodes that are merged together receive the same color. Similarly, any valid coloring corresponds to a valid solution of your problem. The number of colors used is the size of the solution to your problem. Therefore, the optimal solution (of smallest size) to your problem corresponds to the optimal coloring (with the fewest colors).

Of course, graph coloring is NP-hard, so it follows that your problem is as well.

Given an instance of your problem, you can build a graph (add an edge between each pair of nodes that have a conflict) and then solve your problem by using any off-the-shelf algorithm for graph coloring. For instance, you could use a heuristic, or you could translate it to an instance of SAT and solve it with a SAT solver.