Search

Abstract When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a "good" puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP -complete, and we show their FCP versions are Σ 2 P -complete. Along the way, we show that the FCP versions of Triangle Partition , Planar 1- in -3 SAT , and Latin Square are all Σ 2 P -complete. We show that even problems in P have difficult FCP versions, sometimes even Σ 2 P -complete, though "closed under cluing" problems are in the (presumably) smaller class NP ; for example, FCP 2 SAT is NP -complete. [ABSTRACT FROM AUTHOR]

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in an n × n array. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions. The algorithm is efficient and straightforward, with runtime O (n 2 log ⁡ n + ρ) , where n 2 is the size of the input array and ρ is the number of maximal 2D repetitions in the output. [ABSTRACT FROM AUTHOR]

The problem of reducing ϵ -NN to (c , r) -NN is very important in theoretical computer science area and has attracted many research efforts. In this paper a new algorithm for such problem is proposed, which achieves O (log ⁡ n) query time. Comparing with the former algorithms for the same problem, this query time is the lowest, which is the main contribution of this paper. The low query time complexity is achieved by raising the preprocessing time and space complexity. How to reduce the cost added into the two complexities is also discussed in this paper. [ABSTRACT FROM AUTHOR]

Abstract A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t , whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t -Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t -Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t -Garden-Of-Eden Problem, a variant of the t -Predecessor Problem that asks whether a configuration has a t -predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we consider the problems for covering multiple intervals on a line. Given a set B of m line segments (called "barriers") on a horizontal line L and another set S of n horizontal line segments of the same length in the plane, we want to move all segments of S to L so that their union covers all barriers and the maximum movement of all segments of S is minimized. Previously, an O (n 3 log ⁡ n) -time algorithm was given for the case m = 1. In this paper, we propose an O (n 2 log ⁡ n log ⁡ log ⁡ n + n m log ⁡ m) -time algorithm for a more general setting with any m ≥ 1 , which also improves the previous work when m = 1. We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an O (n log ⁡ n) -time algorithm was known for the case m = 1. We present an algorithm of O (m log ⁡ m + n log ⁡ m log ⁡ n) time for any m ≥ 1. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks. [ABSTRACT FROM AUTHOR]

Let B be a set of b blue points and R be a set of r red points in the plane. In this paper we study the problem of finding rectangles that contain the maximum number of blue points without containing any red points, known as the maximum-box problem . First we study this problem for axis-aligned rectangles, and propose an exact worst-case optimal O ( r 2 + r b + b log ⁡ b ) time algorithm using O ( r + b ) space to find all maximum boxes. We also provide a 2-approximation algorithm running in O ( ( r + b ) log ⁡ ( r + b ) ) time and using O ( r + b ) space to find a single maximum box in the axis-aligned case. Then we generalize the exact algorithm for the axis-aligned case to find all arbitrarily oriented maximum boxes leading to a worst-case optimal O ( ( r + b ) 2 ( r + log ⁡ b ) ) time algorithm using O ( ( r + b ) 2 ) space to solve the problem. We conclude the paper by discussing time and space trade-offs. Our results improve the previously best known solutions to the maximum-box problem. [ABSTRACT FROM AUTHOR]

This paper addresses for the first time the problem of MWMR atomic memory in a Mobile Byzantine Agents model. The register is maintained by n servers and faulty (Byzantine) agents move from one server to another and when they are affecting a server, this one behaves arbitrarily. This paper addresses the round-based synchronous communication model. We focus on four Mobile Byzantine Failure models differing in the diagnosis capabilities at server side. We address the case when servers can diagnose their failure state (that is, servers are aware that the mobile Byzantine agent has left), and the case when servers cannot self-diagnose. We first prove lower bounds on the number of servers n necessary to construct a safe register tolerant to the presence of f < n Mobile Byzantine Failures for four Mobile Byzantine Failure models. Additionally, we prove that our lower bounds do not change when the system is affected by any number of transient failures . Furthermore, we propose a parametric algorithm that implements an atomic MWMR register algorithm working in all the above models and matches the lower bounds. Additionally, our algorithm is also self-stabilizing. That is, started in an arbitrary state (i.e. after the occurrence of a transient failure) it is able to self-recover a correct behavior in a finite, bounded number of rounds. Our algorithm tolerates (i) any number of transient failures and (ii) up to f Mobile Byzantine Failures. [ABSTRACT FROM AUTHOR]

Calculating and analyzing the number of spanning trees of graphs (network models) is an important and interesting research project in wide variety of fields, such as mathematics, physics, theoretical computer science, chemistry and so on. The number of spanning trees of graphs (models) displays amounts of information on its structural features and also on some relevant dynamical properties, in particular network security, random walks and percolation. In this paper, firstly, due to lots of graphs (models) are built on the basis of various simple and small elements (components), we provide primarily some helpful network-operation, such as link-operation and merge-operation, to generate more realistic and complicated graphs (models). Secondly, considering reliability of fault-tolerance to random faults and of intrusion-tolerance to selectively remove attacks, synchronization capability and diffusion properties of networks, we present an iterative method (algorithm) for computing the total number of spanning trees. As a pellucid example, we apply our method to tree space and cycle space, notice that it is proved to be indeed a better tool. In order to reflect more widely practical meanings, we study its applications in graph theory, including ladder-graph with zero clustering coefficient, wheel-graph having nonzero clustering coefficient as constituent ingredients of maximal planar graphs. In the rest of this paper, we make a brief summary that the method described by us can be designed a program (algorithm) for obtaining easily the exact number of spanning trees of some models. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]

The longest common increasing subsequences (LCIS) problem is to find out a common increasing subsequence with the maximal length of two given sequences A and B. In this paper, we propose an algorithm for solving the LCIS problem with O ((n + L (m − L)) log ⁡ log ⁡ | Σ |) time and O(n) space, where m and n denote the lengths of A and B , respectively, m ≤ n , L denotes the LCIS length, and Σ denotes the alphabet set. The main idea of our algorithm is to extend the answer from some previously feasible solutions, in which the domination function is invoked. To accomplish the extension and domination functions, the data structure of the van Emde Boas tree is utilized. From the time complexity, it is obvious that our algorithm is extremely efficient when L is very small or L is close to m. Some experiments are performed to demonstrate the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

A mixed domination of a graph G = (V , E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O ⁎ (4.172 k) , which improves the previous bound of O ⁎ (7.465 k). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11 k − 16 vertices. [ABSTRACT FROM AUTHOR]

The Burrows-Wheeler Transform (BWT) has become since its introduction a key tool for representing large text collections in compressed space while supporting indexed searching: on a text of length n over an alphabet of size σ , it requires O (n lg ⁡ σ) bits of space, instead of the O (n lg ⁡ n) bits required by classical indexes. A challenge for its adoption is to build it within O (n lg ⁡ σ) bits as well. There are some sequential algorithms building it within this space, but no such a parallel algorithm. In this paper we present a PRAM CREW algorithm to build the BWT using O (n lg ⁡ n) work, O (lg 3 ⁡ n / lg ⁡ σ) depth, and O (n lg ⁡ σ) bits. [ABSTRACT FROM AUTHOR]

• A new variant of approximate palindromes called single-arm-gapped palindromes. • Efficient algorithms to compute maximal single-arm-gapped palindromes in a string. • Experimental results to compare the proposed methods in practice. In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either w g u c u R w R or w u c u R g w R , where w and u are non-empty strings, w R and u R are respectively the reversed strings of w and u , g is a string called a gap, and c is either a single character or the empty string. Here we call wu and u R w R the arm of the SAGP, and | u v | the length of the arm. We classify SAGPs into two groups: those which have u c u R as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute type-1 SAGPs with longest arms occurring in a given string, based on suffix arrays. Then, we propose a linear-time algorithm to compute all type-1 SAGPs with longest arms, based on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms in linear time. We also perform some preliminary experiments to show practical performances of the proposed methods. [ABSTRACT FROM AUTHOR]

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V , E) , with an integer influence threshold t (v) for each node, and the diffusion process as follows: Initially the members of a chosen set S ⊆ V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new node v that has at least t (v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ = 1 , we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network. [ABSTRACT FROM AUTHOR]

We introduce the notion of expandability in the context of automaton semigroups and groups: a word is k-expandable if one can append a suffix to it such that the size of the orbit under the action of the automaton increases by at least k. This definition is motivated by the question which ω -words admit infinite orbits: for such a word, every prefix is expandable. In this paper, we show that, given a word u , an automaton T and a number k as input, it is decidable to check whether u is k -expandable with respect to the action of T. In fact, this can be done in exponential nondeterministic space. From this nondeterministic algorithm, we obtain a bound on the length of a potential orbit-increasing suffix x. Moreover, we investigate the situation if the automaton is invertible and generates a group. In this case, we give an algebraic characterization for the expandability of a word based on its shifted stabilizer. We also give a more efficient algorithm to decide the expandability of a word in the case of automaton groups, which allows us to improve the upper bound on the maximal orbit-increasing suffix length. Then, we investigate the situation for reversible (and complete) automata and obtain that every word is expandable with respect to such automata. Finally, we give a lower bound example for the length of an orbit-increasing suffix. [ABSTRACT FROM AUTHOR]

This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg ⁡ n − 1.4427 n + O (log ⁡ n). For many efficient algorithms, the first n lg ⁡ n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is "two-element insertion," which inserts two elements A and B , A < B , into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach together with the binary insertion. [ABSTRACT FROM AUTHOR]

In the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", Theor. Comput. Sci. 769 (2019) 63–74, the LHIT problem is proposed as follows: For a given set of non-intersecting line segments L = { ℓ 1 , ℓ 2 , ... , ℓ n } in Image 1 , compute two axis-parallel congruent squares S 1 and S 2 of minimum size whose union hits all the line segments in L , and a linear time algorithm was proposed. Later it was observed that the algorithm has a bug. In this corrigendum, we corrected the algorithm. The time complexity of the corrected algorithm is O (n 2). [ABSTRACT FROM AUTHOR]

The locating-chromatic number of a graph G (V , E) is the cardinality of a minimum resolving partition of the vertex set V (G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices not contained in the same partition class. Determining the locating-chromatic number of any tree is a difficult task. In this paper, we propose an algorithm to compute the upper bound on the locating-chromatic number of any tree. To do so, we decompose a tree into caterpillars and then compute the upper bound of the locating-chromatic number of this tree in terms of the ones for these caterpillars. [ABSTRACT FROM AUTHOR]

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u , v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G , the (strong) conflict-free connection number of G , denoted by (s c f c (G)) c f c (G) , is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E (o r V) → { 1 , 2 , ⋯ , k } (k ≥ 1) of G , determine whether or not G is, respectively, conflict-free connected, conflict-free vertex-connected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether s c f c (G) ≤ k (k ≥ 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k -edge-coloring (k ≥ 2) of G such that all pairs (u , v) ∈ P (P ⊂ V × V) are strongly conflict-free connected. [ABSTRACT FROM AUTHOR]

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in the input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem. [ABSTRACT FROM AUTHOR]

Rumor Blocking, an important optimization problem in social network, has been extensively studied in the literature. Given social network G = (V , E) and rumor seed set A , the goal is asking for k protector seeds that protect the largest expected number of social individuals by truth. However, the source of rumor is always uncertain, rather than being predicted or being known in advance in the real situations, while rumor spreads like wildfire on the Internet. This paper presents General Rumor Blocking with unpredicted rumor seed set (randomized A) and various personal profits while being protected (weights of nodes in V). We first show that the objective function of this problem is non-decreasing and submodular, and thus a (1 − 1 / e) approximate solution can be returned by greedy approach. We then propose an efficient random algorithm R-GRB which returns a (1 − 1 / e − ε) approximate solution with at least 1 − n − ℓ probability. We show that it runs in O (m (n − r) (k log ⁡ (n − r) + ℓ log ⁡ n) / ε 2) expected time, where m = | E | , n = | V | , r = | A | and k is the number of protector seeds. Finally, we conduct extensive experiments to evaluate the R-GRB and show that it is superior in both theory and experiment. [ABSTRACT FROM AUTHOR]

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Given a social network G and a positive integer k , the influence maximization problem seeks for k nodes in G that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. For multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. The Profit Maximization with Multiple Adoptions (PM2A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM2A problem, which could achieve a (1 − 1 / e − ε) -approximate solution with high probability and is also the best performance ratio of the PM2A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget. [ABSTRACT FROM AUTHOR]

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic (b / q ε , (1 − ε)) -bicriteria algorithm for SCPSMC, the output of which fully covers at least (1 − ε) q -percentage of the total profit and the performance ratio is b / q ε , where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e. [ABSTRACT FROM AUTHOR]

In this paper, we explore some connections between covering arrays (CAs) and set covers (SCs) that already existed in the literature, and in some cases we provide new mappings between these structures. In particular, the devised mappings make feasible an interpretation of weighted budgeted CAs (WBCAs) as weighted budgeted SCs. These connections in turn make it possible to reformulate known greedy heuristics for computing mixed-level CAs and evolve new algorithms for WBCA generation. This also enables importing an upper bound on the size or a lower bound on the covered weight of the generated arrays. We further carry out a comparison of a CA generation strategy that has an analogue in the SC world with one developed specifically for CAs. Moreover, we experiment with several problem instances for CA and WBCA generation, and compare CA solvers versus SC solvers, both in quality of their output size and covered weights, as well as computation time. Our experiments underpin the hypothesis that CA solvers provide solutions of comparable quality to the ones returned by the considered SC solvers, although the latter solvers generally provide solutions of better quality. Nevertheless, CA solvers provide solutions to the respective problem instances much faster. [ABSTRACT FROM AUTHOR]

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e 1 , e 2 , ... , e m on a vertex set V. A streamed graph is ω-stream planar with respect to a positive integer window size ω if there exists a sequence of planar topological drawings Γ i of the graphs G i = (V , { e j | i ≤ j < i + ω }) such that the common graph G ∩ i = G i ∩ G i + 1 is drawn the same in Γ i and in Γ i + 1 , for 1 ≤ i ≤ m − ω. The Stream Planarity Problem with window size ω asks whether a given streamed graph is ω -stream planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the Stream Planarity Problem is NP -complete even when the window size is a constant and that the variant with a backbone graph is NP -complete for all ω ≥ 2. On the positive side, we provide O (n + ω m) -time algorithms for (i) the case ω = 1 and (ii) all values of ω provided the backbone graph is 2-connected. Our results improve on the Hanani-Tutte-style algorithm proposed by Schaefer [GD'14] for ω = 1 , which runs in O ((n m) 3) time. [ABSTRACT FROM AUTHOR]

A string X = X [ 1.. n ] , n > 1 , is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X ; for n = 1 , every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k , where X 1 is the longest closed prefix of X , X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O (log ⁡ n) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O (n log 2 ⁡ n) -time algorithm to compute M C F (X) , then we present an on-line algorithm for the same problem. In fact, we show that M C F (X) can be computed in O (L log ⁡ n) time from M C F (X ′) , where X ′ = X [ 1.. n − 1 ] , and L is the largest integer such that the suffix X [ n − L + 1.. n ] is a substring of X ′. [ABSTRACT FROM AUTHOR]

A proper (simple) relation algebra is a collection A of binary relations on a set U such that the top element of the algebra is U × U , and A is closed under union, intersection, complementation, composition, converse and contains the identity relation on U. Proper relation algebras can be constructed using U = Z / p Z as a base set using a method due to Comer. The cycle structure of such an algebra must, in general, be determined a posteriori , normally with the aid of a computer. In this paper, we give an improved algorithm for checking the cycle structure that reduces the time complexity from O (p 2) to O (p). [ABSTRACT FROM AUTHOR]

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W (1 + τ) where τ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Ω (W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct , the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from { 0 , 1 ... , R } in a stream. While it is known that Ω (W log ⁡ R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant τ. Specifically, for τ = Θ (1) , we present a space lower bound of Ω (log ⁡ (R W)) bits. Additionally, we show an Ω (log ⁡ (W / ϵ)) lower bound for RWϵ additive approximations and a Ω (log ⁡ (W / ϵ) + log ⁡ log ⁡ R) bits lower bound for (1 + ϵ) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [17] for (1 + ϵ) -multiplicative approximation that requires O (ϵ − 1 log ⁡ (R W) log ⁡ log ⁡ (R W)) space and performs updates in O (log ⁡ (R W)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct , General-Summing , and Maximum problems. [ABSTRACT FROM AUTHOR]

In Temporal Logic (TL), a well-formed formula is generally formed by applying rules of its syntax finitely many times. However, under some circumstances, although formulas such as ones expressed by index set expressions , are constructed via applying rules of the syntax infinitely many times, they are possibly still well-formed since their equivalent concise syntax formulas can be found. With this motivation, this paper investigates the relationship between formulas specified by index set expressions and concise syntax by means of fixed-point approach. Firstly, we present two kinds of formulas, namely ⋁ i ∈ N 0 ◯ i Q and ⋁ i ∈ N 0 Q i , and prove they are indeed well-formed by proving they are equivalent to formulas ◇ Q and Q ⁎ respectively. Further, we generalize ⋁ i ∈ N 0 ◯ i Q to ⋁ i ∈ N 0 P (i) ∧ ◯ i Q and explore the least and greatest fixed-points of an abstract equation X ≡ Q ∨ P ∧ ◯ X. Based on these, some well-formed special instances of ⋁ i ∈ N 0 P (i) ∧ ◯ i Q are obtained. Besides, with the index set expression technique, we equivalently represent ' U ' (strong until) and ' W ' (weak until) constructs of propositional Linear Temporal Logic (LTL) within Propositional Projection Temporal Logic (PPTL). [ABSTRACT FROM AUTHOR]

In this paper, we study the k -forest problem in the model of resource augmentation. In the k -forest problem, given an edge-weighted graph G (V , E) , a parameter k , and a set of m demand pairs ⊆ V × V , the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate—the best-known approximation ratio is O (min ⁡ { | V | , k }). Furthermore, k -forest is as hard to approximate as the notoriously-hard densest k -subgraph problem. While the k -forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k -forest problem can be viewed as to remove at most m − k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k -forest problem that, for every ε > 0 , removes at most m − k demands and has cost no more than O (1 / ε 2) times the cost of an optimal algorithm that removes at most (1 − ε) (m − k) demands. [ABSTRACT FROM AUTHOR]

This paper deals with the conversion of expressions denoting Hadamard series into weighted rotating automata. We prove that any algorithm converting rational series into one-way weighted automata can be extended to provide an algorithm which achieves our goal. We apply this to define the derivation and the follow automata of a Hadamard expression. Our method may also be used to extend algorithms which perform the inverse conversion, but it is required to enhance the algorithm to fulfil some constraints. [ABSTRACT FROM AUTHOR]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn [8] , which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Beeping models are weak in essence and even simple tasks may become difficult or unfeasible with them. In this paper, we address the problem of computing how many participants there are in a one-hop network: the counting problem. We first observe that no algorithm can compute this number with certainty in BL , even if it is randomised (Las Vegas). We thus consider the stronger variant where beeping nodes are able to detect simultaneous beeps, referred to as B c d L (cd stands for collision detection). We prove that at least n rounds are necessary in B c d L , and we present an algorithm whose running time is O (n) rounds with high probability. Further experimental results show that its expected running time is less than 10 n. Finally, we discuss how this algorithm can be adapted in other beeping models. In particular, we show that the algorithm can be emulated in BL , at the cost of a logarithmic slowdown and of trading its Las Vegas nature (certain result, uncertain time) against a Monte Carlo one (certain time, uncertain result). [ABSTRACT FROM AUTHOR]

It is a well-known result that homomorphic encryption is not secure against adaptive chosen ciphertext attacks (CCA2) because of its malleable property. Very recently, however, Gong et al. proposed a construction asserted to be a CCA2-secure additively homomorphic encryption (AHE) scheme; in their construction, the adversary is not able to obtain a correct answer when querying the decryption oracle on a ciphertext obtained by modifying the challenge ciphertext (Theoretical Computer Science, 2016). Because their construction is very similar to Paillier's AHE, it appeared to support an additively homomorphic property, though they did not specify an evaluation algorithm for the scheme in their paper. In this paper, we present a simple CCA2 attack on their construction by re-randomizing the challenge ciphertext. Furthermore, we look into an additively homomorphic property of their construction. To do this, we first consider a typical candidate for an addition algorithm on ciphertexts, as provided for previous AHE constructions, and establish that it does not function correctly. Subsequently, we provide plausible evidence for the hardness of achieving an additively homomorphic property with their construction. According to our analysis, it seems hard to preserve an additively homomorphic property of their construction without any modification. In addition, as a minor contribution, we point out a flaw in the decryption algorithm of their construction and present a rectified algorithm for correct decryption. [ABSTRACT FROM AUTHOR]

Abstract We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d -degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d -degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K t , t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t -biclique free graph. In particular, the problems k -Dominating Set , Connected k -Dominating Set , Independent k -Dominating Set and Minimum Weight k -Dominating Set are shown to be FPT, when parameterized by t + k , on graphs not containing K t , t as a subgraph. With the exception of Connected k -Dominating Set all described algorithms are linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]

Abstract Let G = (A ∪ P , E) be a bipartite graph where A denotes a set of applicants, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is # P -complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem. [ABSTRACT FROM AUTHOR]

Abstract A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result for the case when the input graph is a maximal outerplanar graph. [ABSTRACT FROM AUTHOR]

Abstract Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. A set of initial spreaders that guarantees that all the nodes become aware of the information is called a perfect seed set. We study the problem of choosing a perfect seed set of minimum size. We provide hardness results and show that the problem becomes tractable on trees. In case of general graphs, we provide an efficient algorithm and validate its effectiveness (in terms of the solution size) on real-life networks. We also study perfect seed sets in dense graphs and derive a bound on the size of a dominating set in Ore graphs. [ABSTRACT FROM AUTHOR]

Abstract The sensitivity conjecture proposed by Nisan and Szegedy in 1994, which asserts that for any Boolean function, its sensitivity complexity is polynomially related to the block sensitivity complexity, is one of the most important and challenging problems in the study of decision tree complexity. Despite a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, is still exponential in terms of sensitivity. In this paper, we give a better upper bound for certificate complexity and block sensitivity, b s (f) ≤ C (f) ≤ (8 9 + o (1)) s (f) 2 s (f) − 1 , where b s (f) , C (f) and s (f) are the block sensitivity, certificate complexity and sensitivity, respectively. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between the 0-certificate complexity C 0 (f) and 0-sensitivity s 0 (f) for functions with small 1-sensitivity s 1 (f). [ABSTRACT FROM AUTHOR]

Abstract We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not exceed a given generation capacity. This naturally captures the supply constraints in alternating current (AC) electric systems. In this paper, we consider maximizing the aggregate user utility subject to power supply limits over a time horizon. We present approximation algorithms characterized by the maximum angle ϕ between any two complex-valued demands. More precisely, a PTAS is presented for the case ϕ ∈ [ 0 , π 2 ] , a bi-criteria FPTAS for ϕ ∈ [ 0 , π - ε ] for any polynomially small ε , assuming the number of time slots in the discretized time horizon is a constant. Furthermore, if the number of time slots is part of the input, we present a reduction to the real-valued unsplittable flow problem on a path with only a constant approximation ratio. Finally, we present a practical greedy algorithm for the single time slot case with an approximation ratio of 1 2 cos ⁡ ϕ 2 and a running time complexity of only O (N log ⁡ N) , N standing for the aggregate number of user demands, which can be implemented efficiently in practice. [ABSTRACT FROM AUTHOR]

Abstract Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung–Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we use a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behavior of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies. We prove the following fundamental structural and algorithmic results on GIRGs. (1) We provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O (n). (2) We establish that GIRGs have clustering coefficients in Ω (1) , (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits. Highlights • GIRGs are a random graph model that reproduces many features of real-world networks. • The model contains the celebrated hyperbolic random graphs as special case. • They have large clustering coefficient, small separators, and small entropy. • We present a linear-time sampling algorithm and a linear-space compression algorithm. [ABSTRACT FROM AUTHOR]

Abstract Airline network, including airports as network nodes and flight routes as directed network edges, has a lot of special features such as departure and arrival times, air ticket budget, flight capacity, transportation cost, etc. Thus, analyzing network behavior and service performance for such a network is much more difficult than that for many other networks. In this paper, taking China domestic airline network as a representative, we try to discuss the reachability issue for each airport respectively, which could reflect its regional connectivity level and service quality of civil aviation. More specifically, we evaluate reachability through many features including node degree, betweenness, closeness, etc. To get the values of some features, we design a fast Dijkstra-based all-pair shortest path algorithm with both time and budget requirements, then use Fenwick Tree to further improve the time efficiency. Actually, it is a shortest path problem with time windows and other constraints. Furthermore, we propose a faster solution by reducing the edges in the duplicated graph as a simplification and then provide the time complexity proof. Finally, we implement Analytic Hierarchy Process (AHP) to convert the reachability feature into numerical values for all airports to measure their service qualities precisely. Our results for China domestic airline network with 210 airports and 69,160 flight routes will definitely become a guide to airline companies and civil aviation administration for their further development and management. [ABSTRACT FROM AUTHOR]

Abstract In this paper we study a variant of the p -center problem on cactus graphs in which the p -center are asked to be connected, and this problem is called the connected p -center problem. For the connected p -center problem on cactus graphs, we propose a dynamic programming algorithm and show that the time complexity is O (n 2 p 2) , where n is the number of the vertices of the cactus graphs. [ABSTRACT FROM AUTHOR]

Abstract We discuss algorithmic issues on the well-known paper-and-pencil game RaceTrack. On a very simple track called Indianapolis, we introduce the problem and simple approaches, which we then extend to more complex tracks. We present and experimentally evaluate efficient algorithms for single player scenarios. We also consider a variant where the parts of the track are known as soon as they become visible during the race. [ABSTRACT FROM AUTHOR]

Abstract We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor α < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis; max-1-DARP-M in which we want to drive the maximum number of clients with one taxi; and 1-DARP-M which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor α , the capacity c a p a of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α , c a p a and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where c a p a and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1 n -polynomial approximation for max-DARP-M. [ABSTRACT FROM AUTHOR]

Abstract Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete. [ABSTRACT FROM AUTHOR]

Abstract This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O ⁎ (3 n) and polynomial space. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to O ⁎ (2 n) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O ⁎ (2 n) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. [ABSTRACT FROM AUTHOR]