Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs

DOI10.1007/978-3-031-23101-8_19MaRDI QIDQ6169534zbMATH OpenOpenAlexFDO

Authors Niels Grüttemeier, Nils Morawietz, Frank Sommer, Petra Wolf

Publication date 14 August 2023

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

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

zbMATH Keywords

parameterized complexityFPT-algorithmtemporal graphsminor containmentsubgraph-freenesssubgraph containmentminor-freeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge $e$ of the graph, a binary string $s_e$ determines in which time steps the edge is present, namely $e$ is present in time step $t$ if and only if $s_e$ contains a $1$ at position $tmod|s_e|$. Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as what is the shortest traversal time between two vertices; is there a time step in which the graph (1) is minor-free; (2) contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several parameterized algorithms.

Recommendations

• Speedup for a periodic subgraph miner
• Efficient algorithms for the periodic subgraphs mining problem
• Edge exploration of temporal graphs
• Feedback edge sets in temporal graphs
• An introduction to temporal graphs: an algorithmic perspective

Cites work

• scientific article; zbMATH DE number 7559442 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 7724250 (Why is no real title available?)
• scientific article; zbMATH DE number 7730620 (Why is no real title available?)
• A game of cops and robbers on graphs with periodic edge-connectivity
• An application of simultaneous diophantine approximation in combinatorial optimization
• Compositionality, computability, and complexity
• Connectivity and inference problems for temporal networks
• Graph minor theory
• Graph minors. XIII: The disjoint paths problem
• How fast can we reach a target vertex in stochastic temporal graphs?
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Multiaspect graphs: algebraic representation and algorithms
• Parameterized algorithms
• Reducibility among combinatorial problems
• Sliding window temporal graph coloring
• Temporal network optimization subject to connectivity constraints
• Temporal vertex cover with a sliding time window
• Traveling salesman problems in temporal graphs

Cited in

(1)

• A cop and robber game on edge-periodic temporal graphs

This page was built for publication: Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs

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