Search Results

Documents authored by Gargano, Luisa

Document
DOI: 10.4230/LIPIcs.FUN.2026.13
The Berlin Safe House Puzzle: Spycraft via Interval Graphs

Authors: Gennaro Cordasco, Luisa Gargano, and Adele Anna Rescigno

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We propose a gamified application of the {Identifying Code} problem on {Interval Graphs}, framed as a high-stakes Cold War counter-intelligence operation. We present a polynomial-time algorithm to assign "Listening Devices" (bugs) to "Safe Houses" (intervals) so that every safe house is uniquely identifiable by its bug signature. While the problem is NP-hard on several graph classes, including chordal and bipartite graphs, the interval-graph structure allows us to compute a 2-approximate solution efficiently.
Cite as

Gennaro Cordasco, Luisa Gargano, and Adele Anna Rescigno. The Berlin Safe House Puzzle: Spycraft via Interval Graphs. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cordasco_et_al:LIPIcs.FUN.2026.13,
  author =	{Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele Anna},
  title =	{{The Berlin Safe House Puzzle: Spycraft via Interval Graphs}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.13},
  URN =		{urn:nbn:de:0030-drops-257325},
  doi =		{10.4230/LIPIcs.FUN.2026.13},
  annote =	{Keywords: Interval Graphs, Watching-System, Approximate Algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.50
An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width

Authors: Luisa Gargano and Adele A. Rescigno

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The minimum branch vertices spanning tree problem consists in finding a spanning tree T of an input graph G having the minimum number of branch vertices, that is, vertices of degree at least three in T. This NP-hard problem has been widely studied in the literature and has many important applications in network design and optimization. Algorithmic and combinatorial aspects of the problem have been extensively studied and its fixed parameter tractability has been recently considered. In this paper we focus on modular-width and show that the problem of finding a spanning tree with the minimum number of branch vertices is FPT with respect to this parameter.
Cite as

Luisa Gargano and Adele A. Rescigno. An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gargano_et_al:LIPIcs.MFCS.2023.50,
  author =	{Gargano, Luisa and Rescigno, Adele A.},
  title =	{{An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.50},
  URN =		{urn:nbn:de:0030-drops-185843},
  doi =		{10.4230/LIPIcs.MFCS.2023.50},
  annote =	{Keywords: Spanning Trees, Branch vertices, Fixed-parameter tractable algorithms, Modular-width}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.21
Speeding up Networks Mining via Neighborhood Diversity

Authors: Gennaro Cordasco, Luisa Gargano, and Adele A. Rescigno

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Parameterized complexity was classically used to efficiently solve NP-hard problems for small values of a fixed parameter. Then it has also been used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd) for several graph theoretic problems in P (e.g., Maximum Matching, Triangle counting and listing, Girth and Global minimum vertex cut). Such problems are known to admit algorithms parameterized by modular-width (mw) and consequently - being the nd a "special case" of mw - by nd. However, the proposed novel algorithms allow to improve the computational complexity from a time O(f(mw)⋅ n +m) - where n and m denote, respectively, the number of vertices and edges in the input graph - which is multiplicative in n to a time O(g(nd)+n +m) which is additive only in the size of the input.
Cite as

Gennaro Cordasco, Luisa Gargano, and Adele A. Rescigno. Speeding up Networks Mining via Neighborhood Diversity. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cordasco_et_al:LIPIcs.FUN.2021.21,
  author =	{Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele A.},
  title =	{{Speeding up Networks Mining via Neighborhood Diversity}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.21},
  URN =		{urn:nbn:de:0030-drops-127823},
  doi =		{10.4230/LIPIcs.FUN.2021.21},
  annote =	{Keywords: Parameterized Complexity, Neighborhood Diversity, Maximum Matching, Triangle Counting, Girth, Global minimum vertex cut}
}
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