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

DOI10.1007/978-3-031-23101-8_19arXiv2203.07401OpenAlexW4313429598MaRDI QIDQ6169534FDOQ6169534

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)

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.

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

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

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)

Cites Work

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

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)