"(1: k) Matching trees" is solvable in polynomial time?

Question

A few months ago there was a good question regarding the “ 1: n match problem ” and there seemed to be no multi-user time algorithm.

I would like to add restrictions in order to find the maximum match for the 1: n match problem with the polynomial algorithm. I would like to say: "For vertex A1, select either {B1, B2, B5} or {B2, B3} if the vertices have not yet been taken from another A-vertex", i.e. I would not allow all possible combinations.

This could be expressed if we introduce auxiliary vertices H for each choice and replace the edges with trees =>, we get a problem similar to ordinary bipartite comparisons. Each vertex A or B can have only one edge in the mapping. The edges at the vertices or from the vertices from H are either all in the mapping, or none of them are present in the mapping. Imagine the following three-part graph:

Now define h_ij = "the root of the tree containing H_ij" to easily express the correspondence:

• Then in the example M = {h12, h22} there will be one maximum match, although not all vertices from B are involved
• The set {h12, h23} is not a coincidence, because then B3 would be selected twice.

Will this problem then be solvable in polynomial time? If so, is there a polytime solution for the weighted (w (h_ij)) option? If not, could you argue or even prove it to a “common person” like me, or propose other restrictions to solve the 1: n matching problem?

eg. can a graph be transformed into a general graph, which could then be solved by weighted matching for general graphs? Or can branching or even related forests help here?

PS: not homework ;-)

Answer 1

There is a difference between maximum and maximum. I assumed that you meant the maximum for the next record.

You do not seem to have defined your problem very clearly, but if I understood your intent correctly, it seems that your NP problem is complete (and "equivalent to " Install Package " ).

We can assume that the admissible sizes of the sets are the same (k) for all A_i in order to find a match [1: k], since any other size of the set can be ignored. To find max k, we simply run the algorithm for [1: k] for k = 1,2,3, etc.

So your problem (I think ...):

Given m, the set of families F_i = {S_1i, .., S_n(i)i} (| F_i | = size F_i = n (i) does not have to be the same as | F_j |), each set of size k, you must find one set from each family (S_i) that

• S_i and S_j do not intersect for any neq j.
• The maximum number of S_i.

We can show that it is NP-complete for k = 3 in two stages:

• The task of NP-Complete Install packaging can be reduced. This shows that it is NP-Hard.
• Your problem is NP and can be reduced to Set Packing. This and 1) implies that your problem is NP-Complete. It also helps you use any approximation / randomization algorithms that already exist for Set-Packing.

Packing Task - Problem:

Considering n sets S_1, S_2, ..., S_n, we find among them the maximum number of pairwise disjoint sets.

This problem remains NP-complete, even if | S_1 | = | S_2 | = ... = | S_n | = 3 and is called the 3-Set packing problem.

We will use this to show that your problem is NP-Hard, providing an easy reduction from 3-Set packaging to your problem.

Given S_1, S_2, ..., S_n just form families

F_i = {S_i}.

Now, if your problem had a solution with polynomial time, we get a set of sets {S_1, S_2, ..., S_r} such that

• S_i and S_j do not intersect
• The maximum number of S_i.

This easy reduction gives us a solution to the 3-pack problem, so your problem is NP-Hard.

To make sure this problem is in NP, we reduce it to Set-Packing as follows:

Given F_i = {S_1i, S_2i, ..., S_ni}

consider the sets T_ji = S_ji U {i} (that is, add the family id to the set itself) and draw them through the Set-Packing algorithm. I will leave this to you to understand why the Set-Packing solution provides a solution to your problem.

---

For the maximum solution, all you need is a greedy algorithm. Just keep collecting sets until you can choose more. It will be polynomial time.