Brief Announcement: Exploring Word-Representable Temporal Graphs

We present a set of results on the problem of exploring word-representable temporal graphs. This combines research on word-representable graphs, temporal graphs, and graph exploration. We provide two primary results. First, we show that for any word-representable temporal graph where each timestep is a fully connected graph, we can construct an exploration schedule requiring at most $2\delta n$ timesteps, where $\delta$ is the minimum degree of any vertex in the graph and $n$ the number of vertices. Second, we show that for any word-representable temporal graph where the underlying graph is connected and the word representation requires at least $n(2dn+d)$ symbols, we can construct an exploration schedule requiring $2dn$ timesteps, where $d$ is the diameter of the graph, and $n$ the number of vertices.

While there is a large body of work on both word-representable graphs and exploration of temporal graphs, we highlight a small number of papers in both fields of particular relevance. Regarding word-representable graphs, we point first to the work of Kitaev and Pyatkin [12] who introduced word-representable graphs as a tool for semigroup theory. From the prespective of structural results on word-representable graphs, in [3], Courcelle shows that circle graphs are word-representable. Halldorson et al. [9] strengthen this by showing that comparability graphs and all $3$-colourable graphs a word-representable, as well as presenting communication from Limouzy that cover graphs are word-representable. On the negative side, Halldorson et al. show that it is NP-hard to determine if a given triangle free graph is word-representable.On the exploration of temporal graphs, we first mention the landmark paper by Erlebach et al. [7], which established many of the key ideas behind temporal graph exploration. In particular, they show a general $O(n^2)$ upper bound on the length of the fastest exploration schedule for a single agent on an always connected temporal graph. This is complemented by schedules of length $O(n^{1.5}{k}^{1.5}\log n)$ for graphs with treewidth $k$, $O(n^{1.8}\log n)$ for planar graphs, $O(n)$ for cycles with one chord, and $O(n{\log }^{3}n)$ for $2\times n$ grids. Building on this, Erlebach and Spooner showed in [8] that an always connected temporal graph in which each timestep is at most $k$-edges inactive can be explored in $O(kn\log n)$ timesteps.

We define a graph $G$ by a tuple containing a set $V$ of vertices, and set $E\subseteq V\times V$ of edges, each a pair of vertices. When writing an edge explicitly as $(v_i,v_j)$ we call $v_i$ the start point and $v_j$ the end point of the edge. We call two vertices $v_i,v_j\in V$ neighbours if $(v_i,v_j)\in E$. We denote by $N(v)=\{v^{\prime }\in V\mid (v,v^{\prime })\in E\}$ the set of neighbours of $v$.. The degree of a vertex $v\in V$, denoted $\mathrm{\Delta }(v)=|N(v)|$, is equal to the number of neighbours of $v$. A walk in a graph $G$ is an ordered sequence of edges, $e_1,e_2,\mathrm{\dots },e_k$ such that the end point of the $i^{th}$ edge is the start point of the ${(i+1)}^{th}$ edge. The start point of a walk is the start point of the first edge of the walk, and the end point of a walk is the end point of the last edge of the walk. Two vertices, $v_i$ and $v_j$, are connected if there exists some walk starting at $v_i$ and ending at $v_j$. We denote the set of all walks in a graph $G$ by $𝒲(G)$. The length of a walk $P=e_1,e_2,\mathrm{\dots },e_k$, denoted $|P|$ is the number of edges in the walk. A walk visits a vertex $v$ if there exists at least one edge $e$ such that $v\in e$. The distance between two vertices $v_i,v_j\in V$, denoted $\mathrm{dist}(v_i,v_j)$ is the walk of minimum length with $v_i$ as the start point and $v_j$ as the end point. We define the diameter of a graph as ${\max }_{v_i,v_j\in V}\mathrm{dist}(v_i,v_j)$.

A temporal graph $𝒢$ is a generalisation of a graph, defined over one set of vertices $V$, and $T$ sets of edges, $E_1,E_2,\mathrm{\dots },E_T$. We refer to the graph formed from the vertex set $V$ and the $t^{th}$ edge set, $E_t$, as the $t^{th}$ timestep, denoted $G_t=(V,E_t)$. The lifetime of a temporal graph $𝒢=(V,E_1,E_2,\mathrm{\dots },E_T)$ is equal to the number $T$ of edge sets in $𝒢$. The underlying graph of a temporal graph $𝒢=(V,E_1,E_2,\mathrm{\dots },E_T)$, denoted $U(𝒢)$, is the graph formed over the vertex set $V$ and the union of all edge sets, giving $U(𝒢)=(V,{\bigcup }_{t\in [1,T]}{E}_t)$. A temporal walk is an extension of a walk, with each step being an edge-time pair, $(e_1,t_1)(e_2,t_2)\mathrm{\dots }(e_k,t_k)$ such that, for every $i\in [1,k-1]$:

• $\mathrm{■}$

  the edge $e_i$ is active in the timestep $E_{t_i}$,

• $\mathrm{■}$

  the end point of $e_i$ is the start point of $e_{i+1}$, and,

• $\mathrm{■}$

  $t_{i+1}>t_i$.

Additionally, $e_k$ must be active in timestep $t_k$. Note that $t_{i+1}$ may be greater than $t_i+1$. In this case, assuming $e_i=(v_j,v_i)$, we say that an agent traversing this walk waits at $v_i$ for $t_{i+1}-t_i-1$ timesteps. A temporal walk $P=(e_1,t_1),(e_2,t_2),\mathrm{\dots },(e_k,t_k)$ visits a vertex $v$ iff there is some edge $e_i$ in the walk such that $v\in e_i$. The length of a temporal walk containing $k$ edges is equal to $t_k$.

An alphabet $\mathrm{\Sigma }=\{1,2,\mathrm{\dots },\sigma \}$ is a finite set of symbols. A word (also known as a string) $w$ is a finite sequence of symbols from a given alphabet. We assume, for the remainder of this paper, that our alphabet $\mathrm{\Sigma }$ is defined over some set of integers $1,2,\mathrm{\dots },\sigma$. The length of a word $w$, denoted $|w|$ is the number of letters in the word. For $i\in [1,|w|]$ let $w[i]$ denote the $i^{th}$ letter of $w$. The set of all finite words over the alphabet $\mathrm{\Sigma }$ is denoted by ${\mathrm{\Sigma }}^{\ast }$. Given $n\in {𝒩}_0$, let ${\mathrm{\Sigma }}^n$ denote all words in ${\mathrm{\Sigma }}^{\ast }$ exactly of length $n$. Given two words $w,v$, we denote by $wv$ the word formed by the concatenation of $w$ and $v$, i.e. the word such that $wv[i]=w[i]$, if $i\in [1,|w|]$ or $v[i-|w|]$ if $i\in [|w|+1,|w|+|v|]$. Given a word $w\in {\mathrm{\Sigma }}^{\ast }$ and natural $k\in {\mathbb{N}}_0$, let $w^k$ denote the word formed by $k$ copies of $w$, satisfying $|w^k|=k|w|$ and $w^k[i]=w[imod|w|]$, $\forall i\in [1,k|w|]$. Let $\mathrm{alph}(w)=\{𝚊\in \mathrm{\Sigma }\mid \exists i\in [|w|]$ s.t. $w[i]=𝚊\}$ be the alphabet of $w$.

Given a pair of words $u,w\in {\mathrm{\Sigma }}^{\ast }$ where $|u|\le |w|$, $u$ is a subsequence of $w$ if there exists some set of indices $i_1,i_2,\mathrm{\dots },i_{|u|}$ such that such that $u=w[i_1]w[i_2]\mathrm{\dots }w[i_{|u|}]$. Given a set of symbols $𝒮\subseteq \mathrm{\Sigma }$ and word $w\in {\mathrm{\Sigma }}^{\ast }$, the subsequence of $w$ ${\pi }_{𝒮}(w)$ satisfies ${\pi }_{𝒮}(w)\in {𝒮}^{\ast }$, and, $\forall u\in {𝒮}^{\ast }$ either $|u|\le |{\pi }_{𝒮}(w)|$ or $u$ is not a subsequence of $w$.

Given a word $w\in {\mathrm{\Sigma }}^{\ast }$, the graph represented by $w$, $G(w)$, is constructed as follows. Let $V=(v_1,v_2,\mathrm{\dots },v_n)$ be a set of $n$ vertices, each labelled uniquely by some symbol from $\mathrm{\Sigma }=1,2,\mathrm{\dots },n$. Informally, $G(w)$ contains the edge $(v_x,v_y)$ iff the symbols $x$ and $y$ alternate in $w$. A pair of symbols, $x,y\in \mathrm{\Sigma }$ alternate in $w$ if ${\pi }_{\{x,y\}}(w)\in \{{(xy)}^k,{(xy)}^{k}x,{(yx)}^k,{(yx)}^{k}y\mid k\in {\mathbb{N}}_0\}$. Thus, we define the edge set $E$ as the set $\{(v_x,v_y)\mid {\pi }_{\{x,y\}}(w)\in \{{(xy)}^k,{(xy)}^{k}x,{(yx)}^k,{(yx)}^{k}y\mid k\in {\mathbb{N}}_0\}\}$. A graph $G$ is word-representable if there exists some word $w$ such that $G(w)=G$.

Given a word $w\in {\mathrm{\Sigma }}^{\ast }$, the temporal graph represented by $w$, $TG(w)$, is constructed using $G(w)$ as a basis. To determine the timesteps, we introduce the set of indices $S_1,S_2,\mathrm{\dots },S_T\in [1,|w|]$ as the set of start points for each timestep. The value of each is computed recursively, with $S_1=1$, and $S_i$ the index such that $w[S_i]\in \mathrm{alph}(w[S_{i-1},S_i-1])$ and, $\forall S_{i^{\prime }}\in [S_{i-1},S_i-1],w[S_i^{\prime }]\notin \mathrm{alph}(w[S_{i-1}+1,S_{i^{\prime }-1}])$.

With this set of indices, the timestep $t$ is defined with regard to the symbols appearing in the factor $w[S_t,S_{t+1}-1]$ (or, $w[S_T,|w|]$ for the final timestep). Formally, given some edge $(v_x,v_y)$ in the edge set $E$ of $G(w)$, the edge $(v_x,v_y)\in E_t$ iff either $x\in \mathrm{alph}(w[S_t,S_{t+1}-1])$ (resp., $x\in w[S_T,|w|]$) or $y\in \mathrm{alph}(w[S_t,S_{t+1}-1])$ (resp., $y\in w[S_T,|w|]$). We call any factor of $w$ of the form $w[S_i,S_{i+1}-1]$ a timestep factor.