1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $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$. $\endgroup$
    – Carser
    Aug 4, 2016 at 0:24

1 Answer 1

Reset to default
2
$\begingroup$

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:

enter image description here

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

enter image description here

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

enter image description here

$\endgroup$
5
  • $\begingroup$ Nice, thank you. Do you think you have any insight into why intuition pointing to equivalence is wrong? $\endgroup$
    – shadowtalker
    Aug 4, 2016 at 2:26
  • 1
    $\begingroup$ No idea. Intuition is different for everyone. When I looked at it my first thought was that it shouldn't be equivalent. $\endgroup$
    – Ian Miller
    Aug 4, 2016 at 2:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shagnik
    Aug 4, 2016 at 10:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shagnik
    Aug 4, 2016 at 10:13
  • $\begingroup$ @Shagnik thanks, that really clears it up. $\endgroup$
    – shadowtalker
    Aug 4, 2016 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.