11 Search Results for "Rescigno, Adele A."

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.STACS.2026.54
A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm

Authors: Stefan Hougardy and Bart Zondervan

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In the Strip Packing problem, we are given a vertical strip of fixed width and unbounded height, along with a set of axis‑parallel rectangles. The task is to place all rectangles within the strip, without overlaps, while minimizing the height of the packing. This problem is known to be NP-hard. The Bottom-Left Algorithm is a simple and widely used heuristic for Strip Packing. Given a fixed order of the rectangles, it places them one by one, always choosing the lowest feasible position in the strip and, in case of ties, the leftmost one. Baker, Coffman, and Rivest proved in 1980 that the Bottom-Left Algorithm has approximation ratio 3 if the rectangles are sorted by decreasing width [Brenda S. Baker et al., 1980]. For the past 45 years, no alternative ordering has been found that improves this bound. We introduce a new rectangle ordering and show that with this ordering the Bottom-Left Algorithm achieves a 13/6 approximation for the Strip Packing problem.
Cite as

Stefan Hougardy and Bart Zondervan. A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hougardy_et_al:LIPIcs.STACS.2026.54,
  author =	{Hougardy, Stefan and Zondervan, Bart},
  title =	{{A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.54},
  URN =		{urn:nbn:de:0030-drops-255432},
  doi =		{10.4230/LIPIcs.STACS.2026.54},
  annote =	{Keywords: Approximation Algorithm, Strip Packing, Bottom-Left Algorithm, Rectangle Packing}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.15
Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs

Authors: Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs.
Cite as

Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes. Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castelo_et_al:LIPIcs.WADS.2025.15,
  author =	{Castelo, Emanuel and Defrain, Oscar and C. M. Gomes, Guilherme},
  title =	{{Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.15},
  URN =		{urn:nbn:de:0030-drops-242467},
  doi =		{10.4230/LIPIcs.WADS.2025.15},
  annote =	{Keywords: algorithmic enumeration, minimal dominating sets, connected dominating sets, total dominating sets, chordal bipartite graphs, sequential method, polynomial delay}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.65
Parameterized Spanning Tree Congestion

Authors: Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V,E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.
Cite as

Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Parameterized Spanning Tree Congestion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2025.65,
  author =	{Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Parameterized Spanning Tree Congestion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{65:1--65:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.65},
  URN =		{urn:nbn:de:0030-drops-241724},
  doi =		{10.4230/LIPIcs.MFCS.2025.65},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Graph Width Parameters}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.4
Induced Disjoint Paths Without an Induced Minor

Authors: Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon

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

Abstract
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs - which avoids the 1-subdivision of, say, K₅ as an induced minor - Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree. We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and Trotignon [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2^{Ω(√ n)}. This complements an algorithm running in subexponential time 2^{Õ(n^{2/3})} by these authors [SODA '24] under the same technical condition.
Cite as

Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon. Induced Disjoint Paths Without an Induced Minor. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aboulker_et_al:LIPIcs.ICALP.2025.4,
  author =	{Aboulker, Pierre and Bonnet, \'{E}douard and Picavet, Timoth\'{e} and Trotignon, Nicolas},
  title =	{{Induced Disjoint Paths Without an Induced Minor}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{4:1--4:14},
  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.4},
  URN =		{urn:nbn:de:0030-drops-233813},
  doi =		{10.4230/LIPIcs.ICALP.2025.4},
  annote =	{Keywords: Induced Disjoint Paths, string graphs, induced subdivisions, induced minors}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.65
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications

Authors: Gianluca De Marco and Dariusz R. Kowalski

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

Abstract
A superimposed code is a collection of binary vectors (codewords) with the property that no vector is contained in the Boolean sum of any k others, enabling unique identification of codewords within any group of k. Superimposed codes are foundational combinatorial tools with applications in areas ranging from distributed computing and data retrieval to fault-tolerant communication. However, classical superimposed codes rely on strict alignment assumptions, limiting their effectiveness in asynchronous and fault-prone environments, which are common in modern systems and applications. We introduce Ultra-Resilient Superimposed Codes (URSCs), a new class of codes that extends the classic superimposed framework by ensuring a stronger codewords' isolation property and resilience to two types of adversarial perturbations: arbitrary cyclic shifts and partial bitwise corruption (flips). Additionally, URSCs exhibit universality, adapting seamlessly to any number k of concurrent codewords without prior knowledge. This is a combination of properties not achieved in any previous construction. We provide the first polynomial-time construction of URSCs with near-optimal length, significantly outperforming previous constructions with less general features, all without requiring prior knowledge of the number of concurrent codewords, k. We demonstrate that our URSCs significantly advance the state of the art in multiple applications, including uncoordinated beeping networks, where our codes reduce time complexity for local broadcast by nearly two orders of magnitude, and generalized contention resolution in multi-access channel communication.
Cite as

Gianluca De Marco and Dariusz R. Kowalski. Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.ICALP.2025.65,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R.},
  title =	{{Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{65:1--65:20},
  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.65},
  URN =		{urn:nbn:de:0030-drops-234429},
  doi =		{10.4230/LIPIcs.ICALP.2025.65},
  annote =	{Keywords: superimposed codes, ultra-resiliency, deterministic algorithms, uncoordinated beeping networks, contention resolution}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.9
Spanner Enumeration for Temporal Graphs

Authors: Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A spanner of a temporal graph is a subset of edges that preserves connectivity over time between vertices. A minimal spanner is one in which no additional edges can be removed without breaking this connectivity. Our focus is on enumerating minimal spanners for a given temporal graph. We explore several variations of this problem based on the type of connectivity that must be maintained, ranging from one-to-all connectivity to one-to-all-to-one, many-to-all, and finally all-to-all connectivity. We establish that these problems become progressively harder: (i) We present a polynomial-delay enumeration algorithm for one-to-all connectivity; (ii) We prove Dual-hardness for both one-to-all-to-one and many-to-all connectivity, even in the restricted case of two-to-all; (iii) Finally, for all-to-all connectivity, we show that enumeration cannot be performed in output-polynomial time unless P = NP.
Cite as

Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner Enumeration for Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kurita_et_al:LIPIcs.SAND.2025.9,
  author =	{Kurita, Kazuhiro and Marino, Andrea and Schoeters, Jason and Uno, Takeaki},
  title =	{{Spanner Enumeration for Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.9},
  URN =		{urn:nbn:de:0030-drops-230621},
  doi =		{10.4230/LIPIcs.SAND.2025.9},
  annote =	{Keywords: temporal graphs, temporal spanners, one-to-all connectivity, all-to-all connectivity enumeration, NP-completeness, Dual-hardness, binary partition tree, flashlight search, polynomial delay}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.34
The Lambda Calculus Is Quantifiable

Authors: Valentin Maestracci and Paolo Pistone

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
In this paper we introduce several quantitative methods for the lambda-calculus based on partial metrics, a well-studied variant of standard metric spaces that have been used to metrize non-Hausdorff topologies, like those arising from Scott domains. First, we study quantitative variants, based on program distances, of sensible equational theories for the λ-calculus, like those arising from Böhm trees and from the contextual preorder. Then, we introduce applicative distances capturing higher-order Scott topologies, including reflexive objects like the D_∞ model. Finally, we provide a quantitative insight on the well-known connection between the Böhm tree of a λ-term and its Taylor expansion, by showing that the latter can be presented as an isometric transformation.
Cite as

Valentin Maestracci and Paolo Pistone. The Lambda Calculus Is Quantifiable. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maestracci_et_al:LIPIcs.CSL.2025.34,
  author =	{Maestracci, Valentin and Pistone, Paolo},
  title =	{{The Lambda Calculus Is Quantifiable}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.34},
  URN =		{urn:nbn:de:0030-drops-227911},
  doi =		{10.4230/LIPIcs.CSL.2025.34},
  annote =	{Keywords: Lambda-calculus, Scott semantics, Partial metric spaces, B\"{o}hm trees, Taylor expansion}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.13
Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility

Authors: Raphael Gerlach, Sören von der Gracht, Christopher Hahn, Jonas Harbig, and Peter Kling

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In the general pattern formation (GPF) problem, a swarm of simple autonomous, disoriented robots must form a given pattern. The robots' simplicity imply a strong limitation: When the initial configuration is rotationally symmetric, only patterns with a similar symmetry can be formed [Masafumi Yamashita and Ichiro Suzuki, 2010]. The only known algorithm to form large patterns with limited visibility and without memory requires the robots to start in a near-gathering (a swarm of constant diameter) [Christopher Hahn et al., 2024]. However, not only do we not know any near-gathering algorithm guaranteed to preserve symmetry but most natural gathering strategies trivially increase symmetries [Jannik Castenow et al., 2022]. Thus, we study near-gathering without changing the swarm’s rotational symmetry for disoriented, oblivious robots with limited visibility (the OBLOT-model, see [Paola Flocchini et al., 2019]). We introduce a technique based on the theory of dynamical systems to analyze how a given algorithm affects symmetry and provide sufficient conditions for symmetry preservation. Until now, it was unknown whether the considered OBLOT-model allows for any non-trivial algorithm that always preserves symmetry. Our first result shows that a variant of Go-To-The-Average always preserves symmetry but may sometimes lead to multiple, unconnected near-gathering clusters. Our second result is a symmetry-preserving near-gathering algorithm that works on swarms with a convex boundary (the outer boundary of the unit disc graph) and without "holes" (circles of diameter 1 inside the boundary without any robots).
Cite as

Raphael Gerlach, Sören von der Gracht, Christopher Hahn, Jonas Harbig, and Peter Kling. Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 13:1-13:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.OPODIS.2024.13,
  author =	{Gerlach, Raphael and von der Gracht, S\"{o}ren and Hahn, Christopher and Harbig, Jonas and Kling, Peter},
  title =	{{Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{13:1--13:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.13},
  URN =		{urn:nbn:de:0030-drops-225490},
  doi =		{10.4230/LIPIcs.OPODIS.2024.13},
  annote =	{Keywords: Swarm Algorithm, Swarm Robots, Distributed Algorithm, Pattern Formation, Limited Visibility, Oblivious}
}
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}
}
  • Refine by Type
  • 11 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 7 2025
  • 1 2023
  • 1 2020

  • Refine by Author
  • 3 Gargano, Luisa
  • 2 Cordasco, Gennaro
  • 2 Rescigno, Adele A.
  • 1 Aboulker, Pierre
  • 1 Bonnet, Édouard
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Mathematics of computing → Graph enumeration
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 2 polynomial delay
  • 1 Approximate Algorithms
  • 1 Approximation Algorithm
  • 1 Bottom-Left Algorithm
  • 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