DROPS

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.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}
}

Search Results

Documents authored by Cordasco, Gennaro

The Berlin Safe House Puzzle: Spycraft via Interval Graphs

Abstract

Cite as

Speeding up Networks Mining via Neighborhood Diversity

Abstract

Cite as

Thanks for your feedback!

Could not send message