Concluding Remarks

In this paper we studied the associated influence digraphs of time-stamped graphs, especially their realizability. Our motivating examples of collaboration graphs are undirected, as an edge represents a collaboration between two authors, and hence each is influenced by the other. In some situations, however, a collaboration between two persons may induce a one-way influence; for example a student may be influenced by but not influence her stodgy supervisor. In this case, the time-stamped graph may be a directed graph, with parallel arcs allowed. (As before, one may usually take the time-stamps in such a time-stamped digraph to be distinct.) Clearly time-stamped digraphs apply to modeling distributed computing as well.

Since this setting gives more freedom in the realizability problem, it is not surprising that it inherits results from the undirected case. For example, the next result follows from Corollary 3.2 with the checking of a few small cases.

Theorem 6.1   For every integer $t$ in $[1,m(m+1)]$, there exists $(G,c)$ where $G$ is a digraph with $m+1$ vertices such that $G^{\rm I}_c$ has $t$ arcs.

We define $p^{\mbox{\tiny\rm d}}$ similar to $p$. Given a digraph $D=(V,A)$, let

$$p^{\mbox{\tiny\rm d}}(D)=\min\;\{\;\vert V(H^{\rm I}_c)\vert-\vert V(D)\vert:\mbox{$D$\ is an induced subdigraph of $H^{\rm I}_c$}\;\},$$

where the minimum is taken over all time-stamped digraphs $(H,c)$.

Problem 6.2   Find $p^{\mbox{\tiny\rm d}}(D)$ for a given digraph $D$.

Of course, $p^{\mbox{\tiny\rm d}}(D)\leq p(D)$. Because of the extra freedom in time-stamped digraphs, this problem seems to be somewhat easier, as we can find more natural classes of digraphs with $p^{\mbox{\tiny\rm d}}$ being 0. For example, if $G$ is an undirected chordal graph, viewed as a symmetric digraph, then $p^{\mbox{\tiny\rm d}}(G)=0$. This follows from the next result.

Theorem 6.3   Let $D=(V,A)$ be a digraph with $p^{\mbox{\tiny\rm d}}(D)=0$. Let $S$ be a set of vertices of $D$ that induce an undirected clique. Let $D'$ be the digraph obtained from $D$ by adding a new vertex $u$ and by adding the arcs $(u,v)$ and $(v,u)$ for all $v\in S$. Then $p^{\mbox{\tiny\rm d}}(D')=0$.

Proof. Let $S=\{v_1,v_2,\ldots,v_k\}$. Start with a time-stamped digraph on $V$ whose associated influence digraph is $D$. Now add $(u,v_i)$ for every $i$, with distinct time-stamps larger than all time-stamps already used, and add $(v_i,u)$ for every $i$, with distinct time-stamps smaller than all time-stamps already used. It is easy to check that $D'$ is the associated influence digraph of this time-stamped digraph. $\qedsymbol$

Corollary 6.4   Let $G$ be a chordal graph. Then $p^{\mbox{\tiny\rm d}}(G)=0$.

Proof. The proof follows from an inductive argument using Theorem 6.3 and the simplicial elimination ordering for chordal graphs (see [4], p. 198). $\qedsymbol$

Corollary 6.5   Let $G=(V,E)$ be a graph such that $G\setminus e$ is chordal for some $e\in E$. Then $p^{\mbox{\tiny\rm d}}(G)\leq 1$ and $p^{\mbox{\tiny\rm d}}(G^u)=0$, where $G^u$ is obtained from $G$ by adding a new vertex $u$ and by adding the arcs $(u,v)$ and $(v,u)$ for all $v\in V$.

Proof. Let $a$ and $b$ be the endpoints of (undirected) edge $e$. Obtain a time-stamped digraph on $V$ whose associated influence digraph is $G\setminus e$ by applying Corollary 6.4. Now add $u$ to it and add $(u,a)$ and $(u,b)$ using large distinct time-stamps, and add $(a,u)$ and $(b,u)$ using small distinct time-stamps. This shows that $p^{\mbox{\tiny\rm d}}(G)\leq 1$. Now for every $w\not\in\{a,b\}$, we add $(u,w)$ with even smaller distinct time-stamps, and add $(w,u)$ with even larger distinct time-stamps. $\qedsymbol$

There are many interesting open questions. We close by stating some of them.

1. Is computing $p(D)$ ${\mathcal N}{\mathcal P}$-hard, or is determining whether $p(D)=0$ ${\mathcal N}{\mathcal P}$-complete?
2. Instead of seeking the minimum number of extra vertices needed to generate a given set of influences, one can ask for the minimum number of edges required. In particular, if a given parameter value is realizable, one may want to find a time-stamped graph with the smallest number of edges that realizes it. Of course, asking for the minimum number of edges required (and not requiring $c$ to be injective) is the classical gossip problem when the given parameter is the complete graph.
3. In many of our constructions (e.g., Proposition 4.8 and Theorem 5.7), we needed only a few distinct time-stamps to achieve the desired results. This might correspond to collaborations over a short time span. What digraphs can be obtained with restrictions like this?

Acknowledgment. We are grateful to the anonymous referees for a number of helpful comments and excellent suggestions that improved the paper, in particular, the short proof of Theorem 3.1.