Matching and Edge Cover in Temporal Graphs

We prove that Temporal Edge Cover restricted to $\tau =2$ is NP-complete by giving a reduction from 3-SAT(2,2). We first describe some (non temporal) graphs needed by our reduction, that have some edges marked (note that the marking is not the time labelling $\lambda$).

Graph $L_i$ is shown in Figure 4. Note that, since it has ten vertices and ten edges, its vertices can be covered using five edges in two ways, denoted by $E_{i,1}^{\prime }$ and $E_{i,2}^{\prime }$:

• $\mathrm{■}$

  $E_{i,1}^{\prime }$ contains both edges marked by $i$ and no edge marked by $-i$

• $\mathrm{■}$

  $E_{i,2}^{\prime }$ contains both edges marked by $-i$ and no edge marked by $i$

Given three integers $j$, $k$, $l$ we define the graph $T_{j,k,l}$, with edges marked $j$, $k$, $l$ as in Figure 4.

We use the graphs $L_i$ and $T_{i,j,k}$ to define an instance of Temporal Edge Cover with lifetime $2$ corresponding to an instance of 3-SAT(2,2). Consider an instance $F$ of 3-SAT(2,2) consisting of clauses $C_1$, …, $C_m$ over $n$ variables $x_1$, …, $x_n$. Recall that each $C_j$, $j\in [m]$ has three literals and each variable $x_i$, $i\in [n]$, appears in exactly two clauses as a positive literal and in exactly two clauses as a negative literal. We construct a corresponding temporal graph $𝒢$, with lifetime $\tau =2$, associated with $F$ as follows:

• $\mathrm{■}$

  At time $1$, $𝒢$ is defined as a graph $G_1$ that contains, for each variable $x_i$, $i\in [n]$, a cycle $L_i$, as defined in Definition 5. Note that these cycles are all vertex disjoint.

• $\mathrm{■}$

  At time $2$, $𝒢$ is defined as a graph $G_2$ that contains, for each clause $C_p$, $p\in [m]$, over variables $x_i$ ,$x_j$, $x_k$, with $i,j,k\in [n]$, a graph $T_{j,k,l}^p$ isomorphic to $T_{j,k,l}$. The marked edges of $T_{j,k,l}^p$ are defined as follows. First, $T_{j,k,l}^p$ shares marked edges with $L_q$, $q\in \{j,k,l\}$, in $G_1$. For each $q\in \{j,k,l\}$, if $x_q$ is positive in $C_p$, then $T_{j,k,l}^p$ and $L_q$ share an edge marked $q$, if $x_q$ is negative in $C_p$, then $T_{j,k,l}^p$ and $L_q$ share an edge marked $-q$. Note that we define a one-to-one correspondence between the marked edges of graphs $T_{j,k,l}^q$ and of the graphs $L_i$, since each $L_i$ has two edges marked $i$ and two edges marked $-i$, and a formula in 3-SAT(2,2) has precisely two positive occurrences of each variable $x_i$ and two occurrences of its negation. Thus, two distinct edges of $L_i$ with the same marking corresponds to two distinct edges of some $T_{i,j,k}^p$, $T_{i,j^{\prime },k^{\prime }}^r$.

The resulting temporal graph can be constructed in polynomial starting from an instance $F$ of 3-SAT(2,2). Using this reduction, we can prove that $F$ is satisfiable if and only if there exists an edge cover of $𝒢$ having at most $5n+6m$ edges. The idea behind the proof is that each $L_i$ can be covered with 5 edges by $E_{i,1}^{\prime }$ or $E_{i,2}^{\prime }$, while each $T_{j,k,l}^p$ must be covered using at least $6$ non marked edges, with $6$ being achieved only if at least one marked edge is part of the covering. Depending on which $E_{i,a}^{\prime }$ is used for the covering, true or false is assigned to the corresponding variable $x_i$.

We show that Temporal Edge Cover is NP-complete when the underlying graph is a tree by giving a reduction from Set Cover to Temporal Edge Cover.

Given an instance $(U,𝒮,k)$ of Set Cover, where $U=[n]$ and $𝒮$ consists of $m$ sets $S_1$,…, $S_m$ ($S_i\subseteq [n]$, for each $i\in [m]$, ), we construct a corresponding temporal graph $𝒢$ (see Figure 5). $𝒢$ has an underlying graph $G$ which is is a tree rooted in $r$; $r$ has $m$ children $x_1$, …, $x_m$, and each $x_i$ has a single child $y_i$, with $i\in [m]$. Function $\lambda$ associates time label to each edge as follows: $\lambda (x_i{y}_i)=S_i$ and $\lambda (r{x}_i)=U$, for each $i\in [m]$. The idea of the reduction is that each edge $x_i{y}_i$, $i\in [m]$, must be in a temporal edge cover, and that the temporal vertices $(r,j)$, $j\in [m]$, are covered by edges incident in $r$ that encode a set cover.

In this subsection we present an $\mathrm{𝖥𝖯𝖳}$ algorithm that finds the minimum cardinality of a temporal edge cover of $𝒢$. Note that we can assume, without loss of generality, that each temporal vertex of the temporal graph $𝒢$ can be covered by at least one edge. That is, we can assume that there are no independent temporal vertex in $𝒢$, since those would not need to be covered and can be ignored during the computation.

Let $𝒢=(G,\lambda )$ be a temporal graph and consider a nice tree decomposition $(T,{\{X_t\}}_{t\in V(T)})$, with $T$ rooted at $r$, of a $G$. For each $t\in V(T)$, let $G_t$ be the subgraph of $G$ containing all the vertices $v\in X_{t^{\prime }}$ for any $t^{\prime }$ in the subtree rooted at $t$. Also, for any $X\subseteq V(G)$, let $E(X)$ denote the set of edges with some endpoint in $X$ (formally, $E(X)=\{uv\in E(G)\mid u,v\in X\}$).

Given $R\subseteq V(G)$, we denote by $V^T(R)$ the set of temporal vertices $R\times [\tau ]$; for simplicity, we write $V^T(G)$ to denote $V^T(V(G))$. Given $S\subseteq E(G)$, we denote by $V^T(S)$ the set of temporal vertices which are endpoints of $S$, i.e., $V^T(S)={\bigcup }_{e\in S}\{(u,i)\mid i\in \lambda (e),u\in e\}$. Additionally, given $S\subseteq E(G)$ and $(u,i)\in V^T(G)$, we say that $S$ covers $(u,i)$ if there exists $e\in S$ such that $u\in e$ and $i\in \lambda (e)$. Observe that $S$ covers $V^T(S)$.

As is usual the case when using tree decomposition, we work with partial solutions, i.e., with sets of edges that only partially cover the temporal vertices of $G_t$. This is because we might cover some temporal vertex $(u,i)\in X_t\times [\tau ]$ only with an edge introduced later, i.e., with an edge $uv$ such that $v\notin V(G_t)$. Therefore, for each node of $T$, we keep track of the temporal vertices within $X_t\times [\tau ]$ that are covered and of the edges within $E(X)$ that are chosen. Formally, given $t\in V(T)$, for each $S\subseteq E(X_t)$ and each $C\subseteq X_t\times [\tau ]$ with $V^T(S)\subseteq C$, we define:

If there is no such set $S^{\prime }$, then $T_t(S,C)=+\mathrm{\infty }$. Essentially, the function gives the minimum cardinality of a partial edge cover $S^{\prime }$ for the temporal graph $(G_t,\lambda {\upharpoonright }_{E(G_t)})$ such that:

• $\mathrm{■}$

  $S$ is exactly the set of edges in $E(X_t)$ that are selected by $S^{\prime }$;

• $\mathrm{■}$

  $C$ is exactly the set of temporal vertices in $X_t\times [\tau ]$ covered by $S^{\prime }$. Observe that these must include the endpoints of the temporal edges related to the edges selected in $S$, and this is why we ask for $V^T(S)$ to be contained in $C$; and

• $\mathrm{■}$

  Each temporal vertex related to some vertex in $G_t\setminus X_t$ must be covered by $S^{\prime }$.

Observe that $T_r(\mathrm{\varnothing },\mathrm{\varnothing })$ gives us the minimum cardinality of a temporal edge cover for $𝒢$. In what follows, we show how to recursively compute $T_t(S,C)$ for each $t\in V(T)$, $S\subseteq E(X_t)$, and $C\subseteq (X_t\times [\tau ))$ with $V^T(S)\subseteq C$, depending of the type of node $t$.

• $\mathrm{■}$

  leaf: if $t$ is a leaf, then $T_t(\mathrm{\varnothing },\mathrm{\varnothing })=0$;

• $\mathrm{■}$

  introduce node: let $v\in V(G)$ be the vertex introduced by $t$ and $t^{\prime }$ be its only child. Also, let $D$ be the set of temporal vertices $(u,i)$ with $u\ne v$ covered by some edge incident to $v$. Formally, $D=V^T(S\cap {\delta }_G(v))\setminus (\{v\}\times [\tau ])$. Additionally, let $S^{\prime }=S\setminus {\delta }_G(v)$, $C^{\prime }=C\setminus (\{v\}\times [\tau ])$, and $k=|S\cap {\delta }_G(v)|$. We have that:

• $\mathrm{■}$

  forget node: let $v\in V(G)$ be the vertex forgotten by $t$ and let $t^{\prime }$ be its only child. Also, let $S^{\prime }={\delta }_G(v)\cap E(X_{t^{\prime }})$. Then:

  $$T_t(S,C)=\underset{\widehat{S}\subseteq S^{\prime }}{\min }{T}_{t^{\prime }}(S\cup \widehat{S},C\cup (\{v\}\times [\tau ])).$$

• $\mathrm{■}$

  join node: let $t_1$ and $t_2$ be the two children of $t$. By definition, we know that $X_{t_1}=X_{t_2}$. Then:

  $$T_t(S,C)=-|S|+\min \{T_{t_1}(S,C_1)+T_{t_2}(S,C_2)\mid C_1\cup C_2=C\text{ and }{V}^T(S)\subseteq C_1\cap C_2\}.$$

We show that Temporal Edge Cover cannot be approximated within factor $b\log \tau$, for any constant . We prove this result by giving an approximation preserving reduction from the Set Cover problem³³3In this section we consider the optimization version of Set Cover, thus we omit $k$ from the instance of the problem.. Consider an instance $(U,𝒮)$ of Set Cover, where $U=\{u_1,\mathrm{\dots },u_n\}$ and $𝒮=\{S_1,\mathrm{\dots },S_m\}$. We can assume $U=[n]$, therefore each $S_i$, $i\in [m]$ is a subset of $[n]$. We define a corresponding instance $𝒢=(G,\lambda )$ of Temporal Edge Cover as follows (see Figure 6):

Note that $𝒢$ has lifetime $\tau =n$. We now show the main properties of the reduction.

In this section we present an approximation algorithm for Temporal Edge Cover of factor $O(\log \tau )$. Given a temporal graph $𝒢=(G,\lambda )$, with lifetime $\tau$ and $G=(V,E)$, the algorithm assumes that the vertices are ordered – the specific order is not relevant – so we denote them as $v_1,\mathrm{\dots },v_n$. The approximation algorithm, described in Algorithm 1, computes an edge cover $E^{\prime }$ by greedily covering the uncovered temporal vertices of each vertex $v_i$, $i\in [n]$, following the order (first it covers the uncovered temporal vertices of $v_1$, then of $v_2$ and so on, until all the temporal vertices are covered). In order to cover the temporal vertices of each $v_i$, it applies the greedy algorithm of Set Cover on an instance that contains an element for each uncovered temporal vertex $(v_i,t)$ and a set, for each edge $v_i{v}_j\in E$, that covers $(v_i,t)$ for each $t\in \lambda (v_i{v}_j)$.

More precisely, consider the $i$-th iteration, $i\in [n]$, of Algorithm 1. Given the set $E^{\prime }$ of edges computed by the first $i-1$-iterations of the algorithm, we define an instance $(U^i,{𝒮}^i)$ of Set Cover, where $U^i$ is the universe set and ${𝒮}^i$ is a collection of sets over $U^i$. For each $i\in [n]$, the universe set $U^i$ is defined as

The collection of sets ${𝒮}^i$ is defined as ${𝒮}^i=\{S_{e_1}^i,\mathrm{\dots },S_{e_z}^i\}$, where $e_1$,…, $e_z$ are the edges incident in $v_i$ and each $S_h^i\subseteq [\tau ]$ is defined as $S_h^i=\{t\in [\tau ]\mid t\in \lambda (e_h)\}$.

Algorithm 1 marks each temporal vertex as covered when it adds to solution $E^{\prime }$ an edge that covers it.

Now, we show the correctness of Algorithm 1.

We show the NP-hardness of Temporal Matching restricted to lifetime 2 with reduction from 3-SAT(2,2) similar to the one given in Section 3.1. This reduction follows the same idea as that of Theorem 6. Indeed, we still use the graph $L_i$ defined in Definition 5 and showed in Figure 4. For this reduction we do not encode clauses with graphs isomorphic to $T_{j,k,l}$, but graphs isomorphic to $C_{j,k,l}$, shown in Figure 8. $C_{j,k,l}$ has three edges marked with integers $j$, $k$, $l$.

Let $F$ be an instance of 3-SAT(2,2), with $n$ variables $x_1,\mathrm{\dots },x_n$ and $m$ clauses $C_1,\mathrm{\dots },C_m$. We construct an associated temporal graph with lifetime $\tau =2$ defined in the following way. At time $1$, $𝒢$ contains a graph $G_1$ consisting of the disjoint union of cycles $L_i$, $i\in [n]$, one for each variable $x_i$. At time $2$, $𝒢$ contains a graph $G_2$ that for each clause $C_p$ over variables $x_j$, $x_k$ and $x_l$, $j,k,l\in [n]$, contains graph $C_{j,k,l}^p$ isomorphic to $C_{j,k,l}$. As in Section 3.1, the marked edges of $C_{j,k,l}^p$ are shared with cycles $L_i$, $i\in \{j,k,l\}$ that encode the variables $x_j$, $x_k$ and $x_l$. The shared marked edge between $C_{j,k,l}^p$ and $L_i$ has mark $-i$ if $x_i$ is negated in the clause, $i$ if the variable is positive in the clause. Note that $C_{j,k,l}^p$’s are build so that the marked edges of $L_i$ are in one-to-one correspondence with marked edges of $C_{j,k,l}$’s.

The correctness of the reduction follows from the fact that a maximum temporal matching of each $L_i$, $i\in [n]$, contains five edges, one including positively marked edges and one including negatively marked edges. This encodes an assignment to the variables. The temporal matching of each $C_{j,k,l}^p$ contains at most one unmarked edge. However, a temporal matching $M$ of $𝒢$ contains one unmarked edge of $C_{j,k,l}^p$ only if there is a marked edge shared by $C_{j,k,l}^p$ and some $L_i$ that does not belong to $M$. This encodes the fact that at least one literal of each clause must be satisfied. This reduction allows us to prove the following result.

We show a reduction from Set Packing to Temporal Matching. Given an instance $(U,𝒮,k)$ of Set Packing with $𝒮=\{S_1,\mathrm{\dots },S_n\}$ a collection of sets over a universe set $U$, we construct a temporal graph $𝒢=(G,\lambda )$ such that there exists $k$ disjoint sets in $𝒮$ if and only if there exists a temporal matching $M$ of $𝒢$ of size at least $k$. Without loss of generality, we assume that $U=[n]$ and that each $S_i\subseteq [n]$, for each $i\in [m]$.

$𝒢=(G,\lambda )$ is defined as follows (the resulting temporal is presented in Figure 8):

• $\mathrm{■}$

  $G$ is a tree rooted at a vertex $r$, which has $n$ children $x_1$, …, $x_n$

• $\mathrm{■}$

  For each $i\in [n]$, $\lambda (r{x}_i)=S_i$

The idea of the reduction is that since any pair of edges $r{x}_i$ and $r{x}_j$ of $𝒢$, where $i,j\in [n]$ and $i\ne j$, share vertex $r$, then they can be in a temporal matching only if they are defined in different times, thus they are related to two disjoint subsets $S_i$ and $S_j$ in an instance of Set Packing. Then, since Set Packing is NP-complete [9], we can prove the following result.

In this subsection we show an algorithm that finds the maximum cardinality of a temporal matching of $𝒢$ in $\mathrm{𝖥𝖯𝖳}$ time when parameterized by $\tau$ plus the treewidth. The approach follows the same idea as the Temporal Edge Cover one (see Section 3.3).

Again, let $𝒢=(G,\lambda )$ be a temporal graph and consider a nice tree decomposition $(T,{\{X_t\}}_{t\in V(T)})$ of $G$, with $T$ rooted at $r$. We use the same notation as the one used in Section 3.3. Given a matching $M\subseteq E(G)$ and a temporal vertex $(u,i)\in V^T(G)$, observe that $(u,i)$ can be covered by $M$ at most once, i.e., there is at most one edge $e\in M$ such that $u\in e$ and $i\in \lambda$. If such an edge exists, we say that $M$ saturates $(u,i)$.

We define the dynamic programming table $T_t$ related to each $t\in V(T)$ as follows. For each $N\subseteq E(X_t)$ and $C\subseteq V^T(X_t)$ with $V^T(N)\subseteq C$:

If there exists no such set $M$ (e.g., it could happen that no temporal matching saturates exactly $C$), then $T_t(N,C)=0$. Essentially, the function gives the maximum cardinality of a temporal matching $M$ for the temporal graph $(G_t,\lambda {\upharpoonright }_{E(G_t)})$ such that:

• $\mathrm{■}$

  $N$ is exactly the set of selected edges in $E(X_t)$;

• $\mathrm{■}$

  $C$ is exactly the set of temporal vertices in $V^T(X_t)$ saturated by $M$.

Because $G_r=G$, the value of $T_r(\mathrm{\varnothing },\mathrm{\varnothing })$ tells us the maximum cardinality of a temporal matching for $𝒢$. We show how to recursively compute $T_t(N,C)$ for each $t\in V(T)$, $N\subseteq E(X_t)$, and $C\subseteq V^T(X_t)$, depending on the type of node $t$.

• $\mathrm{■}$

  leaf: if $t$ is a leaf, then $T_t(\mathrm{\varnothing },\mathrm{\varnothing })=0$;

• $\mathrm{■}$

  introduce node: let $v\in V(G)$ be introduced by $t$ and let $t^{\prime }$ be its only child. Also, let $F=N\cap {\delta }_G(v)$ be the set of edges in $N$ incident to $v$. Then:

• $\mathrm{■}$

  forget node: let $v\in V(G)$ be forgotten by $t$ and let $t^{\prime }$ be its only child. To define the recursive function, let $𝒩$ contain every $\widehat{N}\subseteq {\delta }_G(v)\cap E(X_{t^{\prime }})$ such that $V^T(\widehat{N})\setminus (\{v\}\times [\tau ])\subseteq C$ and such that $\widehat{N}$ is a matching. In words, it contains every subset of edges of $E(X_{t^{\prime }})$ incident to $v$ whose other endpoints are temporal vertices within $C$, while also not having any edges sharing the same temporal vertices. Also, for any $\widehat{N}\in 𝒩$, let ${𝒞}_{\widehat{N}}$ contain every $\widehat{C}\subseteq \{v\}\times [\tau ]$ such that $V^T(\widehat{N})\cap (\{v\}\times [\tau ])\subseteq \widehat{C}$. Then

  $$T_t(N,C)=\max \{T_{t^{\prime }}(N\cup \widehat{N},C\cup \widehat{C})\mid \widehat{N}\in 𝒩\text{ and }\widehat{C}\in {𝒞}_{\widehat{N}}\}.$$

• $\mathrm{■}$

  join node: let $t_1$ and $t_2$ be the children of $t$. Recall that $X_{t_1}=X_{t_2}$. Then:

  $$T_t(N,C)=-|N|+\max \{T_{t_1}(N,C_1)+T_{t_2}(N,C_2)\mid C_1\cap C_2=V^T(N)\text{ and }{C}_1\cup C_2=C\}.$$