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.