44 Search Results for "Uehara, Ryuhei"

Volume

LIPIcs, Volume 157

10th International Conference on Fun with Algorithms (FUN 2021)

FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy

Editors: Martin Farach-Colton, Giuseppe Prencipe, and Ryuhei Uehara

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.38
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Authors: Nader H. Bshouty and George Haddad

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:ℝ^+ → ℝ^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ^{-1}(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n) ≤ n relevant variables), where k(n) = ω_n(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Γ(n))T(Γ(n)²)-time algorithm that properly learns parities, where Γ(x) = γ(γ(x)). If T(Γ(n)²) = exp({o(n/log n)}), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).
Cite as

Nader H. Bshouty and George Haddad. Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.APPROX/RANDOM.2024.38,
  author =	{Bshouty, Nader H. and Haddad, George},
  title =	{{Approximating the Number of Relevant Variables in a Parity Implies Proper Learning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  URN =		{urn:nbn:de:0030-drops-210316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  annote =	{Keywords: PAC Learning, Random Classification Noise, Uniform Distribution, Parity, Sparcity Approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.12
Generalizing Roberts' Characterization of Unit Interval Graphs

Authors: Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine, Florian Sikora, and Stéphane Vialette

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

Abstract
For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1,2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2.
Cite as

Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine, Florian Sikora, and Stéphane Vialette. Generalizing Roberts' Characterization of Unit Interval Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ardevolmartinez_et_al:LIPIcs.MFCS.2024.12,
  author =	{Ard\'{e}vol Mart{\'\i}nez, Virginia and Rizzi, Romeo and Saffidine, Abdallah and Sikora, Florian and Vialette, St\'{e}phane},
  title =	{{Generalizing Roberts' Characterization of Unit Interval Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{12:1--12:15},
  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.12},
  URN =		{urn:nbn:de:0030-drops-205687},
  doi =		{10.4230/LIPIcs.MFCS.2024.12},
  annote =	{Keywords: Interval graphs, Multiple Interval Graphs, Unit Interval Graphs, Characterization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.26
Scalable Hard Instances for Independent Set Reconfiguration

Authors: Takehide Soh, Takumu Watanabe, Jun Kawahara, Akira Suzuki, and Takehiro Ito

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Token Jumping problem, also known as the independent set reconfiguration problem under the token jumping model, is defined as follows: Given a graph and two same-sized independent sets, determine whether one can be transformed into the other via a sequence of independent sets. Token Jumping has been extensively studied, mainly from the viewpoint of algorithmic theory, but its practical study has just begun. To develop a practically good solver, it is important to construct benchmark datasets that are scalable and hard. Here, "scalable" means the ability to change the scale of the instance while maintaining its characteristics by adjusting the given parameters; and "hard" means that the instance can become so difficult that it cannot be solved within a practical time frame by a solver. In this paper, we propose four types of instance series for Token Jumping. Our instance series is scalable in the sense that instance scales are controlled by the number of vertices. To establish their hardness, we focus on the numbers of transformation steps; our instance series requires exponential numbers of steps with respect to the number of vertices. Interestingly, three types of instance series are constructed by importing theories developed by algorithmic research. We experimentally evaluate the scalability and hardness of the proposed instance series, using the SAT solver and award-winning solvers of the international competition for Token Jumping.
Cite as

Takehide Soh, Takumu Watanabe, Jun Kawahara, Akira Suzuki, and Takehiro Ito. Scalable Hard Instances for Independent Set Reconfiguration. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{soh_et_al:LIPIcs.SEA.2024.26,
  author =	{Soh, Takehide and Watanabe, Takumu and Kawahara, Jun and Suzuki, Akira and Ito, Takehiro},
  title =	{{Scalable Hard Instances for Independent Set Reconfiguration}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.26},
  URN =		{urn:nbn:de:0030-drops-203913},
  doi =		{10.4230/LIPIcs.SEA.2024.26},
  annote =	{Keywords: Combinatorial reconfiguration, Benckmark dataset, Graph Algorithm, PSPACE-complete}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.76
Solution Discovery via Reconfiguration for Problems in P

Authors: Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, and Sebastian Siebertz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of k tokens on a graph and the question is whether we can transform this configuration into a feasible solution (for some problem) via a bounded number b of small modification steps. In this work, we study solution discovery variants of polynomial-time solvable problems, namely Spanning Tree Discovery, Shortest Path Discovery, Matching Discovery, and Vertex/Edge Cut Discovery in the unrestricted token addition/removal model, the token jumping model, and the token sliding model. In the unrestricted token addition/removal model, we show that all four discovery variants remain in P. For the token jumping model we also prove containment in P, except for Vertex/Edge Cut Discovery, for which we prove NP-completeness. Finally, in the token sliding model, almost all considered problems become NP-complete, the exception being Spanning Tree Discovery, which remains polynomial-time solvable. We then study the parameterized complexity of the NP-complete problems and provide a full classification of tractability with respect to the parameters solution size (number of tokens) k and transformation budget (number of steps) b. Along the way, we observe strong connections between the solution discovery variants of our base problems and their (weighted) rainbow variants as well as their red-blue variants with cardinality constraints.
Cite as

Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, and Sebastian Siebertz. Solution Discovery via Reconfiguration for Problems in P. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.ICALP.2024.76,
  author =	{Grobler, Mario and Maaz, Stephanie and Megow, Nicole and Mouawad, Amer E. and Ramamoorthi, Vijayaragunathan and Schmand, Daniel and Siebertz, Sebastian},
  title =	{{Solution Discovery via Reconfiguration for Problems in P}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{76:1--76:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.76},
  URN =		{urn:nbn:de:0030-drops-202195},
  doi =		{10.4230/LIPIcs.ICALP.2024.76},
  annote =	{Keywords: solution discovery, reconfiguration, spanning tree, shortest path, matching, cut}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.85
Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration

Authors: Shuichi Hirahara and Naoto Ohsaka

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the Minmax Set Cover Reconfiguration problem, given a set system ℱ over a universe 𝒰 and its two covers 𝒞^start and 𝒞^goal of size k, we wish to transform 𝒞^start into 𝒞^goal by repeatedly adding or removing a single set of ℱ while covering the universe 𝒰 in any intermediate state. Then, the objective is to minimize the maximum size of any intermediate cover during transformation. We prove that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are PSPACE-hard to approximate within a factor of 2-(1/polyloglog N), where N is the size of the universe and the number of vertices in a graph, respectively, improving upon Ohsaka (SODA 2024) [Ohsaka, 2024] and Karthik C. S. and Manurangsi (2023) [Karthik C. S. and Manurangsi, 2023]. This is the first result that exhibits a sharp threshold for the approximation factor of any reconfiguration problem because both problems admit a 2-factor approximation algorithm as per Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (Theor. Comput. Sci., 2011) [Takehiro Ito et al., 2011]. Our proof is based on a reconfiguration analogue of the FGLSS reduction [Feige et al., 1996] from Probabilistically Checkable Reconfiguration Proofs of Hirahara and Ohsaka (STOC 2024) [Hirahara and Ohsaka, 2024]. We also prove that for any constant ε ∈ (0,1), Minmax Hypergraph Vertex Cover Reconfiguration on poly(ε^-1)-uniform hypergraphs is PSPACE-hard to approximate within a factor of 2-ε.
Cite as

Shuichi Hirahara and Naoto Ohsaka. Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 85:1-85:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ICALP.2024.85,
  author =	{Hirahara, Shuichi and Ohsaka, Naoto},
  title =	{{Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{85:1--85:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.85},
  URN =		{urn:nbn:de:0030-drops-202283},
  doi =		{10.4230/LIPIcs.ICALP.2024.85},
  annote =	{Keywords: reconfiguration problems, hardness of approximation, probabilistic proof systems, FGLSS reduction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.113
Alphabet Reduction for Reconfiguration Problems

Authors: Naoto Ohsaka

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We present a reconfiguration analogue of alphabet reduction à la Dinur (J. ACM, 2007) and its applications. Given a binary constraint graph G and its two satisfying assignments ψ^ini and ψ^tar, the Maxmin 2-CSP Reconfiguration problem requests to transform ψ^ini into ψ^tar by repeatedly changing the value of a single vertex so that the minimum fraction of satisfied edges is maximized. We demonstrate a polynomial-time reduction from Maxmin 2-CSP Reconfiguration with arbitrarily large alphabet size W ∈ ℕ to itself with universal alphabet size W₀ ∈ ℕ such that 1) the perfect completeness is preserved, and 2) if any reconfiguration for the former violates ε-fraction of edges, then Ω(ε)-fraction of edges must be unsatisfied during any reconfiguration for the latter. The crux of its construction is the reconfigurability of Hadamard codes, which enables to reconfigure between a pair of codewords, while avoiding getting too close to the other codewords. Combining this alphabet reduction with gap amplification due to Ohsaka (SODA 2024), we are able to amplify the 1 vs. 1-ε gap for arbitrarily small ε ∈ (0,1) up to the 1 vs. 1-ε₀ for some universal ε₀ ∈ (0,1) without blowing up the alphabet size. In particular, a 1 vs. 1-ε₀ gap version of Maxmin 2-CSP Reconfiguration with alphabet size W₀ is PSPACE-hard given a probabilistically checkable reconfiguration proof system having any soundness error 1-ε due to Hirahara and Ohsaka (STOC 2024) and Karthik C. S. and Manurangsi (2023). As an immediate corollary, we show that there exists a universal constant ε₀ ∈ (0,1) such that many popular reconfiguration problems are PSPACE-hard to approximate within a factor of 1-ε₀, including those of 3-SAT, Independent Set, Vertex Cover, Clique, Dominating Set, and Set Cover. This may not be achieved only by gap amplification of Ohsaka, which makes the alphabet size gigantic depending on ε^-1.
Cite as

Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 113:1-113:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ohsaka:LIPIcs.ICALP.2024.113,
  author =	{Ohsaka, Naoto},
  title =	{{Alphabet Reduction for Reconfiguration Problems}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{113:1--113:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.113},
  URN =		{urn:nbn:de:0030-drops-202560},
  doi =		{10.4230/LIPIcs.ICALP.2024.113},
  annote =	{Keywords: reconfiguration problems, hardness of approximation, Hadamard codes, alphabet reduction}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.17
Computational Complexity of Matching Match Puzzle

Authors: Yuki Iburi and Ryuhei Uehara

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Various forms of graph coloring problems have been studied over the years in the society of graph theory. Recently, some original puzzles are popularized in Japanese 100-yen shops, and one of them can be formalized as a graph coloring problem in a natural way. However, this natural graph coloring problem has not been investigated in the context of the graph theory. In this paper, we investigate this puzzle as a graph coloring problem. We first prove that this graph coloring problem is NP-complete even when the graph is restricted to a path or a spider. In these cases, diameter of the graphs seems to play an important role for its difficulty. We then show that the problem can be solved in polynomial time when the graph is restricted to some graph classes of constant diameter.
Cite as

Yuki Iburi and Ryuhei Uehara. Computational Complexity of Matching Match Puzzle. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{iburi_et_al:LIPIcs.FUN.2024.17,
  author =	{Iburi, Yuki and Uehara, Ryuhei},
  title =	{{Computational Complexity of Matching Match Puzzle}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.17},
  URN =		{urn:nbn:de:0030-drops-199251},
  doi =		{10.4230/LIPIcs.FUN.2024.17},
  annote =	{Keywords: Graph coloring, Matching Match puzzle, NP-complete, polynomial-time solvable}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.9
Minimum Separator Reconfiguration

Authors: Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.
Cite as

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
  author =	{C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
  title =	{{Minimum Separator Reconfiguration}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9},
  URN =		{urn:nbn:de:0030-drops-194288},
  doi =		{10.4230/LIPIcs.IPEC.2023.9},
  annote =	{Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.37
On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding

Authors: Szilárd Zsolt Fazekas, Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki, and Hinano Takeuchi

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Algorithms play a primary role in programming an orchestrated self-assembly of shapes into molecules. In this paper, we study the algorithmic self-assembly of squares by RNA co-transcriptional folding in its oritatami model. We formalize the square self-assembly problem in oritatami and propose a universal oritatami transcript made of 939 types of abstract molecules (beads) and of period 1294 that folds deterministically and co-transcriptionally at delay 3 and maximum arity into the n × n square modulo horizontal and vertical scaling factors for all sufficiently large n’s after building a Θ(log n) width "ruler" that measures n upon the seed of size Θ(log n) on which n is encoded in binary.
Cite as

Szilárd Zsolt Fazekas, Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki, and Hinano Takeuchi. On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fazekas_et_al:LIPIcs.ISAAC.2022.37,
  author =	{Fazekas, Szil\'{a}rd Zsolt and Kim, Hwee and Matsuoka, Ryuichi and Seki, Shinnosuke and Takeuchi, Hinano},
  title =	{{On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.37},
  URN =		{urn:nbn:de:0030-drops-173228},
  doi =		{10.4230/LIPIcs.ISAAC.2022.37},
  annote =	{Keywords: Algorithmic molecular self-assembly, Co-transcriptional folding, Oritatami system, Self-assembly of squares}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.4
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares

Authors: Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of n squares into any other using at most O(n²) sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require Ω(n²) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only O( ̄P n) sliding moves to transform one configuration into the other, where ̄P is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( ̄P n) bound never exceeds O(n²), and is optimal (up to constant factors) among all bounds parameterized by just n and ̄P. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid xy-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.
Cite as

Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.SWAT.2022.4,
  author =	{A. Akitaya, Hugo and Demaine, Erik D. and Korman, Matias and Kostitsyna, Irina and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Uehara, Ryuhei and Wulms, Jules},
  title =	{{Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.4},
  URN =		{urn:nbn:de:0030-drops-161644},
  doi =		{10.4230/LIPIcs.SWAT.2022.4},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.6
Rolling Polyhedra on Tessellations

Authors: Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams

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

Abstract
We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.
Cite as

Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baes_et_al:LIPIcs.FUN.2022.6,
  author =	{Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron},
  title =	{{Rolling Polyhedra on Tessellations}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{6:1--6:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6},
  URN =		{urn:nbn:de:0030-drops-159761},
  doi =		{10.4230/LIPIcs.FUN.2022.6},
  annote =	{Keywords: polyhedra, tilings}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.16
Sorting Balls and Water: Equivalence and Computational Complexity

Authors: Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka

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

Abstract
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.
Cite as

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2022.16,
  author =	{Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo},
  title =	{{Sorting Balls and Water: Equivalence and Computational Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{16:1--16:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.16},
  URN =		{urn:nbn:de:0030-drops-159867},
  doi =		{10.4230/LIPIcs.FUN.2022.16},
  annote =	{Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.33
Gourds: A Sliding-Block Puzzle with Turning

Authors: Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1×2 pieces on a hexagonal grid board of 2n+1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant.
Cite as

Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden. Gourds: A Sliding-Block Puzzle with Turning. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hamersma_et_al:LIPIcs.ISAAC.2020.33,
  author =	{Hamersma, Joep and van Kreveld, Marc and Uno, Yushi and van der Zanden, Tom C.},
  title =	{{Gourds: A Sliding-Block Puzzle with Turning}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.33},
  URN =		{urn:nbn:de:0030-drops-133773},
  doi =		{10.4230/LIPIcs.ISAAC.2020.33},
  annote =	{Keywords: computational complexity, divide-and-conquer, Hamiltonian cycle, puzzle game, (combinatorial) reconfiguration, sliding-block puzzle}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.12
Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots

Authors: Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction (chirality), they are activated by an adversarial semi-synchronous scheduler (SSYNCH), and an active robot always reaches the destination point it computes (rigidity). Robots have limited visibility: each robot can see only the points on the circle that have an angular distance strictly smaller than a constant ϑ from the robot’s current location, where 0 < ϑ ≤ π (angles are expressed in radians). We study the Gathering problem for such a swarm of robots: that is, all robots are initially in distinct locations on the circle, and their task is to reach the same point on the circle in a finite number of turns, regardless of the way they are activated by the scheduler. Note that, due to the anonymity of the robots, this task is impossible if the initial configuration is rotationally symmetric; hence, we have to make the assumption that the initial configuration be rotationally asymmetric. We prove that, if ϑ = π (i.e., each robot can see the entire circle except its antipodal point), there is a distributed algorithm that solves the Gathering problem for swarms of any size. By contrast, we also prove that, if ϑ ≤ π/2, no distributed algorithm solves the Gathering problem, regardless of the size of the swarm, even under the assumption that the initial configuration is rotationally asymmetric and the visibility graph of the robots is connected. The latter impossibility result relies on a probabilistic technique based on random perturbations, which is novel in the context of anonymous mobile robots. Such a technique is of independent interest, and immediately applies to other Pattern-Formation problems.
Cite as

Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi. Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2020.12,
  author =	{Di Luna, Giuseppe A. and Uehara, Ryuhei and Viglietta, Giovanni and Yamauchi, Yukiko},
  title =	{{Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.12},
  URN =		{urn:nbn:de:0030-drops-130907},
  doi =		{10.4230/LIPIcs.DISC.2020.12},
  annote =	{Keywords: Mobile robots, Gathering, limited visibility, circle}
}
  • Refine by Author
  • 10 Uehara, Ryuhei
  • 5 Demaine, Erik D.
  • 2 Bosboom, Jeffrey
  • 2 Brunner, Josh
  • 2 Demaine, Martin L.
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Problems, reductions and completeness
  • 5 Theory of computation → Computational geometry
  • 4 Theory of computation
  • 3 Security and privacy → Information-theoretic techniques
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 Card-based cryptography
  • 2 Minesweeper
  • 2 NP-hardness
  • 2 Zero-knowledge proof
  • 2 algorithms
  • Show More...

  • Refine by Type
  • 43 document
  • 1 volume

  • Refine by Publication Year
  • 29 2020
  • 7 2024
  • 4 2022
  • 2 2016
  • 1 2019
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact