On the Hardness of Finding Temporally Connected Subgraphs of Any Size

Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz · 2026

Read On the Hardness of Finding Temporally Connected Subgraphs of Any Size by Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23226.txt.

Introduction

Casteigts, Komusiewicz, and Morawietz strengthen hardness for temporally connected subgraphs: asking if a temporal graph holds one of any nontrivial size is NP-hard. The result covers standard temporal settings and answers questions, separating closed parts from open ones, whose matching problem is polynomial-time solvable. Their reductions also bar approximating the largest temporally connected subgraph within near n in directed graphs, or near half n in undirected ones. They complete the complexity landscape for subgraphs of exact size k and show huge temporally connected graphs can lack nontrivial subgraphs.

Catalog record

CREATORArnaud Casteigts, Christian Komusiewicz, Nils Morawietz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE163130
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.23226

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Hardness of Finding Temporally Connected Subgraphs of Any Size Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz 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 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 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 − ϵ ) ​ n (1-\epsilon)n in directed graphs, and within a factor of ( 1 − ϵ ) ​ n 2 (1-\epsilon)\frac{n}{2} in undirected graphs. One of the reductions also completes the complexity landscape for TC subgraphs of size exactly k k when parameterized by k 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. Department of Computer Science, University of Geneva, [email protected]://orcid.org/0000-0002-7819-7013Supported by the French ANR project TEMPOGRAL (ANR-22-CE48-0001) and Swiss NSF project RECAPT (200021-236640). Friedrich Schiller University Jena, Institute of Computer Science, [email protected]://orcid.org/0000-0003-0829-7032 LaBRI, Université de Bordeaux, France Friedrich Schiller University Jena, Institute of Computer Science, [email protected]://orcid.org/0000-0002-7283-4982Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL). ccs Theory of computation Graph algorithms analysis ccs Mathematics of computing Discrete mathematics keywords Temporal reachability, temporally connected components, parameterized complexity, para-NP-hardness, happy temporal graphs † † runningauthor: Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz † † copyright: Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz 1 Introduction Temporal graphs are graphs whose edges are only present at certain points in time. These graphs have received significant attention for their ability to model dynamic networks, such as transportation, communication, social, and robotic networks. Formally, a temporal graph can be represented by a labeled graph \mathcal{G}=(G,\lambda) where G=(V,E) is a standard finite graph (directed or undirected) called the underlying graph . The labeling function \lambda:E\to 2^{\mathbb{N}} assigns one or several time labels to each edge of E , interpreted as presence times. The largest time label L is called the lifetime of \mathcal{G} . Reachability in these graphs is defined in terms of paths that traverse the edges chronologically. Precisely, a temporal path is a sequence \langle(e_{i},t_{i})\rangle such that \langle e_{i}\rangle is a path in G , \langle t_{i}\rangle is nondecreasing, and t_{i}\in\lambda(e_{i}) for all i in the sequence. The graph \mathcal{G} is temporally connected ( TC , for short) if it has at least one temporal path between all ordered pairs of vertices. Temporal paths differ crucially from standard paths in several aspects. For example, Kempe, Kleinberg, and Kumar [ 14 ] observed that the temporal analog of Menger’s theorem does not hold: the size of a maximum separator may differ from the maximum number of internally node-disjoint temporal paths, rendering the problem of finding k node-disjoint temporal paths between two vertices NP -hard. A further important difference is that temporal paths are not composable, when the first path ends at a later time step than the second path starts. Consequently, the reachability relation is nontransitive, with structural and algorithmic consequences. Bhadra and Ferreira [ 3 ] introduced the notion of temporal components—subsets of vertices that can reach each other by temporal paths. They distinguish between open components , allowing paths to travel outside the component, and closed components , requiring that all paths remain inside. In both cases, they observe that, because of the nontransitivity, (inclusion-wise) maximal temporal components may overlap, and that the component problem which asks for the existence of a component of a given size k is NP -hard. Interestingly, closed components correspond to vertex-induced subgraphs that are themselves TC , a quite natural concept. The literature on temporal graphs is sensitive to definitional details, whose mention is unavoidable. Some works consider temporal paths whose time labels are not just required to be nondecreasing, but strictly increasing, giving rise to so-called strict temporal paths, connectivity, reachability, and components. Another common distinction is that of simple versus nonsimple temporal graphs, where simple refers to the fact that every edge is assigned a single time label. Both distinctions matter, as some of the resulting combinations are incomparable in terms of expressivity (see e.g. [ 5 ] and [ 10 ] ). For example, it is folklore that the open and closed versions of the component problem are already NP -hard in the simple and strict setting, in fact even for lifetime L=1 : for any graph G , the strict temporal components of the graph \mathcal{G}=(G,\lambda) where \lambda assigns label 1 to every edge coincide with the cliques of G . In contrast, the component problem is trivial to solve when L=1 in the nonstrict setting, where temporal components coincide with static components. The above-mentioned reduction from [ 3 ] is more subtle and implies that both component problems are NP -hard also in the nonstrict setting, however considering temporal graphs of lifetime at least L=4 and where the edges may have several labels (later strengthened to L=2 by Balev, Sanlaville, and Schoeters [ 1 ] ). As the reader may feel, the comparison of existing results in temporal graphs is quite delicate. A convenient way to avoid the distinction between the strict and the nonstrict settings is to consider proper temporal graphs, where adjacent edges never share a common label (in directed temporal graphs, this requirement becomes that no in-arc shares a common label with an out-arc at the same node). For negative results, assuming properness does not restrict the generality. To the contrary, if a problem is hard when the input is a proper temporal graph, then de facto, this problem is hard in both the strict and the nonstrict settings, as no underlying path exists that repeats the same label along two consecutive edges. Going further, showing that a problem is hard in proper and simple ( a.k.a. happy) temporal graphs establishes at once that it is hard irrespective of the above combinations, making happy temporal graphs a natural target for reductions. As it happens, open and closed components are indeed NP -hard in happy temporal graphs [ 5 ] , although the corresponding reductions require a nonconstant lifetime. The systematic study of temporal components from the perspective of parameterized complexity was initiated in [ 7 ] ,

Read the complete text