pith. sign in

arxiv: 2604.27227 · v1 · submitted 2026-04-29 · 💻 cs.DS · cs.DM· math.CO

Designing sparse temporal graphs satisfying connectivity requirements

Thomas Bellitto , Jules Bouton Popper , Justine Cauvi , Bruno Escoffier , Rapha\"elle Maistre-Matus This is my paper

Pith reviewed 2026-05-07 08:52 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords temporal graphsconnectivityfeedback vertex setsparse networksNP-completenessreachability requestsgraph design
0
0 comments X

The pith

The minimum number of directed temporal arcs to satisfy given connectivity requests is exactly n minus the request graph's components plus its smallest directed feedback vertex set.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the minimum number of temporal edges needed to satisfy a given set of reachability requests encoded as a directed request graph. For directed temporal graphs the exact minimum is n minus the number of connected components in the request graph plus the size of its smallest directed feedback vertex set. The result shows the problem is NP-complete but fixed-parameter tractable. For undirected temporal graphs it gives a polynomial-time testable condition for when n-1 edges are sufficient when the request graph is strongly connected.

Core claim

The authors prove that in the directed case the number of temporal arcs required 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. It follows that the problem is NP-complete but inherits fixed parameter tractability properties of Directed Feedback Vertex Set. When the temporal graph is undirected they 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, which can be tested in polynomial time.

What carries the argument

The minimum directed feedback vertex set of the request graph, which gives the exact number of extra temporal arcs needed to satisfy the cyclic reachability requirements beyond a forest structure.

Load-bearing premise

The temporal model requires paths to have strictly increasing timestamps and the request graph precisely defines the pairs that need to be connected.

What would settle it

A request graph whose minimum satisfying temporal arc count differs from n - cc + dfvs, such as certain small graphs with cycles, would falsify the formula.

Figures

Figures reproduced from arXiv: 2604.27227 by Bruno Escoffier, Jules Bouton Popper, Justine Cauvi, Rapha\"elle Maistre-Matus, Thomas Bellitto.

Figure 1
Figure 1. Figure 1: A solution to the gossip problem with 2n − 4 edges. A label next to an edge corresponds to the appearance time of the edge. Every vertex can reach every other vertex by a path that uses edges with increasing appearance time. over time. More precisely, it is defined as a graph with each edge being equipped with a set of appearance times. Connectivity in this context is defined by journeys, that is a walk wh… view at source ↗
Figure 2
Figure 2. Figure 2: Request graph R (left), optimal solutions for MinCRS (center part) and for MinDCRS (right part). Note that if we were considering non strict paths/walks in temporal graphs, then in both CRS and DCRS we would use only one time step (all the edges/arcs would have the same appearance time), and then the problems would be equivalent to the problems in static graphs. In static graphs, the problems are trivial: … view at source ↗
Figure 3
Figure 3. Figure 3: Construction for a connected component C, with n vertices and a DFVS of size f, of a request graph R using n + f − 1 temporal arcs and satisfying the requests of R in C. Lemma 7. Let G be a temporal digraph, Reach(G) and G↓ have the same strongly connected components. Proof. • Suppose S ⊆ V is an SCC of Reach(G). Then for u, v ∈ S in G there is a sequence of directed journeys between u and v in both direct… view at source ↗
Figure 4
Figure 4. Figure 4: A request graph that admits a tree representation but does not view at source ↗
Figure 5
Figure 5. Figure 5: A request graph that is not walk-Helly. Example 18. Let us consider the request graph R depicted in view at source ↗
Figure 6
Figure 6. Figure 6: A strongly connected request graph R that is walk-Helly and whose set of authorized arcs is {(a, b),(b, a),(a, d),(d, a),(a, e),(e, a),(c, b),(b, c),(c, e),(e, c),(c, f),(f, c)} plus the arcs associated with forced edges. The arc (a, c) is not authorized: indeed, there is a closed walk (a, d, e, b, a) (so we have W(a, b, c)) and a closed walk (c, f, e, b, c) (so we have W(c, b, a)). As a matter of fact, on… view at source ↗
Figure 7
Figure 7. Figure 7: On the left, a request graph with n−1 forced edges forming a tree representation. In the middle, a topological order of the digraph described in the proof of Lemma 28. On the right, a tree solution for MinCRS. 22 view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the Connectivity Request Satisfaction problem: given a request graph encoding required reachability pairs, construct a temporal graph (directed or undirected) on the same vertices using the minimum number of temporal edges that realizes all requests under the standard strictly-increasing-timestamp model. For directed temporal graphs the central claim is that the minimum equals n - cc + dfvs, where cc is the number of (weakly) connected components of the request graph and dfvs is the size of its minimum directed feedback vertex set; the problem is therefore NP-complete yet FPT. For undirected temporal graphs the paper gives a polynomial-time-checkable characterization of the strongly-connected request graphs that admit a solution with exactly n-1 edges: any collection of pairwise non-vertex-disjoint closed walks must share a common vertex.

Significance. An exact closed-form bound linking temporal connectivity to DFVS would be a notable contribution, immediately yielding FPT algorithms and clarifying the gap between static and temporal sparsity. The undirected characterization is also of independent interest for gossip and temporal connectivity problems. Credit is due for framing the problem cleanly in terms of standard graph parameters and for the polynomial-time test in the undirected case. However, the directed bound appears incorrect, which substantially reduces the paper's significance.

major comments (2)
  1. [Abstract] Abstract (and the directed-formula theorem): the claimed minimum n - cc + dfvs is contradicted by the directed n-cycle request graph (cc = 1, dfvs = 1). For n = 3 the formula asserts exactly 3 temporal arcs suffice, yet no strictly increasing timestamp assignment to the three cycle arcs realizes all six required reachabilities; after traversing the path A→B→C the edge C→A cannot be followed by any earlier edge to reach B. A minimal construction requires 4 arcs (cycle plus one duplicated edge at a later timestamp). The +dfvs term therefore fails to compensate for the monotonicity constraint on cycles.
  2. [Directed-formula proof] Directed-formula proof (the section containing the proof of the n - cc + dfvs bound): the argument must be re-examined because any construction that realizes a strongly-connected request graph on a cycle must either duplicate arcs or add extra arcs beyond the DFVS size; the current bound therefore undercounts the temporal arcs required once timestamps are enforced to be strictly increasing.
minor comments (2)
  1. [Abstract] Abstract: 'connected component' should be clarified as weakly connected components of the underlying undirected graph, since the request graph is directed.
  2. The manuscript should explicitly state whether parallel temporal arcs (same u,v at distinct times) are permitted; the counter-example construction relies on them.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the flaw in the directed bound. We have verified the counterexample and agree that the claimed formula n - cc + dfvs does not hold under the strict timestamp model. We will revise the manuscript to correct the abstract, remove the incorrect theorem, and address the directed case.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the directed-formula theorem): the claimed minimum n - cc + dfvs is contradicted by the directed n-cycle request graph (cc = 1, dfvs = 1). For n = 3 the formula asserts exactly 3 temporal arcs suffice, yet no strictly increasing timestamp assignment to the three cycle arcs realizes all six required reachabilities; after traversing the path A→B→C the edge C→A cannot be followed by any earlier edge to reach B. A minimal construction requires 4 arcs (cycle plus one duplicated edge at a later timestamp). The +dfvs term therefore fails to compensate for the monotonicity constraint on cycles.

    Authors: We agree that the directed n-cycle request graph is a valid counterexample. With cc = 1 and dfvs = 1 the formula predicts n temporal arcs, but the strict increase requirement on timestamps means that a single traversal of the cycle cannot realize all reachability pairs; additional duplicated arcs with later timestamps are needed. We will revise the abstract to remove the incorrect claim and update the directed section. revision: yes

  2. Referee: [Directed-formula proof] Directed-formula proof (the section containing the proof of the n - cc + dfvs bound): the argument must be re-examined because any construction that realizes a strongly-connected request graph on a cycle must either duplicate arcs or add extra arcs beyond the DFVS size; the current bound therefore undercounts the temporal arcs required once timestamps are enforced to be strictly increasing.

    Authors: The referee is correct that the existing proof does not properly account for the monotonicity constraints on cycles. We will re-examine the section, withdraw the n - cc + dfvs claim, and either derive a corrected bound or provide an alternative characterization for the directed case. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bound uses independent standard parameters

full rationale

The paper states a theorem equating the minimum temporal arcs to n - cc + dfvs, with cc and dfvs defined as standard properties of the request graph (connected components and minimum directed feedback vertex set). These are external graph invariants with no dependence on the temporal construction or timestamps. No equation or step reduces the claimed optimum to a fitted quantity, self-definition, or self-citation chain. The NP-completeness and FPT inheritance follow from the reduction to an independently studied problem (DFVS). The undirected characterization (condition on pairwise non-vertex-disjoint closed walks) is likewise an independent combinatorial property testable in polynomial time. No load-bearing step collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard definition of temporal graphs and time-respecting paths together with ordinary directed-graph notions; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • domain assumption Connectivity in a temporal graph is defined via the existence of paths whose edge timestamps are strictly increasing.
    This is the conventional model invoked throughout the abstract for all reachability claims.

pith-pipeline@v0.9.0 · 5584 in / 1211 out tokens · 34700 ms · 2026-05-07T08:52:45.498056+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Akrida, Leszek Gasieniec, George B

    Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs.Theory Comput. Syst., 61(3):907–944, 2017

    work page 2017

  2. [2]

    Tem- poral Connectivity Augmentation

    Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier. Tem- poral Connectivity Augmentation. In4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025), volume 330 ofLeib- 24 niz International Proceedings in Informatics (LIPIcs), pages 3:1–3:16, 2025

    work page 2025

  3. [3]

    Canadian traveler problems in temporal graphs

    Thomas Bellitto, Johanne Cohen, Bruno Escoffier, Minh-Hang Nguyen, and Mika¨ el Rabie. Canadian traveler problems in temporal graphs. InGraph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, pages 33–47, 2025

    work page 2025

  4. [4]

    Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks.Int

    Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing Shortest, Fastest, and Foremost Journeys in Dynamic Networks.Int. J. Found. Comput. Sci., 14(2):267–285, 2003

    work page 2003

  5. [5]

    R. Bumby. A problem with telephones.Siam Journal on Algebraic and Discrete Methods, 2:13–18, 1981

    work page 1981

  6. [6]

    Edge exploration of tem- poral graphs.Algorithmica, 85(3):688–716, 2022

    Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of tem- poral graphs.Algorithmica, 85(3):688–716, 2022

    work page 2022

  7. [7]

    Realization of Temporally Connected Graphs Based on Degree Sequences

    Arnaud Casteigts, Michelle D¨ oring, and Nils Morawietz. Realization of Temporally Connected Graphs Based on Degree Sequences. In36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:18, 2025

    work page 2025

  8. [8]

    Foremost, fastest, shortest: Temporal graph realization under various path metrics

    Justine Cauvi, Nils Morawietz, and Laurent Viennot. Foremost, fastest, shortest: Temporal graph realization under various path metrics. In 43rd International Symposium on Theoretical Aspects of Computer Sci- ence, STACS 2026, Grenoble, France, March 9-13, 2026, LIPIcs, pages 24:1–24:19, 2026

    work page 2026

  9. [9]

    A fixed-parameter algorithm for the directed feedback vertex set problem.J

    Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Raz- gon. A fixed-parameter algorithm for the directed feedback vertex set problem.J. ACM, 55(5):21:1–21:19, 2008

    work page 2008

  10. [10]

    Optimizing reachability sets in temporal graphs by delaying.Inf

    Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying.Inf. Comput., 285(Part):104890, 2022

    work page 2022

  11. [11]

    Stuart E. Dreyfus. An Appraisal of Some Shortest-Path Algorithms. Operations Research, 17(3):395–412, 1969

    work page 1969

  12. [12]

    Enright, Kitty Meeks, George B

    Jessica A. Enright, Kitty Meeks, George B. Mertzios, and Viktor Za- maraev. Deleting edges to restrict the size of an epidemic in temporal networks.J. Comput. Syst. Sci., 119:60–77, 2021. 25

    work page 2021

  13. [13]

    Graphs with prescribed degrees of ver- tices.Mat

    Paul Erd˝ os and Tibor Gallai. Graphs with prescribed degrees of ver- tices.Mat. Lapok, 11:264–274, 1960

    work page 1960

  14. [14]

    Recognizing and realizing temporal reachability graphs

    Thomas Erlebach, Othon Michail, and Nils Morawietz. Recognizing and realizing temporal reachability graphs. In33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15- 17, 2025, LIPIcs, pages 93:1–93:18, 2025

    work page 2025

  15. [15]

    Parameterized Al- gorithms for Multi-Label Periodic Temporal Graph Realization

    Thomas Erlebach, Nils Morawietz, and Petra Wolf. Parameterized Al- gorithms for Multi-Label Periodic Temporal Graph Realization. In3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), volume 292 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:16, 2024

    work page 2024

  16. [16]

    Hypergraphes arbor´ es.Discrete Mathematics, 21(3):223–227, 1978

    Claude Flament. Hypergraphes arbor´ es.Discrete Mathematics, 21(3):223–227, 1978

    work page 1978

  17. [17]

    Hypertrees and their host trees: a survey, 2025.arXiv:2504.15570

    Pablo De Caria Di Fonzo. Hypertrees and their host trees: a survey, 2025.arXiv:2504.15570

    work page arXiv 2025

  18. [18]

    G¨ obel, J

    F. G¨ obel, J. Orestes Cerdeira, and H. J. Veldman. Label-connected graphs and the gossip problem.Discrete Math., 87(1):29–40, 1991

    work page 1991

  19. [19]

    Hajnal, E

    A. Hajnal, E. C. Milner, and E. Szemer´ edi. A cure for the telephone disease.Canadian Mathematical Bulletin, 15(3):447–450, 1972.doi: 10.4153/CMB-1972-081-0

    work page doi:10.4153/cmb-1972-081-0 1972

  20. [20]

    Louis Hakimi and S

    S. Louis Hakimi and S. S. Yau. Distance matrix of a graph and its realizability.Quarterly of Applied Mathematics, 22:305–317, 1965

    work page 1965

  21. [21]

    Hedetniemi, Stephen T

    Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liest- man. A survey of gossiping and broadcasting in communication net- works.Networks, 18(4):319–349, 1988

    work page 1988

  22. [22]

    Richard M. Karp. Reducibility among combinatorial problems. InPro- ceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103, 1972

    work page 1972

  23. [23]

    Kleinberg, and Amit Kumar

    David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks.J. Comput. Syst. Sci., 64(4):820–842, 2002

    work page 2002

  24. [24]

    Mertzios, Hendrik Molter, and Paul G

    Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spi- rakis. The complexity of computing optimum labelings for temporal connectivity.J. Comput. Syst. Sci., 146:103564, 2024. 26

    work page 2024

  25. [25]

    Mertzios, Hendrik Molter, and Paul G

    Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spi- rakis. Temporal graph realization from fastest paths.Theoretical Com- puter Science, 1056:115508, 2025

    work page 2025

  26. [26]

    Spanner Enumeration for Temporal Graphs

    Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner Enumeration for Temporal Graphs. In4th Symposium on Al- gorithmic Foundations of Dynamic Networks (SAND 2025), volume 330 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:21, 2025

    work page 2025

  27. [27]

    Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul G

    George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Temporal network optimization subject to connec- tivity constraints. InAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 ofLecture Notes in Computer Sci- ence, pages 657–668, 2013

    work page 2013

  28. [28]

    Mertzios, Hendrik Molter, Nils Morawietz, and Paul G

    George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spi- rakis. Realizing temporal transportation trees. InGraph-Theoretic Con- cepts in Computer Science - 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11-13, 2025, Revised Selected Papers, Lecture Notes in Computer Science, pages 390–404, 2025

    work page 2025

  29. [29]

    Mertzios, Hendrik Molter, Nils Morawietz, and Paul G

    George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spi- rakis. Temporal graph realization with bounded stretch. In50th In- ternational Symposium on Mathematical Foundations of Computer Sci- ence, MFCS 2025, Warsaw, Poland, August 25-29, 2025, LIPIcs, pages 75:1–75:19, 2025

    work page 2025

  30. [30]

    Di- rected Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

    Julia Meusel, Matthias M¨ uller-Hannemann, and Klaus Reinhardt. Di- rected Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases. In25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025), volume 137 ofOpen Access Series in Informatics (OASIcs), pages 3:1– 3:22, 2025

    work page 2025

  31. [31]

    Spirakis

    Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs.Theoretical Computer Science, 634:1–23, 2016

    work page 2016

  32. [32]

    Efficient Algorithms for Temporal Path Computation

    Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient Algorithms for Temporal Path Computation. IEEE Transactions on Knowledge and Data Engineering, 28(11):2927– 2942, 2016. 27

    work page 2016