On computing large temporal (unilateral) connected components

DOI10.1007/978-3-031-34347-6_24arXiv2302.12068OpenAlexW4379117553MaRDI QIDQ6182912FDOQ6182912

Authors: Isnard Lopes Costa, Raul Lopes, Andrea Marino, Ana Silva 

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, $au$. Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasingly (i.e., non-decreasing) depending on the scenario. Then, the classical concept of connected components and also of unilateral connected components in static graphs and digraphs naturally extends to the temporal setting. In this paper, we answer to the following fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size $k$, parameterized by $au$, by $k$, and by $k+au$? We show that this question has a different answer depending on the considered definition of component and whether the temporal graph is directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable? A quadratic algorithm is known but, contrary to the static case, we show that a better running time is unlikely unless SETH fails. (iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the definition of temporal component this test is NP-complete.

Full work available at URL: https://arxiv.org/abs/2302.12068

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• On the complexity of \(k\)-SAT
• Connectivity and inference problems for temporal networks
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Computing the Minimum Fill-In is NP-Complete
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• The maximum edge biclique problem is NP-complete
• Into the square: on the complexity of some quadratic-time solvable problems
• On finding all unilaterally connected components of a digraph
• Components in time-varying graphs
• The complexity of finding small separators in temporal graphs
• Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs

Cited In (1)

• Temporally connected components

This page was built for publication: On computing large temporal (unilateral) connected components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182912)