11
\$\begingroup\$

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 \}$$

Gossip Operation
(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

Original graph

After one iteration

Closure

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks 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? \$\endgroup\$ – isaacg Feb 12 at 20:17
  • \$\begingroup\$ I clarified the definition a bit: each vertex implicitly has a loop. I will add an example later. \$\endgroup\$ – kyrill Feb 12 at 20:32
  • 1
    \$\begingroup\$ Regarding "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? \$\endgroup\$ – xnor Feb 13 at 6:49
  • 1
    \$\begingroup\$ I 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 of a,b,c end up in the closure this way. \$\endgroup\$ – xnor Feb 13 at 7:02
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – kyrill Feb 14 at 18:51

Your Answer

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

Browse other questions tagged or ask your own question.