INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does the receiving centroid of T have <= K vertices?

Let v be an arbitrary vertex in a graph G = (V,E). Vertex v is to receive a unique message from each other vertex w in V, subject to the following constraints: (i) messages are communicated/relayed to v by a series of two-person, local phone calls over the edges of G, and (ii) each phone call requires only one time unit to convey all of the messages known by the two parties at that time. When each message finally arrives at the destination v, record the time it took to get there and add it to a running sum of receiving times. You are to minimize the sum of times it takes for v to receive each message. Can you construct an algorithm for computing the minimum total receiving time for an arbitrary vertex in an arbitrary tree T? The receiving centroid of a graph consists of the set of vertices whose sum of receiving times are a minimum. Can you construct an algorithm for finding the receiving centroid of an arbitrary tree T? The NP-completeness of this problem has not been settled. NOTE: Cheston has constructed a linear algorithm for finding the receiving center of an arbitrary tree, where the receiving center is defined in terms of the minimum number of time units required for a vertex to receive all messages.

INSTANCE: A tree T = (V,E), a positive integer K.

QUESTION: Does the polling centroid of T have <= K vertices?

In this problem a vertex v in a graph G = (V,E) must poll all of the vertices in the graph, i.e. it must broadcast a query to each vertex and then receive a response from each vertex. You are to sum the times it takes to send a query and receive a response from each vertex. This sum is to be minimized over all polling schemes originating at v and is called the polling sum for vertex v. The polling centroid consists of the set of vertices in a graph whose polling sums are a minimum. Can you construct an algorithm to find the polling centroid of an arbitrary tree, or equivalently, can you construct an algorithm for computing the polling sum of an arbitrary vertex v in an arbitrary tree T? The NP-completeness of this problem has not been settled. Cheston and Hedetniemi [1984] have constructed a linear algorithm for finding the polling center of an arbitrary tree, where the polling center is defined in terms of the minimum number of time units for the a vertex to send a query and receive responses from every vertex. [G.A. Cheston and S.T. Hedetniemi, Polling in tree networks, Congr. Numer. 41 (1984), 7-20]

INSTANCE: A graph G = (V,E) and positive integers M and K.

QUESTION: Does there exist a sequence of vertex subsets S₁,S₂,...,S_K', for some K' <= K, such that:

(i) |S_i| <= M, for every i, 1 <= i <= K';

(ii) |S_i+1 - S_i| = 1;

(iii) the vertex w in S_i+1 - S_i is adjacent to a vertex in S_i;

(iv) the union of the S_i equals V?

INSTANCE: A graph G = (V,E).

QUESTION: Can destructive gossiping be completed in G?

Let the edges of a connected graph G represent the allowable, local calls which can be made in a communications network. During a call over a given edge the two vertices exchange all information that they know at that time. After this call is completed, however, the edge is destroyed and cannot be used again. Is it possible for all vertices to broadcast their unique message to all other vertices (all-to-all broadcasting, or gossiping) if each edge can be used only once?

INSTANCE: A graph G = (V,E), a positive integer K.

QUESTION: Does the broadcast center of G contain <= K vertices?

In this problem a given vertex in a graph G is to broadcast a message to every other vertex in the graph. This is to be accomplished by a series of local, two-party phone calls over the edges of G, subject to the constraints that: each phone call takes one unit of time; no vertex can be involved in more than one phone call per unit of time; and all information transmission is error-free. The broadcast number of a vertex is the minimum number of time units that is takes to broadcast its message to every vertex. The broadcast center of G is the set of vertices whose broadcast times are a minimum. Slater, Cockayne and Hedetniemi have constructed a linear algorithm for finding the broadcast center of an arbitrary tree. As far as I know, no other broadcast center algorithm is known. [P.J. Slater, E.J. Cockayne and S.T. Hedetniemi, Information dissemination in trees, SIAM J. Comput. 10 (1981) 692-701]

INSTANCE: A 3X3X3 grid G = (V,E), a positive integer K.

QUESTION: Can gossiping be completed in G in time <= K?

This isn't so much a complexity question as it is simply the observation that no one knows how long it takes to gossip in the 3X3X3 grid.