Search

For a given set of pieces and a frame, an anti-slide puzzle asks us to arrange the pieces so that none of the pieces can slide in the frame. Since the first anti-slide puzzle that consists of dozens of cuboid pieces in 3D was invented, tons of anti-slide puzzles using pentominoes have been proposed. Some of them are not in a frame, which we call that interlock puzzles. In this paper, we investigate computational complexity of anti-slide puzzles and interlock puzzles in 2D. In previous work in theoretical computer science, a few models have been proposed for dealing with the notion of anti-slide, however, there exist gaps between these models and real puzzles. We first give mathematical characterizations of anti-slide puzzles and show the relationship between the previous work. Using a mathematical characterization, we give a polynomial time algorithm for determining if a given arrangement of polyominoes is anti-slide or not in a model. Next, we prove that the decision problem whether a given set of polyominoes can be arranged to be anti-slide or not is strongly NP-complete even if every piece is x -monotone. On the other hand, a set of pieces cannot be arranged to be interlocked if all pieces are convex polygons. [ABSTRACT FROM AUTHOR]

Suppose that two independent sets I b and I r of a graph such that | I b | = | I r | are given, and a token is placed on each vertex in I b. The sliding token problem is to determine whether 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. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. In general, even if it is polynomial time solvable to decide whether two instances are reconfigurable into each other, it can be 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 some graph classes which are subclasses of the class of interval graphs. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours. [ABSTRACT FROM AUTHOR]

We investigate the enumeration problems for the class of distance-hereditary graphs and related graph classes. We first give an enumeration algorithm for the class of distance-hereditary graphs using the recent framework for enumerating every non-isomorphic element in a graph class. In the algorithm, we use the vertex-incremental characterization of distance-hereditary graphs, which consists of three generation rules for adding one vertex to a distance-hereditary graph. Reducing the three generation rules, we can obtain vertex-incremental characterization of cographs and (6,2)-chordal bipartite graphs. These enumeration algorithms are slower than previously known theoretical enumeration algorithms, however, ours are easy to implement. In fact, we implemented our algorithm and obtained catalogs of these graph classes of up to 15 vertices. The class of Ptolemaic graphs is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. We modify the enumeration algorithm for distance-hereditary graphs and obtain an enumeration algorithm for Ptolemaic graphs. The running time of the enumeration of Ptolemaic graphs is much improved from the previously known one, and we also enumerated the graphs up to 15 vertices. We also enumerate the class of 3-leaf power graphs by modifying the algorithm for Ptolemaic graphs. As far as the authors know, some of these graph classes had been counted, however, they had never been enumerated. [ABSTRACT FROM AUTHOR]

We give an efficient encoding and decoding scheme for computing a compact representation of a graph in one of unordered reduced trees, cographs and series-parallel graphs. The unordered reduced trees are rooted trees in which (i) the ordering of children of each vertex does not matter, and (ii) no vertex has exactly one child. This is one of basic models frequently used in many areas. Our algorithm computes a bit string of length 2ℓ - 1 for a given unordered reduced tree with £ ≧ 1 leaves in 0(f) time, whereas a known folklore algorithm computes a bit string of length 2n - 2 for an ordered tree with n vertices. Note that in an unordered reduced tree, ℓ £ n < 2ℓ holds. To the best of our knowledge this is the first of such a compact representation for unordered reduced trees. From the theoretical point of view, the length of the representation gives us an upper bound of the number of unordered reduced trees with £ leaves. Precisely, the number of unordered reduced trees with £ leaves is at most 22ℓ-2 for £ > 1. Moreover, the encoding and decoding can be done in linear time. Therefore, from the practical point of view, our representation is also useful to store a lot of unordered reduced trees efficiently. We also apply the scheme for computing a compact representation to cographs and series-parallel graphs. We show that each of cographs with n vertices has a compact representation in 2n - 1 bits, and the number of cographs with n vertices is at most 22n-1. The resulting flumber is close to the number of cographs with rivertices obtained by the enumeration for small n that approximates Cdn/n3/2, where C = 0.4126 and d = 3.5608 ... Series-parallel graphs are well-investigated in the context of the graphs of bounded treewidth. We give a method to represent a series-parallel graph with m edges in 12.5285m - 2] bits. Hence the number of series-parallel graphs with in edges is at most 212.5285m-21 . As far as the authors know, this is the first non-trivial result about the number of series-parallel graphs. The encoding and decoding of the cographs and series-parallel graphs also can be done in linear time. [ABSTRACT FROM AUTHOR]

A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. There are several natural graph classes that have geometric intersection representations. The geometric representations sometimes help to prove tractability/intractability of problems on graph classes. In this paper, we show some results proved by using geometric representations. [ABSTRACT FROM AUTHOR]

We investigate common developments that can fold into several incongruent orthogonal boxes. It was shown that there are infinitely many orthogonal polygons that fold into two incongruent orthogonal boxes in 2008. In 2011, it was shown that there exists an orthogonal polygon that folds into three boxes of size 1 × 1 × 5, 1 × 2 × 3, and 0 × 1 × 11. However it remained open whether there exists an orthogonal polygon that folds into three boxes of positive volume. We give an affirmative answer to this open problem. We show how to construct an infinite number of orthogonal polygons that fold into three incongruent orthogonal boxes. [ABSTRACT FROM AUTHOR]

Abstract: A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a chordal graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward algorithm to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is for each perfect sequence. [ABSTRACT FROM AUTHOR]

Abstract: Ptolemaic graphs are those satisfying the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. It can also be seen as a natural generalization of block graphs (and hence trees). In this paper, we first state a laminar structure of cliques, which leads to its canonical tree representation. This result is a translation of -acyclicity which appears in the context of relational database schemes. The tree representation gives a simple intersection model of ptolemaic graphs, and it is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an efficient algorithm for the Hamiltonian cycle problem. [Copyright &y& Elsevier]

The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes. [ABSTRACT FROM AUTHOR]

Abstract: This paper deals with the graph isomorphism (GI) problem for two graph classes: chordal bipartite graphs and strongly chordal graphs. It is known that GI problem is GI complete even for some special graph classes including regular graphs, bipartite graphs, chordal graphs, comparability graphs, split graphs, and k-trees with unbounded k. On the other hand, the relative complexity of the GI problem for the above classes was unknown. We prove that deciding isomorphism of the classes are GI complete. [Copyright &y& Elsevier]

We introduce a structural parameter of a graph, the longest directed path length (LDPL), and express the boundary of the difficulty of the problems along this parameter. The parallel complexity of the lexicographically first maximal independent set (LFMIS) problem gradually increases as the value of LDPL grows; the LFMIS problem on a graph of LDPL O(log[SUPk] n) can be solved in O(log[SUPk] n) time in parallel; and the problem is Pcomplete on a graph of LDPL Θ(n[SUP∊]). Computing the LDPL itself is in NC[SUP2]. This is important in the sense that a "measure" is valid only if measuring the complexity of a problem is easier than solving it. On the other hand, we also show the limits of the measure. We reduce the LFMIS problem to a kind of the lexicographically first maximal subgraph (LFMS) problems on a graph of LDPL 1. This implies that, even on a graph of LDPL 1, the LFMS problem is P-complete. Finally we discuss the probability that a random graph has LDPL l and show that a random graph of which each edge exists with probability p has LDPL Θ(np) with high probability. This implies the limit of the LDPL on the average case, because the LFMIS problem on a random graph can be efficiently solved in parallel. [ABSTRACT FROM AUTHOR]

We investigate a folding problem that inquires whether a polygon P can be folded, without overlap or gaps, onto a polyhedron Q for given P and Q. An efficient algorithm for this problem when Q is a box was recently developed. We extend this idea to a class of convex polyhedra, which includes the five regular polyhedra, known as Platonic solids. Our algorithms use a common technique, which we call stamping. When we apply this technique, we use two special vertices shared by both P and Q (that is, there exist two vertices of P that are also vertices of Q). All convex polyhedra and their developments have such vertices, except a special class of tetrahedra, the tetramonohedra. We develop two algorithms for the problem as follows. For a given Q, when Q is not a tetramonohedron, we use the first algorithm which solves the folding problem for a certain class of convex polyhedra. On the other hand, if Q is a tetramonohedron, we use the second algorithm to handle this special case. Combining these algorithms, we can conclude that the folding problem can be solved in pseudo-polynomial time when Q is a polyhedron in a certain class of convex polyhedra that includes regular polyhedra. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the way of unfolding a given tetramonohedron, which is a tetrahedron that consists of four congruent triangles. Our aim is finding a way that achieves the minimum cut length to develop it. We first show the rigorous way to unfold any given tetramonohedron with minimum cut length. Next, we focus on a family of tetramonohedra that consist of four congruent isosceles triangles. For this family, we apply our result and investigate their behavior. [ABSTRACT FROM AUTHOR]

Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph ) contains a subgraph isomorphic to the second one (the pattern graph ). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time. In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. [ABSTRACT FROM AUTHOR]

Abstract: There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in time where is the number of creases and is the total crease width. [Copyright &y& Elsevier]

The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible. [ABSTRACT FROM AUTHOR]

The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general. [ABSTRACT FROM AUTHOR]

Suppose there is a collection of n simple polygons in the plane, none of which overlap each other. The polygons are interlocked if no subset can be separated arbitrarily far from the rest. It is natural to ask the characterization of the subsets that makes the set of interlocked polygons free (not interlocked). This abstracts the essence of a kind of sliding block puzzle. We show that any monotone Boolean function ƒ on n variables can be described by m = O(n) interlocked polygons. We also show that the decision problem that asks if given polygons are interlocked is PSPACE-complete. [ABSTRACT FROM AUTHOR]

Abstract: The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. [ABSTRACT FROM AUTHOR]

Abstract: Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly under a certain distribution, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from many other models. Based on such arguments, we show for our random interval graph that its degree distribution follows a power law, and that it has a large average clustering coefficient. [Copyright &y& Elsevier]

Background: In population-based studies, it is generally recognized that single nucleotide polymorphism (SNP) markers are not independent. Rather, they are carried by haplotypes, groups of SNPs that tend to be coinherited. It is thus possible to choose a much smaller number of SNPs to use as indices for identifying haplotypes or haplotype blocks in genetic association studies. We refer to these characteristic SNPs as index SNPs. In order to reduce costs and work, a minimum number of index SNPs that can distinguish all SNP and haplotype patterns should be chosen. Unfortunately, this is an NP-complete problem, requiring brute force algorithms that are not feasible for large data sets. Results: We have developed a double classification tree search algorithm to generate index SNPs that can distinguish all SNP and haplotype patterns. This algorithm runs very rapidly and generates very good, though not necessarily minimum, sets of index SNPs, as is to be expected for such NP-complete problems. Conclusions: A new algorithm for index SNP selection has been developed. A webserver for index SNP selection is available at http://cognia.cu-genome.org/cgi-bin/genome/snpIndex.cgi/ [ABSTRACT FROM AUTHOR]

We are given a set S of points in the Euclidean plane. We assume that S is in general position. A simple polygon P is a surrounding polygon of S if each vertex of P is a point in S and every point in S is either inside P or a vertex of P. In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons. [ABSTRACT FROM AUTHOR]

In the context of computational complexity of puzzles, the sliding block puzzles play an important role. Depending on the rules and set of pieces, the sliding block puzzles can be polynomial-time solvable, NP-complete, or PSPACE-complete. On the other hand, a relatively new notion of jumping block puzzles has been proposed in the puzzle community. This is a counterpart to the token jumping model of the combinatorial reconfiguration problems in the context of block puzzles. We investigate some variants of jumping block puzzles, which are based on actual puzzles, and a natural model from the viewpoint of combinatorial reconfiguration, and determine their computational complexities. More precisely, we investigate two generalizations of two actual puzzles which are called Flip Over puzzles and Flying Block puzzles and one natural model of jumping block puzzles from the viewpoint of combinatorial reconfiguration. We prove that they are PSPACE-complete in general. We also prove the NP-completeness of these puzzles in some restricted cases, and we give polynomial-time algorithms for some restricted cases. [ABSTRACT FROM AUTHOR]

In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only nonisomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also given. The catalogs of graphs in these graph classes are also provided. [ABSTRACT FROM AUTHOR]

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. 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. [ABSTRACT FROM AUTHOR]

The study of reconfiguration problems has grown into a field of its own. The basic idea is to consider the scenario of moving from one given (feasible) solution to another, maintaining feasibility for all intermediate solutions. The solution space is often represented by a "reconfiguration graph", where vertices represent solutions to the problem in hand and an edge between two vertices means that one can be obtained from the other in one step. A typical application background would be for a reorganization or repair work that has to be done without interruption to the service that is provided. [ABSTRACT FROM AUTHOR]

Abstract We investigate folding problems for a class of petal (or star-like) polygons P , which have an n -polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. We give linear time algorithms using constant precision to determine if P can fold to a pyramid with flat base B , and to determine a triangulation of B (crease pattern) that allows folding into a convex (triangulated) polyhedron. By Alexandrov's Theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with running time O (n 456.5) ; ours is the first efficient algorithm for Alexandrov's Theorem for a special class of polyhedra. We also give a polynomial time algorithm that finds the crease pattern to produce the maximum volume triangulated polyhedron. [ABSTRACT FROM AUTHOR]

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 a ≤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. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps 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 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. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded. [ABSTRACT FROM AUTHOR]

When can a plane graph with prescribed edge lengths and prescribed angles (from among{0, 180°; 360°}) be folded flat to lie in an infinitesimally thin line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to 360° and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles and a polynomial-time algorithm for counting the number of distinct folded states. [ABSTRACT FROM AUTHOR]

We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a right-angled polygon (i.e., a polygon made by connecting unit squares along their edges). In the tiling problem, we are given a right-angled polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the # P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. Our results answer two open questions proposed by Moore and Robson (Discrete Comput Geom 26:573-590, 2001) and Pak and Yang (J Comb Theory 120:1804-1816, 2013). [ABSTRACT FROM AUTHOR]

We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that fold into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, and the smallest possible surface area for three different boxes is 46. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge to search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1 × 1 × 7 and 1 × 3 × 3 . Moreover, when we fold along diagonal lines of rectangles of size 1 × 2 , this area 30 may admit to fold into a box of size 5 × 5 × 5 . The results are summarized as follows. There exist 1,080 common developments of two boxes of size 1 × 1 × 7 and 1 × 3 × 3 . Among them, there are nine common developments of three boxes of size 1 × 1 × 7 , 1 × 3 × 3 , and 5 × 5 × 5 . Interestingly, one of nine such polygons folds into three different boxes 1 × 1 × 7 , 1 × 3 × 3 , and 5 × 5 × 5 in four different ways. [ABSTRACT FROM AUTHOR]

We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs. [ABSTRACT FROM AUTHOR]

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. [ABSTRACT FROM AUTHOR]

Suppose that we are given two independent sets I b and I r of a graph such that | I b | = | I r | , and imagine that a token is placed on each vertex in I b . Then, the sliding token problem is to determine whether 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. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I b and I r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. [ABSTRACT FROM AUTHOR]

A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given base-lines (Chun et al., 2012 [4] ). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n × n pixel grid. We then present an O ( n 3 ) -time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. [ABSTRACT FROM AUTHOR]

We introduce a computational origami problem which we call the segment folding problem: given a set of n line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alter the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether n line segments can be folded in n simple folding operations. [ABSTRACT FROM AUTHOR]

We update the record of the simplest possible topologically convex polyhedron that has no edge unfolding, measuring complexity in terms of number of vertices or number of faces. Specifically, we prove that 6 vertices are sufficient, and that 6 faces are sufficient, for ununfoldability. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the popular card game UNO® from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P. [Copyright &y& Elsevier]

Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider two problems of finding an orientation of all edges in G: min-sum orientation is to minimize the sum of the shortest directed distances between all st-pairs; and min-max orientation is to minimize the maximum shortest directed distance among all st-pairs. Note that these shortest directed paths for st-pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomial time, whereas min-max orientation remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st-pairs is a fixed constant. [ABSTRACT FROM AUTHOR]

A planar point set S is an (i, t) set of ghost chimneys if there exist lines H0, H1,...,Ht-1 such that the orthogonal projection of S onto Hj consists of exactly i + j distinct points. We give upper and lower bounds on the maximum value of t in an (i, t) set of ghost chimneys, showing that it is linear in i. [ABSTRACT FROM AUTHOR]

How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length- n uniform string (all mountains or all valleys), and hence of a length- n pleat (alternating mountain/valley), is O(lg n). We also show that a lower bound of the complexity of the problems is Ω(lg n/lg lg n). Next we show that almost all mountain-valley patterns require Ω( n/lg n) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length n in O( n/lg n) folds, meeting the lower bound up to a constant factor. [ABSTRACT FROM AUTHOR]

Abstract: Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. [Copyright &y& Elsevier]

We propose a simple model of random interval graphs generated by immigration- death processes (also known as M/G/∞ queuing processes), where the length of each interval follows a subexponential distribution, and provide a condition under which the stationary degree distribution is also subexponential. Furthermore, we consider the conditional expectation of the cluster coefficient of a vertex given the degree and show that it vanishes in the limit as the degree goes to infinity under the same condition as that for obtaining the tail asymptotics of the stationary degree distribution. [ABSTRACT FROM AUTHOR]

Abstract: A ladder lottery, known as “Amidakuji” in Japan, is a common way to choose a permutation randomly. A ladder lottery corresponding to a given permutation is optimal if has the minimum number of horizontal lines among the ladder lotteries corresponding to . In this paper we show that for any two optimal ladder lotteries and of a permutation, there exists a sequence of local modifications which transforms into . We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting , the algorithm enumerates all arrangements of pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of pseudolines for each . [Copyright &y& Elsevier]

We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant. [ABSTRACT FROM AUTHOR]