Maximum bipartite matching with extra reward for covering certain sets

Question

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.

Answer 1

Let Y131P be "your problem with [weights all equal to 1] and
[left-side degrees bounded above by 3] and [right-side degrees all equal to 1]".
I will show hardness of Y131P.


Wikipedia gives two local gadget reductions from 3-SAT to 1-in-at-most-3-SAT.
The longer one induces a locally-computable bijection between
satisfying assignments whose inverse is also locally-computable.


The following is a linear reduction from 1-in-at-most-3-SAT to Y131P:

There is a left-side node for each variable and for each clause. ​ ​ ​ Each literal corresponds
to a set of ​ ( 1 + number_of_occurences_of_that_literal_in_the_input ) ​ right-side nodes,
one of which is labeled with the literal LIT and the others of which are labeled ​ $\langle$LIT,C$\rangle$ ​ for the
constraints C in which they appear. ​ ​ ​ Each right-side node labeled with a literal is adjacent
to the left-side node labeled with that literal's variable, and each right-side node labeled
with a pair ​ $\langle$LIT,C$\rangle$ ​ is adjacent to the left-side node that corresponds to the constraint C.

(A satisfying assignment induces a matching which uses every left-side node and number_of_variables sets, so its value is ​ ​ ​ # left-side edges ​ + ​ number of variables ​ ​ ​ .
Since the graph is bipartite, no matching can have more edges than the number of left-side nodes.
Due to the left-side variables, sets for complementary literals can't simultaneously be chosen. ​ Thus, no matchings have value greater than ​ ​ ​ # left-side edges ​ + ​ number of variables ​ ,
and since the constraints are Exactly-1, there is an efficiently-computable bijection
[between [matchings whose value is that sum] and satisfying assignments]
whose inverse is also efficiently computable.)


In particular, Y131P is FNP-hard.

By [that reduction being linear] and the sparsification lemma, one gets that a
strong version of ETH would imply that Y131P takes takes 2^Ω(|E|) time to decide.
Since Y131P can be efficiently padded without changing k (just throw in
isolated edges between new vertices), the same strengthened ETH assumption
would imply that Y131P algorithms' runtime's dependency on k must be 2^Ω(k).

The rest of this answer's results apply even when the weights are
given in unary and are equal to each other (but not necessarily to 1).

As I'll use the phrase, "threshold constraints" specify [a multi-set of literals] and
[a positive integer (the "threshold") that's at most the constraint's "size"], where its "size"
is the sum of the multiplicities of the literals in the multi-set. ​ The constraint is satisfied
if and only if the sum of the multiplicities of the true literals is at least the threshold.


The following is a reduction from [satisfying a list of threshold constraints] to
your problem such that [the number of sets is twice the number of variables] and
[the degree of the left-side nodes are at most ​ max ( 2 , size_of_largest_constraint ) ]
and the degree of each right-side node is at most
max ​ ( ​ 1 ​ , ​ [the maximum, taken over the constraints, of size minus threshold] ​ ) ​ ​ ​ :

Each variable corresponds to one left-side node and each constraint corresponds
to ​ ( size_of_the_constraint - the_constraint's_threshold ) ​ left-side nodes.
Each literal corresponds to a set of
( 1 + number_of_occurences_of_its_complement_in_the_input )
right-side nodes, one of which is labeled with the literal LIT and the others of which
are labeled ​ $\langle$LIT,C$\rangle$ ​ for each occurrence of LIT's complement in a constraint C.
For each constraint C, for each literal LIT whose complement is in C, the node labeled
$\langle$LIT,C$\rangle$ ​ is adjacent to [the left-side nodes that correspond to C] and nothing else.
For each variable v, [the 2 right-side nodes labeled with v's literals] are
adjacent to [the left-side node that corresponds to v] and nothing else.
The weights are equal to each other and greater than the number of variables plus
[the sum, taken over the variables, of the maximum, taken over the variable's
positive and negative literal, of the number of occurrences of that literal in the input].

(Due the the left-side variables, one can't choose both a variable and its negation.
Due to the number of nodes corresponding to a given constraint, one can't
choose too many literals in that constraint to be false, but can do anything else.
The weights are equal and large-enough to dominate over the other part of the matchings' values.
Thus, there's a many-one correspondence between [solutions to the outputted instance of your problem] and [solutions to the input problem], although the output problem can easily have
more than one solution even when the constraint satisfaction problem has a unique solution.)


Since threshold constraints can implement clauses by letting the thresholds be 1,
it follows that if $\big[$there is a real number c such that ​ c < 1/2 ​ and there are arbitrarily-large
integers d such that for all integers b, there is an algorithm for [$\hspace{.02 in}$your problem with [$\hspace{.02 in}$left-side nodes
having degree d$\hspace{.02 in}$] and [right-side nodes having degree d-1] and ​ |E| < b$\cdot \hspace{-0.02 in}$k ] ​ whose runtime is
not eventually bounded below by ​ 2^{$\hspace{.02 in}$c$\hspace{.02 in}\cdot \hspace{-0.02 in}$k} $\big]$ ​ ​ then the corresponding strengthing of SETH is false.

For the same reason, high-power compression of the graph and/or the sets
would yield compression of [threshold-constraint]-SAT, and I'm
not aware of any feasibility results regarding such compression.
(Reminder: ​ Threshold constraints can implement clauses by letting the thresholds be 1.)

However, that does not say anything about compressing the weights, and independently:

Weighted set packing reduces to maximum-weight independent set with number of vertices equal to the number of sets (adjacent if and only if intersect). ​ Maximum-weight independent set reduces to your problem (incidence graph). ​ When the right-side nodes each have degree at most 1, your problem reduces to weighted set packing with the number of sets equal to the number of vertices.
(Remove sets with degree-zero nodes, remove sets with a pair of nodes adjacent to the same node, then replace each set with the set of left-side nodes adjacent to an element of the set
and weight those sets by the original sets' weight plus number of non-removed elements.)


Thus, when the right-side nodes each have degree at most 1, your problem can be
somewhat kernelized. ​ (That "somewhat kernelization" doesn't simplify the weights.)