Designing sparse temporal graphs satisfying connectivity requirements
This work provides theoretical foundations and complexity results for designing sparse temporal graphs with partial connectivity constraints, relevant to network design and gossip theory.
This paper studies the minimum number of temporal edges needed to satisfy partial connectivity requirements in temporal graphs, introducing the Connectivity Request Satisfaction problem. For directed temporal graphs, the optimal number of temporal arcs is n - cc + dfvs, where cc is the number of connected components of the request graph and dfvs is the size of its smallest directed feedback vertex set, making the problem NP-complete but fixed-parameter tractable. For undirected temporal graphs, they characterize when n-1 edges suffice for strongly connected request graphs and provide a polynomial-time test.
Connectivity of temporal graphs has been widely studied both as graph theory and as gossip theory. In particular, it is well known that in order to connect every vertex to every other, a temporal graph needs to have at least $2n-4$ edges where $n$ is the number of vertices. This paper investigates the optimal number of edges required to satisfy partial connectivity requirements. We introduce the problem of Connectivity Request Satisfaction where we are given a directed graph that we call the request graph, where an arc from $u$ to $v$ means that we need to be able to go from $u$ to $v$. Our goal is to build a temporal graph on the same vertex set with as few temporal edges as possible that would satisfy all the requests. When the graph we build is directed, we prove that the number of temporal arcs required is $n-\mathrm{cc}+\mathrm{dfvs}$ where $\mathrm{cc}$ is the number of connected component of the request graph and $\mathrm{dfvs}$ is the size of its smallest directed feedback vertex set. It follows that the problem is NP-complete but inherits fixed parameter tractability properties of Directed Feedback Vertex Set. When the graph we build is undirected, we establish a characterization of strongly connected request graphs that admit a solution with $n-1$ edges: it is possible if and only if any set of pairwise non-vertex-disjoint closed walks all share a common vertex. We prove that this criteria can be tested in polynomial time.