50 Search Results for "Fraigniaud, Pierre"


Volume

LIPIcs, Volume 226

11th International Conference on Fun with Algorithms (FUN 2022)

FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy

Editors: Pierre Fraigniaud and Yushi Uno

Document
Distributed Partial Coloring via Gradual Rounding

Authors: Avinandan Das, Pierre Fraigniaud, and Adi Rosén

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
For k ≥ 0, k-partial (k+1)-coloring asks to color the nodes of an n-node graph using a palette of k+1 colors such that every node v has at least min{k,deg(v)} neighbors colored with colors different from its own color. Hence, proper (Δ+1)-coloring is the special case of k-partial (k+1)-coloring when k = Δ. Ghaffari and Kuhn [FOCS 2021] recently proved that there exists a deterministic distributed algorithm that solves proper (Δ+1)-coloring of n-node graphs with maximum degree Δ in O(log n ⋅ log²Δ) rounds under the LOCAL model of distributed computing. This breakthrough result is achieved via an original iterated rounding approach. Using the same technique, Ghaffari and Kuhn also showed that there exists a deterministic algorithm that solves proper O(a)-coloring of n-node graphs with arboricity a in O(log n ⋅ log³a) rounds. It directly follows from this latter result that k-partial O(k)-coloring can be solved deterministically in O(log n ⋅ log³k) rounds. We develop an extension of the Ghaffari and Kuhn algorithm for proper (Δ+1)-coloring, and show that it solves k-partial (k+1)-coloring, thus generalizing their main result. Our algorithm runs in O(log n ⋅ log³k) rounds, like the algorithm that follows from Ghaffari and Kuhn’s algorithm for graphs with bounded arboricity, but uses only k+1 color, i.e., the smallest number c of colors such that every graph has a k-partial c-coloring. Like all the previously mentioned algorithms, our algorithm actually solves the general list-coloring version of the problem. Specifically, every node v receives as input an integer demand d(v) ≤ deg(v), and a list of at least d(v)+1 colors. Every node must then output a color from its list such that the resulting coloring satisfies that every node v has at least d(v) neighbors with colors different from its own. Our algorithm solves this problem in O(log n ⋅ log³k) rounds where k = max_v d(v). Moreover, in the specific case where all lists of colors given to the nodes as input share a common colors c^* known to all nodes, one can save one log k factor. In particular, for standard k-partial (k+1)-coloring, which corresponds to the case where all nodes are given the same list {1,… ,k+1}, one can modify our algorithm so that it runs in O(log n ⋅ log²k) rounds, and thus matches the complexity of Ghaffari and Kuhn’s algorithm for (Δ+1)-coloring for k = Δ.

Cite as

Avinandan Das, Pierre Fraigniaud, and Adi Rosén. Distributed Partial Coloring via Gradual Rounding. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.OPODIS.2023.30,
  author =	{Das, Avinandan and Fraigniaud, Pierre and Ros\'{e}n, Adi},
  title =	{{Distributed Partial Coloring via Gradual Rounding}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.30},
  URN =		{urn:nbn:de:0030-drops-195205},
  doi =		{10.4230/LIPIcs.OPODIS.2023.30},
  annote =	{Keywords: Distributed graph coloring, partial coloring, weak coloring}
}
Document
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks

Authors: Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)


Abstract
The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task Π, if there is a round-reduction proof establishing the impossibility of solving Π using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrarily number n ≥ 2 of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by n ≥ 2 processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms.

Cite as

Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.4,
  author =	{Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio},
  title =	{{One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4},
  URN =		{urn:nbn:de:0030-drops-191304},
  doi =		{10.4230/LIPIcs.DISC.2023.4},
  annote =	{Keywords: Wait-free computing, lower bounds}
}
Document
Efficient Collaborative Tree Exploration with Breadth-First Depth-Next

Authors: Romain Cosson, Laurent Massoulié, and Laurent Viennot

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)


Abstract
We study the problem of collaborative tree exploration introduced by Fraigniaud, Gasieniec, Kowalski, and Pelc [Pierre Fraigniaud et al., 2006] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the 𝒪(n/log(k)+D) algorithm of [Pierre Fraigniaud et al., 2006] achieves a 𝒪(k/log(k)) competitive ratio with respect to the cost of offline exploration which is at least max{{2n/k,2D}}. Brass, Cabrera-Mora, Gasparri, and Xiao [Peter Brass et al., 2011] study an alternative performance criterion, the competitive overhead with respect to the cost of offline exploration, with their 2n/k+𝒪((D+k)^k) guarantee. In this paper, we introduce "Breadth-First Depth-Next" (BFDN), a novel and simple algorithm that performs collaborative tree exploration in 2n/k+𝒪(D²log(k)) rounds, thus outperforming [Peter Brass et al., 2011] for all values of (n,D,k) and being order-optimal for trees of depth D = o(√n). Our analysis relies on a two-player game reflecting a problem of online resource allocation that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of 𝒪_𝓁(n/k^{1/𝓁}+log(k) D^{1+1/𝓁}) for parameter 𝓁 ≥ 1, thereby improving performance for trees with large depth.

Cite as

Romain Cosson, Laurent Massoulié, and Laurent Viennot. Efficient Collaborative Tree Exploration with Breadth-First Depth-Next. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{cosson_et_al:LIPIcs.DISC.2023.14,
  author =	{Cosson, Romain and Massouli\'{e}, Laurent and Viennot, Laurent},
  title =	{{Efficient Collaborative Tree Exploration with Breadth-First Depth-Next}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.14},
  URN =		{urn:nbn:de:0030-drops-191409},
  doi =		{10.4230/LIPIcs.DISC.2023.14},
  annote =	{Keywords: collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms}
}
Document
Distributed Certification for Classes of Dense Graphs

Authors: Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)


Abstract
A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graphs is a mechanism used for certifying the legality with respect to Π of global network states in a distributed manner. In a PLS, a certificate is assigned to each processing node of the network, and the nodes are in charge of checking that the collection of certificates forms a global proof that the system is in a correct state, by exchanging the certificates once, between neighbors only. The main measure of complexity is the size of the certificates. Many PLSs have been designed for certifying specific predicates, including cycle-freeness, minimum-weight spanning tree, planarity, etc. In 2021, a breakthrough has been obtained, as a "meta-theorem" stating that a large set of properties have compact PLSs in a large class of networks. Namely, for every MSO₂ property Π on labeled graphs, there exists a PLS for Π with O(log n)-bit certificates for all graphs of bounded tree-depth. This result has been extended to the larger class of graphs with bounded tree-width, using certificates on O(log² n) bits. We extend this result even further, to the larger class of graphs with bounded clique-width, which, as opposed to the other two aforementioned classes, includes dense graphs. We show that, for every MSO₁ property Π on labeled graphs, there exists a PLS for Π with O(log² n)-bit certificates for all graphs of bounded clique-width. As a consequence, certifying families of graphs such as distance-hereditary graphs and (induced) P₄-free graphs (a.k.a., cographs) can be done using a PLS with O(log² n)-bit certificates, merely because each of these two classes can be specified in MSO₁. In fact, we show that certifying P₄-free graphs can be done with certificates on O(log n) bits only. This is in contrast to the class of C₄-free graphs (which does not have bounded clique-width) which requires Ω̃(√n)-bit certificates.

Cite as

Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed Certification for Classes of Dense Graphs. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2023.20,
  author =	{Fraigniaud, Pierre and Mazoit, Fr\'{e}d\'{e}ric and Montealegre, Pedro and Rapaport, Ivan and Todinca, Ioan},
  title =	{{Distributed Certification for Classes of Dense Graphs}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.20},
  URN =		{urn:nbn:de:0030-drops-191467},
  doi =		{10.4230/LIPIcs.DISC.2023.20},
  annote =	{Keywords: CONGEST, Proof Labelling Schemes, clique-width, MSO}
}
Document
Computing Power of Hybrid Models in Synchronous Networks

Authors: Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of an independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector x ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.

Cite as

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Computing Power of Hybrid Models in Synchronous Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.OPODIS.2022.20,
  author =	{Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
  title =	{{Computing Power of Hybrid Models in Synchronous Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.20},
  URN =		{urn:nbn:de:0030-drops-176401},
  doi =		{10.4230/LIPIcs.OPODIS.2022.20},
  annote =	{Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}
Document
Fault Tolerant Coloring of the Asynchronous Cycle

Authors: Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
We present a wait-free algorithm for proper coloring the n nodes of the asynchronous cycle C_n, where each crash-prone node starts with its (unique) identifier as input. The algorithm is independent of n ≥ 3, and runs in O(log^*n) rounds in C_n. This round-complexity is optimal thanks to a known matching lower bound, which applies even to synchronous (failure-free) executions. The range of colors used by our algorithm, namely {0,…,4}, is optimal too, thanks to a known lower bound on the minimum number of names for which renaming is solvable wait-free in shared-memory systems, whenever n is a power of a prime. Indeed, our model coincides with the shared-memory model whenever n = 3, and the minimum number of names for which renaming is possible in 3-process shared-memory systems is 5.

Cite as

Pierre Fraigniaud, Patrick Lambein-Monette, and Mikaël Rabie. Fault Tolerant Coloring of the Asynchronous Cycle. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.23,
  author =	{Fraigniaud, Pierre and Lambein-Monette, Patrick and Rabie, Mika\"{e}l},
  title =	{{Fault Tolerant Coloring of the Asynchronous Cycle}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.23},
  URN =		{urn:nbn:de:0030-drops-172147},
  doi =		{10.4230/LIPIcs.DISC.2022.23},
  annote =	{Keywords: graph coloring, LOCAL model, shared-memory model, immediate snapshot, renaming, wait-free algorithms}
}
Document
Brief Announcement
Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks

Authors: Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable.

Cite as

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2022.43,
  author =	{Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
  title =	{{Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.43},
  URN =		{urn:nbn:de:0030-drops-172345},
  doi =		{10.4230/LIPIcs.DISC.2022.43},
  annote =	{Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}
Document
Complete Volume
LIPIcs, Volume 226, FUN 2022, Complete Volume

Authors: Pierre Fraigniaud and Yushi Uno

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


Abstract
LIPIcs, Volume 226, FUN 2022, Complete Volume

Cite as

11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1-450, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{fraigniaud_et_al:LIPIcs.FUN.2022,
  title =	{{LIPIcs, Volume 226, FUN 2022, Complete Volume}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1--450},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022},
  URN =		{urn:nbn:de:0030-drops-159693},
  doi =		{10.4230/LIPIcs.FUN.2022},
  annote =	{Keywords: LIPIcs, Volume 226, FUN 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Pierre Fraigniaud and Yushi Uno

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


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.FUN.2022.0,
  author =	{Fraigniaud, Pierre and Uno, Yushi},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{0:i--0:xii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.0},
  URN =		{urn:nbn:de:0030-drops-159703},
  doi =		{10.4230/LIPIcs.FUN.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Pushing Blocks by Sweeping Lines

Authors: Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta

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


Abstract
We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well. Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete. We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.

Cite as

Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
  author =	{A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
  title =	{{Pushing Blocks by Sweeping Lines}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1:1--1:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1},
  URN =		{urn:nbn:de:0030-drops-159719},
  doi =		{10.4230/LIPIcs.FUN.2022.1},
  annote =	{Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}
Document
A Practical Algorithm for Chess Unwinnability

Authors: Miguel Ambrona

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


Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games. We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.

Cite as

Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ambrona:LIPIcs.FUN.2022.2,
  author =	{Ambrona, Miguel},
  title =	{{A Practical Algorithm for Chess Unwinnability}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{2:1--2:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2},
  URN =		{urn:nbn:de:0030-drops-159721},
  doi =		{10.4230/LIPIcs.FUN.2022.2},
  annote =	{Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
Document
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude

Authors: Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch

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


Abstract
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (first posed in 1999). We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later.

Cite as

Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ani_et_al:LIPIcs.FUN.2022.3,
  author =	{Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson},
  title =	{{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{3:1--3:30},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.3},
  URN =		{urn:nbn:de:0030-drops-159737},
  doi =		{10.4230/LIPIcs.FUN.2022.3},
  annote =	{Keywords: gadgets, motion planning, hardness of games}
}
Document
Fun Slot Machines and Transformations of Words Avoiding Factors

Authors: Marcella Anselmo, Manuela Flores, and Maria Madonia

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


Abstract
Fun Slot Machines are a variant of the classical ones. Pulling a lever, the player generates a sequence of symbols which are placed on the reels. The machine pays when a given pattern appears in the sequence. The variant consists in trying to transform a losing sequence of symbols in another one, in such a way that the winning pattern does not appear in any intermediate step. The choice of the winning pattern can be crucial; there are "good" and "bad" sequences. The game results in a combinatorial problem on transformations of words avoiding a given pattern as a factor. We investigate "good" and "bad" sequences on a k-ary alphabet and the pairs of words that witness that a word is "bad". A main result is an algorithm to decide whether a word is "bad" or not and to provide a pair of witnesses of minimal length when the word is "bad". It runs in O(n) time with a preprocessing of O(n) time and space to construct an enhanced suffix tree of the word.

Cite as

Marcella Anselmo, Manuela Flores, and Maria Madonia. Fun Slot Machines and Transformations of Words Avoiding Factors. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{anselmo_et_al:LIPIcs.FUN.2022.4,
  author =	{Anselmo, Marcella and Flores, Manuela and Madonia, Maria},
  title =	{{Fun Slot Machines and Transformations of Words Avoiding Factors}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{4:1--4: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4},
  URN =		{urn:nbn:de:0030-drops-159743},
  doi =		{10.4230/LIPIcs.FUN.2022.4},
  annote =	{Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance}
}
Document
Chess Is Hard Even for a Single Player

Authors: N.R. Aravind, Neeldhara Misra, and Harshil Mittal

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


Abstract
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.

Cite as

N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5,
  author =	{Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil},
  title =	{{Chess Is Hard Even for a Single Player}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{5:1--5:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5},
  URN =		{urn:nbn:de:0030-drops-159753},
  doi =		{10.4230/LIPIcs.FUN.2022.5},
  annote =	{Keywords: chess, strategy, board games, NP-complete}
}
  • Refine by Author
  • 23 Fraigniaud, Pierre
  • 7 Paz, Ami
  • 4 Montealegre, Pedro
  • 4 Rapaport, Ivan
  • 4 Todinca, Ioan
  • Show More...

  • Refine by Classification
  • 12 Theory of computation → Distributed algorithms
  • 7 Theory of computation → Design and analysis of algorithms
  • 5 Theory of computation → Distributed computing models
  • 4 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 4 Distributed Network Computing
  • 3 CONGEST
  • 3 Distributed verification
  • 2 Algorithmic Aspects of Networks
  • 2 Broadcast Congested Clique
  • Show More...

  • Refine by Type
  • 49 document
  • 1 volume

  • Refine by Publication Year
  • 29 2022
  • 4 2017
  • 4 2023
  • 3 2021
  • 2 2016
  • Show More...

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