ALBERT

Description: Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition , asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976 ) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension . The input of this problem consists of a graph G with a partial representation \({{{\mathcal {R}}}}'\) fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation \({{{\mathcal {R}}}}\) of the entire graph G extending \({{{\mathcal {R}}}}'\) . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965 ) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

Description: Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are very useful in network monitoring applications such as detecting distributed denial-of-service attacks. Our results improve the previous best results by Arackaparambil et al. in ICLP 1: 95–106 ( 2009 ). Our technical contribution also includes implementing the celebrated AMS sampling method (by Alon et al. in J Comput Syst Sci 58(1): 137–147 1999 ) in the distributed monitoring model, which could be of independent interest.

Description: In the Boundary Labeling problem, we are given a set of  n points, referred to as sites , inside an axis-parallel rectangle  R , and a set of  n pairwise disjoint rectangular labels that are attached to  R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders , with at most one bend. In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of  R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

Description: In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of a Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the h - handed assembly model ( h -HAM), which generalizes the 2-HAM to allow up to h assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows: We provide a 6-HAM construction for a Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a near perfect way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble a Sierpinski triangle within the 3-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a 2-HAM result that works at scale factor 3 and uses 1216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of a Sierpinski triangle and the Sierpinski carpet.

Description: We consider k -Facility Location games, where n strategic agents report their locations on the real line and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost , which is group strategyproof and achieves a bounded approximation ratio for all k and n , for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost . To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with \(k \ge 3\) facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k . On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser , which applies to instances with k facilities and only \(n = k+1\) agents. For any given concave cost function, Pick the Loser is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost .

Description: We give a deterministic #SAT algorithm for de Morgan formulas of size up to \(n^{2.63}\) , which runs in time \(2^{n-n^{{\varOmega }(1)}}\) . This improves upon the deterministic #SAT algorithm of Chen et al. (Proceedings of the twenty-ninth annual IEEE conference on computational complexity, 2014 ), which has similar running time but works only for formulas of size less than \(n^{2.5}\) . Our new algorithm is based on the shrinkage of de Morgan formulas under random restrictions, shown by Paterson and Zwick (Random Struct Algorithms 4(2):135–150, 1993 ). We prove a concentrated and constructive version of their shrinkage result. Namely, we give a deterministic polynomial-time algorithm that selects variables in a given de Morgan formula so that, with high probability over the random assignments to the chosen variables, the original formula shrinks in size, when simplified using a given deterministic polynomial-time formula-simplification algorithm.

Description: We consider Conditional random fields ( CRFs ) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) \(x_1\ldots x_n\) is the sum of terms over intervals [ i ,  j ] where each term is non-zero only if the substring \(x_i\ldots x_j\) equals a prespecified pattern w . Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively \(O(\textit{nL})\) , \(O(\textit{nL} \ell _{\max })\) and \(O(\textit{nL} \min \{|D|,\log (\ell _{\max }\!+\!1)\})\) where L is the combined length of input patterns, \(\ell _{\max }\) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009 ) whose complexities are respectively \(O(\textit{nL} |D|)\) , \(O\left( n |\varGamma | L^2 \ell _{\max }^2\right) \) and \(O(\textit{nL} |D|)\) , where \(|\varGamma |\) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.

Description: Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.

Description: We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code , (Open) Open Locating-Dominating Set and Metric Dimension ) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting Metric Dimension is W [2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

Description: Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of \(\sum _{i=1}^n \lfloor {n \over i} \rfloor \) is necessary and sufficient. In other words, \(\lg n + \lg \lg n + O(1)\) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \(\lceil \lg n \rceil \) for the label length, if each vertex need not get a unique label. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , n\}\) , we first show that \(\varTheta (\sqrt{n})\) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O (1) time in the standard word RAM model. We also develop a dynamic structure that uses \(O(\sqrt{n} \lg n)\) bits to support equivalence queries and unions in \(O(\lg n/\lg \lg n)\) worst case time or \(O(\alpha (n))\) expected amortized time where \(\alpha (n)\) is the inverse Ackermann function. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , cn\}\) for any constant \(c 〉 1\) , we show that \(\varTheta (\lg n)\) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O (1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.

Description: We perform a thorough study of various characteristics of the asynchronous push–pull protocol for spreading a rumor on Erdős–Rényi random graphs \(G_{n,p}\) , for any \(p〉c\ln (n)/n\) with \(c〉1\) . In particular, we provide a simple strategy for analyzing the asynchronous push–pull protocol on arbitrary graph topologies and apply this strategy to \(G_{n,p}\) . We prove tight bounds of logarithmic order for the total time that is needed until the information has spread to all nodes. Surprisingly, the time required by the asynchronous push–pull protocol is asymptotically almost unaffected by the average degree of the graph. Similarly tight bounds for Erdős–Rényi random graphs have previously only been obtained for the synchronous push protocol, where it has been observed that the total running time increases significantly for sparse random graphs. Finally, we quantify the robustness of the protocol with respect to transmission and node failures. Our analysis suggests that the asynchronous protocols are particularly robust with respect to these failures compared to their synchronous counterparts.

Description: We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty , each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty , the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r .

Description: We define the modular treewidth of a graph as its treewidth after contraction of modules. This parameter properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments can be computed in polynomial time for CNF formulas whose incidence graphs have bounded modular treewidth. Our result generalizes known results for the treewidth of incidence graphs and is incomparable with known results for clique-width (or rank-width) of signed incidence graphs. The contraction of modules is an effective data reduction procedure. Our algorithm is the first one to harness this technique for #SAT. The order of the polynomial bounding the runtime of our algorithm depends on the modular treewidth of the input formula. We show that it is unlikely that this dependency can be avoided by proving that SAT is W[1]-hard when parameterized by the modular incidence treewidth of the given CNF formula.

Description: In a classical online network design problem, traffic requirements are gradually revealed to an algorithm. Each time a new request arrives, the algorithm has to satisfy it by augmenting the network under construction in a proper way (with no possibility of recovery). In this paper we study a natural generalization of online network design problems, where a fraction of the requests (the outliers ) can be disregarded. Now, each time a request arrives, the algorithm first decides whether to satisfy it or not, and only in the first case it acts accordingly. We cast three classical network design problems into this framework: (i) Online Steiner tree with outliers In this case a set of t terminals that belong to an n -node graph is presented, one at a time, to an algorithm. Each time a new terminal arrives, the algorithm can either discard or select it. In the latter case, the algorithm connects it to the Steiner tree under construction (initially consisting of a given root node). At the end of the process, at least k terminals must be selected. (ii) Online TSP with outliers This is the same problem as above, but with the Steiner tree replaced by a TSP tour. (iii) Online facility location with outliers In this case, we are also given a set of facility nodes, each one with an opening cost. Each time a terminal is selected, we have to connect it to some facility (and open that facility, if it is not already open). We focus on the known distribution model, where terminals are independently sampled from a given distribution. For all the above problems, we present bicriteria online algorithms that, for any constant \(\epsilon 〉0\) , select at least \((1-\epsilon )k\) terminals with high probability and pay in expectation \(O(\log ^2n)\) times more than the expected cost of the optimal offline solution (selecting k terminals). These upper bounds are complemented by inapproximability results for the case that one insists on selecting exactly k terminals, and by lower bounds including an \(\varOmega (\log n/\log \log n)\) lower bound for the case that the online algorithm is allowed to select \(\alpha \,k\) terminals only, for a sufficiently large constant \(\alpha \in (0,1)\) .

Description: A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer \(\ell \) , we can test whether D contains \(\ell \) arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP -complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP -complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc - Disjoint Branchings and Non - Disconnecting Out - Branching . In Arc - Disjoint Branchings ( Non - Disconnecting Out - Branching ), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non - Disconnecting Out - Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc - Disjoint Branchings is FPT on strong digraphs. The algorithm for Non - Disconnecting Out - Branching runs in time \(2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}\) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.

Description: We study the stable roommates problem in networks where players are embedded in a social context and may incorporate positive externalities into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We characterize prices of anarchy and stability, which capture the ratio of the total profit in the optimum matching over the total profit of the worst and best stable matching, respectively. When the benefit from a match (which we model by associating a reward with each edge) is the same for both players, we show that externalities can significantly improve the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the bound on the price of stability can be obtained in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different benefits from the match. For this more general case, we show that network externalities (i.e., “caring about your friends”) can make an even larger difference and greatly reduce the price of anarchy. We show a variety of existence results and present upper and lower bounds on the prices of anarchy and stability for various structures of matching benefits. All our results on stable matchings immediately extend to the more general case of fractional stable matchings.

Description: We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise \(\beta \) describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter \(\beta \) . In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in \(\beta \) and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with \(\beta \) . Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in \(\beta \) . Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in \(\beta \) and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

Description: Given a plane graph G (i.e., a planar graph with a fixed planar embedding and outer face) and a biconnected subgraph \(G^{\prime }\) with a fixed planar straight-line convex drawing, we consider the question whether this drawing can be extended to a planar straight-line drawing of G . We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, one can be computed in the same running time.

Description: The rotor–router model , also called the Propp machine , was first considered as a deterministic alternative to the random walk. The edges adjacent to each node  v (or equivalently, the exit ports at  v ) are arranged in a fixed cyclic order, which does not change during the exploration. Each node  v maintains a port pointer   \(\pi _v\) which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the “next exit port”). The rotor–router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph  G with  m edges, the route adopted by an agent controlled by the rotor–router mechanism eventually forms an Euler tour based on arcs obtained via replacing each edge in  G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem . In Yanovski et al. (Algorithmica 37(3):165–186, 2003 ), it was proved that, independently of the initial configuration of the rotor–router mechanism in  G , the agent locks-in in time bounded by  \(2mD\) , where \(D\) is the diameter of  G . In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor–router mechanism. Our analysis is performed in the form of a game between a player \({\mathcal {P}}\) intending to lock-in the agent in an Euler tour as quickly as possible and its adversary \({\mathcal {A}}\) with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values \(\pi _v\) . We show, for example, that if \({\mathcal {A}}\) provides its own port numbering after the initial setup of pointers by \({\mathcal {P}}\) , the worst-case complexity of the lock-in problem is \({\varTheta }(m\cdot \min \{\log m,D\})\) . We also investigate the robustness of the rotor–router graph exploration in presence of faults in the pointers \(\pi _v\) or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a new Eulerian cycle is established within \(\mathcal {O}(km)\) steps.

Description: 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.

Description: 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\) .

Description: 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 \) .

Description: 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 .

Description: Let \(\mathcal {D} = \{\mathsf {T}_1,\mathsf {T}_2, \ldots ,\mathsf {T}_D\}\) be a collection of D string documents of n characters in total, that are drawn from an alphabet set \(\varSigma =[\sigma ]\) . The top-k document retrieval problem is to preprocess \(\mathcal{D}\) into a data structure that, given a query \((P[1\ldots p],k)\) , can return the k documents of \(\mathcal{D}\) most relevant to the pattern P . The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in \(\mathsf {T}_d\) . For example, it can be the term frequency (i.e., the number of occurrences of P in \(\mathsf {T}_d\) ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in \(\mathsf {T}_d\) ), or a pattern-independent importance score of \(\mathsf {T}_d\) such as PageRank. Linear space and optimal query time solutions already exist for the general top- k document retrieval problem. Compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o ( n ) bits on top of any compressed suffix array of \(\mathcal{D}\) and solves queries in \(O((p+k) {{\mathrm{polylog}}}\,\,n)\) time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection.

Description: We study the parameterized complexity of Geometric Graph Isomorphism (Known as the Point Set Congruence problem in computational geometry): given two sets of n points A and B with rational coordinates in k -dimensional euclidean space, with k as the fixed parameter, the problem is to decide if there is a bijection \(\pi :A \rightarrow B\) such that for all \(x,y \in A\) , \(\Vert x-y\Vert = \Vert \pi (x)-\pi (y)\Vert \) , where \(\Vert \cdot \Vert \) is the euclidean norm. Our main result is the following: We give a \(O^*(k^{O(k)})\) time (The \(O^*(\cdot )\) notation here, as usual, suppresses polynomial factors) FPT algorithm for Geometric Isomorphism. This is substantially faster than the previous best time bound of \(O^*(2^{O(k^4)})\) for the problem (Evdokimov and Ponomarenko in Pure Appl Algebra 117–118:253–276, 1997 ). In fact, we show the stronger result that even canonical forms for finite point sets with rational coordinates can also be computed in \(O^*(k^{O(k)})\) time. We also briefly discuss the isomorphism problem for other \(l_p\) metrics. Specifically, we describe a deterministic polynomial-time algorithm for finite point sets in \(\mathbb {Q}^2\) .

Description: We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model (Aiello et al. in SODA, pp 771–780 2003 ). In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an \(O\left( \log ^{O(1)}(n)\right) \) competitive ratio for uni-directional grids (where n denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range \([3 \ldots \log n]\) . Our randomized algorithm achieves an expected competitive ratio of \(O(\log n)\) for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous \(O(\log ^2 n)\) -competitive ratio of Azar and Zachut (ESA, pp 484–495, 2005 ).

Description: In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) and integer \(\ell \) and the question is to decide whether there is a superstring s of length at most \(\ell \) containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time \(2^{\mathcal {O}(k)} {\text {poly}}(n)\) finds a superstring of length at most \(\ell \) containing at least k strings of S . We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.

Description: 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 \(2\) -SCSS- \((k,1)\) relies on a structural result regarding an optimal solution followed by using the idea of a “token game” similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the \(2\) -SCSS- \((k_1, k_2)\) problem if \(\min \{k_1, k_2\}\ge 2\) . Therefore \(2\) -SCSS- \((k,1)\) is the most general problem one can attempt to solve with our techniques. To obtain the lower bound matching the algorithm, we reduce from a special variant of the Grid Tiling problem introduced by Marx [FOCS ’07; ICALP ’12].

Description: Communication in “natural” settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the “prior” from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity.

Description: This paper deals with a matching game in which the nodes of a simple graph are independent agents who try to form pairs. If we let the agents make their decision without any central control then a possible outcome is a Nash equilibrium, that is a situation in which no unmatched player can change his strategy and find a partner. However, there can be a big difference between two possible outcomes of the same instance, in terms of number of matched nodes. A possible solution is to force all the nodes to follow a centrally computed maximum matching but it can be difficult to implement this approach. This article proposes a tradeoff between the total absence and the full presence of a central control. Concretely, we study the optimization problem where the action of a minimum number of agents is centrally fixed and any possible equilibrium of the modified game must be a maximum matching. In algorithmic game theory, this approach is known as the price of optimum of a game. For the price of optimum of the matching game, deciding whether a solution is feasible is not straightforward, but we prove that it can be done in polynomial time. In addition, the problem is shown APX -hard, since its restriction to graphs admitting a perfect matching is equivalent, from the approximability point of view, to vertex cover . Finally we prove that this problem admits a polynomial 6-approximation algorithm in general graphs.

Description: This article is motivated by the following satisfiability question: pick uniformly at random an \(\mathsf {and/or}\) Boolean expression of length n , built on a set of \(k_n\) Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence \((k_n)_{n\ge 1}\) . The fundamental breakthrough of this paper is to generalise the previous results for any (reasonable) sequence of integers \((k_n)_{n\ge 1}\) , which enables us, in particular, to solve the above satisfiability question. We also analyse the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomena at \(k_n = {n}\big /{\ln n}\) .

Description: In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G ( V ,  E ) and a function \(\gamma :V \rightarrow \{1,2,\dots ,k\}\) and asks whether a planar drawing of G exists such that each edge is represented by a curve that is monotone in the y -direction and, for any \(u,v\in V\) with \(\gamma (u)〈\gamma (v)\) , it holds that \(y(u)〈y(v)\) . The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity , upward planarity , and level planarity . Most notably, we provide a polynomial-time reduction from strip planarity testing to clustered planarity. We show that the strip planarity testing problem is polynomial-time solvable if G has a prescribed combinatorial embedding.

Description: In 1967, Moon and Moser proved a tight bound on the critical density of squares in squares: any set of squares with a total area of at most 1/2 can be packed into a unit square, which is tight. The proof requires full knowledge of the set, as the algorithmic solution consists in sorting the objects by decreasing size, and packing them greedily into shelves. Since then, the online version of the problem has remained open; the best upper bound is still 1/2, while the currently best lower bound is 1/3, due to Han et al. (Theory Comput Syst 43(1):38–55, 2008 ). In this paper, we present a new lower bound of 11/32, based on a dynamic shelf allocation scheme, which may be interesting in itself. We also give results for the closely related problem in which the size of the square container is not fixed, but must be dynamically increased in order to accommodate online sequences of objects. For this variant, we establish an upper bound of 3/7 for the critical density, and a lower bound of 1/8. When aiming for accommodating an online sequence of squares, this corresponds to a \(2.82{\ldots }\) -competitive method for minimizing the required container size, and a lower bound of \(1.33{\ldots }\) for the achievable factor.

Description: We show that in the model of zero-error communication complexity, direct sum fails for average communication complexity as well as for external information complexity. Our example also refutes a version of a conjecture by Braverman et al. that in the zero-error case amortized communication complexity equals external information complexity. In our examples the underlying distributions do not have full support. One interpretation of a distribution of non full support is as a promise given to the players (the players have a guarantee on their inputs). This brings up the issue of promise versus non-promise problems in this context.

Description: In an \(\epsilon \) -Nash equilibrium, a player can gain at most \(\epsilon \) by changing his behaviour. Recent work has addressed the question of how best to compute \(\epsilon \) -Nash equilibria, and for what values of \(\epsilon \) a polynomial-time algorithm exists. An \(\epsilon \) - well-supported Nash equilibrium ( \(\epsilon \) -WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most \(\epsilon \) less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

Description: We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small world phenomenon holds for them. In the special case when the generated graph is a tree, we provide close lower and upper bounds for the diameters of both models.

Description: Given two point sets S and T , in a many-to-many matching between S and T each point in S is assigned to one or more points in T and vice versa. A generalization of the many-to-many matching problem is the limited capacity many-to-many matching problem , where the number of points that can be matched to each point (the capacity of each point) is limited. In this paper, we provide an \(O\left( n^2\right) \) time algorithm for the one dimensional minimum-cost limited capacity many-to-many matching problem, where \(\left| S\right| +\left| T\right| =n\) . Our algorithm improves the best previous time complexity of \(O(kn^2)\) , that in which k is the largest capacity of the points in \(S \cup T\) . In this problem, both S and T lie on the real line and the cost of matching \(s \in S\) to \(t \in T\) is equal to the distance between s and t .

Description: In the Directed Feedback Arc (Vertex) Set problem, we are given a digraph D with vertex set V ( D ) and arcs set A ( D ) and a positive integer k , and the question is whether there is a subset X of arcs (vertices) of size at most k such that the digraph obtained after deleting X from D is an acyclic digraph. In this paper we study these two problems in the realm of parametrized and kernelization complexity. More precisely, for these problems we give polynomial time algorithms, known as kernelization algorithms, on several digraph classes that given an instance ( D ,  k ) of the problem returns an equivalent instance \((D',k')\) such that the size of \(D'\) and \(k'\) is at most \(k^{O(1)}\) . We extend previous results for Directed Feedback Arc (Vertex) Set on tournaments to much larger and well studied classes of digraphs. Specifically we obtain polynomial kernels for k -FVS on digraphs with bounded independence number, locally semicomplete digraphs and some totally \(\Phi \) -decomposable digraphs, including quasi-transitive digraphs. We also obtain polynomial kernels for k -FAS on some totally \(\Phi \) -decomposable digraphs, including quasi-transitive digraphs. Finally, we design a subexponential algorithm for k -FAS running in time \(2^{O(\sqrt{k} (\log k)^c)}n^d\) for constants c ,  d . on locally semicomplete digraphs.

Description: Braess’s paradox states that removing a part of a network may improve the players’ latency at equilibrium. In this work, we study the approximability of the best subnetwork problem for the class of random \({\mathcal {G}}_{n,p}\) instances proven prone to Braess’s paradox by Valiant and Roughgarden RSA ’10 (Random Struct Algorithms 37(4):495–515, 2010 ), Chung and Young WINE ’10 (LNCS 6484:194–208, 2010 ) and Chung et al. RSA ’12 (Random Struct Algorithms 41(4):451–468, 2012 ). Our main contribution is a polynomial-time approximation-preserving reduction of the best subnetwork problem for such instances to the corresponding problem in a simplified network where all neighbors of source s and destination t are directly connected by 0 latency edges. Building on this, we consider two cases, either when the total rate r is sufficiently low , or, when r is sufficiently high . In the first case of low \(r= O(n_{+})\) , here \(n_{+}\) is the maximum degree of \(\{s, t\}\) , we obtain an approximation scheme that for any constant \(\varepsilon 〉 0\) and with high probability, computes a subnetwork and an \(\varepsilon \) -Nash flow with maximum latency at most \((1+\varepsilon )L^*+ \varepsilon \) , where \(L^*\) is the equilibrium latency of the best subnetwork. Our approximation scheme runs in polynomial time if the random network has average degree \(O(\mathrm {poly}(\ln n))\) and the traffic rate is \(O(\mathrm {poly}(\ln \ln n))\) , and in quasipolynomial time for average degrees up to o ( n ) and traffic rates of \(O(\mathrm {poly}(\ln n))\) . Finally, in the second case of high \(r= {\varOmega }(n_{+})\) , we compute in strongly polynomial time a subnetwork and an \(\varepsilon \) -Nash flow with maximum latency at most \((1+2\varepsilon + o(1))L^*\) .

Description: A semi-matching in a bipartite graph \(G = (U, V, E)\) is a set of edges \(M \subseteq E\) such that each vertex in U is incident to exactly one edge in M , i.e., \(deg_M(u)=1\) for each \(u \in U\) . An optimal semi-matching is a semi-matching with the minimal value of the cost function \(\sum _{v \in V} \frac{deg_M(v) \cdot (deg_M(v)+1)}{2}\) . Exploiting the divide-and-conquer nature of the semi-matching problem, we reduce the problem to a simpler problem whose objective is to compute a maximum weak bounded-degree semi-matching. Using the reduction we derive three algorithms for the optimal semi-matching problem. The first one runs in time \(O(\sqrt{n} \cdot m \cdot \log {n})\) on a graph with n vertices and m edges. The second one is randomized and computes an optimal semi-matching with high probability in time \(O(n^{\omega } \cdot \log ^{1+o(1)} n)\) , where \(\omega \) is the exponent of the best known matrix multiplication algorithm. Since \(\omega 〈 2.38\) , this algorithm breaks through \(O(n^{2.5})\) barrier for dense graphs. In the case of planar graphs, the third one computes an optimal semi-matching in deterministic time \(O(n\cdot \log ^4{n})\) .

Description: Online makespan minimization is a classical problem in which a sequence of jobs \(\sigma = J_1, \ldots , J_n\) has to be scheduled on m identical parallel machines so as to minimize the maximum completion time of any job. In this paper we investigate the problem with an essentially new model of resource augmentation. More specifically, an online algorithm is allowed to build several schedules in parallel while processing \(\sigma \) . At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. As a main result we develop a \((4/3+\varepsilon )\) -competitive algorithm, for any \(0〈\varepsilon \le 1\) , that uses a constant number of schedules. The constant is equal to \(1/\varepsilon ^{O(\log (1/\varepsilon ))}\) . We also give a \((1+\varepsilon )\) -competitive algorithm, for any \(0〈\varepsilon \le 1\) , that builds a polynomial number of \((m/\varepsilon )^{O(\log (1/\varepsilon ) / \varepsilon )}\) schedules. This value depends on m but is independent of the input \(\sigma \) . The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4 / 3 must construct \(\Omega (m)\) schedules. Our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of a job sequence \(\sigma \) to within a factor of \(1+\varepsilon \) and (2) guess the job processing times and their frequencies in \(\sigma \) . In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant. We remark that the competitive ratios achieved using parallel schedules are considerably smaller than those in the standard problem without resource augmentation. Furthermore they are at least as good and in most cases better than the ratios obtained with other means of resource augmentation for makespan minimization.

Description: In the path minimum problem, we preprocess a tree on n weighted nodes, such that given an arbitrary path, the node with the smallest weight along this path can be located. We design novel succinct indices for this problem under the indexing model , for which weights of nodes are read-only and can be accessed with ranks of nodes in the preorder traversal sequence of the input tree. We present an index within O ( m ) bits of additional space that supports queries in \(O(\varvec{\alpha }(m, n))\) time and \(O(\varvec{\alpha }(m, n))\) accesses to the weights of nodes, for any integer \(m \ge n\) ; and an index within \(2n + o(n)\) bits of additional space that supports queries in \(O(\varvec{\alpha }(n))\) time and \(O(\varvec{\alpha }(n))\) accesses to the weights of nodes. Here \(\varvec{\alpha }(m, n)\) is the inverse-Ackermann function, and \(\varvec{\alpha }(n) = \varvec{\alpha }(n, n)\) . These indices give us the first succinct data structures for the path minimum problem. Following the same approach, we also develop succinct data structures for semigroup path sum queries, for which a query asks for the sum of weights along a given query path. One of our data structures requires \(n\lg \sigma + 2n + o(n\lg \sigma )\) bits of space and \(O(\varvec{\alpha }(n))\) query time, where \(\sigma \) is the size of the semigroup. In the path reporting problem, queries ask for the nodes along a query path whose weights are within a two-sided query range. Using the succinct indices for path minimum queries, we achieve three different time/space tradeoffs for path reporting by designing an O ( n )-word data structure with \(O(\lg ^\epsilon n + occ \cdot \lg ^\epsilon n)\) query time; an \(O(n\lg \lg n)\) -word data structure with \(O(\lg \lg n + occ \cdot \lg \lg n)\) query time; and an \(O(n \lg ^\epsilon n)\) -word data structure with \(O(\lg \lg n + occ)\) query time. Here occ is the number of nodes reported and \(\epsilon \) is an arbitrary constant between 0 and 1. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries (Chan et al. 2011 ), which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than n , we further improve both the query time and the space cost of these three results.

Description: In this paper we provide a systematic treatment of several shape parameters of (random) k -trees. Our research is motivated by many important algorithmic applications of k -trees in the context of tree-decomposition of a graph and graphs of bounded tree-width. On the other hand, k -trees are also a very interesting object from the combinatorial point of view. For both labeled and unlabeled k -trees, we prove that the number of leaves and more generally the number of nodes of given degree satisfy a central limit theorem with mean value and variance that are asymptotically linear in the size of the k -tree. In particular we solve the asymptotic counting problem for unlabeled k -trees. By applying a proper singularity analysis of generating functions we show that the numbers \(U_k(n)\) of unlabeled k -trees of size n are asymptotically given by \(U_k(n) \sim c_k n^{-5/2}\rho _{k}^{-n}\) , where \(c_k〉 0\) and \(\rho _{k}〉0\) denotes the radius of convergence of the generating function \(U(z)=\sum _{n\ge 0} U_k(n) z^n\) .

Description: This paper considers max-min fair rate allocation and routing in energy harvesting networks where fairness is required among both the nodes and the time slots . Unlike most previous work on fairness, we focus on multihop topologies and consider different routing methods . We assume a predictable energy profile and focus on the design of efficient and optimal algorithms that can serve as benchmarks for distributed and approximate algorithms. We first develop an algorithm that obtains a max-min fair rate assignment for any routing that is specified at the input. We then turn to the problem of determining a “good” routing. For time-invariable unsplittable routing , we develop an algorithm that finds routes that maximize the minimum rate assigned to any node in any slot. For fractional routing , we derive a combinatorial algorithm for the time-invariable case with constant rates. We show that the time-variable case is at least as hard as the 2-commodity feasible flow problem and design an FPTAS to combat the high running time. Finally, we show that finding an unsplittable routing or a routing tree that provides lexicographically maximum rate assignment (i.e., the best in the max-min fairness terms) is NP-hard, even for a time horizon of a single slot. Our analysis provides insights into the problem structure and can be applied to other related fairness problems.

Description: In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover’s distance between two sets of weighted points A and B in \({\mathbb {R}}^{d}\) under rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. Previous research on this problem has resulted in only constant factor approximations and it has been an open problem for a long time to achieve PTAS solution. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly in \(O((nm)^{d+2}(\log nm)^{2d})\) time (which is close to a lower bound on any PTAS for this problem), where n and m are the sizes of A and B , respectively. Our result is based on several new techniques, such as the Sequential Orthogonal Decomposition and Optimum Guided Base , and can be extended to several related problems, such as the problem of earth mover’s distance under similarity transformation and the alignment problem, to achieve FPTAS for each of them.

Description: We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling–Mandelbrot distribution, studied by Darling (Trans Am Math Soc 73:95–107, 1952 ) and Lew (Constr Approx 10(1):15–30, 1994 ). We also give an explicit form to the density of the Darling–Mandelbrot distribution and derive some of its analytic properties.

Description: A covering problem is an integer linear program of type \(\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \in \mathbb {Z}\}\) where \(A\in \mathbb {Z}^{m\times n}_+\) , \(D\in \mathbb {Z}_+^m\) , and \(c,d\in \mathbb {Z}_+^n\) . In this paper, we study covering problems with additional precedence constraints \(\{x_i\le x_j \ \forall j\preceq i \in \mathcal {P}\}\) , where \(\mathcal {P}=([n], \preceq )\) is some arbitrary, but fixed partial order on the items represented by the column-indices of A . Such precedence constrained covering problems ( PCCPs ) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem , that is, where \(m=1\) and \(d\equiv 1\) . Our main result is a strongly-polynomial primal–dual approximation algorithm for PCCP with \(d\equiv 1\) . Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of \(\mathcal {P}\) , that is, by the size of a maximum antichain in \(\mathcal {P}\) . Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets \(\mathcal {P}\) . For the general case with \(d\not \equiv 1\) , we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions.

Description: Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported budgets of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should be incentivized to truthfully report their advertising budget. For a general class of influence spread models, we show that when there are two players, the social welfare can be \(\frac{e}{e-1}\) -approximated by a polynomial-time strategyproof mechanism. Our mechanism uses a dynamic programming procedure to randomize the order in which advertisers are allocated seeds according to a greedy method. For three or more players, we demonstrate that under an additional assumption (satisfied by many existing models of influence spread) there exists a simpler strategyproof \(\frac{e}{e-1}\) -approximation mechanism; notably, this natural greedy mechanism is not necessarily strategyproof when there are only two players.

Description: Analyzing the runtime of a Randomized Search Heuristic (RSH) by theoretical means often turns out to be rather tricky even for simple optimization problems. The main reason lies in the randomized nature of these algorithms. Both the optimization routines and the initialization of RSHs are typically based on random samples. It has often been observed, though, that the expected runtime of RSHs does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori could greatly simplify runtime analyses, as it reduces the necessity of analyzing the influence of the random initialization. Most runtime bounds in the literature, however, do not profit from this observation and are either too pessimistic or require a rather complex proof. In this work we show for the two search heuristics Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm on the two well-studied problems OneMax and LeadingOnes that their expected runtimes indeed deviate by at most a small additive constant from the expected runtime when started in a solution of average fitness. For RLS on OneMax , this additive discrepancy is \(-1/2 \pm o(1)\) , leading to the first runtime statement for this problem that is precise apart from additive o (1) terms: The expected number of iterations until an optimal search point is found, is \(n H_{n/2} - 1/2 \pm o(1)\) , where \(H_{n/2}\) denotes the ( n  / 2)th harmonic number when n is even, and \(H_{n/2}:= (H_{\lfloor n/2 \rfloor } + H_{\lceil n/2 \rceil })/2\) when n is odd. For this analysis and the one of the (1+1) EA optimizing OneMax we use a coupling technique, which we believe to be interesting also for the study of more complex optimization problems. For the analyses of the LeadingOnes test function, we show that one can express the discrepancy solely via the waiting times for leaving fitness level 0 and 1, which then easily yields the discrepancy, and in particular, without having to deal with so-called free-riders.

Description: The ( \(1+1\) ) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on three easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, solving a class of satisfiable 2-CNF formulas, and solving a class of satisfiable propositional Horn formulas. We prove that it is inefficient on all three problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to so-called metastable states at which, with probability \(1 - o(1)\) , the ( \(1+1\) ) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the ( \(1+1\) ) EA slightly in order to obtain a polynomial-time performance guarantee on all three problems.

Description: Some recent results (Bauer et al. in Algorithms in bioinformatics, Springer, Berlin, pp 326–337, 2012 ; Cox et al. in Algorithms in bioinformatics, Springer, Berlin, pp. 214–224, 2012 ; Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353–364, 2013 ) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows–Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367–i373, 2010 ): to design an external-memory algorithm to compute the string graph.

Description: We characterize the best possible trade-off achievable when optimizing the construction of a decision tree with respect to both the worst and the expected cost. It is known that a decision tree achieving the minimum possible worst case cost can behave very poorly in expectation (even exponentially worse than the optimal), and the vice versa is also true. Led by applications where deciding which optimization criterion might not be easy, several authors recently have focussed on the bicriteria optimization of decision trees. Here we sharply define the limits of the best possible trade-offs between expected and worst case cost. More precisely, we show that for every \(\rho 〉0\) there is a decision tree D with worst testing cost at most \((1 + \rho )\textit{OPT}_W\) and expected testing cost at most \(\frac{1}{1 - e^{-\rho }} \textit{OPT}_E,\) where \(\textit{OPT}_W\) and \(\textit{OPT}_E\) denote the minimum worst testing cost and the minimum expected testing cost of a decision tree for the given instance. We also show that this is the best possible trade-off in the sense that there are infinitely many instances for which we cannot obtain a decision tree with both worst testing cost smaller than \((1 + \rho )\textit{OPT}_W\) and expected testing cost smaller than \(\frac{1}{1 - e^{-\rho }} \textit{OPT}_E\) .

Description: A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, \(\beta \) -decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by \(\beta 〉0\) ) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n -vertex graphs admit an \(O(\ln n)\) -padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996 ), and that excluded-minor graphs admit O (1)-padded decomposition (Klein et al., 25th annual ACM symposium on theory of computing, pp 682–690, 1993 ; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004 ; Abraham et al., Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014 ). We design decompositions to the family of p -path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006 ) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p -path-separable n -vertex graph admits an \(O(\ln (p \ln n))\) -decomposition, which refines the \(O(\ln n)\) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs.

Description: Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.

Description: The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. ( 2014 ) presented a randomized algorithm for the OCFL and proved that it is \(\mathrm {O}(\log ^2 n)\) -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is \(\mathrm {O}(\log n)\) -competitive. Since there is a lower bound of \(\mathrm {\Omega }(\log n)\) for this problem, our result achieves the best possible competitive ratio, asymptotically.

Description: Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi: 10.1109/FOCS.2012.71 ,  2012 ) proved the following result: Unless the unlikely complexity-theoretic collapse \(\mathsf {coNP}\subseteq \mathsf {NP/poly}\) occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker’s theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances \(x_1,\ldots ,x_t\) to a single SAT-instance y of size \({\text {poly}}(\max _i|x_i|)\) such that y is satisfiable if and only if all \(x_i\) are satisfiable. The “AND” in the name stems from the fact that the predicate “ y is satisfiable” can be written as the AND of all predicates “ \(x_i\) is satisfiable”. Drucker’s theorem complements the result by Bodlaender et al. (J Comput Syst Sci 75:423–434,  2009 ) and Fortnow and Santhanam (J Comput Syst Sci 77:91–106,  2011 ), who proved the analogous statement for OR-compressions, and Drucker’s proof not only subsumes their result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi: 10.1109/FOCS.2012.71 ,  2012 ) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (J Comput Syst Sci 26:209–211,  1983 ) for \(\mathsf {P}\) -selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker’s theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker.

Description: The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in \(O(n^{2} \sqrt{\log n})\) time when \(k = 2\) (Jansson and Sung in Algorithmica 66(2):329–345, 2013 ) and \(O(k n^{3})\) time when \(k \ge 3\) (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003 ). This paper shows how to compute it in \(O(n^{2})\) time for \(k = 2, O(n^{2} \log ^{4/3} n)\) time for \(k = 3\) , and \(O(n^{2} \log ^{k+2} n)\) time for unbounded k .

Description: 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 .

Description: 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.

Description: Consider any Boolean function \(F(X_1,\ldots ,X_N)\) that has more than \(2^{-N^{\delta }}\cdot 2^N\) satisfying assignments for some \(\delta \) , \(0〈\delta 〈1\) , and that can be expressed by a CNF formula with at most \(N^d\) clauses for some \(d〉0\) . Then how many variables do we need to fix in order to satisfy F ? We show that one can always find some “short” partial assignment on which F evaluates to 1 by fixing at most \(\alpha N\) variables for some constant \(\alpha 〈1\) ; that is, F has an implicant of size \(\le \alpha N\) . A lower bound for such \(\alpha \) is also shown in terms of \(\delta \) and d . We also discuss an algorithm for obtaining a short partial assignment. For any \(\delta \) and \(\varepsilon \) such that \(0〈\delta +\varepsilon 〈1\) , we show a deterministic algorithm that finds a short partial assignment in \({\widetilde{O}}(2^{N^{\beta }})\) -time (By \({\widetilde{O}}(2^{N^{\beta }})\) we mean \(O\bigl (2^{N^{\beta }}\cdot N^{O(1)}\bigr )\) .) for some \(\beta 〈1\) and for any CNF formula with at most \(N^{1+\varepsilon }\) clauses having more than \(2^{-N^{\delta }}\cdot 2^N\) satisfying assignments.

Description: This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical searchers, or may require each individual node to provide additional resources, e.g., in the case of searchers modeling software agents. We thus introduce and investigate exclusive graph searching, in which no two or more searchers can occupy the same node at the same time. As for the classical variants of graph searching, we study the minimum number of searchers required to capture the intruder. This number is called the exclusive search number of the considered graph. Exclusive graph searching appears to be considerably more complex than classical graph searching, for at least two reasons: (1) it does not satisfy the monotonicity property , and (2) it is not closed under minor . Moreover, we observe that the exclusive search number of a tree may differ exponentially from the values of classical search numbers (e.g., pathwidth). Nevertheless, we design a polynomial-time algorithm which, given any n -node tree  T , computes the exclusive search number of T in time \(O(n^3)\) . Moreover, for any integer k , we provide a characterization of the trees  T with exclusive search number at most k . Finally, we prove that the ratio between the exclusive search number and the pathwidth of a graph is bounded by its maximum degree.

Description: We study the bilateral version of the adversary network formation game introduced by the author in 2010. In bilateral network formation, a link is formed only if both endpoints agree on it and then both have to pay the link cost \(\alpha 〉0\) for it. In the adversary model, the cost of each player comprises this building cost plus the expected number of other players to which she will lose connection if one link is destroyed randomly according to a known probability distribution. Two adversaries are considered: one chooses the link to destroy uniformly at random from the set of all built links, the other instead concentrates the probability measure on the built links which cause a maximum number of player pairs to be separated when destroyed. Pairwise stability (PS) and pairwise Nash equilibrium (PNE) are used as equilibrium concepts. For the first adversary, we prove convexity of cost, hence PS and PNE coincide. The main result is an upper bound of 10 on the price of anarchy for this adversary, for link cost \(\alpha 〉 \frac{1}{2}\) . New proof techniques are required to obtain this bound, compared to the version with unilateral link formation. For the second adversary, we also prove a bound tight up to constants, namely \(\varTheta (1+\frac{n}{\alpha })\) , where n is the number of players.

Description: We provide an information-theoretic framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975 ). The framework is a generalization of the one in Braverman and Moitra (Proceedings of the forty-fifth annual ACM symposium on theory of computing, pp 161–170, 2013 ) for the shifted uniqe disjointness (UDISJ) matrix to arbitrary nonnegative matrices. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we compute the (almost) exact common information of UDISJ partial matrix. The bounds are obtained very naturally. We also establish robustness of this estimation under random or adversarial removal of rows and columns of the UDISJ partial matrix. This robustness translates, via a variant of Yannakakis’s factorization theorem, to lower bounds on the average case and adversarial approximate extension complexity of removals. We present the first family of polytopes, the hard pair introduced in Braun et al. (Math Oper Res 40(3):756–772, 2015 ) related to the CLIQUE problem, with high average case and adversarial approximate extension complexity of removals. The framework relies on a strengthened version of the link between information theory and Hellinger distance from Bar-Yossef (J Comput Syst Sci 68(4):702–732, 2004 ). We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.

Description: The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP -complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013 ). So unless \({\textsf {P}} = {\textsf {NP}}\) , proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

Description: In the Hausdorff Voronoi diagram of a family of clusters of points in the plane, the distance between a point t and a cluster P is measured as the maximum distance between t and any point in P , and the diagram is defined in a nearest-neighbor sense for the input clusters. In this paper we consider non-crossing clusters in the plane, for which the combinatorial complexity of the Hausdorff Voronoi diagram is linear in the total number of points, n , on the convex hulls of all clusters. We present a randomized incremental construction, based on point location, that computes this diagram in expected \(O(n\log ^2{n})\) time and expected O ( n ) space. Our techniques efficiently handle non-standard characteristics of generalized Voronoi diagrams, such as sites of non-constant complexity, sites that are not enclosed in their Voronoi regions, and empty Voronoi regions. The diagram finds direct applications in VLSI computer-aided design.

Description: We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on q -calculus) to directly derive the generating functions to analyze.

Description: We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks ( Crown ) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max - Crown , in which realizing each desired adjacency yields a certain profit. We present the first O (1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.

Description: The Weighted Vertex Integrity (wVI) problem takes as input an n -vertex graph G , a weight function \(w:V(G)\rightarrow {\mathbb {N}}\) , and an integer p . The task is to decide if there exists a set \(X\subseteq V(G)\) such that the weight of X plus the weight of a heaviest component of \(G-X\) is at most  p . Among other results, we prove that: wVI is NP -complete on co-bipartite graphs, even if each vertex has weight 1; wVI can be solved in \(O(p^{p+1}n)\) time; wVI admits a kernel with at most \(p^3\) vertices. Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16:65–73, 1994 ) and answers an open question by Ray et al. (Ars Comb 79:77–95, 2006 ). It also complements a result by Kratsch et al. (Discret Appl Math 77(3):259–270, 1997 ), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an n -vertex graph G , a weight function \(w:V(G)\rightarrow {\mathbb {N}}\) , and two integers k and \(\ell \) , and the task is to decide if there exists a set \(X\subseteq V(G)\) such that the weight of X is at most  k and the weight of a heaviest component of \(G-X\) is at most  \(\ell \) . In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on the wCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that: wCOC can be solved in \(O(\min \{k,\ell \}\cdot n^3)\) time on interval graphs, while the unweighted version can be solved in \(O(n^2)\) time on this graph class; wCOC is W [1]-hard on split graphs when parameterized by k or by \(\ell \) ; wCOC can be solved in \(2^{O(k\log \ell )} n\) time; wCOC admits a kernel with at most \(k\ell (k+\ell )+k\) vertices. We also show that result (6) is essentially tight by proving that wCOC cannot be solved in \(2^{o(k \log \ell )}n^{O(1)}\) time, even when restricted to split graphs, unless the Exponential Time Hypothesis fails.

Description: 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.

Description: 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.

Description: 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.

Description: The equality problem is usually one’s first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on three subtle aspects. The first is to consider the expected communication cost (at a worst-case input) for a protocol that uses limited interaction—i.e., a bounded number of rounds of communication—and whose error probability is zero or close to it. The second is to treat the false negative error rate separately from the false positive error rate. The third is to consider the information cost of such protocols. We obtain asymptotically optimal rounds-versus-cost tradeoffs for equality : both expected communication complexity and information complexity scale as \(\Theta ({{\mathrm{ilog}}}^{r-1} n)\) , where r is the number of rounds and \({{\mathrm{ilog}}}^k n = \log \log \cdots \log n\) , with k logs. These bounds hold even when the false negative rate approaches 1. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. We also provide some applications. As an application of our information cost bounds, we obtain new bounded-round randomized lower bounds for the Intersection problem, in which there are two players who hold subsets \(S,T \subseteq [n]\) . In many realistic scenarios, the sizes of S and T are significantly smaller than n , so we impose the constraint that \(|S|, |T| \le k\) . We study the minimum number of bits the parties need to communicate in order to compute the entire intersection set \(S \cap T\) , using r rounds. We show that any r -round protocol has information cost (and thus communication cost) \(\Omega (k {{\mathrm{ilog}}}^r k)\) bits. We also give an O ( r )-round protocol achieving \(O(k{{\mathrm{ilog}}}^r k)\) bits, which for \(r = \log ^* k\) gives a protocol with O ( k ) bits of communication. This is in contrast to other basic problems such as computing the union or symmetric difference, for which \(\Omega (k\log (n/k))\) bits of communication is required for any number of rounds.

Description: Black-box complexity studies lower bounds for the efficiency of general-purpose black-box optimization algorithms such as evolutionary algorithms and other search heuristics. Different models exist, each one being designed to analyze a different aspect of typical heuristics such as the memory size or the variation operators in use. While most of the previous works focus on one particular such aspect, we consider in this work how the combination of several algorithmic restrictions influence the black-box complexity of a problem. Our testbed are so-called OneMax functions which require to minimize the Hamming distance to an unknown target string \(z \in \{0,1\}^n\) . We analyze in particular the combined memory-restricted ranking-based black-box complexity of OneMax for different memory sizes. While its isolated (1+1) memory-restricted as well as its ranking-based black-box complexity for bit strings of length n is only of order \(n/\log n\) , the combined model does not allow for algorithms being faster than linear in n , as can easily be seen by standard information-theoretic considerations. Our main result is a matching upper bound. That is, we show that the (1+1) memory-restricted ranking-based black-box complexity of OneMax is linear. We also analyze its black-box complexity for memory sizes other than (1+1). Moreover, we show that these results apply to the (Monte Carlo) complexity of OneMax in the recently introduced elitist model [Doerr/Lengler GECCO 2015] that combines the above-mentioned memory-restrictions and ranking-based decisions with an enforced usage of truncation selection. Finally, we also provide improved lower bounds for the complexity of OneMax in the regarded models.

Description: 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.

Description: Graph modification problems typically ask for a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem that allows all three types of operations: given a graph and integers , and , the chordal editing problem asks whether can be transformed into a chordal graph by at most vertex deletions, edge deletions, and edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill - in ). Our main result is an algorithm for chordal editing in time , where and is the number of vertices of . Therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion .

Description: Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut , Graph Coloring , Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al. (Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 493–502, 2010a ; SIAM J Comput 39(5):1941–1956, 2010b ). We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle (New width parameters of graphs. The University of Bergen, 2012 ) on maximum matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut , Graph Coloring , Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.

Description: We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al. (EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property which, to the best of our knowledge, was not known before. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler.

Description: 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.

Description: We prove \(n^{1+\varOmega (1/p)}/p^{O(1)}\) lower bounds for the space complexity of p -pass streaming algorithms solving the following problems on n -vertex graphs: (1) testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size), (2) testing if two specific vertices are at distance at most \(2(p+1)\) in an undirected graph, (3) testing if there is a directed path from s to t for two specific vertices s and t in a directed graph. The lower bounds hold for \(p = O(\log n / \log \log n)\) . Prior to our result, it was known that these problems require \(\varOmega (n^2)\) space in one pass, but no \(n^{1+\varOmega (1)}\) lower bound was known for any \(p\ge 2\) . These streaming results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices at distance exactly \(p+1\) from a specific vertex intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem.

Description: The signature of a permutation \(\sigma \) is a word \(\mathtt {sg}(\sigma )\subseteq \{\mathfrak {a},\mathfrak {d}\}^*\) with i th letter \(\mathfrak {d}\) when \(\sigma \) has a descent [i.e.  \(\sigma (i)〉\sigma (i+1)\) ] and \(\mathfrak {a}\) when \(\sigma \) has an ascent [i.e.  \(\sigma (i)〈\sigma (i+1)\) ]. The combinatorics of permutations with a prescribed signature is quite well explored. Here we introduce regular classes of permutations, the sets \(\varLambda (L)\) of permutations with signature in regular languages \(L\subseteq \{\mathfrak {a},\mathfrak {d}\}^*\) . Given a regular class of permutations we (i) count the permutations of a given length within the class; (ii) compute a closed form formula for the exponential generating function; and (iii) sample uniformly at random the permutation of a given length. We first recall how (i) is solved in the literature for the case of a single signature. We then explain how to extend these methods to regular classes of permutations using language equations from automata theory. We give two methods to solve (ii) in terms of exponentials of matrices. For the third problem we provide both discrete and continuous recursive methods as well as an extension of Boltzmann sampling to uncountable union of sets parametrised by a variable ranging over an interval. Last but not least, a part of our contributions are based on a geometric interpretation of a subclass of regular timed languages (that is, recognised by timed automata specific to our problem).

Description: 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.

Description: We study the storage allocation problem ( SAP ) which is a variant of the unsplittable flow problem on paths ( UFPP ). A SAP instance consists of a path \(P = (V,E)\) and a set J of tasks. Each edge \(e \in E\) has a capacity \(c_e\) and each task \(j \in J\) is associated with a path \(I_j\) in P , a demand \(d_j\) and a weight \(w_j\) . The goal is to find a maximum weight subset \(S \subseteq J\) of tasks and a height function \(h:S \rightarrow \mathbb {R}^+\) such that (i) \(h(j)+d_j \le c_e\) , for every \(e \in I_j\) ; and (ii) if \(j,i \in S\) such that \(I_j \cap I_i \ne \emptyset \) and \(h(j) \ge h(i)\) , then \(h(j) \ge h(i) + d_i\) . SAP can be seen as a rectangle packing problem in which rectangles can be moved vertically, but not horizontally. We present a polynomial time \((9+\varepsilon )\) -approximation algorithm for SAP . Our algorithm is based on a variation of the framework for approximating UFPP by Bonsma et al. [FOCS 2011] and on a \((4+\varepsilon )\) -approximation algorithm for \(\delta \) -small SAP instances (in which \(d_j \le \delta \cdot c_e\) , for every \(e \in I_j\) , for a sufficiently small constant \(\delta 〉0\) ). In our algorithm for \(\delta \) -small instances, tasks are packed carefully in strips in a UFPP manner, and then a \((1+\varepsilon )\) factor is incurred by a reduction from SAP to UFPP in strips. The strips are stacked to form a SAP solution. Finally, we provide a \((10+\varepsilon )\) -approximation algorithm for SAP on ring networks.

Description: 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.

Description: Let \(G=(V,E)\) be a finite undirected graph. An edge set \(E' \subseteq E\) is a dominating induced matching ( d.i.m. ) in G if every edge in E is intersected by exactly one edge of \(E'\) . The Dominating Induced Matching ( DIM ) problem asks for the existence of a d.i.m. in G ; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is \({\mathbb {NP}}\) -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for \(P_7\) -free graphs. However, its complexity was open for \(P_k\) -free graphs for any \(k \ge 8\) ; \(P_k\) denotes the chordless path with k vertices and \(k-1\) edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for \(P_8\) -free graphs.

Description: 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.

Description: 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.

Description: We study the dynamic scheduling problem for jobs with fixed start and end times on multiple machines. The problem is to design efficient data structures that support the update operations: insertions and deletions of jobs. Call the period of time in a schedule between two consecutive jobs in a given machine an idle interval . We show that for any set of jobs there exists a schedule such that the corresponding set of idle intervals forms a tree under the set-theoretic inclusion. We prove that any such schedule is optimal. Based on this result, we provide a data structure that maintains the updates the optimal schedule in \(O(d+\log n)\) worst-case time, where d is the depth of the set of idle intervals and n is the number of jobs. Furthermore, we show this bound is tight.

Description: 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 .

Description: 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.

Description: 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.

Description: We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data structures with various properties: in particular, we give data structures that achieve expected query times logarithmic in the entropy of the distribution of queries but with space bounded in terms of universe size, as well as data structures that use only linear space but with query times that are higher (but still sublinear) functions of the entropy. For these structures, the distribution is assumed to be known. We also consider individual query times on universe elements with general weights, as well as the case when the distribution is not known in advance.

Description: Working in a three-dimensional variant of Winfree’s abstract Tile Assembly Model, we show that, for all \(N \in \mathbb {N}\) , there is a tile set that uniquely self-assembles into an \(N \times N\) square shape at temperature 1 with program-size complexity of \(O\left( \frac{\log N}{\log \log N}\right) \) (the program-size complexity, also known as tile complexity, of a shape is the minimum number of unique tile types required to uniquely self-assemble it). Note that this tile complexity is optimal for all algorithmically random values of N . Moreover, our construction is “just barely” 3D in the sense that it works even when the placement of tiles is restricted to the \(z = 0\) and \(z = 1\) planes. This result affirmatively answers an open question from Cook et al. (SODA 2011 ). To achieve this result, we develop a general 3D temperature 1 optimal encoding construction, reminiscent of the 2D temperature 2 optimal encoding construction of Soloveichik and Winfree (SIAM J Comput 36(6):1544–1569, 2007 ), and perhaps of independent interest. We also develop a more sophisticated 3D temperature 1 optimal encoding construction that places asymptotically fewer tiles than our original optimal encoding construction. We use the method of conditional determinism of Lutz and Shutters (Theory Comput Syst 51(3):372–400, 2012 ) to prove the correctness of our constructions.

Description: Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information , where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information.

Description: 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.