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]

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]

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.

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]

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]

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]

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]

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.

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]

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 is presented in which the editor discusses various papers from the "11th Scandinavian Workshop on Algorithm Theory (SWAT)," which was held in Gothenburg, Sweden on July 2-4, 2008.

IPEC (formerly IWPEC) is a series of international symposia covering research in all aspects of parameterized and exact algorithms and complexity. We are pleased to present this special issue of Algorithmica dedicated to the 14th International Symposium on Parameterized and Exact Computation (IPEC) which took place September 11-13 in Munich, Germany. The authors provide parameterized algorithms for computing graph embeddings that visualize a recursive clustering structure. [Extracted from the article]

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]

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]

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]

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]

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]

A foreword to "Algorithmica" is presented.

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]

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]

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]

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

An introduction is presented in which the editors discuss various reports within the issue on topics including the algorithmic applications of bounded treewidth graph, the fast minor testing for planar graphs and the multivariate complexity of swap bribery.

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]

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]

This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a centralized environment. Such sets, called smooth sets, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for ρ,Δ∈ℝ a set A of natural numbers is ( ρ,Δ) -smooth if abs(| I|⋅ ρ−| I∩ A|)<Δ for any interval I⊂ℕ. The paper studies scheduling persistent clients on a single slot-oriented resource in a flexible and predictable manner. Each client γ has a given rate ρ that defines the share of the resource he is entitled to receive and the goal is a smooth schedule in which, for some predefined Δ, each client γ is served in a ( ρ,Δ)-smooth set of slots (natural numbers). The paper considers a centralized environment where a single algorithm computes the user of the current slot. It constructs a smooth schedule with a very efficient algorithm that computes the user of each slot in O(log log q) time and O( n) space, where n is the number of clients and q ≜max { ρ/ ρ | γ, γ′∈Γ}; in many practical applications this O(log log q) value is actually a small constant. Our scheduling technique is based on a reduction from allocation of slots to allocation of sub-intervals of the unit interval. This technique naturally extends to the problem of scheduling multiple resources, even under the restriction that a client can be served concurrently by at most one resource. This paper constructs such a schedule in which the users of each slot are computed very fast-in O( mlog log q) time per slot and O( n) space where m is the number of resources; this result is a significant improvement on the prior fastest algorithm that produces such a schedule (actually of a special type-a P-fair schedule) in O( mlog n) time per slot and O( n) space. Moreover, the paper introduces a novel approach to multi-resource scheduling in which each resource independently computes, slot after slot, what client to serve in this slot. Under this approach the paper constructs a smooth schedule which is computed in O( n) space and O(log log q) time per slot. [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]

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]

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]

Fujishige et al. propose the LP-Newton method, a new algorithm for linear programming problem (LP). They address LPs which have a lower and an upper bound for each variable, and reformulate the problem by introducing a related zonotope. The LP-Newton method repeats projections onto the zonotope by Wolfe's algorithm. For the LP-Newton method, Fujishige et al. show that the algorithm terminates in a finite number of iterations. Furthermore, they show that if all the inputs are rational numbers, then the number of projections is bounded by a polynomial in L, where L is the input length of the problem. In this paper, we propose a modification to their algorithm using a binary search. In addition to its finiteness, if all the inputs are rational numbers and the optimal value is an integer, then the number of projections is bounded by L+1, that is, a linear bound. [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]

Given a network represented by a graph G=(V,E), we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes S (a target set) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of 2log1-ϵ|V|, for any ϵ>0. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: (1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); (2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on previously known upper bounds; (3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs). [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]

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]