11
Problem description
Vertices \$V\$ of directed graph \$G=(V,E)\$ represent gossipping ladies; edge \$(u,v) \in E\$ signifies that lady \$u\$ knows of lady \$v\$ (which does not imply that lady \$v\$ knows of lady \$u\$). Assume that each lady knows of herself.
Intuitively, lady \$a\$ gossips about every lady \$b\$ she knows about, except herself, to every other lady \$c\$ whom \$a\$ knows about (other than \$b\$ herself). Lady \$c\$, upon hearing gossip from lady \$a\$ about lady \$b\$, will learn about \$b\$ but not about \$a\$. For \$c\$, this then means two things:
- \$c\$ will from now on gossip about \$b\$ to all other ladies she knows about, and
- \$c\$ will from now on gossip to \$b\$ about all other ladies she knows about, except about her own self.
Formally, the Gossip Operation \$g(G)\$ produces a graph \$G' = (V, E')\$, where
$$E' = E \ \cup\ \{(c,b) \ \vert\ \exists\ (a,b) \in E : a \neq b \ \land\ \exists\ (a,c) \in E: c \neq b \}$$
(Added edges in red.)
The Gossip Closure of a graph \$G\$ is the fixed point of the Gossip Operation starting from \$G\$.
Example
Input:
a:{a,b,c,d}
b:{b,e}
c:{c,d}
d:{d}
e:{e}
f:{f,a}
g:{g}
Output:
a:{a,b,c,d}
b:{b,e,c,d}
c:{c,d,b,e}
d:{d,b,c,e}
e:{e,b,c,d}
f:{f,a}
g:{g}
Larger example
Loops not shown in graphs.
Task
Implement an algorithm of lowest possible time complexity, which given an directed unweighted graph* \$G\$ in any suitable format (viz. any format supporting directed unweighted graphs), outputs its Gossip Closure.
* You may impose certain limits on the input, eg. an upper bound on graph density if your solution is better suited for sparse graphs.
kyrill
Posted 2020-02-12T19:18:12.770
Reputation: 575
1Thanks for the challenge! Could you give an example of a graph and its Gossip Closure, to clarify the definition? Also, are self- loops allowed? Can b=c? – isaacg – 2020-02-12T20:17:09.010
I clarified the definition a bit: each vertex implicitly has a loop. I will add an example later. – kyrill – 2020-02-12T20:32:26.823
Just to verify;
Wouldn't that mean every lady gossips about herself? Do you mean to add another "other" in the first clause; "a gossips about every other lady b she knows about to all other ladies a knows about"? That way these relationships stay one-sided. – Mathgeek – 2020-02-12T20:45:36.167
@Mathgeek Yes, that's how it was intended. The condition that each lady knows of herself was added later and I forgot to update the definitions. I believe the definition is now complete. – kyrill – 2020-02-12T22:05:48.783
1Regarding "lowest possible time complexity", graph algorithm time complexities are often stated in terms of the number of edges and number of vertices. Algorithms may do differently on sparse graphs or dense graphs, or depending on the input representation (edge lists, adjacency matrix, etc). Could you clarify this? – xnor – 2020-02-13T06:49:46.063
1I think the math notation in the problem statement is too much and makes it intimidating, despite the good explanation in terms of gossip. Would it not work to say that the gossip closure of a graph G is the smallest graph G' that contains all the edges of G, and that whenever
(a,b)and(a,c)are edges of G', so is(b,c)? Though now having written that, it seems like all edges between pairs ofa,b,cend up in the closure this way. – xnor – 2020-02-13T07:02:02.170@xnor I agree that the formal problem statement may be intimidating to some, but without a rigorous mathematical definition it would be ambiguous or incomplete. As per complexity, any solution X which takes the same kind of input (eg. restructed to "dense" / "sparse" graphs) as some solution Y and has a lower complexity, wins over such Y. – kyrill – 2020-02-13T08:34:38.350
Frankly, I think this problem needs work before it's a good challenge. First, while you have clarified the winning criterion, @xnor's question about the lowest possible time complexity is still an issue. Moreover, the problem itself is pretty degenerate for most cases, as if $(a,b)$ and $(a,c)$ are edges in a graph, then $b\leftrightarrow c$ after one move. In other words, there is nothing that distinguishes $b$ from $c$. So, the general premise of any solution posted will be just taking combinations of nodes that are pointed to by one node, and adding bidirectional edges between these – Don Thousand – 2020-02-14T16:38:25.907
combinations. Not only does that mean that most graphs (including sparse ones) will become dense, but they will become dense in a way that is quite uninteresting from a programming standpoint, as any language with a well implemented combinatorial library can just plug and chug. – Don Thousand – 2020-02-14T16:39:42.310
1@DonThousand Firstly, "just taking combinations of nodes that are pointed to by one node, and adding bidirectional edges between these" will accomplish one step of the operation; I am interested in the closure. Secondly, the challenge I am posing here is not to "plug and chug" into some combinatorial library and arrive at a short but inefficient solution. The challenge is to come up with an efficient algorithm; the key words being "come up with" and "efficient". If that is uninteresting for you then leave it. – kyrill – 2020-02-14T18:51:36.300