سؤال

Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S_1,S_2,\dots,S_k$, with each set $S_{i}$ being defined as a collection of nodes from the right side of the graph $G$ as well as a weight.

Suppose that in a matching all nodes which $S_{i}$ describes are matched. Then an extra bonus of weight($S_{i}$) is gained.

Given a certain matching, define as $Y$ the set of all indexes $i$ such that $S_{i}$ is fully covered by the matching (i.e all its nodes are matched). Then the profit of this matching is

$$\text{# edges} + \sum_{a \in Y} \text{weight}(S_{a}),$$

where $\text{# edges}$ is the number of edges in the matching.

The problem is, of course, to find the matching which maximizes the above quantity.

I instantly thought of the following exponential time algorithm. The algorithm works as follows:

For i in [0,2^k -1]:
    Define X= a subset containing all S_{j} such that  j-bit in i is 1.
    Try to find a maximum matching  only for the nodes which are defined by the elements of X
    If it is a maximum matching(I.e all elements in the right side are matched)
       Add all the other nodes not already present and continue the augmenting path algorihtm
Pick the maximum for all i

As I remember from my algorithm class, in the augmenting path algorithm, once a node in the left side has been assigned to the matching it never leaves it. Hence, the algorithm tries to make sure that in each iteration certain sets will be satisfied. Essentially, it is brute force. Therefore, optimality is proven easily. Unless of course my assumption is wrong.

The running time is $O(2^{k}\text{poly}(V,E))$ which is fine for my needs as $k$ is only 7.

But I am wondering whether there exists a polynomial algorithm for this or if the problem is NP-hard. Its clearly in NP but I have not had much success proving NP-completeness.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top