Search Results

Documents authored by Hand, Samuel D.

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}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.15
Making Life More Confusing for Firefighters

Authors: Samuel D. Hand, Jessica Enright, and Kitty Meeks

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
It is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem is NP-Complete on all but a few classes of graphs. Thankfully, firefighters do not have to work alone, and are often aided by the efforts of good natured civillians who slow the spread of a fire by maintaining firebreaks when they are able. We will show that this help, although well-intentioned, unfortunately makes the optimal deployment of firefighters an even harder problem. To model this scenario we introduce the Temporal Firefighter problem, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have polynomial time solutions. This motivates us to explore making use of the temporal structure of the graph in our search for tractability, and we conclude by presenting an FPT algorithm for Temporal Firefighter with respect to the temporal graph parameter vertex-interval-membership-width.
Cite as

Samuel D. Hand, Jessica Enright, and Kitty Meeks. Making Life More Confusing for Firefighters. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hand_et_al:LIPIcs.FUN.2022.15,
  author =	{Hand, Samuel D. and Enright, Jessica and Meeks, Kitty},
  title =	{{Making Life More Confusing for Firefighters}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.15},
  URN =		{urn:nbn:de:0030-drops-159851},
  doi =		{10.4230/LIPIcs.FUN.2022.15},
  annote =	{Keywords: Temporal graphs, Spreading processes, Parameterised complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2022.22
Brief Announcement: The Temporal Firefighter Problem

Authors: Samuel D. Hand, Jessica Enright, and Kitty Meeks

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
The Firefighter problem asks how many vertices can be saved from a fire spreading over the vertices of a graph. At timestep 0 a vertex begins burning, then on each subsequent timestep a non-burning vertex is chosen to be defended, and the fire then spreads to all undefended vertices that it neighbours. The problem is NP-Complete on arbitrary graphs, however existing work has found several graph classes for which there are polynomial time solutions. We introduce Temporal Firefighter, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have a polynomial-time solution. This motivates us to explore restrictions on the temporal structure of the graph, and we find that Temporal Firefighter is fixed parameter tractable with respect to the temporal graph parameter vertex-interval-membership-width.
Cite as

Samuel D. Hand, Jessica Enright, and Kitty Meeks. Brief Announcement: The Temporal Firefighter Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 22:1-22:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hand_et_al:LIPIcs.SAND.2022.22,
  author =	{Hand, Samuel D. and Enright, Jessica and Meeks, Kitty},
  title =	{{Brief Announcement: The Temporal Firefighter Problem}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{22:1--22:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.22},
  URN =		{urn:nbn:de:0030-drops-159644},
  doi =		{10.4230/LIPIcs.SAND.2022.22},
  annote =	{Keywords: Temporal graphs, Spreading processes, Parameterised complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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