Search Results

Documents authored by Larios-Jones, Laura

Document
DOI: 10.4230/LIPIcs.SAND.2026.4
Families of Tractable Problems with Respect to Vertex-Interval-Membership Width and Its Generalisations

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

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership (VIM) width. Broadly, this gives a bound on the number of vertices we need to keep track of at any given time to solve many problems. Our contributions are two-fold. Firstly, we introduce a new parameter, tree-interval-membership (TIM) width, that generalises both VIM width and several existing generalisations. Secondly, we provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. In doing this, we provide a characterisation of problems in FPT with respect to both parameters. We apply these algorithms to temporal versions of Hamiltonian path, dominating set, matching, and edge deletion to limit maximum reachability.
Cite as

Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks. Families of Tractable Problems with Respect to Vertex-Interval-Membership Width and Its Generalisations. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{enright_et_al:LIPIcs.SAND.2026.4,
  author =	{Enright, Jessica and Hand, Samuel D. and Larios-Jones, Laura and Meeks, Kitty},
  title =	{{Families of Tractable Problems with Respect to Vertex-Interval-Membership Width and Its Generalisations}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.4},
  URN =		{urn:nbn:de:0030-drops-262386},
  doi =		{10.4230/LIPIcs.SAND.2026.4},
  annote =	{Keywords: Graph algorithms, Parameterized Algorithms, Temporal Graphs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2026.9
FO and MSO Model Checking on Temporal Graphs

Authors: Michelle Döring, Jessica Enright, Laura Larios-Jones, and George Skretas

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
Algorithmic meta-theorems provide an important tool for showing tractability of graph problems on graph classes defined by structural restrictions. While such results are well established for static graphs, corresponding frameworks for temporal graphs are comparatively limited. In this work, we revisit past applications of logical meta-theorems to temporal graphs and develop an extended unifying logical framework. Our first contribution is the introduction of logical encodings for the parameters vertex-interval-membership width (vim) and tree-interval-membership width (tim), parameters that capture the signature of vertex and component activity over time. Building on this, we extend existing monadic second-order (MSO) meta-theorems for bounded lifetime and temporal total degree to the parameters vim and tim, and establish novel first-order (FO) meta-theorems for all four parameters. Finally, we signpost a modular lexicon of reusable FO and MSO formulas for a broad range of temporal graph problems, and give an example. This lexicon allows new problems to be expressed compositionally and directly yields fixed-parameter tractability results across the four parameters we consider.
Cite as

Michelle Döring, Jessica Enright, Laura Larios-Jones, and George Skretas. FO and MSO Model Checking on Temporal Graphs. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{doring_et_al:LIPIcs.SAND.2026.9,
  author =	{D\"{o}ring, Michelle and Enright, Jessica and Larios-Jones, Laura and Skretas, George},
  title =	{{FO and MSO Model Checking on Temporal Graphs}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.9},
  URN =		{urn:nbn:de:0030-drops-262430},
  doi =		{10.4230/LIPIcs.SAND.2026.9},
  annote =	{Keywords: temporal graphs, dynamic graphs, time-varying graphs, parameterized complexity, logic, meta-theorems, monadic second-order logic, first-order logic, treewidth, planar, nowhere dense, lifetime, temporal total degree, vertex-interval membership width, tree-interval membership width}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact