Search

Bloxorz is an online puzzle game where players move a $$1 \times 1 \times 2$$ block by tilting it on a subset of the two dimensional grid, that also features switches that open and close trapdoors. The puzzle is to move the block from its initial position to an upright position on the goal square. We show that the problem of deciding whether a given Bloxorz level is solvable is $$\mathsf{PSPACE}$$-complete and that this remains so even when all trapdoors are initially closed or all trapdoors are initially open. We also answer an open question of Viglietta [6], showing that 2-buttons are sufficient for $$\mathsf{PSPACE}$$-hardness of general puzzle games. We also examine the hardness of some variants of Bloxorz, including variants where the block is a $$1 \times 1 \times 1$$ cube, and variants with single-use tiles.

Background Given a peptide as a string of amino acids, the masses of all its prefixes and suffixes can be found by a trivial linear scan through the amino acid masses. The inverse problem is the ideal de novo peptide sequencing problem: Given all prefix and suffix masses, determine the string of amino acids. In biological reality, the given masses are measured in a lab experiment, and measurements by necessity are noisy. The (real, noisy) de novo peptide sequencing problem therefore has a noisy input: a few of the prefix and suffix masses of the peptide are missing and a few other masses are given in addition. For this setting, we ask for an amino acid string that explains the given masses as accurately as possible. Results Past approaches interpreted accuracy by searching for a string that explains as many masses as possible. We feel, however, that it is not only bad to not explain a mass that appears, but also to explain a mass that does not appear. We propose to minimize the symmetric difference between the set of given masses and the set of masses that the string explains. For this new optimization problem, we propose an efficient algorithm that computes both the best and the k best solutions. Proof-of-concept experiments on measurements of synthesized peptides show that our approach leads to better results compared to finding a string that explains as many given masses as possible. Conclusions We conclude that considering the symmetric difference as optimization goal can improve the identification rates for de novo peptide sequencing. A preliminary version of this work has been presented at WABI 2016., Algorithms for Molecular Biology, 12 (1), ISSN:1748-7188

Additional file 1. Supplementary Figures

International audience; Given a set of paths (called lines) L, a subway network is a graph GL = (V, A) where V contains exactly the vertices and arcs of every line l ∈ L. An st-route is a pair (π, γ) where γ = (l1,. .. , l h) is a line sequence and π is an st-path in GL which is the concatena-tion of subpaths of the lines l1,. .. , l h , in this order. We study three related problems concerning traveling from s to t in GL. We present an efficient (i.e., polynomial-time) algorithm for computing an st-route (π, γ) where |γ| (i.e., the number of line changes plus one) is minimum among all st-routes. We show for the problem of finding an st-route (π, γ) that minimizes the number of different lines in γ, even computing an o(log |V |)-approximation is NP-hard. Finally, given an integer β, we present an algorithm for enumerating all st-paths π for which a route (π, γ) with |γ| ≤ β exists, and show that the running time of this algorithm is polynomial with respect to both input and output size.

Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points’ bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation θ∈[0,2π) , whose value influences the geometric properties and hence the running times of our algorithms.

Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be re- ordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is simple and is based essentially on lexicographic breadth-first search (Lex-BFS), using a divide-and-conquer strategy. When applied to a non- negative symmetric n × n matrix with m nonzero entries and given as a weighted adjacency list, it runs in O(d(n + m)) time, where d is the depth of the recursion tree, which is at most the number of distinct nonzero entries of A.

Given an urban public transportation network and historic delay information, we consider the problem of computing reliable journeys. We propose new algorithms based on our recently presented solution concept (Böhmová et al., ATMOS 2013), and perform an experimental evaluation using real-world delay data from Zürich, Switzerland. We compare these methods to natural approaches as well as to our recently proposed method which can also be used to measure typicality of past observations. Moreover, we demonstrate how this measure relates to the predictive quality of the individual methods. In particular, if the past observations are typical, then the learning- based methods are able to produce solutions that perform well on typical days, even in the presence of large delays., OpenAccess Series in Informatics (OASIcs), 48, ISSN:2190-6807, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015), ISBN:978-3-939897-99-6

International audience; We study the problem of robust routing in urban public transportation networks. In order to propose solutions that are robust for typical delays, we assume that we have past observations of real traffic situations available. In particular, we assume that we have "daily records" containing the observed travel times in the whole network for a few past days. We introduce a new concept to express a solution that is feasible in any record of a given public transportation network. We adapt the method of Buhmann et al. [Buhmann et al., ITCS 2013] for optimization under uncertainty, and develop algorithms that allow its application for finding a robust journey from a given source to a given destination. The performance of the algorithms and the quality of the predicted journey are evaluated in a preliminary experimental study. We furthermore introduce a measure of reliability of a given journey, and develop algorithms for its computation. The robust routing concepts presented in this work are suited specially for public transportation networks of large cities that lack clear hierarchical structure and contain services that run with high frequencies.

In this work we completely characterize how the frequency with which each player participates in the game dynamics affects the possibility of reaching efficient states, i.e., states with an approximation ratio within a constant factor from the price of anarchy, within a polynomially bounded number of best responses. We focus on the well known class of linear congestion games and we show that (i) if each player is allowed to play at least once and at most β times in T best responses, states with approximation ratio O(β) times the price of anarchy are reached after T ⌈loglogn⌉ best responses, and that (ii) such a bound is essentially tight also after exponentially many ones. One important consequence of our result is that the fairness among players is a necessary and sufficient condition for guaranteeing a fast convergence to efficient states. This answers the important question of the maximum order of β needed to fast obtain efficient states, left open by [10,11] and [3], in which fast convergence for constant β and very slow convergence for β = O(n) have been shown, respectively. Finally, we show that the structure of the game implicitly affects its performances. In particular, we prove that in the symmetric setting, in which all players share the same set of strategies, the game always converges to an efficient state after a polynomial number of best responses, regardless of the frequency each player moves with. All the results extend to weighted congestion games.

We study the solution quality for min-cut problems on graphs when restricting the shapes of the allowed cuts. In particular we are interested in min-cut problems with additional size constraints on the parts being cut out from the graph. Such problems include the bisection problem, separator problem, or the sparsest cut problem. We therefore aim at cutting out a given number m of vertices from a graph using as few edges as possible. We consider this problem on solid grid graphs which are finite, connected subgraphs of the infinite two-dimensional grid that do not have holes. Our interest is in the tradeoff between the simplicity of the cut shapes and their solution quality: we study corner cuts in which each cut has at most one right-angled bend. We prove that optimum corner cuts get us arbitrarily close to a cut out part of size m, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the effect of limiting these to corner cuts., Technical Report / ETH Zurich, Department of Computer Science, 731 (b)

Technical Report / ETH Zurich, Department of Computer Science, 607

We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other, i.e. if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counter-clockwise order as they appear on the boundary, and for every two such vertices,it can distinguish whether the angle between them is convex (≤ π) or reflex (> π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound onthe number of vertices is known and show that the robot is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable and deterministic such robots can always position themselves such that they mutually see each other, i.e. such that they form a clique in the visibility graph., Leibniz International Proceedings in Informatics (LIPIcs), 9, ISSN:1868-8969, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), ISBN:978-3-939897-25-5

The graph bisection problem asks to partition the n vertices of a graph into two sets of equal size so that the number of edges across the cut is minimum. We study nite, connected subgraphs of the innite twodimensional grid that do not have holes. Since bisection is an intricate problem, our interest is in the tradeo between runtime and solution quality that we get by limiting ourselves to a special type of cut, namely cuts with at most one bend each (corner cuts). We prove that optimum corner cuts get us arbitrarily close to equal sized parts, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the eect of limiting these to corner cuts., Technical report, 731

Technical report, 730

This book constitutes the refereed conference proceedings of the 9th International Conference on Algorithms and Complexity, CIAC 2015, held in Paris, France, in May 2015. The 30 revised full papers presented were carefully reviewed and selected from 93 submissions and are presented together with 2 invited papers. The papers present original research in the theory and applications of algorithms and computational complexity.

We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair., OpenAccess Series in Informatics (OASIcs), 14, ISSN:2190-6807, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010), ISBN:978-3-939897-20-0

We study the sensor and movement capabilities that simple robots need in order to create a map of an unknown polygon of size n, and to meet. We consider robots that can move from vertex to vertex, can backtrack movements, and see distant vertices in counter-clockwise order but have no means of visibly identifying them. We show that such robots can always solve the weak rendezvous problem and reconstruct the visibility graph, given an upper bound on n. Our results are tight: The strong rendezvous problem, in which robots need to gather at a common location, cannot be solved in general, and without a bound on n, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known., Technical report, 692

We consider a simple agent exploring a polygon by moving from vertex to vertex along the boundary. At every vertex, the agent observes all angles between pairs of edges of the visibility graph, i.e. the angle between all pairs of visible vertices. The goal of the agent is to reconstruct the shape of the polygon, or equivalently its visibility graph. A polynomial time algorithm exists if the agent knows the total number of vertices a priori. We adapt this algorithm to work even if the number of vertices is not known beforehand., Technical report, 700