ALBERT

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the 〈span〉 〈span〉\(\ell _p\)〈/span〉 〈/span〉-norm of the vector of loads of the machines, and each case allows the possibility of job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously-studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme was known into an EPTAS.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The parameterised complexity of various consensus string problems (〈span〉Closest String〈/span〉, 〈span〉Closest Substring〈/span〉, 〈span〉Closest String with Outliers〈/span〉) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance 〈em〉and〈/em〉 a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of 〈span〉Closest String〈/span〉 and 〈span〉Closest Substring〈/span〉, and partly for 〈span〉Closest String with Outliers〈/span〉; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(P \subset \mathbb {R}^d\)〈/span〉 〈/span〉 be a set of 〈em〉n〈/em〉 points in 〈em〉d〈/em〉 dimensions such that each point 〈span〉 〈span〉\(p \in P\)〈/span〉 〈/span〉 has an 〈em〉associated radius〈/em〉〈span〉 〈span〉\(r_p 〉 0\)〈/span〉 〈/span〉. The 〈em〉transmission graph〈/em〉〈em〉G〈/em〉 for 〈em〉P〈/em〉 is the directed graph with vertex set 〈em〉P〈/em〉 such that there is an edge from 〈em〉p〈/em〉 to 〈em〉q〈/em〉 if and only if 〈span〉 〈span〉\(|pq| \le r_p\)〈/span〉 〈/span〉, for any 〈span〉 〈span〉\(p, q \in P\)〈/span〉 〈/span〉. A 〈em〉reachability oracle〈/em〉 is a data structure that decides for any two vertices 〈span〉 〈span〉\(p, q \in G\)〈/span〉 〈/span〉 whether 〈em〉G〈/em〉 has a path from 〈em〉p〈/em〉 to 〈em〉q〈/em〉. The quality of the oracle is measured by the space requirement 〈em〉S〈/em〉(〈em〉n〈/em〉), the query time 〈em〉Q〈/em〉(〈em〉n〈/em〉), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 time an oracle with 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉. For planar point sets, the ratio 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉 between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉: the first works only for 〈span〉 〈span〉\(\Psi 〈 \sqrt{3}\)〈/span〉 〈/span〉 and achieves 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉 and preprocessing time 〈span〉 〈span〉\(O(n\log n)\)〈/span〉 〈/span〉; the second data structure gives 〈span〉 〈span〉\(Q(n) = O(\Psi ^3 \sqrt{n})\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(\Psi ^3 n^{3/2})\)〈/span〉 〈/span〉; the third data structure is randomized with 〈span〉 〈span〉\(Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and answers queries correctly with high probability.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the construction of the 〈em〉suffix tree〈/em〉 and the 〈em〉directed acyclic word graph〈/em〉 (〈em〉DAWG〈/em〉) indexing data structures for a collection 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 of texts, where a new symbol may be appended to any text in 〈span〉 〈span〉\(\mathcal {T} = \{T_1, \ldots , T_K\}\)〈/span〉 〈/span〉, 〈em〉at any time〈/em〉. This 〈em〉fully-online〈/em〉 scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved 〈em〉semi-online〈/em〉 text indexing problem, where texts 〈span〉 〈span〉\(T_1, \ldots , T_{k}\)〈/span〉 〈/span〉 are permanently fixed before the next text 〈span〉 〈span〉\(T_{k+1}\)〈/span〉 〈/span〉 is processed for each 〈em〉k〈/em〉 (〈span〉 〈span〉\(1 \le k 〈 K\)〈/span〉 〈/span〉). We first show that a direct application of Weiner’s right-to-left online construction for the suffix tree of a single text to fully-online multiple texts requires superlinear time. This also means that Blumer et al.’s left-to-right online construction for the DAWG of a single text requires superlinear time in the fully-online setting. We then present our fully-online versions of these algorithms that run in 〈span〉 〈span〉\(O(N \log \sigma )\)〈/span〉 〈/span〉 time and 〈em〉O〈/em〉(〈em〉N〈/em〉) space, where 〈em〉N〈/em〉 is the total length of the texts in 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉 is their alphabet size. We then show how to extend Ukkonen’s left-to-right online suffix tree construction to fully-online multiple strings, with the aid of Weiner’s suffix tree for the reversed texts. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉〈em〉Stochastic dominance〈/em〉 is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. When there is a uniform distribution over the request sequences, this technique reduces to 〈em〉bijective analysis〈/em〉. These methods have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have often provided a clear separation between algorithms whose performance varies significantly in practice. Despite their appealing properties, the above techniques are quite stringent, in that a relation between online algorithms may be either too difficult to establish analytically, or worse, may not even exist. In this paper, we propose remedies to these shortcomings. Our objective is to make all online algorithms amenable to the techniques of stochastic dominance and bijective analysis. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the 〈em〉bijective ratio〈/em〉 as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This makes it possible to compare two arbitrary online algorithms for an arbitrary online problem. In addition, the bijective ratio is a generalization of the Max/Max ratio (due to Ben-David and Borodin), and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous 〈em〉k〈/em〉-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of 〈em〉O〈/em〉(〈em〉k〈/em〉) across these metrics.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this article, 〈em〉q〈/em〉-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail:〈/p〉 〈ul〉 〈li〉 〈p〉sequences defined as the sum of outputs written by a transducer when reading a 〈em〉q〈/em〉-ary expansion of the input;〈/p〉 〈/li〉 〈li〉 〈p〉the amount of esthetic numbers in the first 〈em〉N〈/em〉 natural numbers; and〈/p〉 〈/li〉 〈li〉 〈p〉the number of odd entries in the rows of Pascal’s rhombus.〈/p〉 〈/li〉 〈/ul〉 For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known.

Description: 〈h3〉Abstract〈/h3〉 〈p〉For any integer 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉, a 〈em〉middle levels Gray code〈/em〉 is a cyclic listing of all 〈em〉n〈/em〉-element and 〈span〉 〈span〉\((n+1)\)〈/span〉 〈/span〉-element subsets of 〈span〉 〈span〉\(\{1,2,\ldots ,2n+1\}\)〈/span〉 〈/span〉 such that any two consecutive sets differ in adding or removing a single element. The question whether such a Gray code exists for any 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. 〈em〉Proc. London Math. Soc.〈/em〉, 112(4):677–713, 2016]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. 〈em〉ACM Trans. Algorithms〈/em〉, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉 on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time 〈span〉 〈span〉\({{\mathcal {O}}}(1)\)〈/span〉 〈/span〉 on average, and the required space is 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉〈span〉QuickXsort〈/span〉 is a highly efficient in-place sequential sorting scheme that mixes Hoare’s 〈span〉Quicksort〈/span〉 algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like 〈span〉Heapsort〈/span〉, 〈span〉Insertionsort〈/span〉 and 〈span〉Mergesort〈/span〉. Its major advantage is that 〈span〉QuickXsort〈/span〉 can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of 〈span〉QuickXsort〈/span〉 in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of 〈span〉QuickXsort〈/span〉 and X differ only by 〈em〉o〈/em〉(〈em〉n〈/em〉)-terms. For median-of-〈em〉k〈/em〉 pivot selection for some constant 〈em〉k〈/em〉, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three 〈span〉QuickMergesort〈/span〉 uses at most 〈span〉 〈span〉\(n \lg n - 0.8358n + {\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to 〈span〉 〈span〉\(n \lg n - 1.4112n + o(n)\)〈/span〉 〈/span〉 for a remaining gap of only 0.0315〈em〉n〈/em〉 comparisons to the known lower bound (while using only 〈span〉 〈span〉\({\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 additional space and 〈span〉 〈span〉\({\mathcal {O}}(n\log n)\)〈/span〉 〈/span〉 time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s 〈span〉Introsort〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In a recent breakthrough paper Braverman et al. (in: STOC’13, pp 151–160, 〈span〉2013〈/span〉) developed a local characterization for the zero-error information complexity in the two-party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain natural distributions. Our proof has new components, and in particular, it fixes a minor gap in the proof of Braverman et al.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping 〈span〉 〈span〉\(f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m\)〈/span〉 〈/span〉 such that for any vector 〈span〉 〈span〉\(x \in {\mathbb {R}}^n\)〈/span〉 〈/span〉, 〈em〉f〈/em〉 preserves its norm to within 〈span〉 〈span〉\((1 {\pm } \varepsilon )\)〈/span〉 〈/span〉 with probability 〈span〉 〈span〉\(1 - \delta \)〈/span〉 〈/span〉 if 〈span〉 〈span〉\(m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉. Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions has an embedding time of 〈span〉 〈span〉\({\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))\)〈/span〉 〈/span〉. An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random 〈span〉 〈span〉\(m \times n\)〈/span〉 〈/span〉 Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in 〈span〉 〈span〉\({\mathcal {O}}(n \lg m)\)〈/span〉 〈/span〉 time. The big question is of course whether 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring 〈span〉 〈span〉\(m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 for the Toeplitz approach to work.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider a two-way trading problem, where investors buy and sell a stock whose price moves within a certain range. Naturally they want to maximize their profit. Investors can perform up to 〈em〉k〈/em〉 trades, where each trade must involve the full amount. We give optimal algorithms for three different models which differ in the knowledge of how the price fluctuates. In the first model, there are global minimum and maximum bounds 〈em〉m〈/em〉 and 〈em〉M〈/em〉. We first show an optimal lower bound of 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 (where 〈span〉 〈span〉\(\varphi =M/m\)〈/span〉 〈/span〉) on the competitive ratio for one trade, which is the bound achieved by trivial algorithms. Perhaps surprisingly, when we consider more than one trade, we can give a better algorithm that loses only a factor of 〈span〉 〈span〉\(\varphi ^{2/3}\)〈/span〉 〈/span〉 (rather than 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉) per additional trade. Specifically, for 〈em〉k〈/em〉 trades the algorithm has competitive ratio 〈span〉 〈span〉\(\varphi ^{(2k+1)/3}\)〈/span〉 〈/span〉. Furthermore we show that this ratio is the best possible by giving a matching lower bound. In the second model, 〈em〉m〈/em〉 and 〈em〉M〈/em〉 are not known in advance, and just 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 is known. We show that this only costs us an extra factor of 〈span〉 〈span〉\(\varphi ^{1/3}\)〈/span〉 〈/span〉, i.e., both upper and lower bounds become 〈span〉 〈span〉\(\varphi ^{(2k+2)/3}\)〈/span〉 〈/span〉. Finally, we consider the bounded daily return model where instead of a global limit, the fluctuation from one day to the next is bounded, and again we give optimal algorithms, and interestingly one of them resembles common trading strategies that involve stop loss limits.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A splittable good provided in 〈em〉n〈/em〉 pieces shall be divided as evenly as possible among 〈em〉m〈/em〉 agents, where every agent can take shares from at most 〈em〉F〈/em〉 pieces. We call 〈em〉F〈/em〉 the fragmentation and mainly restrict attention to the cases 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉. For 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉, the max–min and min–max problems are solvable in linear time. The case 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if 〈span〉 〈span〉\(m\ge n-1\)〈/span〉 〈/span〉, and a solution always exists in this case, in contrast to 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉. Moreover, the problem is fixed-parameter tractable in the parameter 〈span〉 〈span〉\(2m-n\)〈/span〉 〈/span〉. (Note that this parameter measures the number of agents above the trivial threshold 〈span〉 〈span〉\(m=n/2\)〈/span〉 〈/span〉.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 to this averaging problem, and some approximation results in cases when 〈em〉m〈/em〉 is close to either 〈em〉n〈/em〉 or 〈em〉n〈/em〉 / 2.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We introduce a compressed suffix array representation that, on a text 〈em〉T〈/em〉 of length 〈em〉n〈/em〉 over an alphabet of size 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉, can be built in 〈em〉O〈/em〉(〈em〉n〈/em〉) deterministic time, within 〈span〉 〈span〉\(O(n\log \sigma )\)〈/span〉 〈/span〉 bits of working space, and counts the number of occurrences of any pattern 〈em〉P〈/em〉 in 〈em〉T〈/em〉 in time 〈span〉 〈span〉\(O(|P| + \log \log _w \sigma )\)〈/span〉 〈/span〉 on a RAM machine of 〈span〉 〈span〉\(w=\Omega (\log n)\)〈/span〉 〈/span〉-bit words. This time is almost optimal for large alphabets (〈span〉 〈span〉\(\log \sigma =\Theta (\log n)\)〈/span〉 〈/span〉), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require 〈span〉 〈span〉\(\Theta (n\log n)\)〈/span〉 〈/span〉 bits. For smaller alphabets, where 〈span〉 〈span〉\(\log \sigma = o(\log n)\)〈/span〉 〈/span〉, we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time 〈span〉 〈span〉\(O(|P|/\log _\sigma n + \log _\sigma ^\epsilon n)\)〈/span〉 〈/span〉 for any constant 〈span〉 〈span〉\(\epsilon 〉0\)〈/span〉 〈/span〉. This is almost RAM-optimal in the typical case where 〈span〉 〈span〉\(w=\Theta (\log n)\)〈/span〉 〈/span〉. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(n=|V|\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(m=|E|\)〈/span〉 〈/span〉, and an integer value 〈span〉 〈span〉\(k\ge 1\)〈/span〉 〈/span〉, there is an algorithm that computes in 〈span〉 〈span〉\(O(2^{k}n\log ^2 n)\)〈/span〉 〈/span〉 time for any set 〈em〉F〈/em〉 of size at most 〈em〉k〈/em〉 the strongly connected components of the graph 〈span〉 〈span〉\(G{\setminus }F\)〈/span〉 〈/span〉. The running time of our algorithm is almost optimal since the time for outputting the SCCs of 〈span〉 〈span〉\(G{\setminus } F\)〈/span〉 〈/span〉 is at least 〈span〉 〈span〉\(\varOmega (n)\)〈/span〉 〈/span〉. The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size 〈span〉 〈span〉\(O(2^{k} n^2)\)〈/span〉 〈/span〉. Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan (J Comput Syst Sci 26:362–391, 〈span〉1983〈/span〉) and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study popular matchings in the many-to-many matching problem, which is given by a graph 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 and, for every agent 〈span〉 〈span〉\(u\in V\)〈/span〉 〈/span〉, a capacity 〈span〉 〈span〉\(\textsf {cap}(u) \ge 1\)〈/span〉 〈/span〉 and a preference list strictly ranking her neighbors. A matching in 〈em〉G〈/em〉 is popular if it weakly beats every matching in a majority vote when agents cast votes for one matching versus the other according to their preferences. First, we show that when 〈span〉 〈span〉\(G = (A\cup B,E)\)〈/span〉 〈/span〉 is bipartite, e.g., when matching students to courses, every pairwise stable matching is popular. In particular, popular matchings are guaranteed to exist. Our main contribution is to show that a max-size popular matching in 〈em〉G〈/em〉 can be computed in linear time by the 〈em〉2-level Gale–Shapley〈/em〉 algorithm, which is an extension of the classical Gale–Shapley algorithm. We prove its correctness via linear programming. Second, we consider the problem of computing a max-size popular matching in 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 (not necessarily bipartite) when every agent has capacity 1, e.g., when matching students to dorm rooms. We show that even when 〈em〉G〈/em〉 admits a stable matching, this problem is 〈span〉 〈span〉\(\mathsf {NP}\)〈/span〉 〈/span〉-hard, which is in contrast to the tractability result in bipartite graphs.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from 〈em〉K〈/em〉 different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of 〈em〉O〈/em〉(〈em〉K〈/em〉), and for the connected version, we get the first LP-based bound of 〈em〉O〈/em〉(1).〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph 〈em〉G〈/em〉 with 〈em〉m〈/em〉 edges and 〈em〉n〈/em〉 vertices, this takes 〈span〉 〈span〉\({\tilde{O}}(\log ^2 n)\)〈/span〉 〈/span〉 time and 〈span〉 〈span〉\((m + n) n^{o(1)}\)〈/span〉 〈/span〉 processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188–1207, 〈span〉1997〈/span〉) for maximum acyclic subgraph and Gale–Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619–626, 〈span〉2002〈/span〉). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson–Lindenstrauss Lemma.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(\mathcal {P}(G,X)\)〈/span〉 〈/span〉 be a property associating a boolean value to each pair (〈em〉G〈/em〉, 〈em〉X〈/em〉) where 〈em〉G〈/em〉 is a graph and 〈em〉X〈/em〉 is a vertex subset. Assume that 〈span〉 〈span〉\(\mathcal {P}\)〈/span〉 〈/span〉 is expressible in counting monadic second order logic (CMSO) and let 〈em〉t〈/em〉 be an integer constant. We consider the following optimization problem: given an input graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉, find subsets 〈span〉 〈span〉\(X\subseteq F \subseteq V\)〈/span〉 〈/span〉 such that the treewidth of 〈em〉G〈/em〉[〈em〉F〈/em〉] is at most 〈em〉t〈/em〉, property 〈span〉 〈span〉\(\mathcal {P}(G[F],X)\)〈/span〉 〈/span〉 is true and 〈em〉X〈/em〉 is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., 〈span〉Longest Induced Path〈/span〉, 〈span〉Maximum Induced Forest〈/span〉, 〈span〉Independent〈/span〉〈span〉 〈span〉\(\mathcal {H}\)〈/span〉 〈/span〉-〈span〉Packing〈/span〉, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 〈span〉2015〈/span〉) proved that the problem is polynomial on the class of graph 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉, i.e. the graphs having at most 〈span〉 〈span〉\({\text {poly}}(n)\)〈/span〉 〈/span〉 minimal separators for some polynomial 〈span〉 〈span〉\({\text {poly}}\)〈/span〉 〈/span〉. Here we consider the class 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, formed by graphs of 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉 to which we add a set of at most 〈em〉k〈/em〉 vertices with arbitrary adjacencies, called 〈em〉modulator〈/em〉. We prove that the generic optimization problem is fixed parameter tractable on 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, with parameter 〈em〉k〈/em〉, if the modulator is also part of the input.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is 〈span〉NP〈/span〉-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. There are both polynomial-time solvable and 〈span〉NP〈/span〉-complete results in this direction, depending on 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. We present a general framework for the problem if 〈span〉 〈span〉\(\mathcal{H}\)〈/span〉 〈/span〉 is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of outerplanar graphs and 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of graphs of pathwidth at most 2.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments. Our main result is Dynamic Space Efficient Cuckoo Table (DySECT ) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is counterbalanced by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with loads up to 98%. With up to 1.9 times better performance than the next best solution. Additionally, we give a tight theoretical analysis for the possible load threshold of DySECT, i.e., a bound where with high probability the table can be filled up to that load but not above said load. This load also matches our experimental findings.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈em〉P〈/em〉 be a finite set of points in the plane and 〈em〉S〈/em〉 a set of non-crossing line segments with endpoints in 〈em〉P〈/em〉. The visibility graph of 〈em〉P〈/em〉 with respect to 〈em〉S〈/em〉, denoted 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉, has vertex set 〈em〉P〈/em〉 and an edge for each pair of vertices 〈em〉u〈/em〉, 〈em〉v〈/em〉 in 〈em〉P〈/em〉 for which no line segment of 〈em〉S〈/em〉 properly intersects 〈em〉uv〈/em〉. We show that the constrained half-〈span〉 〈span〉\(\theta _6\)〈/span〉 〈/span〉-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉. We then show how to construct a plane 6-spanner of 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉 with maximum degree 〈span〉 〈span〉\(6+c\)〈/span〉 〈/span〉, where 〈em〉c〈/em〉 is the maximum number of segments of 〈em〉S〈/em〉 incident to a vertex.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A directed multigraph is said 〈em〉vulnerable〈/em〉 if it can generate 〈em〉Braess paradox〈/em〉 in traffic networks. In this paper, we give a graph–theoretic characterisation of vulnerable directed multigraphs. Analogous results appeared in the literature only for undirected multigraphs and for a specific family of directed multigraphs. The proof of our characterisation provides the first polynomial time algorithm that checks if a general directed multigraph is vulnerable in 〈span〉 〈span〉\(\mathcal{O}(|V| \cdot |E|^2)\)〈/span〉 〈/span〉. Our algorithm also contributes to the directed subgraph homeomorphism problem without node mapping, by providing another pattern graph for which a polynomial time algorithm exists.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any 〈span〉 〈span〉\(d〉0\)〈/span〉 〈/span〉, the first algorithm maintains a proper 〈span〉 〈span〉\(O(\mathcal {C} dN ^{1/d})\)〈/span〉 〈/span〉-coloring while recoloring at most 〈em〉O〈/em〉(〈em〉d〈/em〉) vertices per update, where 〈span〉 〈span〉\(\mathcal {C} \)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(N \)〈/span〉 〈/span〉 are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an 〈span〉 〈span〉\(O(\mathcal {C} d)\)〈/span〉 〈/span〉-coloring with 〈span〉 〈span〉\(O(dN ^{1/d})\)〈/span〉 〈/span〉 recolorings per update. The two converge when 〈span〉 〈span〉\(d = \log N \)〈/span〉 〈/span〉, maintaining an 〈span〉 〈span〉\(O(\mathcal {C} \log N)\)〈/span〉 〈/span〉-coloring with 〈span〉 〈span〉\(O(\log N)\)〈/span〉 〈/span〉 recolorings per update. We also present a lower bound, showing that any algorithm that maintains a 〈em〉c〈/em〉-coloring of a 2-colorable graph on 〈span〉 〈span〉\(N \)〈/span〉 〈/span〉 vertices must recolor at least 〈span〉 〈span〉\(\varOmega (N ^\frac{2}{c(c-1)})\)〈/span〉 〈/span〉 vertices per update, for any constant 〈span〉 〈span〉\(c \ge 2\)〈/span〉 〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we study the NP-complete 〈em〉colorful〈/em〉 variant of the classical 〈span〉Matching〈/span〉 problem, namely, the 〈span〉Rainbow Matching〈/span〉 problem. Given an edge-colored graph 〈em〉G〈/em〉 and a positive integer 〈em〉k〈/em〉, this problem asks whether there exists a matching of size at least 〈em〉k〈/em〉 such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves 〈span〉Rainbow Matching〈/span〉 on paths in time 〈span〉 〈span〉\(\mathcal{O}^\star \left( \left( \frac{1+\sqrt{5}}{2}\right) ^k\right) \)〈/span〉 〈/span〉 and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a “divide-and-conquer-like” approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures “divided-and-conquered” pieces of the path. Our second result is a randomized algorithm that solves 〈span〉Rainbow Matching〈/span〉 on general graphs in time 〈span〉 〈span〉\(\mathcal {O} ^\star (2^k)\)〈/span〉 〈/span〉 and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 〈span〉2017〈/span〉) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for 〈span〉Rainbow Matching〈/span〉 on general and bounded-degree graphs.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among 〈em〉n〈/em〉 players to meet these conditions: (I) every player (weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the allocation is dominant strategy-proof (truthful) (III) the number of cuts made on the cake is small. We provide methods for dividing the cake under different assumptions on the valuation functions of the players. First, we suppose that the valuation function of every player is a single interval with a special property, namely 〈em〉ordering property〈/em〉. For this case, we propose a process called 〈em〉expansion process〈/em〉 and show that it results in an envy-free and truthful allocation that cuts the cake into exactly 〈em〉n〈/em〉 pieces. Next, we remove the ordering restriction and show that for this case, an extended form of the expansion process, called 〈em〉expansion process with unlocking〈/em〉 yields an envy-free allocation of the cake with at most 〈span〉 〈span〉\(2(n-1)\)〈/span〉 〈/span〉 cuts. Furthermore, we show that in the 〈em〉expansion process with unlocking〈/em〉, the players may misrepresent their valuations to earn more share. In addition, we use a more complex form of the 〈em〉expansion process with unlocking〈/em〉 to obtain an envy-free and truthful allocation that cuts the cake in at most 〈span〉 〈span〉\(2(n-1)\)〈/span〉 〈/span〉 locations. We also, evaluate our expansion method in practice. In the empirical results, we compare the number of cuts made by our method to the number of cuts in the optimal solution (〈span〉 〈span〉\(n-1\)〈/span〉 〈/span〉). The experiments reveal that the number of cuts made by the expansion and unlocking process for envy-free division of the cake is very close to the optimal solution. Finally, we study piecewise constant and piecewise uniform valuation functions with 〈em〉m〈/em〉 pieces and present the conditions, under which a generalized form of expansion process can allocate the cake via 〈em〉O〈/em〉(〈em〉nm〈/em〉) cuts.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, we develop a general two-stage framework which consists of efficiently solving a problem-specific number problem and transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while 〈em〉f〈/em〉-factor computations as used in the undirected case seem not to work for the directed case.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we discuss the design and analysis of polynomial time algorithms for two problems associated with a linearly infeasible system of Unit Two Variable Per Inequality (UTVPI) constraints, viz., (a) the read-once refutation (ROR) problem, and (b) the literal-once refutation (LOR) problem. Recall that a UTVPI constraint is a linear relationship of the form: 〈span〉 〈span〉\(a_{i}\cdot x_{i}+a_{j} \cdot x_{j} \le b_{ij}\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(a_{i},a_{j} \in \{0,1,-1\}\)〈/span〉 〈/span〉. A conjunction of such constraints is called a UTVPI constraint system (UCS) and can be represented in matrix form as: 〈span〉 〈span〉\(\mathbf{A \cdot x \le b}\)〈/span〉 〈/span〉. These constraints find applications in a host of domains including but not limited to operations research and program verification. For the linear system 〈span〉 〈span〉\(\mathbf{A\cdot x \le b}\)〈/span〉 〈/span〉, a refutation is a collection of 〈em〉m〈/em〉 variables 〈span〉 〈span〉\(\mathbf{y}=[y_{1},y_{2},\ldots , y_{m}]^{T} \in \mathfrak {R}^{m}_{+}\)〈/span〉 〈/span〉, such that 〈span〉 〈span〉\(\mathbf{y\cdot A =0}\)〈/span〉 〈/span〉, 〈span〉 〈span〉\(\mathbf{y \cdot b } 〈 0\)〈/span〉 〈/span〉. Such a refutation is guaranteed to exist for any infeasible linear program, as per Farkas’ lemma. The refutation is said to be read-once, if each 〈span〉 〈span〉\(y_{i} \in \{0,1\}\)〈/span〉 〈/span〉. Read-once refutations are 〈strong〉incomplete〈/strong〉 in that their existence is not guaranteed for infeasible linear programs, in general. Indeed they are not complete, even for UCSs. Hence, the question of whether an arbitrary UCS has an ROR is both interesting and non-trivial. In this paper, we reduce this problem to the problem of computing a minimum weight perfect matching (MWPM) in an undirected graph. This transformation results in an algorithm that runs in in time polynomial in the size of the input UCS. Additionally, we design a polynomial time algorithm (also via a reduction to the MWPM problem) for a variant of read-once resolution called literal-once resolution. The advantage of reducing our problems to the MWPM problem is that we can leverage recent advances in algorithm design for the MWPM problem towards solving the ROR and LOR problems in UCSs. Finally, we show that another variant of read-once refutation problem called the non-literal read-once refutation (NLROR) problem is 〈strong〉NP-complete〈/strong〉 in UCSs.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The classic 〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 problem asks if a graph 〈em〉G〈/em〉, with vertex-set 〈em〉V〈/em〉(〈em〉G〈/em〉), has a simple cycle containing all vertices of a given set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉. In terms of colored graphs, it can be rephrased as follows: Given a graph 〈em〉G〈/em〉, a set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉 and an injective coloring 〈span〉 〈span〉\(c: K\rightarrow \{1,2,\ldots ,|K|\}\)〈/span〉 〈/span〉, decide if 〈em〉G〈/em〉 has a simple cycle containing each color in 〈span〉 〈span〉\(\{1,2,\ldots ,|K|\}\)〈/span〉 〈/span〉 exactly once. Another problem widely known since the introduction of color coding is 〈span〉Colorful Cycle〈/span〉. Given a graph 〈em〉G〈/em〉 and a coloring 〈span〉 〈span〉\(c: V(G)\rightarrow \{1,2,\ldots ,k\}\)〈/span〉 〈/span〉 for some 〈span〉 〈span〉\(k\in \mathbb {N}\)〈/span〉 〈/span〉, it asks if 〈em〉G〈/em〉 has a simple cycle of length 〈em〉k〈/em〉 containing each color in 〈span〉 〈span〉\(\{1,2,\ldots ,k\}\)〈/span〉 〈/span〉 exactly once. We study a generalization of these problems: Given a graph 〈em〉G〈/em〉, a set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉, a list-coloring 〈span〉 〈span〉\(L: K\rightarrow 2^{\{1,2,\ldots ,k^*\}}\)〈/span〉 〈/span〉 for some 〈span〉 〈span〉\(k^*\in \mathbb {N}\)〈/span〉 〈/span〉 and a parameter 〈span〉 〈span〉\(k\in \mathbb {N}\)〈/span〉 〈/span〉, 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 asks if one can assign a color to each vertex in 〈em〉K〈/em〉 so that 〈em〉G〈/em〉 has a simple cycle (of arbitrary length) containing exactly 〈em〉k〈/em〉 vertices from 〈em〉K〈/em〉 with distinct colors. We design a randomized algorithm for 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 running in time 〈span〉 〈span〉\(2^kn^{{{\mathcal {O}}}(1)}\)〈/span〉 〈/span〉 on an 〈em〉n〈/em〉-vertex graph, matching the best known running times of algorithms for both 〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 and 〈span〉Colorful Cycle〈/span〉. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 that generalizes the classic 〈span〉Hamiltonicity〈/span〉 problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA’12), Björklund, Kaski and Kowalik (STACS’13), and Björklund (FOCS’10).〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the 〈em〉k〈/em〉-〈span〉Center〈/span〉 problem and some generalizations. For 〈em〉k〈/em〉-〈span〉Center〈/span〉 a set of 〈em〉k〈/em〉〈em〉center vertices〈/em〉 needs to be found in a graph 〈em〉G〈/em〉 with edge lengths, such that the distance from any vertex of 〈em〉G〈/em〉 to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded 〈em〉highway dimension〈/em〉, as proposed by Abraham et al. (SODA, pp 782–793, 〈span〉2010〈/span〉). We show both approximation and fixed-parameter hardness results, and how to overcome them using 〈em〉fixed-parameter approximations〈/em〉, where the two paradigms are combined. In particular, we prove that for any 〈span〉 〈span〉\({\varepsilon }〉0\)〈/span〉 〈/span〉 computing a 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximation is W[2]-hard for parameter 〈em〉k〈/em〉, and NP-hard for graphs with highway dimension 〈span〉 〈span〉\(O(\log ^2 n)\)〈/span〉 〈/span〉. The latter does not rule out fixed-parameter 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximations for the highway dimension parameter 〈em〉h〈/em〉, but implies that such an algorithm must have at least doubly exponential running time in 〈em〉h〈/em〉 if it exists, unless ETH fails. On the positive side, we show how to get below the approximation factor of 2 by combining the parameters 〈em〉k〈/em〉 and 〈em〉h〈/em〉: we develop a fixed-parameter 3 / 2-approximation with running time 〈span〉 〈span〉\(2^{O(kh\log h)}\cdot n^{O(1)}\)〈/span〉 〈/span〉. Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximations for only the parameter 〈em〉h〈/em〉. We also provide similar fixed-parameter approximations for the 〈span〉weighted〈/span〉〈em〉k〈/em〉-〈span〉Center〈/span〉 and 〈span〉 〈span〉\((k,{\mathcal {F}})\)〈/span〉 〈/span〉-〈span〉Partition〈/span〉 problems, which generalize 〈em〉k〈/em〉-〈span〉Center〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Given a read-only memory for input and a write-only stream for output, an 〈em〉s〈/em〉-workspace algorithm, for a positive integer parameter 〈em〉s〈/em〉, is an algorithm using only 〈em〉O〈/em〉(〈em〉s〈/em〉) words of workspace in addition to the memory for the input. In this paper, we present an 〈span〉 〈span〉\(O(n^2/s)\)〈/span〉 〈/span〉-time 〈em〉s〈/em〉-workspace algorithm for subdividing a simple 〈em〉n〈/em〉-gon into 〈span〉 〈span〉\(O(\min \{n/s,s\})\)〈/span〉 〈/span〉 subpolygons of complexity 〈span〉 〈span〉\(O(\max \{n/s,s\})\)〈/span〉 〈/span〉. As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately by adopting the proposed subdivision: (1) computing the shortest path between two points inside a simple 〈em〉n〈/em〉-gon, (2) computing the shortest-path tree from a point inside a simple 〈em〉n〈/em〉-gon, (3) computing a triangulation of a simple 〈em〉n〈/em〉-gon. In addition, we improve the algorithm for problem (2) further by applying different approaches depending on the size of the workspace.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We present space-efficient algorithms for computing cut vertices in a given graph with 〈em〉n〈/em〉 vertices and 〈em〉m〈/em〉 edges in linear time using 〈span〉 〈span〉\(O(n+\min \{m,n\log \log n\})\)〈/span〉 〈/span〉 bits. With the same time and using 〈span〉 〈span〉\(O(n+m)\)〈/span〉 〈/span〉 bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in 〈span〉 〈span〉\(O(n\log \log n)\)〈/span〉 〈/span〉 time using 〈em〉O〈/em〉(〈em〉n〈/em〉) bits.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players’ payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing 〈em〉approximate well supported Nash equilibria (WSNE)〈/em〉 that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of 〈em〉approximate Nash equilibria〈/em〉, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The paper considers scheduling jobs online to minimize the objective 〈span〉 〈span〉\(\sum _{i \in [n]}w_ig(C_i-r_i)\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(w_i\)〈/span〉 〈/span〉 is the weight of job 〈em〉i〈/em〉, 〈span〉 〈span〉\(r_i\)〈/span〉 〈/span〉 is its release time, 〈span〉 〈span〉\(C_i\)〈/span〉 〈/span〉 is its completion time and 〈em〉g〈/em〉 is any non-decreasing convex function. It is known that the clairvoyant algorithm Highest-Density-First (HDF) is 〈span〉 〈span〉\((2+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive for this objective on a single machine for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉 (Im et al., in: ACM-SIAM symposium on discrete algorithms, pp 1254–1265, 〈span〉2012〈/span〉). In this paper, we give the first non-trivial results for this problem when 〈em〉g〈/em〉 is a non-decreasing convex function and the algorithm must be 〈em〉non-clairvoyant〈/em〉. More specifically, our results include:〈/p〉 〈ul〉 〈li〉 〈p〉A 〈span〉 〈span〉\((2+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive non-clairovyant algorithm on a single machine for all non-decreasing convex 〈em〉g〈/em〉, matching the performance of HDF for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉.〈/p〉 〈/li〉 〈li〉 〈p〉A 〈span〉 〈span〉\((3+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive non-clairovyant algorithm on multiple identical machines for all non-decreasing convex 〈em〉g〈/em〉 for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉.〈/p〉 〈/li〉 〈/ul〉 The paper gives the first non-trivial upper-bound on multiple machines even if the algorithm is allowed to be clairvoyant. All performance guarantees above hold for all non-decreasing convex functions 〈em〉g〈/em〉〈em〉simultaneously〈/em〉. The positive results are supplemented by almost matching lower bounds. We show that any algorithm that is oblivious to 〈em〉g〈/em〉 is not 〈em〉O〈/em〉(1)-competitive with speed augmentation less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function 〈em〉g〈/em〉 cannot be 〈em〉O〈/em〉(1)-competitive with speed augmentation less than 〈span〉 〈span〉\(\sqrt{2}\)〈/span〉 〈/span〉 on a single machine or  〈span〉 〈span〉\((2-\frac{1}{m})\)〈/span〉 〈/span〉 on 〈em〉m〈/em〉 identical machines.

Description: 〈h3〉Abstract〈/h3〉 〈p〉Given a vertex-weighted connected graph 〈span〉 〈span〉\(G = (V, E)\)〈/span〉 〈/span〉, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree 〈em〉T〈/em〉 of 〈em〉G〈/em〉 such that the total weight of internal vertices in 〈em〉T〈/em〉 is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of 〈span〉 〈span〉\(1/3 - \epsilon \)〈/span〉 〈/span〉, for any 〈span〉 〈span〉\(\epsilon 〉 0\)〈/span〉 〈/span〉. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(B=(X,Y,E)\)〈/span〉 〈/span〉 be a bipartite graph. A half-square of 〈em〉B〈/em〉 has one color class of 〈em〉B〈/em〉 as vertex set, say 〈em〉X〈/em〉; two vertices are adjacent whenever they have a common neighbor in 〈em〉Y〈/em〉. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC ’98, pp 514–523. 〈span〉https://doi.org/10.1145/276698.276865〈/span〉, 〈span〉1998〈/span〉; J ACM 49(2):127–138. 〈span〉https://doi.org/10.1145/506147.506148〈/span〉, 〈span〉2002〈/span〉), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup’s 〈span〉 〈span〉\(O(n^{120})\)〈/span〉 〈/span〉-time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. 〈span〉https://doi.org/10.1109/SFCS.1998.743490〈/span〉, 〈span〉1998〈/span〉). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉It is well known that any set of 〈em〉n〈/em〉 intervals in 〈span〉 〈span〉\(\mathbb {R} ^1\)〈/span〉 〈/span〉 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the subspace proximity problem: Given a vector 〈span〉 〈span〉\({\varvec{x}} \in {\mathbb {R}}^n\)〈/span〉 〈/span〉 and a basis matrix 〈span〉 〈span〉\(V \in {\mathbb {R}}^{n \times m}\)〈/span〉 〈/span〉, the objective is to determine whether 〈span〉 〈span〉\({\varvec{x}}\)〈/span〉 〈/span〉 is close to the subspace spanned by 〈em〉V〈/em〉. Although the problem is solvable by linear programming, it is time consuming especially when 〈em〉n〈/em〉 is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time 〈em〉independent〈/em〉 of 〈em〉n〈/em〉 and can be used as a sieve before computing the exact distance between 〈span〉 〈span〉\({\varvec{x}}\)〈/span〉 〈/span〉 and the subspace. The number of coordinates of 〈span〉 〈span〉\({\varvec{x}}\)〈/span〉 〈/span〉 queried by our tester is 〈span〉 〈span〉\(O(\frac{m}{\epsilon }\log \frac{m}{\epsilon })\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(\epsilon \)〈/span〉 〈/span〉 is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this article we develop a 〈em〉vectorial kernel method〈/em〉—a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a 〈em〉pattern〈/em〉), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks/bridges/meanders/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. 〈em〉En passant〈/em〉, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern 〈em〉p〈/em〉), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of 〈em〉Borges’s theorem〈/em〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We investigate the problem of computing the number of linear extensions of a given 〈em〉n〈/em〉-element poset whose cover graph has treewidth 〈em〉t〈/em〉. We present an algorithm that runs in time 〈span〉 〈span〉\({\tilde{O}}(n^{t+3})\)〈/span〉 〈/span〉 for any constant 〈em〉t〈/em〉; the notation 〈span〉 〈span〉\({\tilde{O}}\)〈/span〉 〈/span〉 hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters 〈em〉n〈/em〉 and 〈em〉t〈/em〉 alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In 1969, Roberts introduced 〈em〉proper〈/em〉 and 〈em〉unit interval graphs〈/em〉 and proved that these classes are equal. Natural generalizations of unit interval graphs called 〈em〉k〈/em〉〈em〉-length interval graphs〈/em〉 were considered in which the number of different lengths of intervals is limited by 〈em〉k〈/em〉. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for 〈span〉 〈span〉\(k=2\)〈/span〉 〈/span〉. We propose generalizations of proper interval graphs called 〈em〉k〈/em〉〈em〉-nested interval graphs〈/em〉 in which there are no chains of 〈span〉 〈span〉\(k+1\)〈/span〉 〈/span〉 intervals nested in each other. It is easy to see that 〈em〉k〈/em〉-nested interval graphs are a superclass of 〈em〉k〈/em〉-length interval graphs. We give a linear-time recognition algorithm for 〈em〉k〈/em〉-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is 〈span〉FPT〈/span〉 with respect to the nesting 〈em〉k〈/em〉 and the length of the formula, while the problem is 〈span〉W[2]〈/span〉-hard when parameterized just by the length of the formula. We show that a generalization of recognition called 〈em〉partial representation extension〈/em〉 is 〈span〉NP〈/span〉-hard for 〈em〉k〈/em〉-length interval graphs, even when 〈span〉 〈span〉\(k=2\)〈/span〉 〈/span〉, while Klavík et al. show that it is polynomial-time solvable for 〈em〉k〈/em〉-nested interval graphs.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this work we consider 〈em〉temporal networks〈/em〉, i.e. networks defined by a 〈em〉labeling〈/em〉〈span〉 〈span〉\(\lambda \)〈/span〉 〈/span〉 assigning to each edge of an 〈em〉underlying graph〈/em〉〈em〉G〈/em〉 a set of 〈em〉discrete〈/em〉 time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on 〈em〉path problems〈/em〉 of temporal networks. In particular, we consider 〈em〉time-respecting〈/em〉 paths, i.e. paths whose edges are assigned by 〈span〉 〈span〉\(\lambda \)〈/span〉 〈/span〉 a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a 〈em〉natural analogue of Menger’s theorem〈/em〉 holding for arbitrary temporal networks. Finally, we propose two 〈em〉cost minimization parameters〈/em〉 for temporal network design. One is the 〈em〉temporality〈/em〉 of 〈em〉G〈/em〉, in which the goal is to minimize the maximum number of labels of an edge, and the other is the 〈em〉temporal cost〈/em〉 of 〈em〉G〈/em〉, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some 〈em〉connectivity constraint〈/em〉. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth. We use these two types of layouts to characterize leveled planar graphs, which are the graphs with planar leveled drawings with no dummy vertices. It follows from the known NP-completeness of leveled planarity that track-number and layered pathwidth are also NP-complete, even for the smallest constant parameter values that make these parameters nontrivial. We prove that the graphs with bounded layered pathwidth include outerplanar graphs, Halin graphs, and squaregraphs, but that (despite having bounded track-number) series–parallel graphs do not have bounded layered pathwidth. Finally, we investigate the parameterized complexity of these layouts, showing that past methods used for book layouts do not work to parameterize the problem by treewidth or almost-tree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The FM index (Ferragina and Manzini in J ACM 52(4):552–581, 〈span〉2005〈/span〉) is a widely-used compressed data structure that stores a string 〈em〉T〈/em〉 in a compressed form and also supports fast pattern matching queries. In this paper, we describe new FM-index variants that combine nice theoretical properties, simple implementation and improved practical performance. Our main theoretical result is a new technique called 〈em〉fixed block compression boosting〈/em〉, which is a simpler and faster alternative to optimal compression boosting and implicit compression boosting used in previous FM-indexes. We also describe several new techniques for implementing fixed-block boosting efficiently, including a new, fast, and space-efficient implementation of wavelet trees. Our extensive experiments show the new indexes to be consistently fast and small relative to the state-of-the-art, and thus they make a good “off-the-shelf” choice for many applications.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / 〈em〉K〈/em〉 in the so-called compact Genetic Algorithm (cGA) and the evaporation factor 〈span〉 〈span〉\(\rho \)〈/span〉 〈/span〉 in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of 〈span〉 〈span〉\({\varOmega }(K\sqrt{n} + n \log n)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\({\varOmega }(\sqrt{n}/\rho + n \log n)\)〈/span〉 〈/span〉, respectively, suggesting that the update strength should be limited to 〈span〉 〈span〉\(1/K, \rho = O(1/(\sqrt{n} \log n))\)〈/span〉 〈/span〉. In fact, choosing 〈span〉 〈span〉\(1/K, \rho \sim 1/(\sqrt{n}\log n)\)〈/span〉 〈/span〉 both algorithms efficiently optimize OneMax in expected time 〈span〉 〈span〉\({\varTheta }(n \log n)\)〈/span〉 〈/span〉. Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the 〈span〉 〈span〉\(\#\hbox {P}\)〈/span〉 〈/span〉-complete problem of counting the number of linear extensions of a poset 〈span〉 〈span〉\((\textsc {\#LE})\)〈/span〉 〈/span〉; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of 〈span〉 〈span〉\(\textsc {\#LE}\)〈/span〉 〈/span〉 parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that 〈span〉 〈span〉\(\textsc {\#LE}\)〈/span〉 〈/span〉 is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Algorithms. On the positive side we show that 〈span〉 〈span〉\({\textsc {\#LE}}\)〈/span〉 〈/span〉 becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the 〈em〉existence〈/em〉 of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them 〈em〉constructive〈/em〉 kernels with reasonably low 〈em〉explicit〈/em〉 constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of 〈em〉vertices〈/em〉. In this article we enhance our framework to deal with 〈em〉packing〈/em〉 problems, that is, problems whose solutions can be certified by collections of 〈em〉subgraphs〈/em〉 of the input graph satisfying certain properties. 〈span〉 〈span〉\({\mathcal F}\)〈/span〉 〈/span〉-〈span〉Packing〈/span〉 is a typical example: for a family 〈span〉 〈span〉\({\mathcal F}\)〈/span〉 〈/span〉 of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph 〈em〉G〈/em〉 contains 〈em〉k〈/em〉 vertex-disjoint subgraphs such that each of them contains a graph in 〈span〉 〈span〉\({{\mathcal {F}}}\)〈/span〉 〈/span〉 as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of 〈span〉 〈span〉\({{\mathcal {F}}}\)〈/span〉 〈/span〉-〈span〉Packing〈/span〉: for an integer 〈span〉 〈span〉\(\ell \geqslant 1\)〈/span〉 〈/span〉, one aims at finding either minor-models that are pairwise at distance at least 〈span〉 〈span〉\(\ell \)〈/span〉 〈/span〉 in 〈em〉G〈/em〉 (〈span〉 〈span〉\(\ell \)〈/span〉 〈/span〉-〈span〉 〈span〉\(\mathcal {F}\)〈/span〉 〈/span〉〈span〉-Packing〈/span〉), or such that each vertex in 〈em〉G〈/em〉 belongs to at most 〈span〉 〈span〉\(\ell \)〈/span〉 〈/span〉 minors-models (〈span〉 〈span〉\(\mathcal {F}\)〈/span〉 〈/span〉〈span〉-Packing with〈/span〉〈span〉 〈span〉\(\ell \)〈/span〉 〈/span〉〈span〉-Membership〈/span〉). Finally, we also provide linear kernels for the versions of these problems where one wants to pack 〈em〉subgraphs〈/em〉 instead of minors.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The 〈span〉NP〈/span〉-complete problem 〈span〉Feedback Vertex Set〈/span〉 is that of deciding whether or not it is possible, for a given integer 〈span〉 〈span〉\(k\ge 0\)〈/span〉 〈/span〉, to delete at most 〈em〉k〈/em〉 vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called 〈span〉Independent Feedback Vertex Set〈/span〉 and is also 〈span〉NP〈/span〉-complete. In fact, even deciding if an independent feedback vertex set exists is 〈span〉NP〈/span〉-complete and this problem is closely related to the 〈span〉3-Colouring〈/span〉 problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of 〈span〉Independent Feedback Vertex Set〈/span〉 for 〈em〉H〈/em〉-free graphs. We prove that it is 〈span〉NP〈/span〉-complete if 〈em〉H〈/em〉 contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for 〈span〉 〈span〉\(P_4\)〈/span〉 〈/span〉-free graphs. We show that it remains polynomial-time solvable for 〈span〉 〈span〉\(P_5\)〈/span〉 〈/span〉-free graphs. We prove analogous results for the 〈span〉Independent Odd Cycle Transversal〈/span〉 problem, which asks whether or not a graph has an independent odd cycle transversal of size at most 〈em〉k〈/em〉 for a given integer 〈span〉 〈span〉\(k\ge 0\)〈/span〉 〈/span〉. Finally, in line with our underlying research aim, we compare the complexity of 〈span〉Independent Feedback Vertex Set〈/span〉 for 〈em〉H〈/em〉-free graphs with the complexity of 〈span〉3-Colouring〈/span〉, 〈span〉Independent Odd Cycle Transversal〈/span〉 and other related problems.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A geometric graph is a graph whose vertices are points in the plane and whose edges are straight-line segments between the points. A plane spanning tree in a geometric graph is a spanning tree that is non-crossing. Let 〈em〉R〈/em〉 and 〈em〉B〈/em〉 be two disjoint sets of points in the plane such that 〈span〉 〈span〉\(R\cup B\)〈/span〉 〈/span〉 is in general position, and let 〈span〉 〈span〉\(n=|R\cup B|\)〈/span〉 〈/span〉. Assume that the points of 〈em〉R〈/em〉 are colored red and the points of 〈em〉B〈/em〉 are colored blue. A bichromatic plane spanning tree is a plane spanning tree in the complete bipartite geometric graph with bipartition (〈em〉R〈/em〉, 〈em〉B〈/em〉). In this paper we consider the maximum bichromatic plane spanning tree problem, which is the problem of computing a bichromatic plane spanning tree of maximum total edge length.〈/p〉 〈ol〉 〈li〉 〈p〉For the maximum bichromatic plane spanning tree problem, we present an approximation algorithm with ratio 1 / 4 that runs in 〈span〉 〈span〉\(O(n\log n)\)〈/span〉 〈/span〉 time.〈/p〉 〈/li〉 〈li〉 〈p〉We also consider the multicolored version of this problem where the input points are colored with 〈span〉 〈span〉\(k〉2\)〈/span〉 〈/span〉 colors. We present an approximation algorithm that computes a plane spanning tree in a complete 〈em〉k〈/em〉-partite geometric graph, and whose ratio is 1 / 6 if 〈span〉 〈span〉\(k=3\)〈/span〉 〈/span〉, and 1 / 8 if 〈span〉 〈span〉\(k\geqslant 4\)〈/span〉 〈/span〉.〈/p〉 〈/li〉 〈li〉 〈p〉We also revisit the special case of the problem where 〈span〉 〈span〉\(k=n\)〈/span〉 〈/span〉, i.e., the problem of computing a maximum plane spanning tree in a complete geometric graph. For this problem, we present an approximation algorithm with ratio 0.503; this is an extension of the algorithm presented by Dumitrescu and Tóth (Discrete Comput Geom 44(4):727–752, 〈span〉2010〈/span〉) whose ratio is 0.502.〈/p〉 〈/li〉 〈li〉 〈p〉For points that are in convex position, the maximum bichromatic plane spanning tree problem can be solved in 〈span〉 〈span〉\(O(n^3)\)〈/span〉 〈/span〉 time. We present an 〈span〉 〈span〉\(O(n^5)\)〈/span〉 〈/span〉-time algorithm that solves this problem for the case where the red points lie on a line and the blue points lie on one side of the line.〈/p〉 〈/li〉 〈/ol〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We introduce and study the 〈span〉Minimum Feasible Tileset〈/span〉 problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is 〈span〉 〈span〉\(\mathsf {APX}\)〈/span〉 〈/span〉-hard and that it is 〈span〉 〈span〉\(\mathsf {NP}\)〈/span〉 〈/span〉-hard even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the 〈span〉Minimum Feasible Tileset〈/span〉 problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Given a matroid 〈em〉M〈/em〉 defined by an independence oracle on a ground set 〈em〉E〈/em〉, the 〈em〉Matroid Base Game〈/em〉 is played by two players: the 〈em〉defender〈/em〉 chooses a basis 〈em〉B〈/em〉 and (simultaneously) the 〈em〉attacker〈/em〉 chooses an element 〈span〉 〈span〉\(e \in E\)〈/span〉 〈/span〉. The attacker incurs a cost 〈em〉c〈/em〉(〈em〉e〈/em〉) for choosing an element 〈em〉e〈/em〉, and if 〈span〉 〈span〉\(e \in B\)〈/span〉 〈/span〉 then there is a probability 〈em〉p〈/em〉(〈em〉e〈/em〉) that the attacker will detect the defender. The defender has to find a bases-selection strategy that minimizes the average probability of being detected. The attacker has to find a probabilistic selection strategy that maximizes the average detection probability minus its average cost. An algorithm to compute Nash-equilibrium mixed strategies was given in Szeszlér (Math Program 161:347–364, 〈span〉2016〈/span〉). Its time complexity is 〈span〉 〈span〉\(O(|E|^{10} IO)\)〈/span〉 〈/span〉, where 〈em〉IO〈/em〉 is the time that it takes one call to the independence oracle. Here we present an algorithm that requires 〈span〉 〈span〉\(O(|E|^6 IO)\)〈/span〉 〈/span〉 time. For graphic matroids, i.e., when the defender chooses a spanning tree in a graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉, and the attacker chooses an edge, we give an algorithm that takes 〈span〉 〈span〉\(O(|V|^4 |E|^{1/2})\)〈/span〉 〈/span〉 time. This type of game is extended to common bases of two matroids. For this case we give a strongly polynomial algorithm, settling a question that was left open in Szeszlér (〈span〉2016〈/span〉). We also treat the case when the defender chooses a rooted arborescence in a directed graph 〈span〉 〈span〉\(D=(V,\mathscr {A})\)〈/span〉 〈/span〉, and the attacker chooses an arc, we use this structure to give an algorithm that requires 〈span〉 〈span〉\(O(|V||\mathscr {A}|^3 \log (|V|^2/|\mathscr {A}|) \log |\mathscr {A}|)\)〈/span〉 〈/span〉 time.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter 〈span〉 〈span〉\({\epsilon }\in (0,1/2)\)〈/span〉 〈/span〉, a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it is 〈span〉 〈span〉\({\epsilon }\)〈/span〉 〈/span〉-far from satisfying the property. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only 〈span〉 〈span〉\(O({\epsilon }^{-1})\)〈/span〉 〈/span〉 samples. In contrast, we prove that convexity can be tested with 〈span〉 〈span〉\(O({\epsilon }^{-1})\)〈/span〉 〈/span〉 queries by testers that can make queries of their choice while uniform testers for this property require 〈span〉 〈span〉\(\varOmega ({\epsilon }^{-5/4})\)〈/span〉 〈/span〉 samples. Previously, the fastest known tester for convexity needed 〈span〉 〈span〉\(\varTheta ({\epsilon }^{-4/3})\)〈/span〉 〈/span〉 queries.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In the 〈span〉Edge Bipartization〈/span〉 problem one is given an undirected graph 〈em〉G〈/em〉 and an integer 〈em〉k〈/em〉, and the question is whether 〈em〉k〈/em〉 edges can be deleted from 〈em〉G〈/em〉 so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386–1396, 〈span〉2006〈/span〉) proposed an algorithm solving this problem in time 〈span〉 〈span〉\(\mathcal {O}(2^k\cdot {m}^2)\)〈/span〉 〈/span〉; today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for 〈span〉Edge Bipartization〈/span〉 that works in time 〈span〉 〈span〉\(\mathcal {O}(1.977^k\cdot {nm})\)〈/span〉 〈/span〉, which is the first algorithm with the running time dependence on the parameter better than 〈span〉 〈span〉\(2^k\)〈/span〉 〈/span〉. To this end, we combine the general iterative compression strategy of Guo et al.  (〈span〉2006〈/span〉), the technique proposed by Wahlström (in: Proceedings of SODA’14, SIAM, 〈span〉2014〈/span〉) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Data analysis typically involves 〈em〉error recovery〈/em〉 and 〈em〉detection of regularities〈/em〉 as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A common notion of regularity in strings is that of 〈em〉a cover〈/em〉. Data describing measures of a natural coverable phenomenon may be corrupted by errors caused by the measurement process, or by the inexact features of the phenomenon itself. Due to this reason, different variants of approximate covers have been introduced, some of which are 〈span〉 〈span〉\(\mathcal {NP}\)〈/span〉 〈/span〉-hard to compute. In this paper we assume that the Hamming distance metric measures the amount of corruption experienced, and study the problem of recovering the correct cover from data corrupted by mismatch errors, formally defined as the 〈em〉cover recovery problem (CRP)〈/em〉. We show that for the Hamming distance metric, coverability is a powerful property allowing 〈em〉detecting〈/em〉 the original cover and 〈em〉correcting〈/em〉 the data, under suitable conditions. We also study a relaxation of another problem, which is called the 〈em〉approximate cover problem (ACP)〈/em〉. Since the ACP is proved to be 〈span〉 〈span〉\(\mathcal {NP}\)〈/span〉 〈/span〉-hard (Amir et al. in: Approximate cover of strings. CPM, 〈span〉2017〈/span〉), we study a relaxation, which we call 〈em〉the candidate-relaxation of the ACP〈/em〉, and show it has a polynomial time complexity. As a result, we get that the ACP also has a polynomial time complexity in many practical situations. An important application of our ACP relaxation study is also a polynomial time algorithm for the CRP.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Digital watermarks have been regarded as a promising way to fight copyright violations in the software industry. In some graph-based watermarking schemes, identification data is disguised as control-flow graphs of dummy code. Recently, Chroni and Nikolopoulos proposed an ingenious such scheme whereby an integer is encoded into a particular kind of permutation graph. We give a formal characterization of the class of graphs generated by their encoding function, which we call canonical reducible permutation graphs. A linear-time recognition algorithm is also given, setting the basis for a polynomial-time algorithm to restore watermarks that underwent the malicious removal of some edges. Finally, we give a simpler decoding algorithm for Chroni and Nikolopoulos’ watermarks.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a 〈span〉 〈span〉\((1+\epsilon )\)〈/span〉 〈/span〉-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking down them into a small number of parametrized cases.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈em〉P〈/em〉 be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let 〈span〉 〈span〉\(s\in P\)〈/span〉 〈/span〉 be a given source node. Each node 〈em〉p〈/em〉 can transmit information to all other nodes within unit distance, provided 〈em〉p〈/em〉 is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source 〈em〉s〈/em〉 can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem—in the latter 〈em〉s〈/em〉 must be able to reach every node within a specified number of hops—where we also consider how the complexity depends on the width 〈em〉w〈/em〉 of the strip. We prove the following two lower bounds. First, we show that the regular version of the problem is 〈span〉 〈span〉\({\mathsf {W[1]}}\)〈/span〉 〈/span〉-complete when parameterized by the solution size 〈em〉k〈/em〉. More precisely, we show that the problem does not admit an algorithm with running time 〈span〉 〈span〉\(f(k)n^{o(\sqrt{k})}\)〈/span〉 〈/span〉, unless ETH fails. The construction can also be used to show an 〈span〉 〈span〉\(f(w)n^{\varOmega (w)}\)〈/span〉 〈/span〉 lower bound when we parameterize by the strip width 〈em〉w〈/em〉. Second, we prove that the hop-bounded version of the problem is NP-hard in strips of width 40. These results complement the algorithmic results in a companion paper (de Berg et al. in Algorithmica, submitted).〈/p〉

Description: 〈p〉The article, “Longest Common Substring with Approximately 〈em〉k〈/em〉 Mismatches”, written by Tomasz Kociumaka, Jakub Radoszewski and Tatiana Starikovskaya was originally published electronically on the publisher’s internet portal (currently SpringerLink) on February 16, 2019, as open access, with “© The Author(s)”; instead, it should be “© Springer Science+Business Media, LLC, part of Springer Nature 2018,” and the article is forthwith distributed under the terms of copyright.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we propose the rectangle transformation problem (RTP) and its variants. RTP asks for rectangle partitions on two rectangles of the same area which produce two identical sets of pieces. We are interested in the minimum RTP which requires to minimize the partition size. This initiates the algorithmic study of dissection problems in module number optimization, particularly in the category of rectangle partition. We mainly focus on the strict rectangle transformation problem (SRTP) in which rotation is not allowed during the transformation. It has been shown that SRTP has no finite solution if the ratio of the two parallel side lengths of input rectangles is irrational. So we turn to its complemental case, SRTP with integral input, denoted by SIRTP, in which case both side lengths are assumed integral. We give a polynomial time algorithm 〈span〉 〈span〉\(\text {ALGSIRTP}\)〈/span〉 〈/span〉 which gives a solution at most 〈span〉 〈span〉\(q/p+7\log _2 p\)〈/span〉 〈/span〉 to 〈span〉 〈span〉\(\text {SIRTP}(p,q)\)〈/span〉 〈/span〉 (〈span〉 〈span〉\(q\ge p\)〈/span〉 〈/span〉), where 〈em〉p〈/em〉 and 〈em〉q〈/em〉 are two integral side lengths of input rectangles 〈span〉 〈span〉\(p\times q\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(q\times p\)〈/span〉 〈/span〉. Note that 〈em〉q〈/em〉 / 〈em〉p〈/em〉 is an intrinsic lower bound for 〈span〉 〈span〉\(\text {SIRTP}(p,q)\)〈/span〉 〈/span〉. So 〈span〉 〈span〉\(\text {ALGSIRTP}\)〈/span〉 〈/span〉 is a 〈span〉 〈span〉\((7\log p)\)〈/span〉 〈/span〉-approximation algorithm for minimum 〈span〉 〈span〉\(\text {SIRTP}(p,q)\)〈/span〉 〈/span〉. On the other hand, we show that for any 〈span〉 〈span〉\(\varepsilon 〉0\)〈/span〉 〈/span〉 and any constant range 〈span〉 〈span〉\((1,1+\delta )\)〈/span〉 〈/span〉, there are integers 〈em〉p〈/em〉 and 〈em〉q〈/em〉 (〈span〉 〈span〉\(q〉p\)〈/span〉 〈/span〉) of ratio 〈em〉q〈/em〉 / 〈em〉p〈/em〉 in this range, such that there is no solution less than 〈span〉 〈span〉\(\max \{q/p,\log _2^{1-\varepsilon } q\}\)〈/span〉 〈/span〉 to 〈span〉 〈span〉\(\text {SIRTP}(p,q)\)〈/span〉 〈/span〉. This is an almost tight bound since the algorithm 〈span〉 〈span〉\(\text {ALGSIRTP}\)〈/span〉 〈/span〉 gives an upper bound 〈span〉 〈span〉\(7\log _2 p+O(1)\)〈/span〉 〈/span〉 in this case. We also raise a long series of open questions for further research along this line.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Online matching on a line involves matching an online stream of requests to a given set of servers, all in the real line, with the objective of minimizing the sum of the distances between matched server-request pairs. The best previously known upper and lower bounds on the optimal deterministic competitive ratio are linear in the number of requests, and constant, respectively. We show that online matching on a line is essentially equivalent to a particular search problem, which we call 〈em〉k〈/em〉〈em〉-lost-cows〈/em〉. We then obtain the first deterministic sub-linearly competitive algorithm for online matching on a line by giving such an algorithm for the 〈em〉k〈/em〉-lost-cows problem.〈/p〉

Description: It is well known that any set of n intervals in $$mathbb {R} ^1$$R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.

Description: We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of $$(2+varepsilon )$$(2+ε) and an amortized update time of $$O(log n/varepsilon ^2)$$O(logn/ε2). Our result can be generalized to give a fully dynamic $$O(f^3)$$O(f3)-approximate algorithm with $$O(f^2)$$O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.