Search

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.

Consider a region that requires to be protected from unauthorized penetrations. The border of the region, modeled as a unit line segment, consists of high priority segments that require the highest level of protection separated by low priority segments that require to be visited infinitely often. We study the problem of patrolling the border with a set of k robots. The goal is to obtain a strategy that minimizes the maximum idle time (the time that a point is left unattended) of the high priority points while visiting the low priority points infinitely often. We use the concept of single lid cover (segments of fixed length) where each high priority point is covered with at least one lid, and then we extend it to strong double-lid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let λk-1 be the minimum lid length that accepts a single λk-1-lid cover with k - 1 lids and Λ2k be the minimum lid length that accepts a strong double Λ2k-lid cover with 2k lids. We show that 2min(Λ2k, λk-1) is the lower bound of the idle time when the max speed of the robots is one. To compute Λ2k and λk-1, we present an algorithm with time complexity O(max(k, n) logn) where n is the number of high priority sections. Our algorithm improves by a factor of min(n, k) the previous O(knlogn) running time algorithm. For the upper bound, first we present a strategy with idle time λk-1 where one robot covers the unit line, and the remaining robots cover the lids of a single λk-1-lid cover with k - 1 lids. Then, we present a simple strategy with idle time 3Λ2k that splits the unit line into not-disjoint k segments of equal length that robots synchronously cover, i.e., reaching the leftmost and rightmost point simultaneously. Then, we present a complex strategy that split the unit line into k non-disjoint segments that robots asynchronously cover. We show that combining strategies one and two attain an approximation of 1.5 the optimal idle time and combining strategy one and third attain optimal idle time.

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the problem to decide for a vertex set $U \subseteq V$, if there exists a \textit{minimal} dominating set $S$ with $U\subseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.

We introduce two new metrics of "simplicity" for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with $9.25n+O(1)$ turns and $12n+O(1)$ crossings on an $n\times n$ board, and we show lower bounds of $(6-\epsilon)n$ and $4n-O(1)$ on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of $9.25/6+o(1)$ and $3+o(1)$. Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in $O(n^2/p)$ time using $p$ processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for $(1,4)$-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases., Comment: 43 pages, 29 figures. FUN 2020 (FUN with Algorithms); FUN 2020 special issue in TCS

Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The running time of our algorithm on general graphs with error tolerance $\varepsilon$ is at most $O(2^{0.2680n})$ times a polynomial in $1/\varepsilon$. On bipartite graphs, the exponential term in the running time is improved to $O(2^{0.2372n})$. Our methods combine techniques from exact exponential algorithms with techniques from approximate counting. Along the way we generalise (to the multivariate case) the FPTAS of Sinclair, Srivastava, \v{S}tefankovi\v{c} and Yin for approximating the hard-core partition function on graphs with bounded connective constant. Also, we obtain an FPTAS for counting independent sets on graphs with no vertices with degree at least 6 whose neighbours' degrees sum to 27 or more. By a result of Sly, there is no FPTAS that applies to all graphs with maximum degree 6 unless $\mbox{P}=\mbox{NP}$., Comment: 52pp

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop ( 1 , 2 )-Minimum Spanning Tree problem (abbr. 2H-( 1 , 2 )-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-( 1 , 2 )-MSTP (including the ( 1 + 1 ) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the ( 1 + 1 ) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones.

Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable and which can serve as an approximation of minimum cardinality edge modifications, albeit with no guarantee on the cardinality of the resulting modification set. Over the past fifteen years, the primary design approach used for inclusion-minimal edge modification algorithms is based on a specific incremental scheme. Unfortunately, nothing guarantees that the set E of edge modifications of a graph G that can be obtained in this specific way spans all the inclusion-minimal edge modifications of G. Here, we focus on edge modification problems into the class of chordal graphs and we show that for this the set E may not even contain any solution of minimum size and may not even contain a solution close to the minimum; in fact, we show that it may not contain a solution better than within an Ω ( n ) factor of the minimum. These results show strong limitations on the the use of the current favored algorithmic approach to inclusion-minimal edge modification in heuristics for computing a minimum cardinality edge modification. They suggest that further developments might be better using other approaches.

We prove #P-completeness results for counting edge colorings on simple graphs. These strengthen the corresponding results on multigraphs from [4] . We prove that for any κ ≥ r ≥ 3 counting κ-edge colorings on r-regular simple graphs is #P-complete. Furthermore, we show that for planar r-regular simple graphs, where r ∈ { 3 , 4 , 5 } , counting edge colorings with κ colors for any κ ≥ r is also #P-complete. As there are no planar r-regular simple graphs for any r > 5 , these statements cover all interesting cases in terms of the parameters ( κ , r ) .

Cops and Robbers games have been studied for the last few decades in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers); however, players move in turn and are constrained to move on a discrete structure, usually a graph, and know the exact location of their opponent. In 2017, Bonato and MacGillivray presented a general characterization of Cops and Robbers games in order for them to be globally studied. However, their model doesn't cover cases where stochastic events may occur, such as the robbers moving in a random fashion. In this paper we present a novel model with stochastic elements that we call a Generalized Probabilistic Cops and Robbers game (GPCR). A typical such game is one where the robber moves according to a probabilistic distribution, either because she is rather lost or drunk than evading, or because she is a robot. We present results to solve GPCR games, thus enabling one to study properties relating to the optimal strategies in large classes of Cops and Robbers games. Some classic Cops and Robbers games properties are also extended., 36 pages, submitted to the journal Theoretical Computer Science

The Random Satisfiability problem has been intensively studied for decades. For a number of reasons the focus of this study has mostly been on the model, in which instances are sampled uniformly at random from a set of formulas satisfying some clear conditions, such as fixed density or the probability of a clause to occur. However, some non-uniform distributions are also of considerable interest. In this paper we consider Random 2-SAT problems, in which instances are sampled from a wide range of non-uniform distributions. The model of random SAT we choose is the so-called configuration model, given by a distribution $\xi$ for the degree (or the number of occurrences) of each variable. Then to generate a formula the degree of each variable is sampled from $\xi$, generating several \emph{clones} of the variable. Then 2-clauses are created by choosing a random paritioning into 2-element sets on the set of clones and assigning the polarity of literals at random. Here we consider the random 2-SAT problem in the configuration model for power-law-like distributions $\xi$. More precisely, we assume that $\xi$ is such that its right tail $F_{\xi}(x)$ satisfies the conditions $W\ell^{-\alpha}\le F_{\xi}(\ell)\le V\ell^{-\alpha}$ for some constants $V,W$. The main goal is to study the satisfiability threshold phenomenon depending on the parameters $\alpha,V,W$. We show that a satisfiability threshold exists and is determined by a simple relation between the first and second moments of $\xi$.

We present an efficient coreset construction algorithm for large-scale Support Vector Machine (SVM) training in Big Data and streaming applications. A coreset is a small, representative subset of the original data points such that a model trained on the coreset is provably competitive with that trained on the original data set. Since the size of the coreset is generally much smaller than the original set, our preprocess-then-train scheme has potential to lead to significant speedups when training SVM models. We prove lower and upper bounds on the size of the coreset required to obtain small data summaries for the SVM problem. As a corollary, we show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings. We evaluate the performance of our algorithm on real-world and synthetic data sets. Our experimental results reaffirm the favorable theoretical properties of our algorithm and demonstrate its practical effectiveness in accelerating SVM training.

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A ( a ) , whom a ranks strictly; we use p a ( b ) to denote the position of b ∈ A ( a ) in a's preference list. The objective is to decide whether there exists a stable matching μ such that balance ( μ ) ≜ max ⁡ { ∑ ( m , w ) ∈ μ p m ( w ) , ∑ ( m , w ) ∈ μ p w ( m ) } ≤ k . In SM , all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance ( μ ) ≥ | A ⋆ | 2 for any stable matching μ, BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2 . With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k − | A ⋆ | 2 ). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W . Let O M = ∑ ( m , w ) ∈ μ M p m ( w ) , and O W = ∑ ( m , w ) ∈ μ W p w ( m ) . In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M , O W } admits (1) a kernel where the number of people is linear in t, and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M , O W } is W[1]-hard.

The transformation of graphs and graph-like structures is ubiquitous in computer science. When a system is described by graph-transformation rules, it is often desirable that the rules are both terminating and confluent so that rule applications in an arbitrary order produce unique resulting graphs. However, there are application scenarios where the rules are not globally confluent but confluent on a subclass of graphs that are of interest. In other words, non-resolvable conflicts can only occur on graphs that are considered as "garbage". In this paper, we introduce the notion of confluence up to garbage and generalise Plump's critical pair lemma for double-pushout graph transformation, providing a sufficient condition for confluence up to garbage by non-garbage critical pair analysis. We apply our results in two case studies about efficient language recognition: we present backtracking-free graph reduction systems which recognise a class of flow diagrams and a class of labelled series-parallel graphs, respectively. Both systems are non-confluent but confluent up to garbage. We also give a critical pair condition for subcommutativity up to garbage which, together with closedness, implies confluence up to garbage even in non-terminating systems., 33 pages, 2021

The tree inclusion problem is, given two node-labeled trees P and T (the “pattern tree” and the “target tree”), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpelainen and Mannila from 1995 that runs in O ( d 2 2 d m n ) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O ( d 2 d m n 2 ) time, improving the exponential factor from 2 2 d to 2 d by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem.

International audience; Causal broadcast is a communication abstraction built on top of point-to-point send/receive networks, which ensures that any two messages whose broadcasts are causally related (as captured by Lamport's "happened before" relation) are delivered in their sending order. Several causal broadcast algorithms have been designed for failure-free and crash-prone asynchronous message-passing systems. This article first gives a formal definition of a causal broadcast abstraction in the presence of Byzantine processes, in the form of two equivalent characterizations, and then presents a simple causal broadcast algorithm that implements it. The main difficulty in the design and the proof of this algorithm comes from the very nature of Byzantine faults: Byzantine processes may have arbitrary behavior, and the algorithm must ensure that correct processes (i) maintain a coherent view of causality and (ii) are never prevented from communicating between themselves. To this end, the algorithm is built modularly, namely it works on top of any Byzantine-tolerant reliable broadcast algorithm. Due to this modularity, the proposed algorithm is easy to understand and inherits the computability assumptions (notably the maximal number of processes that may be Byzantine) and the message/time complexities of the underlying reliable broadcast on top of which it is built.

The one-visibility cops and robber game is a variation of the classic cops and robber game, where one-visibility means that the information of the robber is known to all cops only when the distance between the robber and at least one cop is at most one. In this paper, we give a lower bound on the one-visibility copnumber of general trees. We present strategies to clear trees according to their structures. We propose a linear-time algorithm for computing the one-visibility copnumber of trees.

The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable. This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add , Remove , Contains , and NNS . Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap ( ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree.

Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and multisets to support approximate versions of the operations rank(i) (i.e., computing sum_{j = i}) queries. We study multiple types of approximations (allowing an error in the query or the result) and present lower bounds and succinct data structures for several variants of the problem. We also extend our model to sliding windows, in which we process a stream of elements and compute suffix sums. This is a generalization of the window summation problem that allows the user to specify the window size at query time. Here, we provide an algorithm that supports updates and queries in constant time while requiring just (1+o(1)) factor more space than the fixed-window summation algorithms., To appear in ISAAC 2018

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamcik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Δ is acyclically edge ( Δ + 2 ) -colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.

We introduce quantum-K ($QK$), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of $QK$. Many properties enjoyed by prefix-free Kolmogorov complexity ($K$) have analogous versions for $QK$; notably a counting condition. Several connections between Solovay randomness and $K$, including the Chaitin type characterization of Solovay randomness, carry over to those between weak Solovay randomness and $QK$. We work towards a Levin-Schnorr type characterization of weak Solovay randomness in terms of $QK$. Schnorr randomness has a Levin-Schnorr characterization using $K_C$; a version of $K$ using a computable measure machine, $C$. We similarly define $QK_C$, a version of $QK$. Quantum Schnorr randomness is shown to have a Levin-Schnorr and a Chaitin type characterization using $QK_C$. The latter implies a Chaitin type characterization of classical Schnorr randomness using $K_C$., Comment: 21 pages. This has been submitted to a journal

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns.

A locally surjective homomorphism from a graph G to a graph H is called an H-role colouring of G. Deciding the existence of such a colouring with | H | = k is known to be NP-hard even under substantial restrictions on the input graph G. We study the family of hereditary classes for which the problem can be solved efficiently. Our main result is the first boundary class for this problem; that is, a minimal obstruction to solving the problem efficiently in a finitely defined hereditary class. We also give the first boundary class for the related k-coupon colouring problem, in which H is a complete graph with each vertex incident to a loop, when k is a prime power. As additional results, we show that 2-role colouring 2 K 2 -free graphs and 2-coupon colouring cographs can be done in linear time.

In this paper, we propose a simple and intuitive model to investigate the efficiency of the two-party election system, especially regarding the nomination process. Each of the two parties has its own candidates, and each of them brings utilities for the people including the supporters and non-supporters. In an election, each party nominates exactly one of its candidates to compete against the other party's. The candidate wins the election with higher odds if he or she brings more utility for all the people. We model such competition as a two-party election game such that each party is a player with two or more pure strategies corresponding to its potential candidates, and the payoff of each party is a mixed utility from a selected pair of competing candidates. By looking into the three models, namely, the linear link, Bradley-Terry, and the softmax models, which differ in how to formulate a candidate's winning odds against the competing candidate, we show that the two-party election game may neither have any pure Nash equilibrium nor a bounded price of anarchy. Nevertheless, by considering the conventional egoism, which states that any candidate benefits his/her party's supporters more than any candidate from the competing party does, we prove that the two-party election game in both the linear link model and the softmax model always has pure Nash equilibria, and furthermore, the price of anarchy is constantly bounded.

We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm., Comment: 29 pages, 4 figures

A recent trend in algorithm design consists of augmenting classic data structures with machine learning models, which are better suited to reveal and exploit patterns and trends in the input data so to achieve outstanding practical improvements in space occupancy and time efficiency. This is especially known in the context of indexing data structures for big data where, despite few attempts in evaluating their asymptotic efficiency, theoretical results are yet missing in showing that learned indexes are provably better than classic indexes, such as B-tree s and their variants. In this paper, we present the first mathematically-grounded answer to this problem by exploiting a link with a mean exit time problem over a proper stochastic process which, we show, is related to the space and time complexity of these learned indexes. As a corollary of this general analysis, we show that plugging this result in the (learned) PGM-index, we get a learned data structure which is provably better than B-tree s.

We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting location after visiting all vertices. We assume that the agent has full knowledge of all edges incident to visited vertices, and, in particular, vertices have unique identifiers. Our bound improves a lower bound of 2.5 by Dobrev et al. [10] and also holds for planar graphs, where it complements an upper bound of 16 by Megow et al. [20] . The question whether a constant competitive ratio can be achieved in general remains open.

Occurrences of a factor $w$ in an infinite uniformly recurrent sequence ${\bf u}$ can be encoded by an infinite sequence over a finite alphabet. This sequence is usually denoted ${\bf d_{\bf u}}(w)$ and called the derived sequence to $w$ in ${\bf u}$. If $w$ is a prefix of a fixed point ${\bf u}$ of a primitive substitution $\varphi$, then by Durand's result from 1998, the derived sequence ${\bf d_{\bf u}}(w)$ is fixed by a primitive substitution $\psi$ as well. For a non-prefix factor $w$, the derived sequence ${\bf d_{\bf u}}(w)$ is fixed by a substitution only exceptionally. To study this phenomenon we introduce a new notion: A finite set $M $ of substitutions is said to be closed under derivation if the derived sequence ${\bf d_{\bf u}}(w)$ to any factor $w$ of any fixed point ${\bf u}$ of $\varphi \in M$ is fixed by a morphism $\psi \in M$. In our article we characterize the Sturmian substitutions which belong to a set $M$ closed under derivation. The characterization uses either the slope and the intercept of its fixed point or its S-adic representation., Comment: 13 pages

In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O ( t 4 log 2 ⁡ t ) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 337 bead types and requires just O ( t | Q | 4 | Σ | 2 ) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ.

Consider a discrete-time process on a graph $G$ where a set $B$ of initial vertices are chosen to be colored blue (the remainder being white) and then a time step consists of every currently blue vertex forcing all of its neighbors to become blue; this process stops when every vertex of the graph is blue, and the process is called full forcing. The full throttling number of $G$ is then defined to be the minimum sum of the cardinality of $B$ and the number of time steps needed to complete the forcing process. On trees, the full throttling number is equivalent to the throttling numbers of several other graph processes, such as positive-semidefinite zero forcing, the game of cops and robbers, and the distance domination number (alternately, the $k$-radius) of a graph. For all of these, it is known that maximum possible throttling number for a tree on $n$ vertices is somewhere between $1.4502\sqrt{n}$ and $\frac{\sqrt{14}}{2}\sqrt{n}$, with the former exhibited by a family of spiders. After introducing some new ideas and methods for working with throttling on trees, this paper determines the exact full throttling number of all balanced spiders (trees with equal-length paths extending from a center vertex), and proves that their full throttling numbers are bounded above by that of paths of the same order $n$, which are known to have full throttling number $\lceil\sqrt{2n}-\frac{1}{2}\rceil$.

Revocation functionality is vital to real-world cryptographic systems for managing their reliability. In the context of identity-based encryption (IBE), Boldyreva, Goyal, and Kumar (ACM CCS 2008) first showed an efficient revocation method for IBE, and such an IBE scheme with the scalable revocation method is called revocable IBE (RIBE). Seo and Emura (PKC 2013) introduced a new security notion, called decryption key exposure resistance (DKER), which is a desirable security notion for RIBE. However, all existing RIBE schemes that achieve adaptive security with DKER require long public parameters or composite-order bilinear groups. In this paper, we first show an RIBE scheme that (1) satisfies adaptive security; (2) achieves DKER; (3) realizes constant-size public parameters; and (4) is constructed over prime-order bilinear groups. Our core technique relies on Seo and Emura's one (PKC 2013), which transform the Waters IBE (EUROCRYPT 2005) to the corresponding RIBE scheme. Specifically, we construct an IBE scheme that satisfies constant-size public parameters over prime-order groups and some requirements for the Seo-Emura technique, and then transform the IBE scheme to an RIBE scheme. We also discuss how to extend the proposed RIBE scheme to a chosen-ciphertext secure one and server-aided one (ESORICS 2015).

In this paper, we study the problem of estimating the covariance matrix under differential privacy, where the underlying covariance matrix is assumed to be sparse and of high dimensions. We propose a new method, called DP-Thresholding, to achieve a non-trivial l 2 -norm based error bound whose dependence on the dimension drops to logarithmic instead of polynomial, it is significantly better than the existing ones, which add noise directly to the empirical covariance matrix. We also extend the l 2 -norm based error bound to a general l w -norm based one for any 1 ≤ w ≤ ∞ , and show that they share the same upper bound asymptotically. Our approach can be easily extended to local differential privacy. Experiments on the synthetic datasets show results that are consistent with theoretical claims.

In a dispersable book embedding, the vertices of a given graph G must be ordered along a line l, called spine, and the edges of G must be drawn in different half-planes bounded by l, called pages of the book, such that: (i) no two edges of the same page cross, and (ii) the graph induced by the edges of each page is 1-regular (or equivalently, a matching). The minimum number of pages needed by any dispersable book embedding of G is referred to as the dispersable book thickness d b t ( G ) of G. Graph G is called dispersable if d b t ( G ) = Δ ( G ) holds (note that Δ ( G ) ≤ d b t ( G ) always holds). Back in 1979, Bernhart and Kainen conjectured that any Δ-regular bipartite graph G is dispersable, i.e., d b t ( G ) = Δ . In this paper, we employ a counting argument to disprove this conjecture for any fixed value of Δ ≥ 3 . Additionally, for the cases Δ = 3 and Δ = 4 we present concrete counterexamples to the conjecture. In particular, we show that the Gray graph, which is 3-regular and bipartite, has dispersable book thickness four (with a computer-aided proof), while the Folkman graph, which is 4-regular and bipartite, has dispersable book thickness five (with a purely combinatorial proof). On the positive side, we prove that 3-regular bipartite planar graphs are dispersable.

We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i.e., an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node v hears a message from a neighbor w in a given round, if v listens in this round, and if w is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. Each node knows its label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems. • What is the shortest labeling scheme that permits topology recognition in all wireless tree networks of diameter D and maximum degree Δ? • What is the fastest topology recognition algorithm working for all wireless tree networks of diameter D and maximum degree Δ, using such a short labeling scheme? We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree Δ ≥ 3 is Θ ( log ⁡ log ⁡ Δ ) . For such short labeling schemes, used by an algorithm working for the class of trees of diameter D ≥ 4 and maximum degree Δ ≥ 3 , we show almost matching bounds on the time of topology recognition: an upper bound O ( D Δ ) , and a lower bound Ω ( D Δ ϵ ) , for any constant ϵ 1 . Our upper bounds are proven by constructing a topology recognition algorithm using a labeling scheme of length O ( log ⁡ log ⁡ Δ ) and using time O ( D Δ ) . Our lower bounds are proven by constructing a class of trees for which any topology recognition algorithm must use a labeling scheme of length at least Ω ( log ⁡ log ⁡ Δ ) , and a class of trees for which any topology recognition algorithm using a labeling scheme of length O ( log ⁡ log ⁡ Δ ) must use time at least Ω ( D Δ ϵ ) , on some tree of this class.

Let P be a set of n points, where each point is colored with one of the k possible colors. We present efficient algorithms to preprocess P such that for a given query point q, we can quickly identify the smallest color spanning object of the desired type containing q. In this paper, we focus on (i) intervals, (ii) axis-parallel square, ( i i i ) axis-parallel rectangle, ( i v ) equilateral triangle of fixed orientation and (v) circle, as our desired type of objects.

In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let $P$ be a set of $n$ points in the plane and let $S$ be a set of line segments whose endpoints are in $P$, with no two line segments intersecting properly. We present the first deterministic 1-local $O(1)$-memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of $P$ with respect to a set of constraints $S$. The strategy never looks beyond the direct neighbors of the current node and does not store more than $O(1)$-information to reach the target. We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation $T$ of $P$ such that $S\subseteq T$, no $o(n)$-competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive deterministic 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.

Relational structures based on acyclic relations can successfully model fundamental aspects of concurrent systems behaviour. Examples include Elementary Net systems and Mazurkiewicz traces. There are however cases where more general relational structures are needed. In this paper, we present a general model of relational structures which can be used for a broad class of concurrent behaviours. We demonstrate how this general set-up works for combined order structures which are based on two relations, viz. an acyclic ‘before’ relation and a possibly cyclic ‘not later than’ relation.

The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs $G$ and $H$, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP-complete: for each $u \in V(G)$, we are given a list ${\mathfrak L}(u) \subseteq V(H)$ of possible images of $u$. After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso. We prove the following: 1) When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso. 2) Combinatorial algorithms for GraphIso translate into algorithms for ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs. 3) Algorithms based on group theory do not translate: ListIso remains NP-complete for cubic colored graphs with sizes of color classes bounded by 8. Also, ListIso allows to classify results for the graph isomorphism problem. Some algorithms are robust and translate to ListIso. A fundamental problem is to construct a combinatorial polynomial-time algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NP-hard for them, so no robust algorithm for cubic graph isomorphism exists, unless P = NP.

Influence maximization (IM) is a widely studied problem in social networks, which aims at finding a seed set with limited size that can maximize the expected number of influenced users. However, existing studies haven't considered the matching relationship, which refers to such scenarios that influenced users seek matched partners among the influenced users, such as time matching with friends to watch movie, or matching for opposite sex in the blind date. In this paper, we investigate different matching scenarios and propose online-matching (offline-matching), in which the matching and influence propagation are simultaneous (asynchronous). For the matching result, we introduce two matched types ‘s- m a t c h e d ’, i.e., i → j and ‘d- m a t c h e d ’, i.e., i ↔ j . Then, we formulate the matching influence maximization (MM) problem to optimize a limited seed set that maximizes the expected number of matched users. We prove that the MM problem is NP-hard and the computation of the matching influence is #P-hard. Next, we analyze the submodularity of the matching influence. To address the problem, we propose efficient methods OPMM (SAMM) to solve the MM in online-matching (offline-matching) with ( 1 − 1 / e − ϵ ) -approximation ( β ( 1 − 1 / e − ϵ ) -approximation) guarantee. Experiments on the real-world datasets show our algorithms outperform state of the art algorithms in terms of more accurate matching propagation results.

The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.

This paper revisits the widely researched gathering problem for two robots without any agreement on the coordinate system in a scenario which allows randomization in the asynchronous scheduling model. The scheduler is considered to be the adversary which determines the activation schedule of the robots. The adversary comes in three flavors, namely, adaptive offline, adaptive online, and oblivious, based on the knowledge of the outcome of random bits. The robots follow wait-look-compute-move cycle. In this paper, we classify the problems based on the capability of the adversary to control the parameters such as wait time, computation delay and the speed of robots and check the feasibility of gathering in terms of adversarial knowledge and capabilities. First, we show the impossibility of gathering under an adaptive offline adversary with non-negative wait time and non-negative computation delay. Gradually relaxing the adversarial capabilities, we present impossibility of gathering for finite random choices and improbability for infinite random choices for an adaptive online adversary. Under an oblivious adversary, we establish the possibility of gathering with zero computation delay. We improve the runtime of the algorithm by restricting the oblivious adversary to choose wait time and computation delay such that the sum of wait time and computation delay is more than a positive constant. Finally, we also extend our algorithm for multiple robots with merging.

We consider graph-based hedonic games such as simple symmetric fractional hedonic games and social distance games, where a group of utility maximizing players have hedonic preferences over the players' set, and wish to be partitioned into clusters so that they are grouped together with players they prefer. The players are nodes in a connected graph and their preferences are defined so that shorter graph distance implies higher preference. We are interested in Nash equilibria of such games, where no player has an incentive to unilaterally deviate to another cluster, and we focus on the notion of the price of stability. We present new and improved bounds on the price of stability for several graph classes, as well as for a slightly modified utility function.

In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in [Leonid Levin. Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory. Problems of information transmission, vol. 10 (1974), pp. 206--211]. The respective information conservation inequalities were stated in that paper without proofs. Later some proofs appeared in the literature, however no proof of the probabilistic conservation inequality has been published yet. In this paper we prove that inequality and for the sake of completeness we present also short proofs of other properties of the said notion.

In digital systems such as fiber optical communications, the ratio between probability of errors of type $1\to 0$ and $0 \to 1$ can be large. Practically, one can assume that only one type of error can occur. These errors arecalled asymmetric. Unidirectional errors differ from asymmetric type of errors; here both $1 \to 0$ and $0 \to 1$ type of errors are possible, but in any submittedcodeword all the errors are of the same type. This can be generalized for the $q$-ary case. We consider $q$-ary unidirectional channels with feedback and give bounds for the capacity error function. It turns out that the bounds depend on the parity of the alphabet $q$. Furthermore, we show that for feedback, the capacity error function for the binary asymmetric channel is different from the symmetric channel. This is in contrast to the behavior of the function without feedback., Comment: 24 pages, short version accepted at ISIT 2020

Register automata (RA) are a computational model that can handle data values by adding registers to finite automata. Recently, weighted register automata (WRA) were proposed by extending RA so that weights can be specified for transitions. In this paper, we first investigate decidability and complexity of decision problems on the weights of runs in WRA. We then propose an algorithm for the optimal run problem related to the above decision problems. For this purpose, we use a register type as an abstraction of the contents of registers, which is determined by binary relations (such as =

Let G be a graph with diameter d. A radio labelling of G is a function f that assigns to each vertex with a non-negative integer such that the following holds for all vertices u , v : | f ( u ) − f ( v ) | ⩾ d + 1 − d ( u , v ) , where d ( u , v ) is the distance between u and v. The span of f is the absolute difference of the largest and smallest values in f ( V ) . The radio number of G is the minimum span of a radio labelling admitted by G. For trees, a general lower bound of the radio number was given by Liu [10] , which has been used to prove special families of trees whose radio number is equal to this bound [1] , [6] , [9] , [10] . In this article, we present improved lower bounds for some trees whose radio number exceeds Liu's lower bound. Some of these new bounds are sharp for special families of trees, including complete binary trees [9] and odd paths [11] . Moreover, using these new bounds, we extend the known results of Halasza and Tuza [6] on complete level-wise regular trees.

With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors.

Building a trustworthy life-critical embedded system requires deep reasoning about the potential effects that sequences of machine instructions can have on full system operation. Rather than trying to analyze complete binaries and the countless ways their instructions can interact with one another — memory, side effects, control registers, implicit state, etc. — we explore a new approach. We propose an architecture controlled by a thin computational layer designed to tightly correspond with the lambda calculus, drawing on principles of functional programming to bring the assembly much closer to myriad reasoning frameworks, such as the Coq proof assistant. This approach allows assembly-level verified versions of critical code to operate safely in tandem with arbitrary code, including imperative and unverified system components, without the need for large supporting trusted computing bases. We demonstrate that this computational layer can be built in such a way as to simultaneously provide full programmability and compact, precise, and complete semantics, while still using hardware resources comparable to normal embedded systems. To demonstrate the practicality of this approach, our FPGA-implemented prototype runs an embedded medical application which monitors and treats life-threatening arrhythmias. Though the system integrates untrusted and imperative components, our architecture allows for the formal verification of multiple properties of the end-to-end system. We present a proof of correctness of the assembly-level implementation of the core algorithm in Coq, the integrity of trusted data via a non-interference proof, and a guarantee that our prototype meets critical timing requirements.

Generic submodularity ratio γ is a general measurement to characterize how close a nonnegative monotone set function is to be submodular. In this paper, we make a systematic analysis of greedy algorithms for maximizing a monotone and normalized set function with a generic submodularity ratio γ under Cardinality constraints, Knapsack constraints, Matroid constraints and K-intersection constraints.

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed $b$ and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance $x$ at speed $s$ is measured as $xs^2$. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is $b$, and the evacuation time is at most $cd$, where $d$ is the distance of the exit from the origin, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for $bc \geq 3$. For the case $bc=3$, we give an optimal algorithm, and give upper bounds on the energy for the case $bc>3$. We also consider the problem of minimizing the evacuation time when the available energy is bounded by $\Delta$. Surprisingly, when $\Delta$ is a constant, independent of the distance $d$ of the exit from the origin, we prove that evacuation is possible in time $O(d^{3/2}\log d)$, and this is optimal up to a logarithmic factor. When $\Delta$ is linear in $d$, we give upper bounds on the evacuation time., Comment: This is the full version of the paper with the same title which will appear in the proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19) L'Aquila, Italy during July 1-4, 2019

Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed e > 0 , unless P = NP , there exists no polynomial-time n 1 − e -approximation algorithm even for bipartite planar graphs. We then give an α ( Δ − 1 ) / 2 -approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t ( α , G ) + O ( Δ n ) time, under the assumption that there is an α-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t ( α , G ) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three.