On the Hardness of Finding Temporally Connected Subgraphs of Any Size

Arnaud Casteigts; Christian Komusiewicz; Nils Morawietz

arxiv: 2604.23226 · v1 · submitted 2026-04-25 · 💻 cs.CC

On the Hardness of Finding Temporally Connected Subgraphs of Any Size

Arnaud Casteigts , Christian Komusiewicz , Nils Morawietz This is my paper

Pith reviewed 2026-05-08 06:54 UTC · model grok-4.3

classification 💻 cs.CC

keywords temporal graphstemporally connected subgraphsNP-hardnessapproximation hardnessparameterized complexitytemporal reachabilityclosed temporal componentsgraph girth

0 comments

The pith

Deciding whether a temporal graph contains a temporally connected subgraph on at least three vertices is NP-hard in every standard model.

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

The paper proves that the existence question for a temporally connected subgraph of size at least three is NP-hard in directed and undirected temporal graphs, under both strict and non-strict edge timing rules. The proofs rely on polynomial-time reductions from established NP-complete problems that keep the chronological reachability intact. A sympathetic reader would care because the result draws a sharp line between closed temporal components, which are hard even at tiny sizes, and open temporal components, whose maximal versions can be recovered efficiently. The same reductions also deliver inapproximability bounds and finish the parameterized picture for exact size k.

Core claim

Deciding the existence of a temporally connected subgraph on at least 3 vertices is NP-hard in directed and undirected temporal graphs under both strict and non-strict semantics. These results follow from simple and proper reductions that also yield new hardness of approximation and parameterized results, as well as structural theorems about the existence of large TC graphs without nontrivial TC subgraphs and TC graphs of arbitrary girth.

What carries the argument

Polynomial-time reductions from classic NP-complete problems to the TC-subgraph decision problem that preserve temporal-path reachability in each of the four standard temporal-graph models.

If this is right

The size of the largest TC subgraph cannot be approximated within a factor of (1-ε)n in directed temporal graphs.
The size cannot be approximated within a factor of (1-ε)n/2 in undirected temporal graphs.
The parameterized complexity status of finding a TC subgraph of exact size k is now complete for all four models.
Arbitrarily large temporally connected graphs exist that have constant lifetime yet contain no nontrivial TC subgraphs.
Temporally connected graphs exist that have arbitrarily large girth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Detecting small closed temporal groups inside real time-stamped networks may require exponential effort in the worst case.
The tractability gap between closed and open components suggests that definitions of temporal communities could usefully allow paths to exit the set.
The same reduction techniques are likely to apply to related questions such as finding dense or highly reachable temporal subgraphs.

Load-bearing premise

The reductions from known NP-hard problems map solutions back and forth while producing valid temporal graphs whose chronological reachability matches the original instances.

What would settle it

A polynomial-time algorithm that, given any temporal graph in any of the four models, correctly answers whether a temporally connected subgraph on three or more vertices exists would falsify the hardness claim.

read the original abstract

Temporal graphs are graphs whose edges are only present at certain points in time. Reachability in these graphs relies on temporal paths, where edges are traversed chronologically. A temporal graph that offers all-pairs reachability is said to be temporally connected (or TC). For temporal graphs that are not TC, a natural question is whether they admit a TC subgraph (a.k.a. closed temporal component) of a given size $k$. This question was one of the earliest in the field, shown to be NP-hard by Bhadra and Ferreira in 2003. We strengthen this result dramatically, showing that deciding if a TC subgraph exists on at least $3$ vertices is already NP-hard in all the standard temporal graph settings (directed/undirected and strict/non-strict through simple and proper reductions). This implies a strong separation between closed temporal components and open temporal components (where temporal paths can travel outside the component), for which inclusion-maximal components can be found in polynomial time. As a by-product, our reductions strengthen a number of existing results and establish new derived results. They imply that the size of the largest TC subgraph cannot be approximated within a factor of $(1-\epsilon)n$ in directed graphs, and within a factor of $(1-\epsilon)\frac{n}{2}$ in undirected graphs. One of the reductions also completes the complexity landscape for TC subgraphs of size exactly $k$ when parameterized by $k$ (answering the missing non-strict case). Finally, on the structural side, our results imply that there exist arbitrarily large TC graphs of constant lifetime without nontrivial TC subgraphs, and we also show that there exist TC graphs of arbitrary girth, both facts being of independent interest.

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.

Desk Editor's Note private letter to a colleague

The paper tightens the 2003 NP-hardness for temporally connected subgraphs down to size 3 in all four standard models and fills the remaining parameterized gap for non-strict exact-k.

read the letter

The core result is that deciding whether a temporal graph has a temporally connected subgraph on at least three vertices is already NP-hard for directed and undirected graphs under both strict and non-strict semantics. The reductions are from standard NP-complete problems and are written out explicitly in the full text, with separate gadgets for each of the four cases that keep temporal paths from leaking around the intended structure. This gives a clean separation from open temporal components, which remain polynomial-time solvable for maximal ones. As side effects the same constructions yield strong inapproximability (no (1-ε)n factor in the directed case, no (1-ε)n/2 in the undirected case) and finish the parameterized complexity map for exact k when the non-strict model was still open. The structural observations about constant-lifetime TC graphs without nontrivial subcomponents and about arbitrary girth are clean bonuses that follow directly from the same instances. The reductions look internally consistent and match the abstract claims; the stress-test note confirms they are self-contained and preserve the temporal properties without hidden assumptions. The only minor softness is that the approximation factors are not proved tight, which is typical for this style of paper and does not affect the main hardness statements. No circularity or invented parameters appear. This work is aimed at researchers who design or analyze algorithms for connectivity queries in time-varying networks. Anyone who needs lower bounds for closed temporal components or who works on parameterized algorithms for temporal graphs will want the updated landscape. It is worth sending to peer review because the reductions are explicit, the four cases are handled uniformly, and the strengthenings are concrete rather than incremental.

Referee Report

0 major / 2 minor

Summary. The paper proves that deciding whether a temporal graph has a temporally connected (TC) subgraph on at least 3 vertices is NP-hard in all four standard models (directed/undirected × strict/non-strict). It supplies explicit, self-contained polynomial-time reductions from established NP-complete problems (with direct if-and-only-if proofs that a size-3 TC subgraph exists in the constructed instance precisely when the source instance is yes), strengthening the 2003 Bhadra-Ferreira result. Corollaries include inapproximability of the maximum TC-subgraph size within (1-ε)n (directed) and (1-ε)n/2 (undirected), completion of the parameterized complexity landscape for exact size k, and structural statements on the existence of arbitrarily large constant-lifetime TC graphs without nontrivial TC subgraphs and of TC graphs of arbitrary girth.

Significance. The explicit reductions constitute a clear technical strength, allowing independent verification and immediately yielding multiple derived results on approximation, parameterization, and structure. The separation between closed and open temporal components is cleanly established, and the structural corollaries are of independent interest. The work is a solid, proportionate strengthening of a known hardness result rather than an incremental improvement.

minor comments (2)

The introduction could briefly recall the precise definition of a temporal path (including the distinction between strict and non-strict) before stating the main theorem, to improve accessibility for readers outside the subfield.
A small illustrative example (one reduction gadget drawn with time labels) would help readers verify the temporal-path constraints at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the clear summary of our contributions, and the recommendation to accept. We are pleased that the explicit reductions, their implications for approximation and parameterization, and the structural corollaries were recognized as strengths.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's core derivation consists of explicit polynomial-time reductions from independently established NP-complete problems (such as those cited from the 2003 Bhadra-Ferreira result and standard graph problems) to the decision problem of existence of a temporally connected subgraph of size at least 3, handled separately for each of the four temporal graph models. These reductions are presented with direct if-and-only-if proofs that preserve temporal properties via time-label assignments and gadgets, without any self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations. The strengthening of prior results and derived claims (approximability, parameterization, structural facts) follow directly from the new reductions rather than reducing to the paper's own inputs by construction. The argument chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of polynomial-time reductions from standard NP-complete problems (e.g., 3-SAT or clique variants) to the temporal subgraph decision problem in each model; no free parameters or invented entities are introduced.

axioms (1)

standard math NP-completeness of the source problems used in the reductions (standard complexity assumptions)
Invoked implicitly when stating that the reductions establish NP-hardness.

pith-pipeline@v0.9.0 · 5622 in / 1108 out tokens · 47196 ms · 2026-05-08T06:54:09.950864+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

the temporal graphG1 obtained fromP by adding a vertexαand edges{20,α}and{8,α} with labels fulfillingr<λ({20,α})<λ({8,α})<b,

work page
[2]

the temporal graphG2 obtained fromP by adding a vertexα, a vertexα′, and edges{20,α}, {α,α′}, and{α′,8}with labels fulfillingr<λ({20,α})<λ({α,α′})<λ({α′,8})<b,

work page
[3]

the temporal graphG3 obtained fromP by adding a vertexωand edges{ω,1}and{ω,8} with labels fulfillingr<λ({ω,8})<λ({ω,1})<b, and

work page
[4]

The four temporal graphs defined in Lemma B.5 are sketched in Figure 5

the temporal graphG4 obtained fromP by adding a vertexω, a vertexω′, and edges{ω,1}, {ω′,ω}, and{ω′,8}with labels fulfillingr<λ({ω′,8})<λ({ω′,ω})<λ({ω,1})<b. The four temporal graphs defined in Lemma B.5 are sketched in Figure 5. 3 Here, the set oftime-edgeis defined as{(e,t )|e∈E(G),t∈λ(e)}. Note that a simple temporal graph has as many edges as it has t...

work page
[5]

For each path connector gadgetPc, we add the edge{tc,α}to G′, wheretc is the sink ofP c

work page
[6]

3.For eachcon u,v∈Vcon, we add the edge{outu,conu,v}toG′

For each vertexv∈V\{α,α′}, we add an edge{v,outv}toG′(called theout-edge ofv). 3.For eachcon u,v∈Vcon, we add the edge{outu,conu,v}toG′. 4.For eachcon u,v∈Vcon, we add the edge{conu,v,inv}toG′. 5.For each vertexv∈V\{ω,ω′}, we add an edge{inv,v}toG′(called thein-edge ofv)

work page
[7]

This completes the definition of the underlying graphG′

For each path connector gadgetPc, we add the edge{ω,sc}toG′, wheresc is the source ofP c. This completes the definition of the underlying graphG′. Some of the edges incident with vertices ofVin∪Vout∪Vcon are depicted in Figure 7. ▶Observation C.2.G ′has a girth of5. We complete the construction by defining the labels of the edges. To this end, we define s...

work page
[8]

3.For each(x,y)∈Acon, we add the edge{outx,iny}toG′

For each vertexv∈V\{α,α′}, we add an edge{v,outv}toG′(called theout-edge ofv). 3.For each(x,y)∈Acon, we add the edge{outx,iny}toG′. 4.For each vertexv∈V\{ω,ω′}, we add an edge{inv,v}toG′(called thein-edge ofv). 5.For eachc∈Vin∪Vout, we add the edge{ω,sc}toG′, wheresc is the source ofPc. This completes the definition of the underlying graphG′. ▶Observation...

work page
[9]

Thus, Claim D.5 implies thatP5 visits only vertices ofV

/∈Acon. Thus, Claim D.5 implies thatP5 visits only vertices ofV. Now focus on the edges ofG[V ]incident with v∗ 3 and v∗

work page
[10]

Asv∗ 3 and v∗ 5 are not adjacent, P5 traverses{v∗ 3,v∗ 8}at time11

Each such edge incident withv∗ 5 has a label of at least4and{v∗ 3,v∗ 8}is the only such edge incident withv∗ 3 that receives a larger label. Asv∗ 3 and v∗ 5 are not adjacent, P5 traverses{v∗ 3,v∗ 8}at time11. For P5 to arrive atv∗ 8 prior to time11, P5 has to start with(v∗ 5,v∗ 6,v∗ 7,v∗ 8)(see Figure 8). This implies thatS contains all vertices from{α,α′...

work page
[11]

▷ Claim D.17.Let i∈[8,k−8]with imod 6 = 2, such thatS containsv∗ i−2andv∗ i

For the inductive case, consider the following claim. ▷ Claim D.17.Let i∈[8,k−8]with imod 6 = 2, such thatS containsv∗ i−2andv∗ i. Then, Scontains at least one vertex ofVℓfor eachℓ∈[i+ 1,i+ 6]. Proof. AsG[S]is temporally connected, there is a temporal pathPi from v∗ i to v∗ i−2inG[S]. We show thatPi = (v∗ i,v∗ i+1,v∗ i+2,xi+3,v∗ i+4,v∗ i+5,v∗ i+6,v∗ i−2)f...

work page

[1] [1]

the temporal graphG1 obtained fromP by adding a vertexαand edges{20,α}and{8,α} with labels fulfillingr<λ({20,α})<λ({8,α})<b,

work page

[2] [2]

the temporal graphG2 obtained fromP by adding a vertexα, a vertexα′, and edges{20,α}, {α,α′}, and{α′,8}with labels fulfillingr<λ({20,α})<λ({α,α′})<λ({α′,8})<b,

work page

[3] [3]

the temporal graphG3 obtained fromP by adding a vertexωand edges{ω,1}and{ω,8} with labels fulfillingr<λ({ω,8})<λ({ω,1})<b, and

work page

[4] [4]

The four temporal graphs defined in Lemma B.5 are sketched in Figure 5

the temporal graphG4 obtained fromP by adding a vertexω, a vertexω′, and edges{ω,1}, {ω′,ω}, and{ω′,8}with labels fulfillingr<λ({ω′,8})<λ({ω′,ω})<λ({ω,1})<b. The four temporal graphs defined in Lemma B.5 are sketched in Figure 5. 3 Here, the set oftime-edgeis defined as{(e,t )|e∈E(G),t∈λ(e)}. Note that a simple temporal graph has as many edges as it has t...

work page

[5] [5]

For each path connector gadgetPc, we add the edge{tc,α}to G′, wheretc is the sink ofP c

work page

[6] [6]

3.For eachcon u,v∈Vcon, we add the edge{outu,conu,v}toG′

For each vertexv∈V\{α,α′}, we add an edge{v,outv}toG′(called theout-edge ofv). 3.For eachcon u,v∈Vcon, we add the edge{outu,conu,v}toG′. 4.For eachcon u,v∈Vcon, we add the edge{conu,v,inv}toG′. 5.For each vertexv∈V\{ω,ω′}, we add an edge{inv,v}toG′(called thein-edge ofv)

work page

[7] [7]

This completes the definition of the underlying graphG′

For each path connector gadgetPc, we add the edge{ω,sc}toG′, wheresc is the source ofP c. This completes the definition of the underlying graphG′. Some of the edges incident with vertices ofVin∪Vout∪Vcon are depicted in Figure 7. ▶Observation C.2.G ′has a girth of5. We complete the construction by defining the labels of the edges. To this end, we define s...

work page

[8] [8]

3.For each(x,y)∈Acon, we add the edge{outx,iny}toG′

For each vertexv∈V\{α,α′}, we add an edge{v,outv}toG′(called theout-edge ofv). 3.For each(x,y)∈Acon, we add the edge{outx,iny}toG′. 4.For each vertexv∈V\{ω,ω′}, we add an edge{inv,v}toG′(called thein-edge ofv). 5.For eachc∈Vin∪Vout, we add the edge{ω,sc}toG′, wheresc is the source ofPc. This completes the definition of the underlying graphG′. ▶Observation...

work page

[9] [9]

Thus, Claim D.5 implies thatP5 visits only vertices ofV

/∈Acon. Thus, Claim D.5 implies thatP5 visits only vertices ofV. Now focus on the edges ofG[V ]incident with v∗ 3 and v∗

work page

[10] [10]

Asv∗ 3 and v∗ 5 are not adjacent, P5 traverses{v∗ 3,v∗ 8}at time11

Each such edge incident withv∗ 5 has a label of at least4and{v∗ 3,v∗ 8}is the only such edge incident withv∗ 3 that receives a larger label. Asv∗ 3 and v∗ 5 are not adjacent, P5 traverses{v∗ 3,v∗ 8}at time11. For P5 to arrive atv∗ 8 prior to time11, P5 has to start with(v∗ 5,v∗ 6,v∗ 7,v∗ 8)(see Figure 8). This implies thatS contains all vertices from{α,α′...

work page

[11] [11]

▷ Claim D.17.Let i∈[8,k−8]with imod 6 = 2, such thatS containsv∗ i−2andv∗ i

For the inductive case, consider the following claim. ▷ Claim D.17.Let i∈[8,k−8]with imod 6 = 2, such thatS containsv∗ i−2andv∗ i. Then, Scontains at least one vertex ofVℓfor eachℓ∈[i+ 1,i+ 6]. Proof. AsG[S]is temporally connected, there is a temporal pathPi from v∗ i to v∗ i−2inG[S]. We show thatPi = (v∗ i,v∗ i+1,v∗ i+2,xi+3,v∗ i+4,v∗ i+5,v∗ i+6,v∗ i−2)f...

work page