6 Search Results for "Lagoutte, Aurélie"

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
Research
DOI: 10.4230/OASIcs.Grossi.19
Designing Output Sensitive Algorithms for Subgraph Enumeration

Authors: Alessio Conte, Kazuhiro Kurita, Andrea Marino, Giulia Punzi, Takeaki Uno, and Kunihiro Wasa

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
The enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e., bounding the running time with respect to the number of subgraphs produced. In this paper, we provide a survey of techniques for designing output-sensitive algorithms for subgraph enumeration, including partition-based approaches such as flashlight search, solution-graph traversal methods such as reverse search, and cost amortization strategies such as push-out amortization. We also briefly discuss classes of efficiency, hardness of enumeration, and variants such as approximate enumeration. The paper is meant as an accessible handbook for learning the basics of the field and as a practical reference for selecting state-of-the-art subgraph enumeration strategies fitting to one’s needs.
Cite as

Alessio Conte, Kazuhiro Kurita, Andrea Marino, Giulia Punzi, Takeaki Uno, and Kunihiro Wasa. Designing Output Sensitive Algorithms for Subgraph Enumeration. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 19:1-19:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{conte_et_al:OASIcs.Grossi.19,
  author =	{Conte, Alessio and Kurita, Kazuhiro and Marino, Andrea and Punzi, Giulia and Uno, Takeaki and Wasa, Kunihiro},
  title =	{{Designing Output Sensitive Algorithms for Subgraph Enumeration}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{19:1--19:40},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.19},
  URN =		{urn:nbn:de:0030-drops-238180},
  doi =		{10.4230/OASIcs.Grossi.19},
  annote =	{Keywords: Graph algorithms, Graph enumeration, Output sensitive enumeration}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.54
Decay of Correlation for Edge Colorings When q > 3Δ

Authors: Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We examine various perspectives on the decay of correlation for the uniform distribution over proper q-edge colorings of graphs with maximum degree Δ. First, we establish the coupling independence property when q ≥ 3Δ for general graphs. Together with the recent work of Chen, Feng, Guo, Zhang and Zou (2024), this result implies a fully polynomial-time approximation scheme (FPTAS) for counting the number of proper q-edge colorings. Next, we prove the strong spatial mixing property on trees, provided that q > (3+o(1))Δ. The strong spatial mixing property is derived from the spectral independence property of a version of the weighted edge coloring distribution, which is established using the matrix trickle-down method developed in Abdolazimi, Liu and Oveis Gharan (FOCS, 2021) and Wang, Zhang and Zhang (STOC, 2024). Finally, we show that the weak spatial mixing property holds on trees with maximum degree Δ if and only if q ≥ 2Δ-1.
Cite as

Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang. Decay of Correlation for Edge Colorings When q > 3Δ. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.54,
  author =	{Chen, Zejia and Wang, Yulin and Zhang, Chihao and Zhang, Zihan},
  title =	{{Decay of Correlation for Edge Colorings When q \rangle 3\Delta}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.54},
  URN =		{urn:nbn:de:0030-drops-234314},
  doi =		{10.4230/LIPIcs.ICALP.2025.54},
  annote =	{Keywords: Strong Spatial Mixing, Edge Coloring, Approximate Counting}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.19
The Canadian Traveller Problem on Outerplanar Graphs

Authors: Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor

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

Abstract
We study the k-Canadian Traveller Problem, where a weighted graph G = (V,E,ω) with a source s ∈ V and a target t ∈ V are given. This problem also has a hidden input E_* ⊊ E of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum distance. At the beginning of the walk, the blockages E_* are unknown: the traveller discovers that an edge is blocked when visiting one of its endpoints. Online algorithms, also called strategies, have been proposed for this problem and assessed with the competitive ratio, i.e., the ratio between the distance actually traversed by the traveller divided by the distance he would have traversed knowing the blockages in advance. Even though the optimal competitive ratio is 2k+1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs. This value 9 also stands as a lower bound for this family of graphs as we prove that, for any ε > 0, no strategy can achieve a competitive ratio 9-ε. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs.
Cite as

Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor. The Canadian Traveller Problem on Outerplanar Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beaudou_et_al:LIPIcs.MFCS.2024.19,
  author =	{Beaudou, Laurent and Berg\'{e}, Pierre and Chernyshev, Vsevolod and Dailly, Antoine and Gerard, Yan and Lagoutte, Aur\'{e}lie and Limouzy, Vincent and Pastor, Lucas},
  title =	{{The Canadian Traveller Problem on Outerplanar Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{19:1--19:16},
  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.19},
  URN =		{urn:nbn:de:0030-drops-205750},
  doi =		{10.4230/LIPIcs.MFCS.2024.19},
  annote =	{Keywords: Canadian Traveller Problem, Online algorithms, Competitive analysis, Outerplanar graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.48
Local Certification of Geometric Graph Classes

Authors: Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond

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

Abstract
The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view and their own unique identifier, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1-δ}) for any δ > 0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.
Cite as

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.MFCS.2024.48,
  author =	{Defrain, Oscar and Esperet, Louis and Lagoutte, Aur\'{e}lie and Morin, Pat and Raymond, Jean-Florent},
  title =	{{Local Certification of Geometric Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{48:1--48:14},
  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.48},
  URN =		{urn:nbn:de:0030-drops-206042},
  doi =		{10.4230/LIPIcs.MFCS.2024.48},
  annote =	{Keywords: Local certification, proof labeling schemes, geometric intersection graphs}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2013.3
Graph coloring, communication complexity and the stubborn problem (Invited Talk)

Authors: Nicolas Bousquet, Aurélie Lagoutte, and Thomassé Stéphan

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We discuss three equivalent forms of the same problem arising in communication complexity, constraint satisfaction problems, and graph coloring. Some partial results are discussed.
Cite as

Nicolas Bousquet, Aurélie Lagoutte, and Thomassé Stéphan. Graph coloring, communication complexity and the stubborn problem (Invited Talk). In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 3-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2013.3,
  author =	{Bousquet, Nicolas and Lagoutte, Aur\'{e}lie and St\'{e}phan, Thomass\'{e}},
  title =	{{Graph coloring, communication complexity and the stubborn problem}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{3--4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.3},
  URN =		{urn:nbn:de:0030-drops-39158},
  doi =		{10.4230/LIPIcs.STACS.2013.3},
  annote =	{Keywords: stubborn problem, graph coloring, Clique-Stable set separation, Alon-Saks-Seymour conjecture, bipartite packing}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 2 2024
  • 1 2013

  • Refine by Author
  • 3 Lagoutte, Aurélie
  • 1 Beaudou, Laurent
  • 1 Bergé, Pierre
  • 1 Bousquet, Nicolas
  • 1 Chen, Zejia
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Computing methodologies → Distributed computing methodologies
  • 1 Mathematics of computing → Graph enumeration
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Alon-Saks-Seymour conjecture
  • 1 Approximate Algorithms
  • 1 Approximate Counting
  • 1 Canadian Traveller Problem
  • 1 Clique-Stable set separation
  • Show More...

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