Extending Ghouila-Houri’s Characterization of Comparability Graphs to Temporal Graphs

Suppose there exists a directed non-monolabel triangle $abc$ in $O$. Then, necessarily there exists an edge $ab$ with maximum time-label value in the triangle which is adjacent to another edge, say $bc$, such that $\lambda (ab)>\lambda (bc)$ and $\lambda (ca)\le \lambda (ab)$. But this contradicts $O$ being QTTO. Now, for the second item, if $O$ is QTTO and acyclic then, in particular, it does not contain any directed triangle and thus is TTO. Suppose $O$ is QTTO but not acyclic and let $C$ be a minimal directed cycle. There must exist along the cycle two consecutive arcs $(a,b)$ and $(b,c)$ such that $\lambda (ab)\le \lambda (bc)$. Since $O$ is QTTO, either $(a,c)$ or $(c,a)$ belong to $O$. The first case would produce a shorter directed cycle, contradicting the minimality of $C$, so we can assume $(c,a)\in O$. But then we get a directed triangle and thus $O$ is not TTO. $◀$

We now define the implication graph of a temporal graph $𝒢$, that will encode the forcing rules between arcs in a QTTO described in the introduction.

Observe that $O$ is a QTTO if and only if for each arc from $(a,b)$ to $(c,b)$ in $Imp(𝒢)$, $(a,b)\in O$ implies $(c,b)\in O$. As we have seen, this implication digraph is not enough to capture the TTO forcing relations because of monolabel triangles. This is why we will augment this digraph using a four-vertex configuration, called correlated monolabel triangle.

For any correlated monolabel triangle $(a,b,c,d)$, it is not difficult to see that there is a directed path $(b,c)(d,c)(d,b)(a,b)$ in $Imp(𝒢)$. Therefore, in any TTO, the presence of $(b,c)$ forces the presence of $(a,b)$. Since a TTO cannot contain the directed triangle $abc$, it follows that if $(b,c)$ is an arc of a TTO, then so will be $(a,c)$. Based on this observation, we propose the following definition.

The following lemma is a direct consequence of the definition of the arcs of $Imp(𝒢)$ and $Aug(𝒢)$. It reflects the law of contraposition if we think of the vertices of $Aug(𝒢)$ as Boolean variables, as in the introduction.

The additional restrictions captured by $Aug(𝒢)$ do not follow directly from the definition of temporal transitive orientations. However, as we have seen before, if $(x,y)$ forces $(u,v)$, then any TTO of $𝒢$ that contains $(x,y)$ must also contain $(u,v)$. In other words, every TTO is an ATTO. Again the converse is not true (consider a monolabel directed triangle), but the main theorem of this section (Theorem 16) will provide the desired analogue of Ghouila-Houri’s theorem: a temporal graph admits a $TTO$ if and only if it admits an $ATTO$.

The definition of the augmented implication digraph $Aug(𝒢)$ immediately implies the following useful lemma.

Since $Imp(𝒢)$ is a subgraph of $Aug(𝒢)$ it is clear that every ATTO is a QTTO. The converse is not true, as one can take as an example the QTTO represented in Figure 1, which is not ATTO as $abc$ is a directed triangle belonging to a correlated monolabel triangle.

The following definition will play a crucial role in establishing the equivalence between admitting a TTO and an ATTO.

Consider $(x,y)\in Ness(𝒢)$ and assume $(x,y)$ forces $(u,v)$. By Lemma 7 $(v,u)$ forces $(y,x)$, and by definition of $\mathrm{Ness}(𝒢)$ $(y,x)$ forces $(x,y)$. Hence $(v,u)$ forces $(u,v)$ and thus $Ness{(𝒢)}^{+}=Ness(𝒢)$. Now if $O$ is an ATTO of $𝒢$, since an arc and its reverse cannot be both in $O$, all arcs in $Ness(𝒢)$ must be contained in $O$. $◀$

By Lemma 3, any TTO is acyclic, so if a temporal graph $𝒢$ admits a TTO, then the arcs in $Ness(𝒢)$ must induce an acyclic orientation in $𝒢$. In fact, the key ingredient to prove that $𝒢$ admits a TTO if and only if it admits an ATTO will be the observation that both conditions are equivalent to $Ness(𝒢)$ containing no directed cycle. Note that the fact that $Ness(𝒢)$ is acyclic for any comparability temporal graph directly implies that the graph represented in Figure 1 does not admit any TTO, as it is not difficult to see that the three arcs $(a,b),(b,c),(c,a)$ are all in $Ness(𝒢)$.

Let us now propose two lemmas, reminiscent of a statement called the Triangle Lemma in [9], that will be central in the proof of our main theorem.

Let $uvw$ be a directed triangle in $O$. Since every ATTO is a QTTO, by Lemma 3, $uvw$ is necessarily monolabel and we denote by $t$ be the common time-label. We will distinguish cases on whether the arc from $(a,b)$ to $(u,v)$ is an arc in $Imp(𝒢)$ or not, and whether $a=u$ or $b=v$.

1. i)

   Let $a=u$ and $((u,b),(u,v))$ be an arc of $Imp(𝒢)$. Then, $\lambda (ub)\ge \lambda (uv)$ and either $bv\notin E$ or . But now, $wub$ is a directed path with $\lambda (wu)\le \lambda (ub)$. Since $O$ is ATTO, we must have $wb\in E$ with $\lambda (wb)\ge \lambda (ub)\ge t$. It is not possible to orient $wb$ from $w$ towards $b$ in $O$, as it would create the time-respecting directed path $vwb$ and by hypothesis $bv\notin E$ or , which would contradict $O$ being ATTO. We conclude that $(b,w)\in O$, which implies triangle $ubw=abw$ is directed.

2. ii)

   Let $b=v$ and $((a,v),(u,v))$ be an arc of $Imp(𝒢)$. For this second case, $\lambda (av)\le t$ and either $au\notin E$ or . Since $O$ is ATTO and $avw$ is a time-respecting directed path, we must have $aw\in E$ and $\lambda (aw)\ge t$. Suppose $aw$ is oriented from $a$ towards $w$ in $O$ and consider the directed path $awu$. Since $au\notin E$ or and, once again, $O$ is ATTO, we must have $\lambda (aw)>t$. Then, the quadruple $(u,v,w,a)$ forms a correlated monolabel triangle. But this is a contradiction by Lemma 9 since triangle $uvw$ is directed in $O$, an ATTO. Hence, $aw$ must be oriented from $w$ towards $a$ in $O$, forming the directed triangle $avw=abw$.

3. iii)

   Let $a=u$ and $((u,b),(u,v))$ be an arc of $Aug(𝒢)$ but not of $Imp(𝒢)$. For this case to be produced, we claim the existence of a vertex $x$ such that $(b,v,u,x)$ is a correlated monolabel triangle: as $(v,u)$ forced $(b,v)$ in $Imp(G)$, arcs $((v,u),(b,u))$ and $((u,b),(u,v))$ were added to $Aug(G)$. Suppose $(v,x)\in O$. Since $O$ is ATTO and $vxu$ form a directed path with $\lambda (xu)>\lambda (vu)$, this forces $(u,x)\in O$ which in turn forces $(w,x)\in O$ with $\lambda (wx)\ge \lambda (ux)>t$. But then, $vwx$ forms a time-respecting path with $\lambda (wx)>t$ and $\lambda (vx)\le t$, a contradiction to $O$ being ATTO. Hence, $(x,v)\in O$. Then, necessarily $(b,v)\in O$ and $wx\in E$ with $\lambda (wx)\ge t$. Suppose $(w,x)\in O$, then $vwx$ must form a monolabel triangle. That is, $\lambda (xv)=\lambda (wx)=t$. But then, both possible orientations $(u,x)$ and $(x,u)$ of $xu$ lead to a contradiction as the triplet $uwx$ would fail to satisfy the ATTO conditions. Therefore, we claim $(x,w)\in O$. Also, we deduce $(x,u)\in O$ as otherwise $xuw$ would form a non-monolabel directed triangle. As $wub$ form a monolabel directed path, either $(w,b)$ or $(b,w)$ belong to $O$, with $\lambda (bw)\ge t$. If $(w,b)\in O$, we obtain a correlated monolabel triangle $(b,v,w,x)$ directed in an ATTO, a contradiction by Lemma 9. Finally, if $(b,w)\in O$ we have found our directed triangle $ubw=abw$.

4. iv)

   Let $b=v$ and $((a,v),(u,v))$ be an arc of $Aug(𝒢)$ but not of $Imp(𝒢)$. Similarly to the previous case, there must exist a vertex $x$ such that $(u,a,v,x)$ is a correlated monolabel triangle. As observed when such quadruples were defined, since $(a,v)$ belongs to $O$, then so do $(x,v)$, $(x,a)$ and $(u,a)$. Consider the monolabel directed path $avw$. As $O$ is ATTO, $aw\in E$ with $\lambda (aw)\ge t$. Notice that if $(a,w)\in O$, then $uaw$ is a directed triangle and if $(w,a)\in O$, then triangle $wav$ is directed. As $O$ is ATTO, the only way for it to contain a directed triangle is for it to be monolabel, we deduce $\lambda (aw)=t$. Assume for contradiction that $aw$ is oriented from $a$ towards $w$. Then, the directed path $xaw$, with $\lambda (xa)\le \lambda (aw)$, implies the existence of an edge $xw$ such that $\lambda (xw)\ge t$. It cannot be oriented from $w$ towards $x$ because it would create a non-monolabel directed triangle $wxv$. Therefore, $(x,w)\in O$. Since by hypothesis $ux\notin E$ or , if $\lambda (xw)=t$, $O$ would fail being ATTO. Hence, $\lambda (xw)>t$. But now, $(u,a,w,x)$ form a correlated monolabel triangle directed in $O$, a contradiction by Lemma 9.

$◀$

As $(a,b)$ forces $(u,v)$, there exists a directed path from $(a,b)$ to $(u,v)$ in $Aug(𝒢)$. Then, we can repeatedly apply Lemma 12 starting from the second to last arc in the directed path, i.e., arc directly forcing $(u,v)$, until reaching arc $(a,b)$. At each step, we get a new directed triangle containing an arc forced by the immediately previous arc in the path, this allows us to continue to apply Lemma 12. When reaching arc $(a,b)$, Lemma 12 will finally guarantee that $abw$ is also a directed triangle in $O$. $◀$

Assume by contradiction that $uvw$ is a directed triangle in $O$ such that $(u,v)\in Ness(𝒢)$. Then, as $(v,u)$ forces $(u,v)$, there exists a directed path $\mu$ in $Aug(𝒢)$ from $(v,u)$ to $(u,v)$. By Lemma 7, $Aug(𝒢)$ will also contain the “contraposite” path of $\mu$, that is the path ${\mu }^{\prime }$ from $(v,u)$ to $(u,v)$ consisting of all arcs $((y_2,x_2),(y_1,x_1))$ such that $((x_1,y_1),(x_2,y_2))$ is an arc in $\mu$. Let $(x,y)$ be the first node in $\mu$ such that $(x,y)\in O$. Since $O$ is ATTO, all nodes in the subpath of $\mu$ from $(x,y)$ to $(u,v)$ will also be included in $O$. Consider $(x^{\prime },y^{\prime })$ the node immediately before $(x,y)$ in $\mu$. As $(x^{\prime },y^{\prime })\notin O$, necessarily $(y^{\prime },x^{\prime })\in O$. Also, $(y^{\prime },x^{\prime })$ belongs to ${\mu }^{\prime }$, and therefore forces $(u,v)$ in $Aug(𝒢)$. Then, both $(y^{\prime },x^{\prime })$ and $(x,y)$ are arcs in $O$ forcing arc $(u,v)$ in $Aug(𝒢)$ and we can apply Lemma 13 twice to state that $y^{\prime }{x}^{\prime }w$ and $xyw$ are two directed triangles in $O$. But now, since $((x^{\prime },y^{\prime }),(x,y))\in Aug(𝒢)$, either $x^{\prime }=x$ or $y^{\prime }=y$. If $x^{\prime }=x$, the directed triangle $y^{\prime }xw$ implies $(x,w)\in O$ while the directed triangle $xyw$ supposes the inverse orientation, i.e., $(w,x)$. If $y^{\prime }=y$, we get a similar conflict with the orientation of edge $wy$. We conclude that triangles $y^{\prime }{x}^{\prime }w$ and $xyw$ cannot be both directed in $O$ and reach a contradiction. $◀$

In the lemma below, we generalize to ATTO a property previously established for TTO: no directed cycle in an ATTO of a temporal graph $𝒢$ is formed exclusively by arcs in $Ness(𝒢)$.

Assume by contradiction that $Ness(𝒢)$ induces a directed cycle in $O$ and let $C$ be a minimal such cycle. Let $O$ be an ATTO of $𝒢$ and recall that, by Lemma 11, $Ness(𝒢)\subset O$. Since $O$ is ATTO, by Lemma 14, we get $|C|>3$. We prove first that $C$ is monolabel, assume for contradiction this is not the case. Then, there must exist two consecutive arcs $(a,b)$ and $(b,c)$ in $C$ such that . As $O$ is ATTO, $(a,c)\in O$ with $\lambda (ac)\ge \lambda (bc)>\lambda (ab)$ and thus $(b,c)$ forces arc $(a,c)$ in $Aug(𝒢)$. Since $(b,c)\in Ness(𝒢)$, by Lemma 11, $(a,c)\in Ness(𝒢)$. Hence, we reached a smaller directed cycle induced by $Ness(𝒢)$, which contradicts $C$ being the minimal one. $C$ is therefore monolabel and we denote by $v_1,\mathrm{\dots },v_k$ its vertices. As $O$ is ATTO and $v_1{v}_2{v}_3$ form a monolabel directed path in $O$, then necessarily $v_1{v}_3\in E$. If $(v_3,v_1)\in O$, we have found a directed triangle $v_1{v}_2{v}_3$ such that $(v_2,v_3)\in C$, a contradiction to Lemma 14. Then, $(v_1,v_3)\in O$. If $\lambda (v_1{v}_3)>t=\lambda (v_2{v}_3)=\lambda (v_1{v}_2)$, then $(v_2,v_3)$ forces $(v_1,v_3)$ in $Aug(𝒢)$ and thus, by Lemma 11, $(v_1,v_3)\in Ness(𝒢)$, yielding a directed cycle formed by arcs in $Ness(𝒢)$ shorter than $C$, a contradiction. Hence $\lambda (v_1{v}_3)=t=\lambda (v_3,v_4)$ and we can repeat the same argument with vertices $v_1,v_3$ and $v_4$ to get $(v_1,v_4)\in O$ with $\lambda (v_1{v}_4)=t$. Hence, in order to avoid creating a directed triangle $v_1{v}_i{v}_{i+1}$ with $(v_i,v_{i+1})\in C$, necessarily $(v_1,v_i)\in O$ for all $i$ such that . But then, $v_{k-1}{v}_k{v}_1$ form a directed triangle with $(v_{k-1},v_k)\in C\subset Ness(𝒢)$, contradicting again Lemma 14. $◀$

We are now ready to prove our main result.

The implication from $i)$ to $ii)$ is straightforward as all TTO are ATTO and the one from $ii)$ to $iii)$ is proved by Lemma 15. To prove the implication from $iii)$ to $i)$, we will mimic the proof provided by Hell et al. in [10] for the static case, by using an analogous lexicographic argument. The proof will provide a simple algorithm to decide whether a given temporal graph $𝒢$ is a comparability temporal graph and construct a TTO of $𝒢$ if the answer is YES, as detailed in Subsection 3.2. Let $O$ be a partial ATTO of $𝒢$ containing $Ness(𝒢)$. We start by showing that taking any edge $ab$ not yet oriented in $O$, ensures that $O^{\prime }=O\cup {\{(a,b)\}}^{+}$ will also be an ATTO of $𝒢$. As $O$ is ATTO, it is clear that $O^{\prime +}=O^{\prime }$ holds. Assume for contradiction that $O^{\prime }\cap O^{\prime R}\ne \mathrm{\varnothing }$, i.e., there exists a pair of vertices $u,v$ such that $\{(u,v),(v,u)\}\subset O^{\prime }$. Since $O$ is ATTO, both arcs cannot belong to $O$, so assume $(u,v)\in {\{(a,b)\}}^{+}$. It is not possible that $(v,u)\in {\{(a,b)\}}^{+}$ as well, as this would imply $(b,a)\in {\{(u,v)\}}^{+}$ and thus $(b,a)\in {\{(a,b)\}}^{+}$, meaning $(b,a)\in Ness(G)$ which contradicts the assumption of edge $ab$ being not yet oriented in $O$. Hence, $(v,u)\in O$. Observe that $(u,v)\in {\{(a,b)\}}^{+}$ implies $(b,a)\in {\{(v,u)\}}^{+}$. But now, since $O^{+}=O$, we must have $(b,a)\in O$, again contradicting the assumption of $ab$ unoriented in $O$. As $Ness(𝒢)$ induces an acyclic digraph, there exists an order $\sigma$ on the vertices of $𝒢$ such that all arcs in $Ness(𝒢)$ are oriented forward, i.e., if $(u,v)\in Ness(𝒢)$ then $u{\prec }_{\sigma }v$. We propose to construct an orientation $O$ in a greedy lexicographic fashion, following the order defined by $\sigma$. We initially set $O=Ness(𝒢)$. Then, while $O$ is not yet a complete orientation of $𝒢$, we repeat what follows. We consider the unoriented edge $ab$, with $a{\prec }_{\sigma }b$, such that it is lexicographically minimal with respect to $\sigma$, and we add ${\{(a,b)\}}^{+}$ to $O$. By the observation above, as $O$ was initially an ATTO of $𝒢$ containing $Ness(𝒢)$, the final orientation obtained by this procedure will also be ATTO. It remains to show that $O$ does not contain directed triangles. Assume by contradiction it contains at least one, and consider the monolabel directed triangle $uvw$ that is lexicographically minimal with respect to the position in $\sigma$ of its three vertices. Then, $uvw$ contains at least one arc oriented backwards by $\sigma$, without loss of generality take $(u,v)$ as this backward arc with $v{\prec }_{\sigma }u$. Since it was oriented backwards, $(u,v)\notin Ness(𝒢)$ and it is not possible that $(u,v)$ was chosen as next unoriented edge $ab$ in the algorithm above. Hence, the orientation of $(u,v)$ was assigned because $(u,v)\in {\{(a,b)\}}^{+}$ for some edge $ab$, chosen as minimal unoriented edge at some step in our greedy algorithm. As at this step $uv$ was also an unoriented edge, this implies that $ab$ is lexicographically smaller that $uv$. But now, since there is a directed path from $(a,b)$ to $(u,v)$ in $Aug(𝒢)$, by applying Lemma 13, we get that $abw$ is also a directed triangle in $O$, contradicting the lexicographic minimality of $uvw$. $◀$