Abstract

A graph that changes with time is called a temporal graph. In this work, we focus on temporal graphs whose vertex sets are fixed while edge sets change in discrete time steps. We use n to refer to the number of vertices in the graph and τ to refer to the total number of time steps over which a temporal graph is observed. We refer to non-temporal graphs as static graphs when we wish to emphasize their unchanging nature.

In this work, we study temporal analogues of the Vertex Separator and Vertex Cover problems from the static world with an emphasis on the Vertex Separator problem. An (s,z)-temporal separator is a set of vertices whose removal disconnects vertex s from vertex z for every time step in a temporal graph. The (s,z)-Temporal Separator problem asks to find the minimum size of an (s,z)-temporal separator for the given temporal graph. The (s,z)-Temporal Separator problem is known to be NP-hard in general, although some special cases (such as bounded treewidth) admit efficient algorithms.

We introduce a generalization of this problem called (s,z,t)-Temporal Separator problem, where the goal is to find the smallest subset of vertices whose removal eliminates all temporal paths from s to z which take less than t time steps. Observe that setting t = τ captures the (s,z)-Temporal Separator problem as a special case of (s,z,t)-Temporal Separator problem.

We present a τ-approximation algorithm for (s,z)-Temporal Separator problem, and we convert it to a τ^2-approximation algorithm for (s,z,t)-Temporal Separator problem. We also present an inapproximability lower bound of Ω(ln(n) + ln(τ)) for (s,z,t)-Temporal Separator problem assuming that P ≠ NP.

We show a polynomial-time reduction from the Discrete Segment Covering problem with bounded-length segments to (s,z,t)-Temporal Separator where the temporal graph has bounded pathwidth.
Therefore, solving (s,z,t)-Temporal Separator on temporal graph whose underlying graph has bounded pathwidth is more difficult than solving Discrete Segment Covering problem where all segments' lengths are bounded.

Discrete segment cover is a set of unit-length intervals, which covers at least one of two endpoints of each input segment.

Lastly, we present a polynomial-time algorithm to find minimum (s,z,t)-temporal separator on temporal graphs whose underlying graph is a series-parallel graph or by removing the source and the terminal it is turned into a tree.

The second problem of interest is the Activity Timeline problem which is a generalization of a Vertex Cover to the temporal setting. An activity timeline is an assignment of time intervals to vertices. An edge between vertex u and vertex v is covered by an activity timeline φ at time t if one of the time intervals assigned to u or v includes the time t (this is required only if the edge is actually present at time t). In MinTimeline the goal is to find an activity timeline that covers all edges while minimizing the total length of time intervals. This problem is known to be NP-hard. In another problem, called MinTimeLine_m, we are asked to find an activity timeline subject to additional constraints specified by a set of prescribed times {m_v}, one for each vertex v. A valid activity timeline for MinTimeline_m must guarantee that for every vertex v the interval corresponding to v contains m_v. The goal is again to minimize the total length of time intervals. Prior to this work, the best known approximation algorithm for MinTimline_m problem was based on a rather complicated primal-dual linear programming approach and achieved 2 approximation.
In this work, we present a simple purely combinatorial 2-approximation algorithm for this problem.

The combinatorial algorithm is inspired by the famous Double Coverage algorithm for the k-Server problem on a line in the area of online algorithms.
This highlights an interesting cross-over between temporal graph algorithms and online algorithms that might require further investigation. Lastly, we present a polynomial-time algorithm for MinTimeline on temporal graphs whose underlying graphs have bounded treewidth.