Authors:Lila Kari; Steffen Kopecki; Pierre-Étienne Meunier; Matthew J. Patitz; Shinnosuke Seki Pages: 1 - 46 Abstract: We solve an open problem, stated in 2008, about the feasibility of designing efficient algorithmic self-assembling systems which produce 2-dimensional colored patterns. More precisely, we show that the problem of finding the smallest tile assembly system which rectilinearly self-assembles an input pattern with 2 colors (i.e., 2-Pats) is \(\mathbf {NP}\) -hard. Of both theoretical and practical significance, the more general k-Pats problem has been studied in a series of papers which have shown k-Pats to be \(\mathbf {NP}\) -hard for \(k=60\) , \(k=29\) , and then \(k=11\) . In this paper, we prove the fundamental conjecture that 2-Pats is \(\mathbf {NP}\) -hard, concluding this line of study. While most of our proof relies on standard mathematical proof techniques, one crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof for the four color theorem and the recent important advance on the Erdős discrepancy problem using computer programs. In this paper, these techniques will be brought to a new order of magnitude, computational tasks corresponding to one CPU-year. We massively parallelize our program, and provide a full proof of its correctness. Its source code is freely available online. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0154-7 Issue No:Vol. 78, No. 1 (2017)

Authors:Aaron M. Andrews; Haitao Wang Pages: 47 - 85 Abstract: We consider an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in \(O(n^2)\) time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an \(O(n\log n)\) time algorithm. We also show an \(\varOmega (n\log n)\) time lower bound for this problem, which implies the optimality of our algorithm. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0153-8 Issue No:Vol. 78, No. 1 (2017)

Authors:Rudolf Scheifele Pages: 86 - 109 Abstract: We consider the Minimum Elmore Delay Steiner Tree Problem, which is a key problem in VLSI design: We are given a set of pins which have to be connected by a Steiner tree. One of the pins is the source. Challenging timing constraints impose tight bounds on the delay of propagating a signal from the source to the other pins. The commonly used measure is Elmore delay (Elmore in J Appl Phys 19:55–63, 1948). We consider two variants: minimizing the maximum Elmore delay or a weighted sum of Elmore delays. Both variants are strongly NP-hard even for very restricted special cases. Although it is a central problem in VLSI design (Kahng and Robins in On optimal interconnections for VLSI. Kluwer, Boston, 1995; Korte and Vygen in Building bridges—between mathematics and computer science. Springer, Berlin, pp 333–368, 2008), no approximation algorithms were known so far. In this work, we give the first constant-factor approximation algorithm. It works for both variants. The algorithm achieves an approximation ratio of 3.39 in the rectilinear plane and 4.11 in general metric spaces. We can show that our algorithm is best possible in a certain sense. We also demonstrate that our algorithm leads to improvements on real world VLSI instances compared to the currently used standard method of computing short Steiner trees. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0149-4 Issue No:Vol. 78, No. 1 (2017)

Authors:Rajesh Chitnis; László Egri; Dániel Marx Pages: 110 - 146 Abstract: In the deletion version of the list homomorphism problem, we are given graphs G and H, a list \(L(v)\subseteq V(H)\) for each vertex \(v\in V(G)\) , and an integer k. The task is to decide whether there exists a set \(W \subseteq V(G)\) of size at most k such that there is a homomorphism from \(G {\setminus } W\) to H respecting the lists. We show that DL-Hom( \({H}\) ), parameterized by k and H , is fixed-parameter tractable for any \((P_6,C_6)\) -free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom( \({H}\) ) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al. (Combinatorica 19(4):487–505, 1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0139-6 Issue No:Vol. 78, No. 1 (2017)

Authors:Sariel Har-Peled; Subhro Roy Pages: 147 - 165 Abstract: Let \(P\) and \(Q\) be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present a \((1-\varepsilon )\) -approximation algorithm, for finding the translation of \(Q\) , which maximizes its area of overlap with \(P\) . Our algorithm runs in \(O\left( {c n}\right) \) time, where c is a constant that depends only on k and \(\varepsilon \) . This suggests that for polygons that are “close” to being convex, the problem can be solved (approximately), in near linear time. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0152-9 Issue No:Vol. 78, No. 1 (2017)

Authors:K. Subramani; Piotr Wojciechowski Pages: 166 - 208 Abstract: In this paper, we discuss a new combinatorial certifying algorithm for the problem of checking linear feasibility in Unit Two Variable Per Inequality (UTVPI) constraints. A UTVPI constraint has at most two non-zero variables and the coefficients of the non-zero variables belong to the set \(\{+1,\ -1\}\) . These constraints occur in a number of application domains, including but not limited to program verification, abstract interpretation, and operations research. The proposed algorithm runs in \(O(m\cdot n)\) time and \(O(m+n)\) space on a UTVPI system with n variables and m constraints. Observe that these resource bounds match the bounds of the fastest strongly polynomial algorithm for difference constraints. Inasmuch as UTVPI constraints subsume difference constraints, it is clear that the resource requirements of our algorithm are optimal. Additionally, our algorithm is certifying, in that it produces a satisfying assignment when presented with a feasible instance, and a refutation, otherwise. At the heart of our algorithm is a new constraint network representation for UTVPI constraints. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0131-1 Issue No:Vol. 78, No. 1 (2017)

Authors:Sander P. A. Alewijnse; Quirijn W. Bouts; Alex P. ten Brink; Kevin Buchin Pages: 209 - 231 Abstract: The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take \(\varOmega (n^2)\) time, limiting its applicability on large data sets. We propose a novel algorithm design which uses the observation that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly. To find the usually few remaining ‘long’ edges, we use a combination of already determined local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets. We give a geometric property that holds with high probability, which in turn implies that if an edge set on these points has t-paths between pairs of points ‘close’ to each other, then it has t-paths between all pairs of points. This characterization gives an \(O(n \log ^2 n \log ^2 \log n)\) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give an \(O((n + E ) \log ^2 n \log \log n)\) expected time algorithm on uniformly distributed points that determines whether E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0160-9 Issue No:Vol. 78, No. 1 (2017)

Authors:Haitao Wang; Jingru Zhang Pages: 232 - 254 Abstract: Uncertain data has been very common in many applications. In this paper, we consider the one-center problem for uncertain data on tree networks. In this problem, we are given a tree T and n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to find a point \(x^*\) on T such that the maximum (weighted) expected distance from \(x^*\) to all uncertain points is minimized. To the best of our knowledge, this problem has not been studied before. We propose a refined prune-and-search technique that solves the problem in linear time. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0158-3 Issue No:Vol. 78, No. 1 (2017)

Authors:Uriel Feige; Moshe Tennenholtz Pages: 255 - 273 Abstract: Consider the problem of selecting k items that maximize the value of a monotone submodular set function f, where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of \(1 - \frac{1}{e}\) . We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of \(\frac{1}{2}\) , and that an approximation ratio of \(\frac{1 + \epsilon }{2}\) requires a number of queries that is exponential in \(\epsilon k\) . For the interesting special case of coverage functions, we show that an approximation ratio strictly better than \(\frac{1}{2}\) is attainable with polynomially many uniform size queries. The “uniform size” requirement is motivated by situations in which a firm may offer a menu of exactly k items to its clients, where k is a parameter determined by external considerations. Performing a query corresponds to physically changing the identities of the items offered, and the reply to the query is deduced by observing the behavior of clients in response to the change. Queries that involve a number of items that differs from k may not be desirable due to these external considerations. In such situations it is natural to ask whether the same approximation ratios that can be guaranteed by general value queries can also be obtained by uniform size queries. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0162-7 Issue No:Vol. 78, No. 1 (2017)

Authors:Amer E. Mouawad; Naomi Nishimura; Venkatesh Raman; Narges Simjour; Akira Suzuki Pages: 274 - 297 Abstract: We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem \(\mathcal {Q}\) takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to \(\mathcal {Q}\) . For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: k, a bound on the size of solutions, and \(\ell \) , a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set, all parameterized by k. In contrast, we show that reconfiguring Unbounded Hitting Set is W[2]-hard when parameterized by \(k+\ell \) . We also demonstrate the W[1]-hardness of reconfiguration variants of a large class of maximization problems parameterized by \(k+\ell \) , and of their corresponding deletion problems parameterized by \(\ell \) ; in doing so, we show that there exist problems in FPT when parameterized by k, but whose reconfiguration variants are W[1]-hard when parameterized by \(k+\ell \) . PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0159-2 Issue No:Vol. 78, No. 1 (2017)

Authors:Basile Couëtoux; Elie Nakache; Yann Vaxès Pages: 298 - 318 Abstract: In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any \(\epsilon >0\) , we provide a polynomial time approximation algorithm that computes a solution of value at least \(OPT^{1-\epsilon }\) and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX-hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless \(P=NP\) . PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0155-6 Issue No:Vol. 78, No. 1 (2017)

Authors:Meirav Zehavi Pages: 319 - 341 Abstract: In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching (k-IOB) problem, which asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The second problem, k-Tree, asks if a given undirected graph G has a (not necessarily induced) copy of a given tree T. That is, k-Tree asks whether T is a subgraph of G. We present an \(O^*(4^k)\) time randomized algorithm for k-IOB, which improves the \(O^*\) running time of the previous best known algorithm for this problem. Then, for directed graphs whose underlying (simple, undirected) graphs have bounded degree \(\varDelta \) , we modify our algorithm to solve k-IOB in time \(O^*(2^{(2-\frac{\varDelta +1}{\varDelta (\varDelta -1)})k})\) . For k- Tree in graphs of bounded degree 3, we obtain an \(O^*(1.914^k)\) time randomized algorithm. In particular, all of our algorithms use polynomial space. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0166-3 Issue No:Vol. 78, No. 1 (2017)

Authors:Isolde Adler; Mamadou Moustapha Kanté; O-joung Kwon Pages: 342 - 377 Abstract: Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every n-vertex distance-hereditary graph, equivalently a graph of rank-width at most 1, can be computed in time \({\mathcal {O}}(n^2\cdot \log _2 n)\) , and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every n-element matroid of branch-width at most 2 can be computed in time \({\mathcal {O}}(n^2\cdot \log _2 n)\) , provided that the matroid is given by its binary representation. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50–79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of ‘limbs’ of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization. PubDate: 2017-05-01 DOI: 10.1007/s00453-016-0164-5 Issue No:Vol. 78, No. 1 (2017)

Authors:Reut Levi; Ronitt Rubinfeld; Anak Yodpinyanee Pages: 971 - 994 Abstract: In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. Instead, we consider the case where parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n; for constant \(\varepsilon > 0\) , a randomized LCA that provides a \((1-\varepsilon )\) -approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0126-y Issue No:Vol. 77, No. 4 (2017)

Authors:Carlo Comin; Romeo Rizzi Pages: 995 - 1021 Abstract: In this work we offer an \(O( V ^2 E \, W)\) pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor \(\log ( V \, W)\) the best previously known pseudo-polynomial time upper bound due to Brim et al. The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0123-1 Issue No:Vol. 77, No. 4 (2017)

Authors:Piotr Micek; Veit Wiechert Pages: 1060 - 1070 Abstract: The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for \(P_9\) -free bipartite graphs. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0130-2 Issue No:Vol. 77, No. 4 (2017)

Authors:Yusuke Kobayashi; Sho Toyooka Pages: 1128 - 1142 Abstract: A group-labeled graph is a directed graph with each arc labeled by a group element, and the label of a path is defined as the sum of the labels of the traversed arcs. In this paper, we propose a polynomial time randomized algorithm for the problem of finding a shortest s-t path with a non-zero label in a given group-labeled graph (which we call the Shortest Non-Zero Path Problem). This problem generalizes the problem of finding a shortest path with an odd number of edges, which is known to be solvable in polynomial time by using matching algorithms. Our algorithm for the Shortest Non-Zero Path Problem is based on the ideas of Björklund and Husfeldt (Proceedings of the 41st international colloquium on automata, languages and programming, part I. LNCS 8572, pp 211–222, 2014). We reduce the problem to the computation of the permanent of a polynomial matrix modulo two. Furthermore, by devising an algorithm for computing the permanent of a polynomial matrix modulo \(2^r\) for any fixed integer r, we extend our result to the problem of packing internally-disjoint s-t paths. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0142-y Issue No:Vol. 77, No. 4 (2017)

Authors:Gahyun Park Pages: 1159 - 1193 Abstract: This paper investigates a general version of the multiple choice model called the (k, d)-choice process in which n balls are assigned to n bins. In the process, \(k<d\) balls are placed into the k least loaded out of d bins chosen independently and uniformly at random in each of \(\frac{n}{k}\) rounds. The primary goal is to derive tight bounds on the maximum bin load for (k, d)-choice for any \(1 \le k < d \le n\) . Our results enable one to choose suitable parameters k and d for which the (k, d)-choice process achieves the optimal tradeoff between the maximum bin load and message cost: a constant maximum load and O(n) messages. The maximum load for a heavily loaded case where \(m>n\) balls are placed into n bins is also presented for the case \(d \ge 2k\) . Potential applications are discussed such as distributed storage as well as parallel job scheduling in a cluster. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0141-z Issue No:Vol. 77, No. 4 (2017)

Authors:Tomasz Kociumaka; Jakub Radoszewski; Wojciech Rytter Pages: 1194 - 1215 Abstract: We introduce efficient indexes for a problem in non-standard stringology: jumbled pattern matching. An index is a data structure constructed for a text of length n over an alphabet of size \(\sigma \) that can answer queries asking if the text contains a fragment which is jumbled (Abelian) equivalent to a pattern, specified by its so-called Parikh vector. We denote the length of the pattern by m. Moosa and Rahman (J Discrete Algorithms 10:5–9, 2012) gave an index for the case of binary alphabets with \(\mathcal {O}\left( \frac{n^2}{(\log n)^2}\right) \) -time construction in the word-RAM model. Several earlier papers stated as an open problem the existence of an efficient solution for larger alphabets. In this paper we develop an index for any constant-sized alphabet. The construction involves a trade-off parameter, which in particular lets us achieve the following complexities: \(\mathcal {O}(n^{2-\delta })\) space and \(\mathcal {O}(m^{(2\sigma -1)\delta })\) query time for any \(0<\delta <1\) , or \(\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) \) space and polylogarithmic, \(o(\log ^{2\sigma -1} m)\) , query time. The construction time in both cases is subquadratic: \(\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) \) in the word-RAM model (using bit-parallelism). Our construction algorithms are randomized (Las Vegas, running time w.h.p.), which is due to the usage of perfect hashing. On the other hand, all queries are answered deterministically. A preliminary version of this work appeared at ESA 2013 (Kociumaka et al. in Algorithms, ESA 2013. LNCS, vol 8125. Springer, Berlin, pp. 625–636, 2013). Here we improve it in several ways. We achieve \(\mathcal {O}(n^2)\) -time construction of the index with \(\mathcal {O}(n^{2-\delta })\) space and \(\mathcal {O}(m^{(2\sigma -1)\delta })\) query time, which was not present in the preliminary version. We also extend the index so that the position of the leftmost occurrence of the query pattern is provided at no additional cost in the complexity; this required rather nontrivial changes in the construction algorithm. PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0140-0 Issue No:Vol. 77, No. 4 (2017)

Authors:Rajesh Chitnis; Hossein Esfandiari; MohammadTaghi Hajiaghayi; Rohit Khandekar; Guy Kortsarz; Saeed Seddighin Pages: 1216 - 1239 Abstract: Given an edge-weighted directed graph \(G=(V,E)\) on n vertices and a set \(T=\{t_1, t_2, \ldots , t_p\}\) of p terminals, the objective of the Strongly Connected Steiner Subgraph (p-SCSS) problem is to find an edge set \(H\subseteq E\) of minimum weight such that G[H] contains an \(t_{i}\rightarrow t_j\) path for each \(1\le i\ne j\le p\) . The p-SCSS problem is NP-hard, but Feldman and Ruhl [FOCS ’99; SICOMP ’06] gave a novel \(n^{O(p)}\) time algorithm. In this paper, we investigate the computational complexity of a variant of 2-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \(2\) -SCSS- \((k_1, k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) with weight function \(\omega : E\rightarrow {\mathbb {R}}^{\ge 0}\) , two terminal vertices s, t, and integers \(k_1, k_2\) ; the objective is to find a set of \(k_1\) paths \(F_1, F_2, \ldots , F_{k_1}\) from \(s\leadsto t\) and \(k_2\) paths \(B_1, B_2, \ldots , B_{k_2}\) from \(t\leadsto s\) such that \(\sum _{e\in E} \omega (e)\cdot \phi (e)\) is minimized, where \(\phi (e)= \max \Big \{ \{i\in [k_1] : e\in F_i\} \ ,\ \{j\in [k_2] : e\in B_j\} \Big \}\) . For each \(k\ge 1\) , we show the following: The \(2\) -SCSS- \((k,1)\) problem can be solved in time \(n^{O(k)}\) . A matching lower bound for our algorithm: the \(2\) -SCSS- \((k,1)\) problem does not have an \(f(k)\cdot n^{o(k)}\) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails. Our algorithm for ... PubDate: 2017-04-01 DOI: 10.1007/s00453-016-0145-8 Issue No:Vol. 77, No. 4 (2017)