# Selecting the highest-weighted edges in a bipartite graph

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:

1. ($G1$) The subgraph with the $k$ highest-scoring vertices from $V_1$ and $V_2$.
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.

• $k$ is the number of vertices in a set, right? So $G1$ would be a subset of the $k^2$ vertices in $G2$. I believe the best way to find the sets is to simply sort the scores then take the best $k$ or $k^2$. Aug 4, 2016 at 0:24

I think I have found a counter example for you however I may have misinterpreted part of your question.

Note my $s_n$ uses integers but they could easily be scaled to $[0,1]$

Consider the following graph:

Taking $k=2$ highest weighted vertices from each half gives:

whereas the highest $k^2=4$ edges connects the following:

• Nice, thank you. Do you think you have any insight into why intuition pointing to equivalence is wrong? Aug 4, 2016 at 2:26
• No idea. Intuition is different for everyone. When I looked at it my first thought was that it shouldn't be equivalent. Aug 4, 2016 at 2:39
• For a more drastic counterexample, you could take all weights equal to $1$ on one side, and on the other side have one vertex of weight $1$ and the others of weight $0$. The $k^2$ highest scoring edges all have weight $1$, but if you choose $k$ vertices from each side, you can only have $k$ edges of positive weight. Aug 4, 2016 at 10:09
• To salvage your intuition, what is true is that you need not have more than $k+1$ vertices on both sides involved in the $k^2$ heaviest edges. If you rank the vertices by their score, in descending order: say $u_1, u_2, ..., u_r$ on one side and $v_1, v_2, ..., v_s$ on the other, then if $i < j$ and $l < m$, the edge $(u_i, v_l)$ will have score at least as big as $(u_j, v_m)$. Hence if you were to have a set of $k^2$ edges, with some edge $(u_i,v_j)$ where $i,j > k$, you would be able to replace it with some edge with smaller indices, without decreasing the total score. Aug 4, 2016 at 10:13
• @Shagnik thanks, that really clears it up. Aug 4, 2016 at 23:26