Search

They give fixed parameter tractable algorithms for the problem parameterized by various structural parameters. The authors give a greedy loop-free algorithm for the exhaustive generation, a successor algorithm that runs in constant amortized time, among other algorithms, as well as results for the fixed spin generalization of this problem. IWOCA (International Workshop on Combinatorial Algorithms) is an annual conference series covering all aspects of combinatorial algorithms. [Extracted from the article]

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for k = 1 and NP-complete for k = 6 . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for k ≥ 3 , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar st-graphs, closes the question about the complexity of the kUBE problem for any k. Motivated by this hardness result, we then focus on the 2UBE Testing for planar st-graphs. On the algorithmic side, we present an O (f (β) · n + n 3) -time algorithm for 2UBE Testing, where β is the branchwidth of the input graph and f is a singly-exponential function on β . Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for st-graphs of bounded treewidth. Furthermore, we describe an O(n)-time algorithm to test whether a plane st-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input st-graph. On the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2 UBE. [ABSTRACT FROM AUTHOR]

In this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding a minimum secondary dominating set in trees is presented. [ABSTRACT FROM AUTHOR]

We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph G = (V , E) , a simple 2-matching is a subset M ⊆ E of edges such that each node in V is incident to at most two edges in M . Clearly, each such M decomposes into a node-disjoint collection of paths and circuits. M is called 1-restricted if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such M of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such M amounts to computing a (not necessarily 1-restricted) simple 2-matching M 0 of maximum cardinality and subsequently altering it into M of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes M 0 ) runs in O E V time, the second one (which turns M 0 into M ) requires O (V E) time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to O E V thus completely closing the gap between 1-restricted and unrestricted cases. [ABSTRACT FROM AUTHOR]

Refereed conferences require every submission to be reviewed by members of a program committee (PC) in charge of selecting the conference program. There are many software packages available to manage the review process. Typically, in a bidding phase PC members express their personal preferences by ranking the submissions. This information is used by the system to compute an assignment of the papers to referees (PC members). We study the problem of assigning papers to referees. We propose to optimize a number of criteria that aim at achieving fairness among referees/papers. Some of these variants can be solved optimally in polynomial time, while others are NP-hard, in which case we design approximation algorithms. Experimental results strongly suggest that the assignments computed by our algorithms are considerably better than those computed by popular conference management software. [ABSTRACT FROM AUTHOR]

Surrogate functions are often employed to reduce the number of objective function evaluations in a continuous optimization. However, their effects have seldom been investigated theoretically. This paper analyzes the effect of a surrogate function in the information-geometric optimization (IGO) framework, which includes as an algorithm instance a variant of the covariance matrix adaptation evolution strategy—a widely used solver for black-box continuous optimization. We derive a sufficient condition on the surrogate function for the parameter update in the IGO algorithms to point to a descent direction of the objective function expected over the search distribution. The condition is expressed in terms of three measures of correlation between the objective function and the surrogate function. Our result constitutes a partial justification for the use of a surrogate function in IGO algorithms. [ABSTRACT FROM AUTHOR]

A function f : V (G) → { 0 , 1 , 2 } is called a Roman dominating function on G = (V (G) , E (G)) if for every vertex v with f (v) = 0 , there exists a vertex u ∈ N G (v) such that f (u) = 2 . A function f : V (G) → { 0 , 1 , 2 } induces an ordered partition (V 0 , V 1 , V 2) of V(G), where V i = { v ∈ V (G) : f (v) = i } for i ∈ { 0 , 1 , 2 } . A function f : V (G) → { 0 , 1 , 2 } with ordered partition (V 0 , V 1 , V 2) is called a unique response Roman function if for every vertex v with f (v) = 0 , | N G (v) ∩ V 2 | ≤ 1 , and for every vertex v with f (v) = 1 or 2, | N G (v) ∩ V 2 | = 0 . A function f : V (G) → { 0 , 1 , 2 } is called a unique response Roman dominating function (URRDF) on G if it is a unique response Roman function as well as a Roman dominating function on G. The weight of a unique response Roman dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) , and the minimum weight of a unique response Roman dominating function on G is called the unique response Roman domination number of G and is denoted by u R (G) . Given a graph G, the Min-URRDF problem asks to find a unique response Roman dominating function of minimum weight on G. In this paper, we study the algorithmic aspects of Min-URRDF. We show that the decision version of Min-URRDF remains NP-complete for chordal graphs and bipartite graphs. We show that for a given graph with n vertices, Min-URRDF cannot be approximated within a ratio of n 1 - ε for any ε > 0 unless P = NP . We also show that Min-URRDF can be approximated within a factor of Δ + 1 for graphs having maximum degree Δ . On the positive side, we design a linear-time algorithm to solve Min-URRDF for distance-hereditary graphs. Also, we show that Min-URRDF is polynomial-time solvable for interval graphs, and strengthen the result by showing that Min-URRDF can be solved in linear-time for proper interval graphs, a proper subfamily of interval graphs. [ABSTRACT FROM AUTHOR]

Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form L x = b , where L is the Laplacian matrix of a weighted graph with weights w (i , j) > 0 on the edges. The solution x of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i, j) is 1/w(i, j). Kelner et al. (in: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp 911–920, 2013. https://doi.org/10.1145/2488608.2488724) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector–matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms (Henzinger et al., in: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pp 21–30, 2015. https://doi.org/10.1145/2746539.2746609). The conjecture implies that the data structure does not have an O (n 1 - ϵ) time algorithm for any ϵ > 0 , and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an O ~ (m 1.5) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O (m 1 + ϵ) for any ϵ > 0 . Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart. [ABSTRACT FROM AUTHOR]

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions. [ABSTRACT FROM AUTHOR]

Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynamic algorithms for the recognition of threshold graphs and chain graphs, which are optimal in the sense that the costs per modification are linear in the number of modified edges. Furthermore, our algorithms also consider the addition and deletion of sets of vertices as well as edges. In the negative case, i.e., where the graph is not a threshold graph or chain graph anymore, our algorithms return a certificate of constant size. Additionally, we present optimal fully dynamic algorithms for the Hamiltonian cycle problem and the Hamiltonian path problem on threshold and chain graphs which return a vertex cutset as certificate for the non-existence of such a path or cycle in the negative case. [ABSTRACT FROM AUTHOR]

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show Average-case Lower Bounds For every k = k (n) with k ⩾ log n , there exists a polynomial-time computable function f k on n bits such that, for every comparator circuit C with at most n 1.5 / O k · log n gates, we have Pr x ∈ 0 , 1 n C (x) = f k (x) ⩽ 1 2 + 1 2 Ω (k) . This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting k = O log n . # SAT Algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n 1.5 / O k · log n gates, in time 2 n - k · poly (n) , for any k ⩽ n / 4 . The running time is non-trivial (i.e., 2 n / n ω (1) ) when k = ω (log n) . Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s 2 / 3 + o (1) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n 1.5 - o (1) lower bound for MCSP against comparator circuits. [ABSTRACT FROM AUTHOR]

This paper is concerned with the 1 | | ∑ p j U j problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also an important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The best known running time follows from the famous Lawler and Moore algorithm that solves a more general weighted version in O (P · n) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for problem, each improving on Lawler and Moore's algorithm in a different scenario. Our first algorithm runs in O ~ (P 7 / 4) time, and outperforms Lawler and Moore's algorithm in instances where n = ω ~ (P 3 / 4) . Our second algorithm runs in O ~ (min { P · D # , P + D }) time, where D # is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore's algorithm when n = ω ~ (D #) or n = ω ~ (D / P) . Further, it extends the known O ~ (P) algorithm for the single due date special case of 1 | | ∑ p j U j in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, and can be easily extended to the case of a fixed number of machines. For the first algorithm we define a new "skewed" version of (max , min) -Convolution which is interesting in its own right. [ABSTRACT FROM AUTHOR]

The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp (Sorting Search 3:197–207, 1999) independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In their seminal papers, Stockmeyer and Yao (SIAM J Comput 9(1):85–90, 1980), Murphy and Paull (Inf Control 42(1):87–96, 1979), and Christen (On the optimality of the straight merging algorithm, 1978) independently showed when the lists to be merged are of size m and n satisfying m ≤ n ≤ ⌊ 3 2 m ⌋ + 1 , the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we use to prove the lower bound is Knuth's (1999) adversary methods. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. Moreover, we design a simple procedure, and by invoking this procedure recursively until the remaining subproblem can be solved efficiently by another known algorithm, we achieve constant improvement of the upper bound for 2 m - 2 ≤ n ≤ 3 m . [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the editor discusses several papers selected at the 20th Annual European Symposium on Algorithms (ESA) held in Ljubljana, Slovenia on September 10?12, 2012 on topics including algorithmic, use of hash functions, and induced graph matching.

A 2-dimensional lattice animal is a set of edge-connected cells on some lattice. In this paper, we address the problem of counting minimum-perimeter lattice animals, that is, animals that have the minimum possible perimeter of all animals of the same area. We provide two types of algorithms for counting minimum-perimeter animals on two lattices, namely, the square and hexagonal lattices, and analyze and compare the algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we study the following pattern search problem: Given a pair of point sets A and B in fixed dimensional space R d , with | B | = n , | A | = m and n ≥ m , the pattern search problem is to find the translations T 's of A such that each of the identified translations induces a matching between T (A) and a subset B ′ of B with cost no more than some given threshold, where the cost is defined as the minimum bipartite matching cost of T (A) and B ′ . We present a novel algorithm to produce a small set of candidate translations for the pattern search problem. For any B ′ ⊆ B with | B ′ | = | A | , there exists at least one translation T in the candidate set such that the minimum bipartite matching cost between T (A) and B ′ is no larger than (1 + ϵ) times the minimum bipartite matching cost between A and B ′ under any translation (i.e., the optimal translational matching cost). We also show that there exists an alternative solution to this problem, which constructs a candidate set of size O d , ϵ (n log 2 n) in O d , ϵ (n log 2 n) time with high probability of success. As a by-product of our construction, we obtain a weak ϵ -net for hypercube ranges, which significantly improves the construction time and the size of the candidate set. Our technique can be applied to a number of applications, including the translational pattern matching problem. [ABSTRACT FROM AUTHOR]

We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight λ -connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weight λ -connectivity Augmentation. It is easy to see that a minimum solution to these problems contains at most 2 λ (n - 1) edges. Using this fact one can design a brute-force algorithm which runs in time 2 O (λ n log n) , however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2 O (λ n) , for both undirected and directed networks. Our results are obtained via well known characterizations of λ -connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets. [ABSTRACT FROM AUTHOR]

Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic weighted vertex cover problem and analyze the runtime performances of the well-studied algorithms randomized local search and (1 + 1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1 + 1) EA with 1/5-th rule requires pseudo-polynomial expected runtime. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of designing a β -additive fault-tolerant approximate BFS (or FT-ABFS for short) structure, namely, a subgraph H of the network G such that subsequent to the failure of a single edge e, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, whose distances satisfy dist (s , v , H \ { e }) ≤ dist (s , v , G \ { e }) + β for every v ∈ V . It was shown in Parter and Peleg (SODA, 2014), that for every β ∈ [ 1 , O (log n) ] there exists an n-vertex graph G with a source s for which any β -additive FT-ABFS structure rooted at s has Ω (n 1 + ϵ (β)) edges, for some function ϵ (β) ∈ (0 , 1) . In particular, 3-additive FT-ABFS structures admit a lower bound of Ω (n 5 / 4) edges. In this paper we present the first upper bound, showing that there exists a poly-time algorithm that for every n-vertex unweighted undirected graph G and source s constructs a 4-additive FT-ABFS structure rooted at s with at most O (n 4 / 3) edges. The main technical contribution of our algorithm is in adapting the path-buying strategy used in Baswana et al. (ACM Trans Algorithms 7:A5, 2010) and Cygan et al. (Proceedings of the 30th symposium on theoretical aspects of computer science, pp 209–220, 2013) to failure-prone settings. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the guest editors discusses various reports published within the May 2011 issue of "Algorithmica," including one by Zoltan Kiraly on algorithms for stable marriage problem, one by Anke van Zuylen on the use of deterministic sampling algorithms for network designing, and one on computer engineering and algorithms by Daniel Delling.

In this paper, we consider the following sum query problem: Given a point set P in R d , and a distance-based function f(p, q) (i.e., a function of the distance between p and q) satisfying some general properties, the goal is to develop a data structure and a query algorithm for efficiently computing a (1 + ϵ) -approximate solution to the sum ∑ p ∈ P f (p , q) for any query point q ∈ R d and any small constant ϵ > 0 . Existing techniques for this problem are mainly based on some core-set techniques which often have difficulties to deal with functions with local domination property. Based on several new insights to this problem, we develop in this paper a novel technique to overcome these encountered difficulties. Our algorithm is capable of answering queries with high success probability in time no more than O ~ ϵ , d (n 0.5 + c) , and the underlying data structure can be constructed in O ~ ϵ , d (n 1 + c) time for any c > 0 , where the hidden constant has only polynomial dependence on 1 / ϵ and d. Our technique is simple and can be easily implemented for practical purpose. [ABSTRACT FROM AUTHOR]

We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t ≥ 0 , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Peres et al. (Random Struct Algorithms 47(4):760–775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of length n the only known upper bound on the expected gap is of order O (n log n) , following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of O (n log n) . We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n / 2 . We complement this with a "gap covering" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by Ω (n) . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. [ABSTRACT FROM AUTHOR]

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an O (n log σ ′) -time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where σ ′ ≤ d is the maximum number of distinct characters in every window. [ABSTRACT FROM AUTHOR]

In this paper we study regular expression matching in cases in which the identity of the symbols received is subject to uncertainty. We develop a model of symbol emission and uses a modification of the shortest path algorithm to find optimal matches on the Cartesian Graph of an expression provided that the input is a finite list. In the case of infinite streams, we show that the problem is in general undecidable but, if each symbols is received with probability 0 infinitely often, then with probability 1 the problem is decidable. [ABSTRACT FROM AUTHOR]

The paper considers scheduling jobs online to minimize the objective ∑ i ∈ [ n ] w i g (C i - r i) , where w i is the weight of job i, r i is its release time, C i is its completion time and g is any non-decreasing convex function. It is known that the clairvoyant algorithm Highest-Density-First (HDF) is (2 + ϵ) -speed O(1)-competitive for this objective on a single machine for any fixed 0 < ϵ < 1 (Im et al., in: ACM-SIAM symposium on discrete algorithms, pp 1254–1265, 2012). In this paper, we give the first non-trivial results for this problem when g is a non-decreasing convex function and the algorithm must be non-clairvoyant. More specifically, our results include: A (2 + ϵ) -speed O(1)-competitive non-clairovyant algorithm on a single machine for all non-decreasing convex g, matching the performance of HDF for any fixed 0 < ϵ < 1 . A (3 + ϵ) -speed O(1)-competitive non-clairovyant algorithm on multiple identical machines for all non-decreasing convex g for any fixed 0 < ϵ < 1 . 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 gsimultaneously. The positive results are supplemented by almost matching lower bounds. We show that any algorithm that is oblivious to g is not O(1)-competitive with speed augmentation less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function g cannot be O(1)-competitive with speed augmentation less than 2 on a single machine or (2 - 1 m) on m identical machines. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈ 1.4659 . They show that k = O (m) is sufficient to achieve this bound and no k = o (n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a δ = Θ (1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + δ with k = o (n) . We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ≈ 1.7992 with k = O (m) . We also show that k = Ω (m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

Biró et al. (Discrete. Math 100(1–3):267–279, 1992) introduced the concept of H-graphs, intersection graphs of connected subgraphs of a subdivision of a graph H. They are related to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. Our paper starts a new line of research in the area of geometric intersection graphs by studying several classical computational problems on H-graphs: recognition, graph isomorphism, dominating set, clique, and colorability. We negatively answer the 25-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. We prove that it is NP -complete if H contains the diamond graph as a minor. On the positive side, we provide a polynomial-time algorithm recognizing T-graphs, for each fixed tree T. For the special case when T is a star S d of degree d, we have an O (n 3.5) -time algorithm. We give FPT - and XP -time algorithms solving the minimum dominating set problem on S d -graphs and H-graphs, parametrized by d and the size of H, respectively. The algorithm for H-graphs adapts to an XP -time algorithm for the independent set and the independent dominating set problems on H-graphs. If H contains the double-triangle as a minor, we prove that the graph isomorphism problem is GI-complete and that the clique problem is APX-hard. On the positive side, we show that the clique problem can be solved in polynomial time if H is a cactus graph. Also, when a graph has a Helly H-representation, the clique problem is polynomial-time solvable. Further, we show that both the k-clique and the list k-coloring problems are solvable in FPT-time on H-graphs, parameterized by k and the treewidth of H. In fact, these results apply to classes of graphs with treewidth bounded by a function of the clique number. We observe that H-graphs have at most n O (‖ H ‖) minimal separators which allows us to apply the meta-algorithmic framework of Fomin, Todinca, and Villanger (2015) to show that for each fixed t, finding a maximum induced subgraph of treewidtht can be done in polynomial time. In the case when H is a cactus, we improve the bound to O (‖ H ‖ n 2) . [ABSTRACT FROM AUTHOR]

Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is (2 - 1 / m) -competitive. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201. No deterministic online strategy can obtain a competitiveness smaller than 1.88. In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds, for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability. [ABSTRACT FROM AUTHOR]

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O (n 2) -time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomial time if the length of preference lists of one side is bounded by one (but that of the other side is unbounded). [ABSTRACT FROM AUTHOR]

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning. In this paper, we prove that this empirically fast algorithm runs in O (3. 460 k n) time, where k is the solution size. This improves the previous best O (3. 619 k n) -time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf Process Lett 114:556–560, 2014. https://doi.org/10.1016/j.ipl.2014.05.001). [ABSTRACT FROM AUTHOR]

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f (pw) n o (pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl + Δ , where tl is the tree-length and Δ the maximum-degree of the input graph. [ABSTRACT FROM AUTHOR]

Let P be a set of n colored points in the d-dimensional Euclidean space. Introduced by Hart (1968), a consistent subset of P, is a set S ⊆ P such that for every point p in P \ S , the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been significant progress from the algorithmic point of view. In this paper we present the following algorithmic results for the consistent subset problem in the plane: (1) The first subexponential-time algorithm for the consistent subset problem. (2) An O (n log n) -time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Along the way we prove the following result which is of an independent interest: given n translations of a cone (defined as the intersection of n halfspaces) and n points in R 3 , in O (n log n) time one can decide whether or not there is a point in a cone. (3) An O (n log 2 n) -time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O (n 2) running time which is due to Wilfong (SoCG 1991). (4) An O(n)-time algorithm for the consistent subset problem on collinear points that are given from left to right; this improves the previous best known O (n 2) running time. (5) A non-trivial O (n 6) -time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines. To obtain these results, we combine tools from planar separators, paraboloid lifting, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, minimum covering of a circle with arcs, and several geometric transformations. [ABSTRACT FROM AUTHOR]

Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as k-center, k-median, and k-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of correlation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O (n · polylog n) -space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the "quality" of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. Unfortunately, the standard LP and SDP formulations are not obviously solvable in O (n · polylog n) -space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. [ABSTRACT FROM AUTHOR]

In this paper, we investigate algorithms for finding centers of a given collection N of sets. In particular, we focus on metric rational set similarities, a broad class of similarity measures including Jaccard and Hamming. A rational set similarity S is called metric if D = 1 - S is a distance function. We study the 1-center problem on these metric spaces. The problem consists of finding a set C that minimizes the maximum distance of C to any set of N . We present a general framework that computes a (1 + ε) approximation for any metric rational set similarity. [ABSTRACT FROM AUTHOR]

In this paper we consider the classical connected dominating set problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem—a centralized greedy approach with an approximation guarantee of H (Δ) + 2 , and a local information greedy approach with an approximation guarantee of 2 (H (Δ) + 1) (where H() is the harmonic function, and Δ is the maximum degree in the graph). A local information greedy algorithm uses significantly less knowledge about the graph, and can be useful in a variety of contexts. However, a fundamental question remained—can we get a local information greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative. [ABSTRACT FROM AUTHOR]

This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage. [ABSTRACT FROM AUTHOR]

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the ‘deletion set’. In this paper, we show thatFVS is fixed-parameter tractable by an O(2knO(1)) time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time O((2-ϵ)knO(1)) is not possible unless SETH fails.When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an O(3.148knO(1)) time algorithm.When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an O(5knO(1)) algorithm. Regarding kernelization results, we show thatWhen parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an O(k7) vertices kernel improving from the previously known O(k10) bound.When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with O(k3d+3) vertices. We also prove a lower bound of Ω(kd+2) size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles. [ABSTRACT FROM AUTHOR]

We propose and analyze a self-adaptive version of the (1 , λ) evolutionary algorithm in which the current mutation rate is encoded within the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O (n λ / log λ + n log n) when λ is at least C ln n for some constant C > 0 . For all values of λ ≥ C ln n , this performance is asymptotically best possible among all λ -parallel mutation-based unbiased black-box algorithms. Our result rigorously proves for the first time that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. In particular, it gives asymptotically the same performance as the relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Gießen, Witt, and Yang (Algorithmica 2019). On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift. [ABSTRACT FROM AUTHOR]

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter tree-cut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded tree-cut width. Our second result shows that EDP parameterized by tree-cut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. [ABSTRACT FROM AUTHOR]

Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands { d io j } i ∈ { 1 , ... , m } , o ∈ { 1 , ... , m } that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu et al. (in: ACM Symposium on parallelism in algorithms and architectures. ACM, New York, pp 294–303, 2015) obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic 67 3 -approximation and a randomized (9 + 16 2 3) ≈ 16.54 -approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm for coflow scheduling with release times, and a deterministic 4-approximation for the case without release times. As for concurrent open shop problem with release times, we give a combinatorial 3-approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem. [ABSTRACT FROM AUTHOR]

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11 to 2.8% of the text size, with a gain up to 50% if compared with previous solutions. [ABSTRACT FROM AUTHOR]

We would like to thank the authors for contributing their manuscripts, the referees for thoroughly reviewing these articles and the WADS 2021 program committee for helping with the selection of these articles. This special issue is dedicated to selected papers from those presented at the 17th Algorithms and Data Structures Symposium (WADS 2021), which was held from August 9-11 fully online. [Extracted from the article]