Search

In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S_1 and S_2 of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S_1 and S_2. We demonstrate that this is polynomial-time solvable if S_1 and S_2 have constant numbers of polyominoes, and it is strongly NP-complete in general. The second puzzle allows us to make copies of the pieces in S_1 and S_2. That is, a polyomino in S_1 can be used multiple times to form a shape. This is a generalized version of the classical puzzle known as the common multiple shape puzzle. For two polyominoes P and Q, the common multiple shape is a shape that can be formed by many copies of P and many copies of Q. We show that the second puzzle is undecidable in general. The undecidability is demonstrated by a reduction from a new type of undecidable puzzle based on tiling. Nevertheless, certain concrete instances of the common multiple shape can be solved in a practical time. We present a method for determining the common multiple shape for provided tuples of polyominoes and outline concrete results, which improve on the previously known results in puzzle society.

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 in 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., 17 pages, 10 figures

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., LIPIcs, Vol. 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), pages 4:1-4:19

Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple type of fixed-angle linkage: every edge has unit length (equilateral), and each joint has a fixed angle of $90^\circ$ (orthogonal) or $180^\circ$ (straight). When the linkage forms a path (open chain), it always has a planar configuration, namely the zig-zag which alternating the $90^\circ$ angles between left and right turns. But when the linkage forms a cycle (closed chain), or is forced to lie in a box of fixed size, we prove that the flattening problem -- deciding whether there is a planar noncrossing configuration -- is strongly NP-complete. Back to open chains, we turn to the Hydrophobic-Hydrophilic (HP) model of protein folding, where each vertex is labeled H or P, and the goal is to find a folding that maximizes the number of H-H adjacencies. In the well-studied HP model, the joint angles are not fixed. We introduce and analyze the fixed-angle HP model, which is motivated by real-world proteins. We prove strong NP-completeness of finding a planar noncrossing configuration of a fixed-angle orthogonal equilateral open chain with the most H--H adjacencies, even if the chain has only two H vertices. (Effectively, this lets us force the chain to be closed.), Comment: 26 pages, 16 figures. A preliminary version was presented at CCCG 2022

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., LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 6:1-6:16

We show that several classes of polyhedra are joined by a sequence of O(1) refolding steps, where each refolding step unfolds the current polyhedron (allowing cuts anywhere on the surface and allowing overlap) and folds that unfolding into exactly the next polyhedron; in other words, a polyhedron is refoldable into another polyhedron if they share a common unfolding. Specifically, assuming equal surface area, we prove that (1) any two tetramonohedra are refoldable to each other, (2) any doubly covered triangle is refoldable to a tetramonohedron, (3) any (augmented) regular prismatoid and doubly covered regular polygon is refoldable to a tetramonohedron, (4) any tetrahedron has a 3-step refolding sequence to a tetramonohedron, and (5) the regular dodecahedron has a 4-step refolding sequence to a tetramonohedron. In particular, we obtain at most 6-step refolding sequence between any pair of Platonic solids, applying (5) for the dodecahedron and (1) and/or (2) for all other Platonic solids. As far as the authors know, this is the first result about common unfolding involving the regular dodecahedron.

We investigate the folding problem that asks if a polygon P can be folded to a polyhedron Q for given P and Q. Recently, an efficient algorithm for this problem has been developed when Q is a box. We extend this idea to regular polyhedra, also known as Platonic solids. The basic idea of our algorithms is common, which is called stamping. However, the computational complexities of them are different depending on their geometric properties. We developed four algorithms for the problem as follows. (1) An algorithm for a regular tetrahedron, which can be extended to a tetramonohedron. (2) An algorithm for a regular hexahedron (or a cube), which is much efficient than the previously known one. (3) An algorithm for a general deltahedron, which contains the cases that Q is a regular octahedron or a regular icosahedron. (4) An algorithm for a regular dodecahedron. Combining these algorithms, we can conclude that the folding problem can be solved pseudo-polynomial time when Q is a regular polyhedron and other related solid.

For a graph class C, the C -Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C -Edge-Deletion problem for C the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.

This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxP_k VC for short): A path consisting of k vertices, i.e., a path of length k－1 is called a k-path. If a k-path P_k includes a vertex v in a vertex set S, then we say that S or v covers Pk . Given a graph G=(V,E) and an integer s, the goal of MaxP_kVC is to find a vertex subset S included in V of at most s vertices such that the number of k-paths covered by S is maximized. MaxPk VC is generally NP-hard. In this paper we consider the tractability/intractability of MaxP_kVC on subclasses of graphs: We prove that MaxP_3 VC and MaxP_4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP_3 VC can be solved in polynomial time., WALCOM: Algorithms and Computation, 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings

Front Matter, Table of Contents, Preface, Conference Organization

LIPIcs, Volume 157, FUN 2021, Complete Volume

We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We first investigate a large class of graphs, which generalizes several classic puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.

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., LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 12:1-12:17

Given a set P of n elements, and a function d that assigns a non-negative real number d(p, q) for each pair of elements p,q∈P, we want to find a subset S⊆P with |S|=k such that cost(S)=min{d(p,q)∣p,q∈S} is maximized. This is the max-min k-dispersion problem. In this paper, exact algorithms for the max-min k-dispersion problem are studied. We first show the max-min k-dispersion problem can be solved in O(n^/^3logn) time. Then, we show two special cases in which we can solve the problem quickly., Frontiers in Algorithmics,12th International Workshop, FAW 2018, Guangzhou, China, May 8-10, 2018, Proceedings

The Tokyo 2020 Olympic and Paralympic games emblems, called ``harmonized chequered emblems,'' are designed with three kinds of rectangles. We enumerate all such tilings in a dodecagon with a hole.

Peg solitaire is one of the most popular classic puzzles around the world. It was proved that this puzzle was computationally intractable in general in 1990. The most common form of the puzzle consists of board with 33 holes and 32 pegs. A lot of solutions have been found by puzzle players by hand, and heuristic algorithms were developed in the 1990s. However, (super)computers running sophisticated algorithms can now enumerate all the solutions for this puzzle in a few minutes. That is, we can now completely solve certain peg solitaire puzzles of reasonable size. Using this technique, we design a ``peg solitaire font'' in the following way. We start with a peg solitaire puzzle on a board of size 5 x 7, which consists of 35 holes filled using 34 pegs placed in all holes except the central hole. Our algorithm running on a (super)computer generates all possible patterns reachable from the initial state. We find that there are 1,045,173,439 reachable patterns from the initial state. From these reachable patterns, we extract or ``design'' our font so that each of the characters in our font can be reached from the initial state. Readers are invited to solve the associated peg solitaire puzzle for each character.

Let I, J be two given independent sets of a graph G. Imagine that the vertices of an independent set are viewed as tokens (coins). A token is allowed to move (or slide) from one vertex to one of its neighbors. The Sliding Token problem asks whether there exists a sequence of independent sets of G starting from I and ending with J such that each intermediate member of the sequence is obtained from the previous one by moving a token according to the allowed rule. In this paper, we claim that this problem is solvable in polynomial time when the input graph is a block graph—a graph whose blocks are cliques. Our algorithm is developed based on the characterization of a non-trivial structure that, in certain conditions, can be used to indicate a no-instance of the problem. Without such a structure, a sequence of token slidings between any two independent sets exists., WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017, Proceedings

The Buttons and Scissors puzzle was recently shown to be NP-hard. In this paper we continue studying the complexity of various versions of the puzzle. For example, we show that it is NP-hard when the puzzle consists of C=2 colors, and polytime solvable for C=1. Similarly, it is NP-hard when each color is used by at most F=4 buttons, and polytime solvable for F=3. We also consider restrictions on the board size, cut directions, and cut lengths. Finally, we introduce new two-player games and show that they are PSPACE-complete., Discrete and Computational Geometry and Graphs. JCDCGG 2015.

A cube is used as a fair die of 6 faces. However, there are many dice of different shapes on the market. To make them fair, most of them usually have some symmetric shapes. We here classify these variants of dice on the market into two groups. We first consider that a sphere as a model of a fair die with infinity faces. Based on this model, many symmetric shapes can be modeled as dice obtained by caving spheres. We also have a familiar fair device; a coin. That is, a fair coin can be seen as a fair die with 2 faces. However, a real coin has a thickness, and hence it is, in fact, an unfair die with 3 faces. From this viewpoint, we propose a way for designing a fair die with n faces for arbitrary n.

For a graph class \(\mathcal {C}\), the \(\mathcal {C}\)-Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in \(\mathcal {C}\). We study the \(\mathcal {C}\)-Edge-Deletion problem for \(\mathcal {C}\) the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.

For given two independent sets I_b and I_r of a graph, the sliding token problem is to determine if there exists a sequence of independent sets which transforms I_b into I_r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. These problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems for finding a shortest reconfiguration sequence are investigated. For the 3SAT reconfiguration problem, a trichotomy for the complexity of finding the shortest sequence has been shown; it is in P, NP-complete, or PSPACE-complete in certain conditions. Even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. We show nontrivial polynomial time algorithms for finding a shortest sequence between two independent sets for some graph classes. As far as the authors know, one of them is the first polynomial time algorithm for the shortest sliding token problem that requires detours of tokens., Algorithms and Computation. WALCOM 2016.

Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs., Algorithms and Computation, 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings

Suppose that two independent sets $I$ and $J$ of a graph with $\vert I \vert = \vert J \vert$ are given, and a token is placed on each vertex in $I$. The Sliding Token problem is to determine whether there exists a sequence of independent sets which transforms $I$ into $J$ so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. It is one of the representative reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. For a yes-instance of a reconfiguration problem, finding a shortest reconfiguration sequence has a different aspect. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be $\mathsf{NP}$-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for spiders (i.e., trees having exactly one vertex of degree at least three)., Accepted for presentation at CIAC 2019

This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k−1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that S or v covers Pk . Given a graph G=(V,E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs: We prove that MaxP3VC and MaxP4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (\(\mathsf{{Max}}{P_k}\mathsf{VC}\) for short): A path consisting of k vertices, i.e., a path of length \(k-1\) is called a k-path. If a k-path \(P_k\) includes a vertex v in a vertex set S, then we say that S or v covers \(P_k\). Given a graph \(G = (V, E)\) and an integer s, the goal of \(\mathsf{{Max}}{P_k}\mathsf{VC}\) is to find a vertex subset \(S\subseteq V\) of at most s vertices such that the number of k-paths covered by S is maximized. \(\mathsf{{Max}}{P_k}\mathsf{VC}\) is generally NP-hard. In this paper we consider the tractability/intractability of \(\mathsf{{Max}}{P_k}\mathsf{VC}\) on subclasses of graphs: We prove that \(\mathsf{{Max}}{P_3}\mathsf{VC}\) and \(\mathsf{{Max}}{P_4}\mathsf{VC}\) remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then \(\mathsf{{Max}}{P_3}\mathsf{VC}\) can be solved in polynomial time.

Consider an undirected and vertex-weighted graph modelinga social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights., Algorithms and Data Structures, 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings

We investigate the computational complexity of the followingproblem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform as small numbers of swappings as possible so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,...,c}, we call this problem c-Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-Colored Token Swapping is NP-complete for every constant c>3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs and in linear time for trees., Algorithms and Data Structures, 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings

Given two independent sets $I, J$ of a graph $G$, and imagine that a token (coin) is placed at each vertex of $I$. The Sliding Token problem asks if one could transform $I$ to $J$ via a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors so that the resulting set of vertices where tokens are placed remains independent. This problem is $\mathsf{PSPACE}$-complete even for planar graphs of maximum degree $3$ and bounded-treewidth. In this paper, we show that Sliding Token can be solved efficiently for cactus graphs and block graphs, and give upper bounds on the length of a transformation sequence between any two independent sets of these graph classes. Our algorithms are designed based on two main observations. First, all structures that forbid the existence of a sequence of token slidings between $I$ and $J$, if exist, can be found in polynomial time. A sufficient condition for determining no-instances can be easily derived using this characterization. Second, without such forbidden structures, a sequence of token slidings between $I$ and $J$ does exist. In this case, one can indeed transform $I$ to $J$ (and vice versa) using a polynomial number of token-slides., Comment: The algorithm for block graphs in this manuscript contains some flaws. More precisely, Proposition 20 is not correct. Therefore, we withdraw this manuscript

We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general., Fun with Algorithms, 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings

We introduce a concept of intersection dimension of a graphwith respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graphtheoretic results, we show that the recognition problems for certain graph classes are NP-complete., Theory and Applications of Models of Computation, 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings

The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem., WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings

We investigate a silhouette puzzle that is recently developed based on the golden ratio. Traditional silhouette puzzles are based on a simple tile. For example, the tangram is based on isosceles right triangles; that is, each of seven pieces is formed by gluing some identical isosceles right triangles. Using the property, we can analyze it by hand, that is, without computer. On the other hand, if each piece has no special property, it is quite hard even using computer since we have to handle real numbers without numerical errors during computation. The new silhouette puzzle is between them; each of seven pieces is not based on integer length and right angles, but based on golden ratio, which admits us to represent these seven pieces in some nontrivial way. Based on the property, we develop an algorithm to handle the puzzle, and our algorithm succeeded to enumerate all convex shapes that can be made by the puzzle pieces. It is known that the tangram and another classic silhouette puzzle known as Sei-shonagon chie no ita can form 13 and 16 convex shapes, respectively. The new puzzle, Nana-kin-san puzzle, admits to form 62 different convex shapes.

Given two independent sets I and J of a graph G, imagine that a token (coin) is placed on each vertex in I. Then, the Sliding Token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors, such that the resulting set of vertices where tokens are placed still remains independent. In this paper, we describe a polynomial-time algorithm for solving Sliding Token in case the graph G is a cactus. Our algorithm is designed based on two observations. First, all structures that forbid the existence of a sequence of token slidings between I and J, if exist, can be found in polynomial time. A no-instance may be easily deduced using this characterization. Second, without such forbidden structures, a sequence of token slidings between I and J does exist.

We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for $C = 2$ colors but polytime solvable for $C = 1$. Similarly the game is NP-complete if every color is used by at most $F = 4$ buttons but polytime solvable for $F \leq 3$. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete., 21 pages, 15 figures. Presented at JCDCG2 2015, Kyoto University, Kyoto, Japan, September 14 - 16, 2015

A procedure that produces a common unfolding of aregular tetrahedron and a cube is given. It is adaptableto the length of an edge. If we allow a small errorof the length of an edge of the tetrahedron, the procedurecertainly halts and generates a common unfoldingof a cube and an almost regular tetramonohedron.If we wish to generate the common unfolding of themwith accuracy, we conjecture that the procedure doesnot halt and we obtain the common unfolding in thelimit as a set of infinitely many points. The procedurehas a potential to design a fractal structure given ina continued fraction form.

Kaboozle is a puzzle consisting of several square cards, each annotated with colored paths and dots drawn on both sides and holes drilled. The goal is to join two colored dots with paths of the same color (and fill all holes) by stacking the cards suitably. The freedoms here are to reflect, rotate, and order the cards arbitrarily, so it is not surprising that the problem is NP-complete (as we show). More surprising is that any one of these freedoms—reflection, rotation, and order—is alone enough to make the puzzle NP-complete. Furthermore, we show NP-completeness of a particularly constrained form of Kaboozle related to 1D paper folding. Specifically, we suppose that the cards are glued together into a strip, where each glued edge has a specified folding direction (mountain or valley). This variation removes the ability to rotate and reflect cards, and restricts the order to be a valid folded state of a given 1D mountain-valley pattern., Fun with Algorithms, 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010.

The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N_1,N_2 with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N_1and N_2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m+e)) time. In this paper, we improve the time complexity to O(n(m + e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m+e) time for planar phylogenetic networks and boundedlevel phylogenetic networks. We also introduce the natural concept of theminimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time., Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010.