DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.52

Structural Parameters for Dense Temporal Graphs

Authors: Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Temporal graphs provide a useful model for many real-world networks. Unfortunately, the majority of algorithmic problems we might consider on such graphs are intractable. There has been recent progress in defining structural parameters which describe tractable cases by simultaneously restricting the underlying structure and the times at which edges appear in the graph. These all rely on the temporal graph being sparse in some sense. We introduce temporal analogues of three increasingly restrictive static graph parameters - cliquewidth, modular-width and neighbourhood diversity - which take small values for highly structured temporal graphs, even if a large number of edges are active at each timestep. The computational problems solvable efficiently when the temporal cliquewidth of the input graph is bounded form a subset of those solvable efficiently when the temporal modular-width is bounded, which is in turn a subset of problems efficiently solvable when the temporal neighbourhood diversity is bounded. By considering specific temporal graph problems, we demonstrate that (up to standard complexity theoretic assumptions) these inclusions are strict.

Cite as

Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks. Structural Parameters for Dense Temporal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{enright_et_al:LIPIcs.MFCS.2024.52,
  author =	{Enright, Jessica and Hand, Samuel D. and Larios-Jones, Laura and Meeks, Kitty},
  title =	{{Structural Parameters for Dense Temporal Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.52},
  URN =		{urn:nbn:de:0030-drops-206082},
  doi =		{10.4230/LIPIcs.MFCS.2024.52},
  annote =	{Keywords: Graph algorithms, Parameterized Algorithms, Temporal Graphs}
}

Search Results

Documents authored by Larios-Jones, Laura

Structural Parameters for Dense Temporal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message