LATIN 2018: Theoretical Informatics

A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The t-tessellability problem aims to decide whether there is a tessellation cover of the graph with t tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove $$\mathcal {NP}$$NP-completeness for t-tessellability if the instance is restricted to planar graphs, chordal (2, 1)-graphs, (1, 2)-graphs, diamond-free graphs with diameter five, or for any fixed t at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm.

Ashtiani et al. (NIPS 2016) introduced a semi-supervised framework for clustering (SSAC) where a learner is allowed to make same-cluster queries. More specifically, in their model, there is a query oracle that answers queries of the form “given any two vertices, do they belong to the same optimal cluster?”. In many clustering contexts, this kind of oracle queries are feasible. Ashtiani et al. showed the usefulness of such a query framework by giving a polynomial time algorithm for the k-means clustering problem where the input dataset satisfies some separation condition. Ailon et al. extended the above work to the approximation setting by giving an efficient $$(1+\varepsilon )$$(1+ε)-approximation algorithm for k-means for any small $$\varepsilon > 0$$ε>0 and any dataset within the SSAC framework. In this work, we extend this line of study to the correlation clustering problem. Correlation clustering is a graph clustering problem where pairwise similarity (or dissimilarity) information is given for every pair of vertices and the objective is to partition the vertices into clusters that minimise the disagreement (or maximises agreement) with the pairwise information given as input. These problems are popularly known as $$\mathsf {MinDisAgree}$$MinDisAgree and $$\mathsf {MaxAgree}$$MaxAgree problems, and $$\mathsf {MinDisAgree}[k]$$MinDisAgree[k] and $$\mathsf {MaxAgree}[k]$$MaxAgree[k] are versions of these problems where the number of optimal clusters is at most k. There exist Polynomial Time Approximation Schemes (PTAS) for $$\mathsf {MinDisAgree}[k]$$MinDisAgree[k] and $$\mathsf {MaxAgree}[k]$$MaxAgree[k] where the approximation guarantee is $$(1+\varepsilon )$$(1+ε) for any small $$\varepsilon $$ε and the running time is polynomial in the input parameters but exponential in k and $$1/\varepsilon $$1/ε. We get a significant running time improvement within the SSAC framework at the cost of making a small number of same-cluster queries. We obtain an $$(1+ \varepsilon )$$(1+ε)-approximation algorithm for any small $$\varepsilon $$ε with running time that is polynomial in the input parameters and also in k and $$1/\varepsilon $$1/ε. We also give non-trivial upper and lower bounds on the number of same-cluster queries, the lower bound being based on the Exponential Time Hypothesis (ETH). Note that the existence of an efficient algorithm for $$\mathsf {MinDisAgree}[k]$$MinDisAgree[k] in the SSAC setting exhibits the power of same-cluster queries since such polynomial time algorithm (polynomial even in k and $$1/\varepsilon $$1/ε) is not possible in the classical (non-query) setting due to our conditional lower bounds. Our conditional lower bound is particularly interesting as it not only establishes a lower bound on the number of same cluster queries in the SSAC framework but also establishes a conditional lower bound on the running time of any $$(1+\varepsilon )$$(1+ε)-approximation algorithm for $$\mathsf {MinDisAgree}[k]$$MinDisAgree[k].

In an r-uniform hypergraph on n vertices a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. We provide a first deterministic polynomial time algorithm, which finds a.a.s. tight Hamilton cycles in random r-uniform hypergraphs with edge probability at least $$C \log ^3n/n$$Clog3n/n.Our result partially answers a question of Dudek and Frieze (Random Struct Algorithms 42:374–385, 2013) who proved that tight Hamilton cycles exists already for $$p=\omega (1/n)$$p=ω(1/n) for $$r=3$$r=3 and $$p=(e + o(1))/n$$p=(e+o(1))/n for $$r\ge 4$$r≥4 using a second moment argument. Moreover our algorithm is superior to previous results of Allen et al. (Random Struct Algorithms 46:446–465, 2015) and Nenadov and Škorić (arXiv:1601.04034) in various ways: the algorithm of Allen et al. is a randomised polynomial time algorithm working for edge probabilities $$p\ge n^{-1+\varepsilon }$$p≥n-1+ε, while the algorithm of Nenadov and Škorić is a randomised quasipolynomial time algorithm working for edge probabilities $$p\ge C\log ^8n/n$$p≥Clog8n/n.

We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $$G=(V,E)$$G=(V,E), find a shortest walk (“route”) from a source $$s\in V$$s∈V to a destination $$t\in V$$t∈V that includes all vertices specified by a set $$\mathscr {W}\subseteq V$$W⊆V: the waypoints. This waypoint routing problem finds immediate applications in the context of modern networked distributed systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial-time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

In the online matching on the line problem, the task is to match a set of requests R online to a given set of servers S. The distance metric between any two points in $$R\,\cup \,S$$R∪S is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and – despite recent improvements – there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is $$O(\log ^2n)$$O(log2n)-competitive, while the best known deterministic lower bound is 9.001. The lower and upper bounds for randomized algorithms are 4.5 and $$O(\log n)$$O(logn) respectively.We prove that any deterministic online algorithm which in each round: (i) bases the matching decision only on information local to the current request, and (ii) is symmetric (in the sense that the decision corresponding to the mirror image of some instance I is the mirror image of the decision corresponding to instance I), must be $$\varOmega (\log n)$$Ω(logn)-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of $$\varOmega (\log n)$$Ω(logn) on the competitive ratio for a large class of “natural” algorithms. This class includes all deterministic online algorithms found in the literature so far.Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The $$\varOmega (\log n)$$Ω(logn)-barrier on the competitive ratio holds for this class of algorithms as well.

For two positive integers k and $$\ell $$ℓ, a $$(k \times \ell )$$(k×ℓ)-spindle is the union of k pairwise internally vertex-disjoint directed paths with $$\ell $$ℓ arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $$\ell \ge 1$$ℓ≥1, finding the largest k such that an input digraph G contains a subdivision of a $$(k \times \ell )$$(k×ℓ)-spindle is polynomial-time solvable if $$\ell \le 3$$ℓ≤3, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.

In the context of computational supervised learning, the primary objective is the classification of data. Especially, the goal is to provide the system with “training” data and design a method which uses the training data to classify new objects with the correct label. A standard scenario is that the examples are points from a metric space, and “nearby” points should have “similar” labels. In practice, it is desirable to reduce the size of the training set without compromising too much on the ability to correctly label new objects. Such subsets of the training data are called as edited sets. Wilfong [SOCG ’91] defined two types of edited subsets: consistent subsets (those which correctly label all objects from the training data) and selective subsets (those which correctly label all new objects the same way as the original training data). This leads to the following two optimization problems:: Given k sets of points $$P_1, P_2, \ldots , P_k$$P1,P2,…,Pk in a metric space $$\mathcal X$$X, the goal is to choose subsets of points $$P'_i \subseteq P_i$$Pi′⊆Pi for $$i=1,2,\ldots ,k$$i=1,2,…,k such that $$\forall \ p \in P_i$$∀p∈Pi its nearest neighbor among $$\bigcup _{j=1}^{k} P'_j $$⋃j=1kPj′ lies in $$P'_i$$Pi′ for each $$i\in [k]$$i∈[k] while minimizing (Note that we also enforce the condition $$|P'_i|\ge 1\ \forall \ i\in [k]$$|Pi′|≥1∀i∈[k].) the quantity $$\sum _{i=1}^k |P'_i|$$∑i=1k|Pi′|.: Given k sets of points $$P_1, P_2, \ldots , P_k$$P1,P2,…,Pk in a metric space $$\mathcal X$$X, the goal is to choose subsets of points $$P'_i \subseteq P_i$$Pi′⊆Pi for $$i=1,2,\ldots ,k$$i=1,2,…,k such that $$\forall \ p \in P_i$$∀p∈Pi its nearest neighbor among $$\Big (\bigcup _{j=1, j\ne i}^{k} P_j\Big ) \cup P'_i $$(⋃j=1,j≠ikPj)∪Pi′ lies in $$P'_i$$Pi′ for each $$i\in [k]$$i∈[k] while minimizing (Note that we again enforce the condition $$|P'_i|\ge 1\ \forall \ i\in [k]$$|Pi′|≥1∀i∈[k].) the quantity $$\sum _{i=1}^k |P'_i|$$∑i=1k|Pi′|.While there have been several heuristics proposed for these two problems in the computer vision and machine learning community, the only theoretical results for these problems (to the best of our knowledge) are due to Wilfong [SOCG ’91] who showed that both 3-MCS-($$\mathbb {R}^2$$R2) and 2-MSS-($$\mathbb {R}^2$$R2) are NP-complete. We initiate the study of these two problems from a theoretical perspective, and obtain several algorithmic and hardness results.On the algorithmic side, we first design an $$O(n^2)$$O(n2) time exact algorithm and $$O(n\log n)$$O(nlogn) time 2-approximation for the 2-MCS-($$\mathbb {R}$$R) problem, i.e., the points are located on the real line. Moreover, we show that the exact algorithm also extends to the case when the points are located on the circumference of a circle. Next, we design an $$O(r^2)$$O(r2) time online algorithm for the 2-MCS-($$\mathbb {R}$$R) problem such that $$r<n$$r<n, where n is the set of points and r is an integer. Finally, we give a PTAS for the k-MSS-($$\mathbb {R}^2$$R2) problem. On the hardness side, we show that both the 2-MCS and 2-MSS problems are NP-complete on graphs. Additionally, the problems are W[2]-hard parameterized by the size k of the solution. For points on the Euclidean plane, we show that the 2-MSS problem is contained in W[1]. Finally, we show a lower bound of $$\varOmega (\sqrt{n})$$Ω(n) bits for the storage of any (randomized) algorithm which solves both 2-MCS-($$\mathbb {R}$$R) and 2-MSS-($$\mathbb {R}$$R).

Consider a secure environment (say an airport) that has a unique entry and exit point with multiple inter-crossing paths between them. We want to place (minimum number of) trackers (or check points) at some specific intersections so that based on the sequence of trackers a person has encountered, we can identify the exact path traversed by the person. Motivated by such applications, we study the Tracking Paths problem in this paper. Given an undirected graph with a source s, a destination t and a non-negative integer k, the goal is to find a set of at most k vertices, a tracking set, that intersects each $$s$$s-$$t$$t path in a unique sequence. Such a set enables a central controller to track all the paths from s to t. We first show that the problem is NP-complete. Then we show that finding a tracking set of size at most k is fixed-parameter tractable (FPT) when parameterized by the solution size. More specifically, given an undirected graph on n vertices and an integer k, we give a polynomial time algorithm that either determines that the graph cannot be tracked by k trackers or produces an equivalent instance of size $$\mathcal {O}(k^7)$$O(k7).

In the limited-workspace model, we assume that the input of size n lies in a random access read-only memory. The output has to be reported sequentially, and it cannot be accessed or modified. In addition, there is a read-write workspace of O(s) words, where $$s \in \{1, \dots , n\}$$s∈{1,⋯,n} is a given parameter. In a time-space trade-off, we are interested in how the running time of an algorithm improves as s varies from 1 to n.We present a time-space trade-off for computing the Euclidean minimum spanning tree ($${{\mathrm{EMST}}}$$EMST) of a set V of n sites in the plane. We present an algorithm that computes $${{\mathrm{EMST}}}(V)$$EMST(V) using $$O(n^3\log s /s^2)$$O(n3logs/s2) time and O(s) words of workspace. Our algorithm uses the fact that $${{\mathrm{EMST}}}(V)$$EMST(V) is a subgraph of the bounded-degree relative neighborhood graph of V, and applies Kruskal’s MST algorithm on it. To achieve this with limited workspace, we introduce a compact representation of planar graphs, called an s-net which allows us to manipulate its component structure during the execution of the algorithm.

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and $$\ell _1$$, few non-trivial algorithms are known for $$\ell _p$$ when $$2<p<\infty $$. In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the best known approximation factor guarantees in this setting.

The broadcast congested clique model is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. The joint input to the n nodes is an undirected graph G on the same set of nodes, with each node receiving the list of its immediate neighbors inG. In each round each node sends the same message to all other nodes, depending on its own input, on the messages it has received so far, and on a public sequence of random bits. One parameter of this model is an upper bound b on the size of the messages, also known as bandwidth. In this paper we introduce another parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r.In this new framework we study one of the hardest problems in distributed graph algorithms, this is, the problem of detecting, in G, an induced cycle of length at most k ($$\textsc {Cycle}_{\le k}$$CYCLE≤k) and the problem of detecting in G an induced cycle of length at least k $$+$$+ 1 ($$\textsc {Cycle}_{>k}$$CYCLE>k). For $$r=1$$r=1, we exhibit a deterministic, one-round algorithm for solving $$\textsc {Cycle}_{\le k}$$CYCLE≤k with $$b = \mathcal {O}(n^{2/k} \log n)$$b=O(n2/klogn) if k is even, and $$b = \mathcal {O}(n^{2/(k-1)}\log n)$$b=O(n2/(k-1)logn) if k is odd. We also prove, assuming the Erdős Girth Conjecture, that this result is tight for $$k \ge 4$$k≥4, up to logarithmic factors. More precisely, if each node, instead of being able to see only its immediate neighbors, is allowed to see up to distance $$r={\lfloor k/4 \rfloor }$$r=⌊k/4⌋, and if we also allowed randomization and multiple rounds, then the number of rounds R needed to solve $$\textsc {Cycle}_{\le k}$$CYCLE≤k must be such that $$R\cdot b = \varOmega ( n^{2/k})$$R·b=Ω(n2/k) if k is even, and $$R\cdot b = \varOmega ( n^{2/(k-1)})$$R·b=Ω(n2/(k-1)) if k is odd.On the other hand, we show that, if each node is allowed to see up to distance $$r={\lfloor k/2 \rfloor + 1}$$r=⌊k/2⌋+1, then a polylogarithmic bandwidth is sufficient for solving $$\textsc {Cycle}_{>k}$$CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance $$r=\lfloor k/3 \rfloor $$r=⌊k/3⌋, then any one-round algorithm that solves $$\textsc {Cycle}_{>k}$$CYCLE>k needs the bandwidth b to be at least $$\varOmega (n/\log n)$$Ω(n/logn).

The problem of partitioning an orthogonal polyhedron into a minimum number of boxes was shown to be NP-hard in 1991, but no approximability result is known except for a 4-approximation algorithm for 3D-histograms. In this paper we broaden the understanding of the 3D-histogram partitioning problem. We prove that partitioning a 3D-histogram into a minimum number of boxes is NP-hard, even for histograms of height two. This settles an open question posed by Floderus et al. We then show the problem to be APX-hard for histograms of height four. On the positive side, we give polynomial-time algorithms to compute optimal or approximate box partitions for some restricted but interesting classes of polyhedra and 3D-histograms.

We present a self-stabilizing leader election algorithm for general networks, with space-complexity $$O(\log \varDelta +\log \log n)$$O(logΔ+loglogn) bits per node in n-node networks with maximum degree $$\varDelta $$Δ. This space complexity is sub-logarithmic in n as long as $$\varDelta = n^{o(1)}$$Δ=no(1). The best space-complexity known so far for general networks was $$O(\log n)$$O(logn) bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $$\varOmega (\log n)$$Ω(logn) bound for silent algorithms in general networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $$O(\log \varDelta +\log \log n)$$O(logΔ+loglogn) bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees — storing the IDs of the neighbors requires $$\varOmega (\log n)$$Ω(logn) bits per node, while we encode spanning trees using $$O(\log \varDelta +\log \log n)$$O(logΔ+loglogn) bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $$\varOmega (\log n)$$Ω(logn) bits per node.

In nature, search processes that use randomly oriented steps of different lengths have been observed at both the microscopic and the macroscopic scales. Physicists have analyzed in depth two such processes on grid topologies: Intermittent Search, which uses two step lengths, and Lévy Walk, which uses many. Taking a computational perspective, this paper considers the number of distinct step lengths k as a complexity measure of the considered process. Our goal is to understand what is the optimal achievable time needed to cover the whole terrain, for any given value of k. Attention is restricted to dimension one, since on higher dimensions, the simple random walk already displays a quasi linear cover time.We say X is a k-intermittent search on the one dimensional n-node cycle if there exists a probability distribution $$\mathbf{p }=(p_i)_{i=1}^k$$p=(pi)i=1k, and integers $$L_1,L_2,\ldots , L_k$$L1,L2,…,Lk, such that on each step X makes a jump $$\pm L_i$$±Li with probability $$p_i$$pi, where the direction of the jump ($$+$$+ or −) is chosen independently with probability 1/2. When performing a jump of length $$L_i$$Li, the process consumes time $$L_i$$Li, and is only considered to visit the last point reached by the jump (and not any other intermediate nodes). This assumption is consistent with biological evidence, in which entities do not search while moving ballistically.We provide upper and lower bounds for the cover time achievable by k-intermittent searches for any integer k. In particular, we prove that in order to reduce the cover time $${\varTheta }(n^2)$$Θ(n2) of a simple random walk to linear in n up to logarithmic factors, roughly $$\frac{\log n}{\log \log n}$$lognloglogn step lengths are both necessary and sufficient, and we provide an example where the lengths form an exponential sequence.In addition, inspired by the notion of intermittent search, we introduce the Walk or Probe problem, which can be defined with respect to arbitrary graphs. Here, it is assumed that querying (probing) a node takes significantly more time than moving to a random neighbor. Hence, to efficiently probe all nodes, the goal is to balance the time spent walking randomly and the time spent probing. We provide preliminary results for connected graphs and regular graphs.

The Point Hyperplane Cover problem in $$\mathbb {R}^d$$ takes as input a set of n points in $$\mathbb {R}^d$$ and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in $$\mathbb {R}^d$$ takes as input a family $$\mathcal {F}$$ of D-degree polynomials from a vector space $$\mathcal {R}$$ in $$\mathbb {R}^d$$, and determines whether there is a set of at most k points in $$\mathbb {R}^d$$ that hit all the polynomials in $$\mathcal {F}$$. For both problems, we exhibit tight kernels where k is the parameter.

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree $$T=(W\uplus B, E)$$T=(W⊎B,E) is being revealed online, i.e., in each round one vertex from $$B$$B with its incident edges arrives. It was conjectured by Chaudhuri et al. [7] that the total length of all shortest augmenting paths found is $$O(n \log n)$$O(nlogn). In this paper we prove a tight $$O(n \log n)$$O(nlogn) upper bound for the total length of shortest augmenting paths for trees improving over $$O(n \log ^2 n)$$O(nlog2n) bound [5].

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places; at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations.Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Given a finite set of weighted points in $$\mathbb {R}^d$$Rd (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in $$d=1$$d=1 these computations are #P-hard, and give pseudo polynomial-time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$d=2, we consider that each point is colored red or blue, where red points have weight $$+1$$+1 and blue points weight $$-\infty $$-∞. The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.

We introduce the online Set Aggregation Problem, which is a natural generalization of the Multi-Level Aggregation Problem, which in turn generalizes the TCP Acknowledgment Problem and the Joint Replenishment Problem. We give a deterministic online algorithm, and show that its competitive ratio is logarithmic in the number of requests. We also give a matching lower bound on the competitive ratio of any randomized online algorithm.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses $$O(n (\log n \log \log n)^2)$$O(n(lognloglogn)2) space, supports queries in worst case $$O(\log ^3 n)$$O(log3n) time, and updates in $$O(\log ^7 n)$$O(log7n) amortized time. This leads to an $$O(n\alpha (n)\log ^7 n)$$O(nα(n)log7n) time algorithm (where $$\alpha $$α is the inverse Ackermann function) to solve the agglomerative clustering problem, which is a significant improvement over the straightforward $$O(n^2 \log n)$$O(n2logn) time algorithm.

The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $$f:\{+1,-1\}^n \rightarrow \{+1,-1\}$$f:{+1,-1}n→{+1,-1}, the Fourier entropy of f is at most its influence up to a universal constant factor. While the FEI conjecture has been proved for many classes of Boolean functions, it is still not known whether it holds for the class of Linear Threshold Functions. A natural question is: Does the FEI conjecture hold for a “random” linear threshold function? In this paper, we answer this question in the affirmative. We consider two natural distributions on the weights defining a linear threshold function, namely uniform distribution on $$[-1,1]$$[-1,1] and Normal distribution.

The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In Property Indexing, we are given a string x of length n and a property $$\varPi $$Π, i.e. a set of $$\varPi $$Π-valid intervals over x. A suffix-tree-like index over these valid prefixes of suffixes of x can be built in time and space $$\mathcal {O}(n)$$O(n). We show here how to directly build a suffix-array-like index, the Property Suffix Array (PSA), in time and space $$\mathcal {O}(n)$$O(n). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold $$\frac{1}{z}$$1z, we say that a string p of length m matches a weighted sequence X of length n at starting position i if the product of probabilities of the letters of p at positions $$i,\ldots ,i+m-1$$i,…,i+m-1 in X is at least $$\frac{1}{z}$$1z. Our algorithm for building the PSA can be directly applied to build an $$\mathcal {O}(nz)$$O(nz)-sized suffix-array-like index over X in time and space $$\mathcal {O}(nz)$$O(nz).

We consider a scheduling problem which abstracts a model of demand-response management in Smart Grid. In the problem, there is a set of unrelated machines and each job j (representing a client demand) is characterized by a release date, and a power request function representing its request demand at specific times. Each machine has an energy power function and the energy cost incurred at a time depends on the load of the machine at that time. The goal is to find a non-migration schedule that minimizes the total energy (over all times).We give a competitive algorithm for the problem in the online setting where the competitive ratio depends (only) on the power functions of machines. In the setting with typical energy function $$P(z) = z^{\nu }$$P(z)=zν, the algorithm is $$\varTheta (\nu ^{\nu })$$Θ(νν)-competitive, which is optimal up to a constant factor. Our algorithm is robust in the sense that the guarantee holds for arbitrary request demands of clients. This enables flexibility on the choices of clients in shaping their demands — a desired property in Smart Grid.We also consider a special case in offline setting in which jobs have unit processing time, constant power request and identical machines with energy function $$P(z) = z^{\nu }$$P(z)=zν. We present a $$2^{\nu }$$2ν-approximation algorithm for this case.

In a seminal work, Williams [22] showed that $$\mathsf {NEXP}$$NEXP (non-deterministic exponential time) does not have polynomial-size $$\mathsf {ACC}^0$$ACC0 circuits. Williams’ technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known. We show that there is a language L in $$\mathsf {NEXP}$$NEXP and a function $$\varepsilon (n) = 1/\log (n)^{\omega (1)}$$ε(n)=1/log(n)ω(1) such that no sequence of polynomial size $$\mathsf {ACC}^0$$ACC0 circuits solves L on more than a $$1/2+\varepsilon (n)$$1/2+ε(n) fraction of inputs of length n for all large enough n. Complementing this result, we give a nontrivial pseudo-random generator against polynomial-size $$\mathsf {AC}^0[6]$$AC0[6] circuits. We also show that learning algorithms for quasi-polynomial size $$\mathsf {ACC}^0$$ACC0 circuits running in time $$2^n/n^\omega (1)$$2n/nω(1) imply lower bounds for the randomised exponential time classes $$\mathsf {RE}$$RE (randomized time $$2^{O(n)}$$2O(n) with one-sided error) and $$\mathsf {ZPE}/1$$ZPE/1 (zero-error randomized time $$2^{O(n)}$$2O(n) with 1 bit of advice) against polynomial size $$\mathsf {ACC}^0$$ACC0 circuits. This strengthens results of Oliveira and Santhanam [15].

The compressed indexing problem is to preprocess a string S of length n into a compressed representation that supports pattern matching queries. That is, given a string P of length m report all occurrences of P in S.We present a data structure that supports pattern matching queries in $$O(m + \mathsf {occ}(\lg \lg n + \lg ^\epsilon z))$$O(m+occ(lglgn+lgϵz)) time using $$O(z \lg (n / z))$$O(zlg(n/z)) space where z is the size of the LZ77 parse of S and $$\epsilon > 0$$ϵ>0 is an arbitrarily small constant, when the alphabet is small or $$z = O(n^{1 - \delta })$$z=O(n1-δ) for any constant $$\delta > 0$$δ>0. We also present two data structures for the general case; one where the space is increased by $$O(z\lg \lg z)$$O(zlglgz), and one where the query time changes from worst-case to expected. These results improve the previously best known solutions. Notably, this is the first data structure that decides if P occurs in S in O(m) time using $$O(z\lg (n/z))$$O(zlg(n/z)) space.Our results are mainly obtained by a novel combination of a randomized grammar construction algorithm with well known techniques relating pattern matching to 2D-range reporting.

A beacon is a point-like object which can be enabled to exert a magnetic pull on other point-like objects in space. Those objects then move towards the beacon in a greedy fashion until they are either stuck at an obstacle or reach the beacon’s location. Beacons placed inside polyhedra can be used to route point-like objects from one location to another. A second use case is to cover a polyhedron such that every point-like object at an arbitrary location in the polyhedron can reach at least one of the beacons once the latter is activated.The notion of beacon-based routing and guarding was introduced by Biro et al. [FWCG’11] in 2011 and covered in detail by Biro in his Ph.D. thesis [SUNY-SB’13], which focuses on the two-dimensional case.We extend Biro’s result to three dimensions by considering beacon routing in polyhedra. We show that $$\lfloor {\frac{m+1}{3}}\rfloor $$⌊m+13⌋ beacons are always sufficient and sometimes necessary to route between any pair of points in a given polyhedron P, where m is the number of tetrahedra in a tetrahedral decomposition of P. This is one of the first results that show that beacon routing is also possible in three dimensions.

In this paper, we are interested in edge intersection graphs of paths in a grid, such that each such path has at most one bend. These graphs were introduced in [12] and they are called $$B_1$$B1-EPG graphs. In particular, we focus on split graphs and characterise those that are $$B_1$$B1-EPG. This characterisation allows us to disprove a conjecture of Cameron et al. [7]. The existence of polynomial-time recognition algorithm for this graph class is still unknown. We furthermore investigate inclusion relationships among subclasses of split graphs that are $$B_1$$B1-EPG.

Efficient computation of shortest cycles which form a homology basis under $$\mathbb {Z}_2$$Z2-additions in a given simplicial complex $$\mathcal {K}$$K has been researched actively in recent years. When the complex $$\mathcal {K}$$K is a weighted graph with n vertices and m edges, the problem of computing a shortest (homology) cycle basis is known to be solvable in $$O(m^2n/\log n+ n^2m)$$O(m2n/logn+n2m)-time. Several works [1, 2] have addressed the case when the complex $$\mathcal {K}$$K is a 2-manifold. The complexity of these algorithms depends on the rank g of the one-dimensional homology group of $$\mathcal {K}$$K. This rank g has a lower bound of $$\varTheta (n)$$Θ(n), where n denotes the number of simplices in $$\mathcal {K}$$K, giving an $$O(n^4)$$O(n4) worst-case time complexity for the algorithms in [1, 2]. This worst-case complexity is improved in [3] to $$O(n^\omega + n^2g^{\omega -1})$$O(nω+n2gω-1) for general simplicial complexes where $$\omega < 2.3728639$$ω<2.3728639 [4] is the matrix multiplication exponent. Taking $$g=\varTheta (n)$$g=Θ(n), this provides an $$O(n^{\omega +1})$$O(nω+1) worst-case algorithm. In this paper, we improve this time complexity. Combining the divide and conquer technique from [5] with the use of annotations from [3], we present an algorithm that runs in $$O(n^\omega +n^2g)$$O(nω+n2g) time giving the first $$O(n^3)$$O(n3) worst-case algorithm for general complexes. If instead of minimal basis, we settle for an approximate basis, we can improve the running time even further. We show that a 2-approximate minimal homology basis can be computed in $$O(n^{\omega }\sqrt{n \log n})$$O(nωnlogn) expected time. We also study more general measures for defining the minimal basis and identify reasonable conditions on these measures that allow computing a minimal basis efficiently.

We show that by restricting the degrees of the vertices of a graph to an arbitrary set $$ \varDelta $$Δ, the threshold point $$ \alpha (\varDelta ) $$α(Δ) of the phase transition for a random graph with $$ n $$n vertices and $$ m = \alpha (\varDelta ) n $$m=α(Δ)n edges can be either accelerated (e.g., $$ \alpha (\varDelta ) \approx 0.381 $$α(Δ)≈0.381 for $$ \varDelta = \{0,1,4,5\} $$Δ={0,1,4,5}) or postponed (e.g., $$ \alpha (\{ 2^0, 2^1, \cdots , 2^k, \cdots \}) \approx 0.795 $$α({20,21,⋯,2k,⋯})≈0.795) compared to a classical Erdős–Rényi random graph with $$ \alpha (\mathbb Z_{\ge 0}) = \tfrac{1}{2} $$α(Z≥0)=12. In particular, we prove that the probability of graph being nonplanar and the probability of having a complex component, goes from $$ 0 $$0 to $$ 1 $$1 as $$ m $$m passes $$ \alpha (\varDelta ) n $$α(Δ)n. We investigate these probabilities and also different graph statistics inside the critical window of transition (diameter, longest path and circumference of a complex component).

In this article we consider the following question: N words of length L are generated using a biased memoryless source, i.e. each letter is taken independently according to some fixed distribution on the alphabet, and collected in a set (duplicates are removed); what are the frequencies of the letters in a typical element of this random set? We prove that the typical frequency distribution of such a word can be characterized by considering the parameter $$\ell = L/\log N$$ℓ=L/logN. We exhibit two thresholds $$\ell _0<\ell _1$$ℓ0<ℓ1 that only depend on the source, such that if $$\ell \le \ell _0$$ℓ≤ℓ0, the distribution resembles the uniform distribution; if $$\ell \ge \ell _1$$ℓ≥ℓ1 it resembles the distribution of the source; and for $$\ell _0\le \ell \le \ell _1$$ℓ0≤ℓ≤ℓ1 we characterize the distribution as an interpolation of the two extremal distributions.

For positive integers k and $$\ell $$ℓ, a k-uniform hypergraph is called a loose path of length$$\ell $$ℓ, and denoted by $$P_\ell ^{(k)}$$Pℓ(k), if its vertex set is $$\{v_1, v_2, \ldots , v_{(k-1)\ell +1}\}$${v1,v2,…,v(k-1)ℓ+1} and the edge set is $$\{e_i = \{ v_{(i-1)(k-1)+q} : 1 \le q \le k \},\ i=1,\dots ,\ell \}$${ei={v(i-1)(k-1)+q:1≤q≤k},i=1,⋯,ℓ}, that is, each pair of consecutive edges intersects on a single vertex. Let $$R(P_\ell ^{(k)};r)$$R(Pℓ(k);r) be the multicolor Ramsey number of a loose path that is the minimum n such that every r-edge-coloring of the complete k-uniform hypergraph $$K_n^{(k)}$$Kn(k) yields a monochromatic copy of $$P_\ell ^{(k)}$$Pℓ(k). In this note we are interested in constructive upper bounds on $$R(P_\ell ^{(k)};r)$$R(Pℓ(k);r) which means that on the cost of possibly enlarging the order of the complete hypergraph, we would like to efficiently find a monochromatic copy of $$P_\ell ^{(k)}$$Pℓ(k) in every coloring. In particular, we show that there is a constant $$c>0$$c>0 such that for all $$k\ge 2$$k≥2, $$\ell \ge 3$$ℓ≥3, $$2\le r\le k-1$$2≤r≤k-1, and $$n\ge k(\ell +1)r(1+\ln (r))$$n≥k(ℓ+1)r(1+ln(r)), there is an algorithm such that for every r-edge-coloring of the edges of $$K_n^{(k)}$$Kn(k), it finds a monochromatic copy of $$P_\ell ^{(k)}$$Pℓ(k) in time at most $$cn^k$$cnk.

We study the problem of sparse matrix multiplication in the Random Access Machine and in the Ideal Cache-Oblivious model. We present a simple algorithm that exploits randomization to compute the product of two sparse matrices with elements over an arbitrary field. Let $$A \in \mathbb {F}^{n \times n}$$A∈Fn×n and $$C \in \mathbb {F}^{n \times n}$$C∈Fn×n be matrices with h nonzero entries in total from a field $$\mathbb {F}$$F. In the RAM model, we are able to compute all the k nonzero entries of the product matrix $$AC \in \mathbb {F}^{n \times n}$$AC∈Fn×n using $$\tilde{\mathcal {O}}(h + kn)$$O~(h+kn) time and $$\mathcal {O}(h)$$O(h) space, where the notation $$\tilde{\mathcal {O}}(\cdot )$$O~(·) suppresses logarithmic factors. In the External Memory model, we are able to compute cache obliviously all the k nonzero entries of the product matrix $$AC \in \mathbb {F}^{n \times n}$$AC∈Fn×n using $$\tilde{\mathcal {O}}(h/B + kn/B)$$O~(h/B+kn/B) I/Os and $$\mathcal {O}(h)$$O(h) space. In the Parallel External Memory model, we are able to compute all the k nonzero entries of the product matrix $$AC \in \mathbb {F}^{n \times n}$$AC∈Fn×n using $$\tilde{\mathcal {O}}(h/PB + kn/PB)$$O~(h/PB+kn/PB) time and $$\mathcal {O}(h)$$O(h) space, which makes the analysis in the External Memory model a special case of Parallel External Memory for $$P=1$$P=1. The guarantees are given in terms of the size of the field and by bounding the size of $$\mathbb {F}$$F as $${|}\mathbb {F}{|} > kn \log (n^2/k)$$|F|>knlog(n2/k) we guarantee an error probability of at most $$1{\text{/ }}n$$1/n for computing the matrix product.

We consider dynamic loading and unloading problems for heavy geometric objects. The challenge is to maintain balanced configurations at all times: minimize the maximal motion of the overall center of gravity. While this problem has been studied from an algorithmic point of view, previous work only focuses on balancing the final center of gravity; we give a variety of results for computing balanced loading and unloading schemes that minimize the maximal motion of the center of gravity during the entire process.In particular, we consider the one-dimensional case and distinguish between loading and unloading. In the unloading variant, the positions of the intervals are given, and we search for an optimal unloading order of the intervals. We prove that the unloading variant is NP-complete and give a 2.7-approximation algorithm. In the loading variant, we have to compute both the positions of the intervals and their loading order. We give optimal approaches for several variants that model different loading scenarios that may arise, e.g., in the loading of a transport ship with containers.

We study online algorithms for bin packing and bin covering in two different probabilistic settings in which the item sizes are drawn randomly or the items are adversarial but arrive in random order. We prove several results on the expected performance of well-known online algorithms in these settings. In particular, we prove that the simple greedy algorithm Dual Next-Fit for bin covering performs in the random-order setting strictly better than in the worst case, proving a conjecture by Christ et al. (Theoret Comput Sci 556:71–84, 2014).Additionally we also study class-constrained bin packing and bin covering. In these problems, each item has not only a size but also a color and there are constraints on the number of different colors in each bin. These problems have been studied before in the classical worst-case model and we provide the first probabilistic analysis of these problems. We prove for several simple online algorithms bounds on their expected performance in the two probabilistic models discussed above. We observe that in the case of class constrained bin packing for several algorithms their performance differs with respect to the two probabilistic performance measures.

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to $$A - cI$$A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time $$O(k^2 n)$$O(k2n). This allows to quickly tell the number of eigenvalues in a given interval.

Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is b, the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing b is NP-complete, a popular gold standard is z, the number of phrases in the Lempel-Ziv parse of the text, where phrases can be copied only from the left. While z can be computed in linear time, almost nothing has been known for decades about its approximation ratio with respect to b. In this paper we prove that $$z=O(b\log (n/b))$$z=O(blog(n/b)), where n is the text length. We also show that the bound is tight as a function of n, by exhibiting a string family where $$z = \varOmega (b\log n)$$z=Ω(blogn). Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating b with r, the number of equal-letter runs in the Burrows-Wheeler transform of the text. On our way, we prove other relevant bounds between compressibility measures.

The homophyly phenomenon is very common in social networks. The Maximum Happy Vertices (MHV) is a newly proposed problem related to homophyly phenomenon. Given a graph $$G=(V,E)$$G=(V,E) and a vertex coloring of G, we say that a vertex v is happy if v shares the same color with all its neighbors, and unhappy, otherwise, and that an edge e is happy, if its two endpoints have the same color, and unhappy, otherwise. Given a partial vertex coloring of G with k number of different colors, the k-MHV problem is to color all the remaining vertices such that the number of happy vertices is at least l. We study k-MHV from the parameterized algorithm perspective; we prove that k-MHV has an exponential kernel of $$2^{kl+l}\,+\,kl\,+\,k\,+\,l$$2kl+l+kl+k+l on general graph. For planar graph, we get a much better polynomial kernel of $$7(kl+l)+k-10$$7(kl+l)+k-10.

In the Red-Blue Nonblocker problem, the input is a bipartite graph $$G=(R \uplus B, E)$$G=(R⊎B,E) and an integer k, and the question is whether one can select at least k vertices from R so that every vertex in B has a neighbor in R that was not selected. While the problem is W[1]-complete for parameter k, a related problem, Nonblocker, is FPT for parameter k. In the Nonblocker problem, we are given a graph H and an integer k, and the question is whether one can select at least k vertices so that every selected vertex has a neighbor that was not selected. There is also a simple reduction from Nonblocker to Red-Blue Nonblocker, creating two copies of the vertex set and adding an edge between two vertices in different copies if they correspond to the same vertex or to adjacent vertices. We give FPT algorithms for Red-Blue Nonblocker instances that are the result of this transformation – we call these instances symmetric. This is not achieved by playing back the entire transformation, since this problem is NP-complete, but by a kernelization argument that is inspired by playing back the transformation only for certain well-structured parts of the instance. We also give an FPT algorithm for almost symmetric instances, where we assume the symmetry relation is part of the input.Next, we augment the parameter by $$\ell = \left| B \right| /\left| R \right| $$ℓ=B/R. Somewhat surprisingly, Red-Blue Nonblocker is W[1]-hard for the parameter $$k+\ell $$k+ℓ, but becomes FPT if no vertex in B has degree 1. The FPT algorithm relies on a structural argument where we show that when |R| is large with respect to k and $$\ell $$ℓ, we can greedily compute a red-blue nonblocker of size at least k. The same results also hold if we augment the parameter by $$d_R$$dR instead of $$\ell $$ℓ, where $$d_R$$dR is the average degree of the vertices in R.

In this paper, we present new incremental algorithms for maintaining data structures that represent all connectivity cuts of size one in directed graphs (digraphs), and the strongly connected components that result by the removal of each of those cuts. We give a conditional lower bound that provides evidence that our algorithms may be tight up to a sub-polynomial factors. As an additional result, with our approach we can also maintain dynamically the 2-vertex-connected components of a digraph during any sequence of edge insertions in a total of O(mn) time. This matches the bounds for the incremental maintenance of the 2-edge-connected components of a digraph.

Given a connected graph G of m edges and n vertices, we consider the basic problem of listing all the choices of k vertex-disjoint st-paths, for any two input vertices s, t of G and a positive integer k. Our algorithm takes O(m) time per solution, using O(m) space and requiring $$O(F_k(G))$$O(Fk(G)) setup time, where $$F_k(G) = O(m \min \{k, n^{2/3} \log n, \sqrt{m} \log n\} )$$Fk(G)=O(mmin{k,n2/3logn,mlogn}) is the cost of running a max-flow algorithm on G to compute a flow of size k. The proposed techniques are simple and apply to other related listing problems discussed in the paper.

Let $$\mathrm {lct}(G)$$lct(G) be the minimum size of a set of vertices that intersects every longest cycle of a 2-connected graph G. Let $$\mathrm {tw}(G)$$tw(G) be the tree-width of G and $$\omega (G)$$ω(G) be the size of a maximum clique in G. We show that $$\mathrm {lct}(G)\le \mathrm {tw}(G)-1$$lct(G)≤tw(G)-1 for every G, and that $$\mathrm {lct}(G)\le \max \{1, {\omega (G){-}3}\}$$lct(G)≤max{1,ω(G)-3} if G is chordal. Those results imply as corollaries that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. We also strengthen the latter result and show that all longest cycles intersect in 2-connected graphs of tree-width at most 3, also known as partial 3-trees.

Consider a graph $$G=(V,E)$$G=(V,E) and an initial random coloring where each vertex $$v \in V$$v∈V is blue with probability $$P_b$$Pb and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random d-regular graph $$\mathbb {G}_{n,d}$$Gn,d. It is shown that for $$\epsilon >0$$ϵ>0, $$P_b \le 1/2-\epsilon $$Pb≤1/2-ϵ results in final complete occupancy by red in $$\mathcal {O}(\log _d\log n)$$O(logdlogn) rounds with high probability, provided that $$d\ge c/\epsilon ^2$$d≥c/ϵ2 for a sufficiently large constant c. We argue that the bound $$\mathcal {O}(\log _d\log n)$$O(logdlogn) is asymptomatically tight. Furthermore, we show that with high probability, $$\mathbb {G}_{n,d}$$Gn,d is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can “take over” in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg [22].

A configuration is a point set on the plane, with no three points collinear. Given three non-collinear points p, q and $$r\in \mathbb {R}^2$$r∈R2, let $$\chi (p,q,r)\in \{-1,1\}$$χ(p,q,r)∈{-1,1}, with $$\chi (p,q,r)=1$$χ(p,q,r)=1 if and only if, when we traverse the circle defined by those points in the counterclockwise direction, we encounter the points in the cyclic order $$p,q,r,p,q,r,\dots $$p,q,r,p,q,r,⋯. For simplicity, extend $$\chi $$χ by setting $$\chi (p,q,r)=0$$χ(p,q,r)=0 if p, q and r are not pairwise distinct. Two configurations A and $$B\subset \mathbb {R}^2$$B⊂R2 are said to have the same order type if there is a bijection $$\iota :A\rightarrow B$$ι:A→B such that $$\chi (p,q,r)=\chi (\iota (p),\iota (q),\iota (r))$$χ(p,q,r)=χ(ι(p),ι(q),ι(r)) for all $$(p,q,r)\in A^3$$(p,q,r)∈A3. We say that a configuration C contains a copy of a configuration A if there is $$B\subset C$$B⊂C with A and B of the same order type. Given a configuration F, let $$\mathrm{Forb}(F)$$Forb(F) be the set of configurations that do not contain a copy of F. The distance between two configurations A and B with $$|A|=|B|=n$$|A|=|B|=n is given by$$\begin{aligned} \mathrm{dist}(A,B) = \min _\iota \frac{1}{2n^3}\sum _{(p,q,r)\in A^3} |\chi (p,q,r)-\chi (\iota (p),\iota (q),\iota (r))|, \end{aligned}$$dist(A,B)=minι12n3∑(p,q,r)∈A3|χ(p,q,r)-χ(ι(p),ι(q),ι(r))|,where the minimum is taken over all bijections $$\iota :A\rightarrow B$$ι:A→B. Roughly speaking, we prove the following property testing result: being free of a given configuration is efficiently testable. Our result also holds in the general case of hereditary properties$$\mathcal {P}=\mathrm{Forb}(\mathcal {F})$$P=Forb(F), defined by possibly infinite families $$\mathcal {F}$$F of forbidden configurations. Our results complement previous results by Czumaj, Sohler and Ziegler and others, in that we use a different notion of distance between configurations. Our proofs are heavily inspired on recent work of Fox and Wei on testing permutations and also make use of the regularity lemma for semi-algebraic hypergraphs of Fox, Pach and Suk. An extremal function involving order types, which may be of independent interest, plays an important rôle in our arguments.

We study two problems concerning the maximal and convex layers of a point set in d dimensions. The first is the average-case complexity of computing the first k layers of a point set drawn from a uniform or component-independent (CI) distribution. We show that, for $$d \in \{2,3\}$$d∈{2,3}, the first $$n^{1/d-\epsilon }$$n1/d-ϵ maximal layers can be computed using $$dn + o(n)$$dn+o(n) scalar comparisons with high probability. For $$d \ge 4$$d≥4, the first $$n^{1/2d-\epsilon }$$n1/2d-ϵ maximal layers can be computed within this bound with high probability. The first $$n^{1/d-\epsilon }$$n1/d-ϵ convex layers in 2D, the first $$n^{1/2d-\epsilon }$$n1/2d-ϵ convex layers in 3D, and the first $$n^{1/(d^2+2)}$$n1/(d2+2) convex layers in $$d \ge 4$$d≥4 dimensions can be computed using $$2dn + o(n)$$2dn+o(n) scalar comparisons with high probability. Since the expected number of maximal layers in 2D is $$2\sqrt{n}$$2n, our result for 2D maximal layers shows that it takes $$dn + o(n)$$dn+o(n) scalar comparisons to compute a $$1/n^\epsilon $$1/nϵ-fraction of all layers in the average case. The second problem is bounding the expected size of the kth maximal and convex layer. We show that the kth maximal and convex layer of a point set drawn from a continuous CI distribution in d dimensions has expected size $$O(k^d \log ^{d-1} (n/k^d))$$O(kdlogd-1(n/kd)).

We study the design of schedules for multi-commodity multicast. In this problem, we are given an undirected graph G and a collection of source-destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. The primary communication constraint of the multi-commodity multicast model is the number of connections that a given node can make, not link bandwidth. Multi-commodity multicast and its special cases, (single-commodity) broadcast and multicast, are all NP-complete. Multi-commodity multicast is closely related to the problem of finding a subgraph of optimal poise, where the poise is defined as the sum of the maximum degree and the maximum distance between any source-destination pair. We show that for any instance of the multicast problem, the minimum poise subgraph can be approximated to within a factor of $$O(\log k)$$O(logk) with respect to the value of a natural LP relaxation in a graph with k source-destination pairs. This is the first upper bound on the integrality gap of the natural LP; all previous algorithms yielded approximations with respect to the integer optimum. Using this integrality gap upper bound and shortest-path separators in planar graphs, we obtain our main result: an $$O(\log ^3 k \frac{\log n}{\log \log n})$$O(log3klognloglogn)-approximation for multi-commodity multicast for planar graphs which improves on the $$2^{\widetilde{O}(\sqrt{\log n})}$$2O~(logn)-approximation for general graphs.We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors and only nodes with a single broadcasting neighbor get a non-interfered message. In earlier work Iglesias et al. (FSTTCS 2015), we showed a strong $$\varOmega (n^{\frac{1}{2} - \epsilon })$$Ω(n12-ϵ)-hardness of approximation for computing a minimum gossip schedule in general graphs. Using our techniques for the telephone model, we give an $$O(\log ^2 n)$$O(log2n)-approximation for radio gossip in planar graphs breaking this barrier. Moreover, this is the first bound for radio gossip given that doesn’t rely on the maximum degree of the graph.

A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ($$\mathbf {src}(G)$$src(G)) of the graph. When proving upper bounds on $$\mathbf {src}(G)$$src(G), it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number ($$\mathbf {vsrc}(G)$$vsrc(G)).In this paper, we give upper bounds on $$\mathbf {vsrc}(G)$$vsrc(G) for several graph classes, some of which are tight. These immediately imply new upper bounds on $$\mathbf {src}(G)$$src(G) for these classes, showing that the study of $$\mathbf {vsrc}(G)$$vsrc(G) enables meaningful progress on bounding $$\mathbf {src}(G)$$src(G). Then we study the complexity of the problem to compute $$\mathbf {vsrc}(G)$$vsrc(G), particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that $$\mathbf {vsrc}(G)$$vsrc(G) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for $$\mathbf {src}(G)$$src(G). We also observe that deciding whether $$\mathbf {vsrc}(G) = k$$vsrc(G)=k is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether $$\mathbf {vsrc}(G) \le 3$$vsrc(G)≤3 nor to approximate $$\mathbf {vsrc}(G)$$vsrc(G) within a factor $$n^{1-\varepsilon }$$n1-ε, unless $$\text {P}=\text {NP}$$P=NP.

The vertex coloring problem asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two neighbors have different colors. The problem is NP-hard. Here, we introduce new integer linear programming formulations based on partial-ordering. They have the advantage that they are as simple to work with as the classical assignment formulation, since they can be fed directly into a standard integer linear programming solver. We evaluate our new models using Gurobi and show that our new simple approach is a good alternative to the best state-of-the-art approaches for the vertex coloring problem. In our computational experiments, we compare our formulations with the classical assignment formulation and the representatives formulation on a large set of benchmark graphs as well as randomly generated graphs of varying size and density. The evaluation shows that the partial-ordering based models dominate both formulations for sparse graphs, while the representatives formulation is the best for dense graphs.

We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation that the knapsack capacity is not given explicitly and can be accessed only through an oracle that answers whether or not the current solution is feasible when an item is added to the solution. Assuming that cancellation of an item is allowed when it overflows the knapsack capacity, we discuss the robustness ratios of adaptive policies for this problem, which are the worst case ratios of the objective values achieved by the output solutions to the optimal objective values. We present a randomized policy of robustness ratio $$(1-1/e)/2$$(1-1/e)/2, and a deterministic policy of robustness ratio $$2(1-1/e)/21$$2(1-1/e)/21. We also consider a universal policy that chooses items following a precomputed sequence. We present a randomized universal policy of robustness ratio $$(1-1/\root 4 \of {e})/2$$(1-1/e4)/2. When the cancellation is not allowed, no randomized adaptive policy achieves a constant robustness ratio. Because of this hardness, we assume that a probability distribution of the knapsack capacity is given, and consider computing a sequence of items that maximizes the expected objective value. We present a polynomial-time randomized algorithm of approximation ratio $$(1-1/\root 4 \of {e})/4-\epsilon $$(1-1/e4)/4-ϵ for any small constant $$\epsilon >0$$ϵ>0.

In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. [10] and Garg et al. [8], who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms—one for the simpler problem of scheduling without release times, and another for the minimum unscheduled weight problem—to create an online algorithm with provably good competitive ratios.We illustrate multiple applications of this method that yield improved competitive ratios. Our framework gives algorithms with the best or only-known competitive ratios for the concurrent open shop, coflow, and concurrent cluster models. We also introduce a randomized variant of our framework based on the ideas of Chakrabarti et al. [3] and use it to achieve improved competitive ratios for these same problems.

Suppose we have an arrangement $$\mathcal {A}$$A of n geometric objects $$x_1, \dots , x_n \subseteq \mathbb {R}^2$$x1,⋯,xn⊆R2 in the plane, with a distinguished point $$p_i$$pi in each object $$x_i$$xi. The generalized transmission graph of $$\mathcal {A}$$A has vertex set $$\{x_1, \dots , x_n\}$${x1,⋯,xn} and a directed edge $$x_ix_j$$xixj if and only if $$p_j \in x_i$$pj∈xi. Generalized transmission graphs provide a generalized model of the connectivity in networks of directional antennas.The complexity class $$\exists \mathbb {R}$$∃R contains all problems that can be reduced in polynomial time to an existential sentence of the form $$\exists x_1, \dots , x_n: \phi (x_1,\dots , x_n)$$∃x1,⋯,xn:ϕ(x1,⋯,xn), where $$x_1,\dots , x_n$$x1,⋯,xn range over $$\mathbb {R}$$R and $$\phi $$ϕ is a propositional formula with signature $$(+, -, \cdot , 0, 1)$$(+,-,·,0,1). The class $$\exists \mathbb {R}$$∃R aims to capture the complexity of the existential theory of the reals. It lies between $$\mathbf {NP}$$NP and $$\mathbf {PSPACE}$$PSPACE.Many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, are complete for $$\exists \mathbb {R}$$∃R. Continuing this line of research, we show that the recognition problem of generalized transmission graphs of line segments and of circular sectors is hard for $$\exists \mathbb {R}$$∃R. As far as we know, this constitutes the first such result for a class of directed graphs.

We prove a tight lower bound on the asymptotic performance ratio $$\rho $$ρ of the bounded space onlined-hypercube bin packing problem, solving an open question raised in 2005. In the classic d-hypercube bin packing problem, we are given a sequence of d-dimensional hypercubes and we have an unlimited number of bins, each of which is a d-dimensional unit hypercube. The goal is to pack (orthogonally) the given hypercubes into the minimum possible number of bins, in such a way that no two hypercubes in the same bin overlap. The bounded space online d-hypercube bin packing problem is a variant of the d-hypercube bin packing problem, in which the hypercubes arrive online and each one must be packed in an open bin without the knowledge of the next hypercubes. Moreover, at each moment, only a constant number of open bins are allowed (whenever a new bin is used, it is considered open, and it remains so until it is considered closed, in which case, it is not allowed to accept new hypercubes). Epstein and van Stee (SIAM J Comput 35(2):431–448, 2005) showed that $$\rho $$ρ is $$\varOmega (\log d)$$Ω(logd) and $$O(d/\log d)$$O(d/logd), and conjectured that it is $$\varTheta (\log d)$$Θ(logd). We show that $$\rho $$ρ is in fact $$\varTheta (d/\log d)$$Θ(d/logd). To obtain this result, we elaborate on some ideas presented by those authors, and go one step further showing how to obtain better (offline) packings of certain special instances for which one knows how many bins any bounded space algorithm has to use. Our main contribution establishes the existence of such packings, for large enough d, using probabilistic arguments. Such packings also lead to lower bounds for the prices of anarchy of the selfish d-hypercube bin packing game. We present a lower bound of $$\varOmega (d/\log d)$$Ω(d/logd) for the pure price of anarchy of this game, and we also give a lower bound of $$\varOmega (\log d)$$Ω(logd) for its strong price of anarchy.

In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that Cycle Packing is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with $$\mathcal {O}(2^{\mathcal {O}(t \log t)} n^{\mathcal {O}(1)})$$O(2O(tlogt)nO(1)) running time. Several structural parameterizations for Cycle Packing have been studied in the literature and our FPT algorithm fills a gap in the ecology of such parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm.

We study the problem of satisfying seating preferences on a circle. We assume we are given a collection of n agents to be arranged on a circle. Each agent is colored either blue or red, and there are exactly b blue agents and r red agents. The w-neighborhood of an agent A is the sequence of $$2w+1$$2w+1 agents at distance $$\le $$≤$$w$$w from A in the clockwise circular ordering. Agents have preferences for the colors of other agents in their w-neighborhood. We consider three ways in which agents can express their preferences: each agent can specify (1) a preference list: the sequence of colors of agents in the neighborhood, (2) a preference type: the exact number of neighbors of its own color in its neighborhood, or (3) a preference threshold: the minimum number of agents of its own color in its neighborhood. Our main result is that satisfying seating preferences is fixed-parameter tractable (FPT) with respect to parameter w for preference types and thresholds, while it can be solved in O(n) time for preference lists. For some cases of preference types and thresholds, we give O(n) algorithms whose running time is independent of w.

In this paper we consider the Two-dimensional Knapsack for Circles problem, in which we are given a set $${\mathcal {C}}$$C of circles and want to pack a subset $${\mathcal {C}}' \subseteq {\mathcal {C}}$$C′⊆C of them into a rectangular bin of dimensions w and h such that the sum of the area of circles in $${\mathcal {C}}'$$C′ is maximum. By packing we mean that the circles do not overlap and they are fully contained inside the bin. We present a polynomial-time approximation scheme that, for any $$\epsilon > 0$$ϵ>0, gives an approximation algorithm that packs a subset of the input circles into an augmented bin of dimensions w and $$(1+O(\epsilon ))h$$(1+O(ϵ))h such that the area packed is at least $$(1-O(\epsilon ))$$(1-O(ϵ)) times the area packed by an optimal solution into the regular bin of dimensions w and h. This result also extends to the multiple knapsack version of this problem.

In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job $$J_i$$Ji arriving at time $$r_i$$ri has an associated function $$p_i(t)$$pi(t) which is the profit obtained for finishing job $$J_i$$Ji at time $$t+r_i$$t+ri. Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.

We consider data structures for graphs where we maintain a subset of the nodes called sites, and allow proximity queries, such as asking for the closest site to a query node, and update operations that enable or disable nodes as sites. We refer to a data structure that can efficiently react to such updates as reactive. We present novel reactive proximity data structures for graphs of polynomial expansion, i.e., the class of graphs with small separators, such as planar graphs and road networks. Our data structures can be used directly in several logistical problems and geographic information systems dealing with real-time data, such as emergency dispatching. We experimentally compare our data structure to Dijkstra’s algorithm in a system emulating random queries in a real road network.

The Moran process, as studied by Lieberman et al. [10], is a stochastic process modeling the spread of genetic mutations in populations. In this process, agents of a two-type population (i.e. mutants and residents) are associated with the vertices of a graph. Initially, only one vertex chosen uniformly at random (u.a.r.) is a mutant, with fitness $$r > 0$$r>0, while all other individuals are residents, with fitness 1. In every step, an individual is chosen with probability proportional to its fitness, and its state (mutant or resident) is passed on to a neighbor which is chosen u.a.r. In this paper, we introduce and study for the first time a generalization of the model of [10] by assuming that different types of individuals perceive the population through different graphs defined on the same vertex set, namely $$G_R = (V, E_R)$$GR=(V,ER) for residents and $$G_M = (V, E_M)$$GM=(V,EM) for mutants. In this model, we study the fixation probability, namely the probability that eventually only mutants remain in the population, for various pairs of graphs.In particular, in the first part of the paper, we examine how known results from the original single-graph model of [10] can be transferred to our 2-graph model. In that direction, by using a Markov chain abstraction, we provide a generalization of the Isothermal Theorem of [10], that gives sufficient conditions for a pair of graphs to have fixation probability equal to the fixation probability of a pair of cliques; this corresponds to the absorption probability of a birth-death process with forward bias r.In the second part of the paper, we give a 2-player strategic game view of the process where player payoffs correspond to fixation and/or extinction probabilities. In this setting, we attempt to identify best responses for each player. We give evidence that the clique is the most beneficial graph for both players, by proving bounds on the fixation probability when one of the two graphs is complete and the other graph belongs to various natural graph classes.In the final part of the paper, we examine the possibility of efficient approximation of the fixation probability. Interestingly, we show that there is a pair of graphs for which the fixation probability is exponentially small. This implies that the fixation probability in the general case of an arbitrary pair of graphs cannot be approximated via a method similar to [2]. Nevertheless, we prove that, in the special case when the mutant graph is complete, an efficient approximation of the fixation probability is possible through an FPRAS which we describe.

We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms.In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.

In this paper, we study a biased version of the nearest-neighbor transposition Markov chain on the set of permutations where neighboring elements i and j are placed in order (i, j) with probability $$p_{i,j}$$pi,j. Our goal is to identify the class of parameter sets $$\mathbf{P} = \{p_{i,j}\}$$P={pi,j} for which this Markov chain is rapidly mixing. Specifically, we consider the open conjecture of Jim Fill that all monotone, positively biased distributions are rapidly mixing.We resolve Fill’s conjecture in the affirmative for distributions arising from k-class particle processes, where the elements are divided into k classes and the probability of exchanging neighboring elements depends on the particular classes the elements are in. We further require that k is a constant, and all probabilities between elements in different classes are bounded away from 1/2. These particle processes arise in the context of self-organizing lists and our result also applies beyond permutations to the setting where all particles in a class are indistinguishable. Our work generalizes recent work by Haddadan and Winkler (STACS ’17) studying 3-class particle processes. Additionally we show that a broader class of distributions based on trees is also rapidly mixing, which generalizes a class analyzed by Bhakta et al. (SODA ’13).Our proof involves analyzing a generalized biased exclusion process, which is a nearest-neighbor transposition chain applied to a 2-particle system. Biased exclusion processes are of independent interest, with applications in self-assembly. We generalize the results of Greenberg et al. (SODA ’09) and Benjamini et al. (Trans. AMS ’05) on biased exclusion processes to allow the probability of swapping neighboring elements to depend on the entire system, as long as the minimum bias is bounded away from 1.

The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and geometric graphs. For the latter, several variants have been studied (e.g., edge slides and edge rotations). In a transition graph on the set $$\mathcal {T}(S)$$T(S) of noncrossing straight-line spanning trees on a finite point set S in the plane, two spanning trees are connected by an edge if one can be transformed into the other by such an operation. We study bounds on the diameter of these graphs, and consider the various operations both on general point sets and sets in convex position. In addition, we address the problem variant where operations may be performed simultaneously. We prove new lower and upper bounds for the diameters of the corresponding transition graphs and pose open problems.

The Continued Logarithm Algorithm –CL for short– introduced by Gosper in 1978 computes the gcd of two integers; it seems very efficient, as it only performs shifts and subtractions. Shallit has studied its worst-case complexity in 2016 and showed it to be linear. We here perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values. Our “dynamical” analysis involves the dynamical system underlying the algorithm, that produces continued fraction expansions whose quotients are powers of 2. Even though this CL system has already been studied by Chan (around 2005), the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying the CL system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the CL algorithm, with explicit constants (Thanks to the Dyna3S ANR Project and the AleaEnAmsud AmSud-STIC Project.).

The known proofs of $$\textsf {MA}\subseteq \textsf {PP}$$ MA⊆PP incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $${\textsf {MA}\text {-}\textsf {TIME}(t)\not \subseteq \textsf {P}\text {-}\textsf {TIME}(o(t^2))}$$ MA-TIME(t)⊈P-TIME(o(t2)). We also show that 2-sided-error Merlin–Arthur games can be simulated by 1-sided-error Arthur–Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika Göös) that there is an oracle relative to which $$\textsf {MA}\not \subseteq \textsf {NP}^\textsf {BPP}$$ MA⊈NPBPP (which was previously known to hold by a proof using generics).

Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #P-complete to compute exactly by Valiant (1979), and a fully polynomial randomized approximation scheme (FPRAS) was presented by Jerrum, Sinclair, and Vigoda (2004) using a Markov chain Monte Carlo (MCMC) approach. However, it has remained an open question whether there exists an FPRAS for counting perfect matchings in general graphs. In fact, it was unresolved whether the same Markov chain defined by JSV is rapidly mixing in general. In this paper, we show that it is not. We prove torpid mixing for any weighting scheme on hole patterns in the JSV chain. As a first step toward overcoming this obstacle, we introduce a new algorithm for counting matchings based on the Gallai−Edmonds decomposition of a graph, and give an FPRAS for counting matchings in graphs that are sufficiently close to bipartite. In particular, we obtain a fixed-parameter tractable algorithm for counting matchings in general graphs, parameterized by the greatest “order” of a factor-critical subgraph.