Association bipartite maximale avec une récompense supplémentaire pour couvrir certains ensembles

Question

Considérez la variation suivante de l'appariement maximum bipartite. Comme d'habitude, nous avons un graphique bipartite $ g $. De plus, il existe une collection supplémentaire d'ensembles $ S_1, S_2, DOTS, S_K $, avec chaque ensemble $ S_ {i} $ étant défini comme une collection de nœuds du côté droit du graphique $ g $ ainsi que un poids.

Supposons que dans une correspondance de tous les nœuds que $ s_ {i} $ décrits soit correspondant. Ensuite, un bonus supplémentaire de poids ($ s_ {i} $) est gagné.

Étant donné une certaine correspondance, définissez comme $ y $, l'ensemble de tous les indices $ i $ tel que $ s_ {i} $ est entièrement couvert par la correspondance (c'est-à-dire que tous ses nœuds sont appariés). Ensuite, le profit de cette correspondance est

$$ text {# bords} + sum_ {a in y} text {poids} (s_ {a}), $$

où $ text {# arêtes} $ est le nombre de bords dans la correspondance.

Le problème est, bien sûr, de trouver la correspondance qui maximise la quantité ci-dessus.

J'ai instantanément pensé à l'algorithme de temps exponentiel suivant. L'algorithme fonctionne comme suit:

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

Comme je me souviens de ma classe d'algorithme, dans l'algorithme de chemin d'augmentation, une fois qu'un nœud du côté gauche a été affecté à la correspondance, il ne le quitte jamais. Par conséquent, l'algorithme essaie de s'assurer que dans chaque itération, certains ensembles seront satisfaits. Essentiellement, c'est une force brute. Par conséquent, l'optimalité est prouvée facilement. À moins bien sûr que mon hypothèse soit mauvaise.

Le temps d'exécution est $ o (2 ^ {k} text {poly} (v, e)) $, ce qui convient à mes besoins car $ k $ n'est que 7.

Mais je me demande s'il existe un algorithme polynomial pour ceci ou si le problème est dur. C'est clairement en NP, mais je n'ai pas eu beaucoup de succès à prouver la complétude NP.