4
$\begingroup$

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:

$$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\leftrightarrow E\\ G+H\leftrightarrow B\\ \end{aligned}$$

The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).

For notational clarity -

$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.

$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.


The first question is, how to maximize the total quantity matched?

Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.

Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.

The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).


An Example with the (not quite bipartite) Graph Approach:

Take input array $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, where $A:5$ indicates an item A with quantity 5. The bipartite graph should look like the below where the colors indicate potential matches (ignoring quantities) except that it allows for impossible matches, namely $\{A, E, A, B\}$ should not be possible but is according to the graph:

Bipartite with Colors

The potential matches should be:

  1. $A, E, D$ (top edges)
  2. $A, B$ (bottom edges)
  3. $A, E, D$ (first bottom then top edges)
  4. $A, B$ (top then bottom edges)

Ultimately the solution including quantity would be 2 matches with some quantity left over:

  • ${A:5/5,\ E:5/5,\ D:5/6}$
  • ${A:3/4,\ B:3/3}$

Left over

  • $D:1$
  • $A:1$
$\endgroup$
  • $\begingroup$ I think your problem is clear, but the method you have chosen is not so clear to me: 1) matchings are generally considered edge sets. If instead 3 nodes are 'matched' to eachother, we no longer have an edge. Are you sure that a matching is what you want? 2) What is the solution to your example? A matching in your graph? Which one? $\endgroup$ – Discrete lizard Jun 14 at 9:43
  • $\begingroup$ It is also unclear to me what property the graph you want should have, but specifying more clearly how the solution of your problem should be created from the graph would probably make that clear. It seems to me that constructing this graph is not your actual problem, but merely how you tried to approach it. In that case, you may want to clarify that in your title. $\endgroup$ – Discrete lizard Jun 14 at 9:48
  • $\begingroup$ For 1) yes, that's what I'm trying to achieve, so a flow through {A, E, D} would be a 3-way match of those items. Once they're matched, none of the items can be "reused". 2) Let me write up the solution $\endgroup$ – luca590 Jun 14 at 9:51
  • $\begingroup$ @Discretelizard do those edits help? $\endgroup$ – luca590 Jun 14 at 10:33
  • $\begingroup$ I'm still not too sure which set of nodes in that graph you call a 'match'. Is set of nodes that can be visited by a simple path from the left S to the right S a match? Then $A, B, A, E, D$ is another match that shouldn't be possible, right? $\endgroup$ – Discrete lizard Jun 14 at 14:42
2
$\begingroup$

The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1

Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.


This special case seems easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type conflict-free. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.

More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.

For example, on the input $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, the graph will look like the following:

Matching on example input

Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but only influences the weight of the two edges between types A and D. So the approach works for this case.

However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1]$. We now get the following graph:

A matching with weird weights

The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.

I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.


1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.

$\endgroup$
  • $\begingroup$ Ok, so that sounds promising, could you add some more detail to the explanation. So, you said this case can be represented as a 2d matching problem. Could you draw the graph? I agree G is not present in another combination, but A is. $\endgroup$ – luca590 Jun 14 at 17:30
  • $\begingroup$ Generally speaking, what algorithm do you use to generate the graph such that all edges only allow for the correct matches? $\endgroup$ – luca590 Jun 14 at 17:35
  • $\begingroup$ @luca590 The paragraph starting with 'more concretely' describes how to construct the graph, one edge at a time. Is there anything particular that is unclear about it? I don't have time to add an example right now, but I can do so later. Should I use the same example input as the one in the question? $\endgroup$ – Discrete lizard Jun 14 at 17:55
  • $\begingroup$ Yeah, use the same input. I think what's not clear to me is why not adding the edge for "conflict free type" gives you the correct graph $\endgroup$ – luca590 Jun 14 at 22:17
  • $\begingroup$ @luca590 Ok, I gave an example. My approach seems to work for the input in the question, but it doesn't reduce to an ordinary weighted matching problem in other cases. It may be possible to handle it with some other approach, but I'll have to think about that for a bit. $\endgroup$ – Discrete lizard Jun 15 at 14:13

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.