This is a real business problem; my apologies if it's trivial or seems like a homework question.
Setup
Consider a fully-connected, bipartite graph $G$ between two vertex sets $V_1$ and $V_2$.
Each vertex set has an associated collection of weights or "scores" $S(V_1)$ and $S(V_2)$ where $S(V_n) = \{s_n(v) : v \in V_n\}$, and $s_n$ is a function mapping $V_n$ to $[0, 1]$.
The edges $E$ also have an associated score that is the product of the scores of the individual vertices; that is, $S(E) = \{s_1(v_1) \cdot s_2(v_2) : (v_1, v_2) \in V_1 \times V_2 \}$.
Question
Consider two particular sub-graphs:
- ($G1$) The subgraph with the $k$ highest-scoring vertices from $V_1$ and $V_2$.
- ($G2$) The subgraph with the $k^2$ highest-scoring edges.
Are $G1$ and $G2$ equivalent?
My intuition says that they should be, and I haven't been able to come up with a counterexample. But I'm not sure where to start in proving it.
Ultimately I'm interested in finding the best-scoring graph that contains at most $k$ elements from each of $V_1$ and $V_2$; if there's some "best" way to achieve this goal I'd appreciate pointers in the comments.