On computing large temporal (unilateral) connected components

DOI10.1007/978-3-031-34347-6_24MaRDI QIDQ6182912zbMATH OpenOpenAlexFDO

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)

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)

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.

Cites work

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

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)