1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure how the tree is relevant to the question. Could you try and phrase it using just lists? $\endgroup$ Jul 15 at 6:39
  • $\begingroup$ What is your question? We are a question-and-answer site. We require you to articulate a specific question. If you want an algorithm to solve some problem, what is the problem you want solved? What is the input to the algorithm, and what is the desired output? (what are the requirements on candidate output for it to be valid?) Please don't specify a problem by telling us how you'd solve it, specify it only in terms of the desired input-output behavior of the algorithm. $\endgroup$
    – D.W.
    Jul 15 at 6:53
  • $\begingroup$ I don't understand what "The score of a selection is the smallest we can make it after performing any sequence of merges" means. How is size measured? Do you have any reason to believe a polynomial-time algorithm exists? $\endgroup$
    – D.W.
    Jul 15 at 6:55
  • $\begingroup$ @D.W. A selection is a set of nodes. Performing a merge removes two nodes and adds one node. The size is just the number of nodes in the set. Which part of my question, or the answer I would like, is not clear? I provided hints as I found they might be helpful for those trying to solve this problem as well. $\endgroup$
    – Adam Jamil
    Jul 15 at 19:39
  • $\begingroup$ @CommandMaster I initially phrased it to some other folks with input of type List[List[List[Pair[int, int]]]]. I found it considerably easier to visualize with the tree, even if it the structure had absolutely nothing to do with the problem. Let me make that more clear in the problem. $\endgroup$
    – Adam Jamil
    Jul 15 at 19:41

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Well done - this is a very nice reduction. I imagine my colleagues will not enjoy this result though 🤣. Thanks for the link as well, the O((n+m)log(n)) algorithm will likely work much better than what we are currently doing. $\endgroup$
    – Adam Jamil
    Jul 17 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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