Solving Gossip Problems using Answer Set Programming: An Epistemic Planning Approach

The gossip problem is described by Hedetniemi et al. in their survey [10] as follows: Gossiping refers to the information dissemination problem that exists when each member of a set A of n individuals knows a unique piece of information and must transmit it to every other person. The problem is solved by producing a sequence of unordered pairs (i, j), i, j A, each of which represents a phone call made between a pair of individuals, such that during each call the two people involved exchange all of the information they know at that time; and such that at the end of the sequence of calls, everybody knows everything. Such a calling sequence, which completes gossiping among the n people, is called complete. The gossip problem has been studied by many researchers, in particular, in the context of communication networks. While the most widely studied variant is the following optimization problem: M Minimize the number of calls in a complete calling sequence.