Maximum bipartite matching with extra reward for covering certain sets
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 &lt; 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| &lt; 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.)