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

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP -hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting.

Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems), where each rule is assigned either with a label chosen from an alphabet Σ or with the empty label λ. A string over an alphabet is accepted by an lRSSNP system if the string is processed from left to right by the system in the sense that in a step only rules labeled with the processed symbol or with λ are used (not both), and the system reaches a final configuration in the moment when the whole string is processed. The set of all accepted strings is categorized as the restricted (computations are done with the application of the rules labeled with symbols from the given alphabet) control language and the unrestricted (rules labeled with λ are allowed in the computations) control language of the system. We study the language accepting power of lRSSNP systems using only standard spiking rules by comparing the family of control languages of lRSSNP systems with the families of languages in the Chomsky hierarchy. It is proved that restricted lRSSNP systems can accept no more than context-sensitive languages, and unrestricted lRSSNP systems can accept recursively enumerable languages.

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.

Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account. The fault-tolerance afforded by a solid code L can be summarised as follows: Consider messages, encoded using L, being sent through a noisy channel. Any code words in L, which are present in the received message, will be decoded correctly, unless they themselves happen to be the results of errors. Thus, errors in the received message will not lead to incorrect decodings of those parts which are error-free. In this paper we consider acceptors which are fault-tolerant in this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant finite-state transducers which act as decoders in such a way that an output is generated exactly when a code word has been read completely. State-invariance means that acceptance does not depend on the initial state — every state can be used as the initial state. The results of Levenshtein and Romanov depend strongly on the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes without any such restriction. Moreover, the solid code is regular as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with equivalent properties. The main results of this paper are as follows: Every acceptor defines a solid code. For every solid code there is a fault-tolerant acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code. For solid codes which are regular as languages these acceptors can be chosen to be finite while preserving all important combinatorial properties. Part of this work was presented at the 14th Journees Montoises of Theoretical Computer Science [32] .

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$.

Consider n identical relocatable sensors, with sensing range r and visibility range 2r, initially placed at arbitrary positions on a line segment barrier; each sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of the barrier that intersects with its sensing range. Sensors operate in Look-Compute-Move cycles: in a cycle a sensor determines the positions of sensors in its visibility range, it computes its next position (within its visibility range), and then moves to the calculated position. The barrier coverage problem we consider is for the sensors to independently make decisions and movements so to reach final positions whereby they collectively cover the barrier; in particular we are interested in oblivious (or memoryless) sensors, and focus on the impact that the level of synchrony and the presence/absence of orientation (i.e., global notion of “left-right”) have on the solvability of the problem. It is known that without orientation, oblivious sensors can solve the problem if they are fully synchronous (i.e., they operate in synchronous rounds and are all active at every round). In this paper, we prove that orientation is critical to being able to solve the problem if we relax the assumption of full synchronization. We first show that if sensors are unoriented, then barrier coverage is unsolvable even in the semi-synchronous setting. In contrast, if sensors agree on a global orientation, then we give an algorithm for barrier coverage, even in the completely asynchronous setting. Finally, we extend the existing result of Cohen and Peleg and show that convergence to barrier coverage by unoriented sensors in the semi-synchronous model is possible with bounded visibility range 2 r + ρ (for arbitrarily small ρ > 0 ) and bounded mobility range r.

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.

This work is devoted to the study of the Balanced Connected Subgraph Problem (BCS) from a complexity, inapproximability and approximation point of view. The input is a graph G = ( V , E ) , with each vertex having been colored, “red” or “blue”; the goal is to find a maximum connected subgraph G ′ = ( V ′ , E ′ ) from G that is color-balanced (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices). This problem is known to be NP -complete in general but polynomial in paths and trees. We propose a polynomial-time algorithm for block graph. We propose some complexity results for bounded-degree or bounded-diameter graphs, and also for bipartite graphs. We also propose inapproximability results for some graph classes, including chordal, planar, or subcubic graphs.

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.

LPN (learning parity with noise) problem is a good candidate for post-quantum cryptography which enjoys simplicity and suitability for weak-power devices. Dottling et al. (ASIACRYPT 2012) initiated the first secure public key encryption (PKE) under the low-noise LPN assumption. Kiltz et al. (PKC 2014) proposed a simpler and more efficient scheme using double-trapdoor technique from the same assumption. Both schemes abide the decoding failure rate (DFR) 2 − Θ ( k ) (k is the security parameter) and there exists CPA/CCA2-secure PKE with squared-exponential DFR 2 − Θ ( k 2 ) from constant-noise LPN (Yu and Zhang, CRYPTO 2016). In this work, we give a positive answer with squared-exponential DFR in the low-noise setting. More precisely, we first introduce a variant (VxLPN) of the low-noise Exact LPN (xLPN, proposed by Jain et al. at ASIACRYPT 2012 and used as building block in commitments and zero-knowledge proofs), where the coefficient matrix A follows the uniform distribution over { 0 , 1 } q × n ( n = Θ ( k 2 ) , q = Θ ( n ) ), the secret x is sampled from B μ n ( B μ is the Bernoulli distribution with noise rate μ = Θ ( 1 q ) ), and the noise e follows a column vector distribution uniform over { z ∈ { 0 , 1 } q : | z | = q μ } . A series of reductions show that VxLPN is at least as hard as the standard LPN for the same noise rate μ. We then construct from the VxLPN CPA/CCA2 secure PKE schemes with squared-exponential DFR 2 − Θ ( k 2 ) which share the common structure extrinsically with Kiltz et al. and Yu-Zhang schemes. The secret key(s) in our schemes are simply sampled from the Bernoulli distribution, and comparatively, the secret key(s) in Yu-Zhang schemes must be chosen from a tailored version of Bernoulli distribution (along with the coefficient matrix A that follows a distribution D λ n × n = U n × λ ⋅ U λ × n induced by multiplying two random matrices in the public key, λ = Θ ( log 2 ⁡ n ) ) in order to guarantee the correctness of their schemes. Consider the performance on 128-bit security level, our CCA2-secure scheme only holds 117.79 MB public keys, 67.31 MB secret keys and 10.15 KB ciphertexts, and thus is more efficient than the schemes of Dottling et al. and Kiltz et al. ((14.53 GB, 14.48 GB, 14.06 KB) and (161.78 MB, 92.45 MB, 13.60 KB) respectively).

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

For the sake of achieving higher reliability, conditional connectivity has gradually become well-known. Component connectivity, as a kind of conditional connectivity, is an extension of the classical connectivity. Given a simple and undirected graph G and a nonnegative integer r, the ( r + 1 ) -component connectivity of graph G, say c κ r + 1 ( G ) , is the minimum number of a vertex cut whose removal causes the surviving graph to have at least r + 1 components. Another basic parameter of reliability, diagnosability is often related to the number of components in the surviving graph. The ( r + 1 ) -component diagnosability, say c t r + 1 ( G ) , is the maximum size of fault sets subject to at least r + 1 components in the surviving graph, provided that all faulty vertices can be detected. A graph is t / k -diagnosable if all faulty vertices can be isolated into a set in which up to k vertices are fault-free, provided that the number of faulty vertices is at most t. As a two-level interconnection network, the hierarchical folded cubic network H F Q ( n ) possesses a great deal of nice properties. In this paper, we first show that the n-dimensional hierarchical folded cubic network is tightly super connected. Then, we explore that c κ r + 1 ( H F Q ( n ) ) = r ( n + 1 ) − ( r 2 ) + 1 ( n ≥ 4 , 1 ≤ r ≤ n − 4 ) , and obtain that c t r + 1 ( H F Q ( n ) ) = ( r + 1 ) n − ( r 2 ) + 2 ( n ≥ 4 , 1 ≤ r ≤ n − 4 ) under the PMC and MM* models. Last, we show that the hierarchical folded cubic network H F Q ( n ) is [ ( k + 1 ) n − ( k 2 ) + 2 ] / k -diagnosable, where n ≥ 4 and 1 ≤ k ≤ n − 4 .

Motivated by the analysis of range queries in databases, we introduce the computation of the depth distribution of a set B of n d-dimensional boxes (i.e., axis aligned d-dimensional hyperrectangles), which generalizes the computation of the Klee's measure and maximum depth of B . We present an algorithm to compute the depth distribution running in time within O ( n d + 1 2 log ⁡ n ) , using space within O ( n log ⁡ n ) , and refine these upper bound for various measures of difficulty of the input instances. Moreover, we introduce conditional lower bounds for this problem which not only provide insights on how fast the depth distribution can be computed, but also clarify the relation between the Depth Distribution problem and other fundamental problems in computer science.

Magnetic Resonance Imaging (MRI) is a widely used medical diagnosis technique. However, the quality of MR image is affected by the noise which is caused by mechanical and environmental reasons during the MR image acquisition process. For decades, various kinds of methods including filtering approaches, transform domain approaches and statistical approaches have been applied to the MR image denoising problem, while there are also some drawbacks exiting in these methods such as arising undesirable change of texture and long computation time needed. In this paper, we proposed a novel MR image denoising method called DESN which is a neural network method and has a novel network architecture with well-designed loss function. In DESN, the convolutional neural networks itself is considered as a regularizer or image prior information for the inverse problems such as denoising. The network architecture of DESN is designed from the auto-encoder architecture, it has three main parts: encoder network for extracting low-resolution image features, decoder network for restoring high-resolution features and skip connections for transmitting abstract information from encoder network to decoder network. Besides, we also design a novel loss function which contains two main parts: data fidelity loss ( L f i d e l i t y ), image quality penalty ( L q ) and three loss terms: mean squared error term ( L M S E ), image structure similarity term ( L S ), image information entropy term ( L I E ). We compare the performance of DESN with DIP and some state of the art denoising methods, and the performance of our network with different loss terms are also compared in three MR modalities. The comparative results show that DESN have the superior performance in generating high-quality MR image with enough edge and texture information.

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.

Gene regulatory networks represent the interactions among genes regulating the activation of specific cell functionalities. They have been successfully modelled using Boolean networks, where a set of Boolean variables model the activation state of each gene, and Boolean functions model positive and negative influences among genes. Moreover, when the effect of such influences is additive, threshold Boolean networks, in which Boolean functions are replaced by simpler threshold functions, turned out to be particularly effective. In this paper we propose a systematic translation of threshold Boolean networks into Ehrenfeucht and Rozenberg's reaction systems. Our translation produces a non redundant set of reactions, each using a minimal set of objects. This translation allows us to simulate the behaviour of a general threshold Boolean network by simply executing the (closed) reaction system we obtain, and to investigate causality relations among genes by applying tools available for reaction systems. We implemented our translation in an open-source tool and applied it in two case studies: the gene regulation network of segment polarity in Drosophila melanogaster and the one controlling the differentiation of Th cells in the immune system. In both case studies, we investigate causalities among genes in the reaction system obtained from the translation by applying a tool for the computation of formula based predictors. In the context of the second case study, we show that also Boolean networks with non-additive influences and modelling genes with multiple expression levels can be dealt with by our approach.

Given a text T and a set of r patterns P 1 , P 2 , … , P r , the exact multiple pattern matching problem reports the ending positions of all occurrences of P i in T for 1 ≤ i ≤ r . By transforming all substrings with a fixed length of T into a reference tree such that each internal node stores a reference string, the exact multiple pattern matching problem can be efficiently solved by searching patterns in the tree via the guidance of the reference strings. We design elegant algorithms to construct the reference tree (the preprocessing phase) and to search patterns in the tree (the searching phase) using bitwise operations. The experiments involving problem instances from the DNA sequence and the English language are conducted to compare the performance of our approach against those of the suffix tree and suffix array algorithms. The computational results demonstrate the advantage of our approach over these algorithms. In spite of the simplicity, our approach is quite efficient, flexible and robust.

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.

We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization.

Snoopy is a powerful modelling and simulation tool for various types of Petri nets, which have been applied to a wide range of biochemical reaction networks. We present an enhanced version of Snoopy, now supporting coloured and uncoloured stochastic, continuous and hybrid Petri Nets with fuzzy kinetic parameters. Colour helps to cope with modelling challenges imposed by larger and more complex networks. Fuzzy parameters are specifically useful when kinetic parameter values can not be precisely measured or estimated. By running fuzzy simulation we obtain output bands of the variables of interest induced by the effect of the fuzzy kinetic parameters. Simulation is always done on the uncoloured level. For this purpose, coloured fuzzy Petri nets are automatically unfolded to their corresponding uncoloured counterparts. Combining the power of fuzzy kinetic parameters with the modelling convenience of coloured Petri nets provides a new quality in user support with sophisticated modelling and analysis features.

The Double Traveling Salesman Problem with Multiple Stacks, DTSPMS , deals with the collect and delivery of n commodities in two distinct cities, where the pickup and the delivery tours are related by LIFO constraints. During the pickup tour, commodities are loaded into a container of k rows, or stacks, with capacity c. This paper focuses on computational aspects of the DTSPMS , which is NP-hard. We first review the complexity of two critical subproblems: deciding whether a given pair of pickup and delivery tours is feasible and, given a loading plan, finding an optimal pair of pickup and delivery tours, are both polynomial under some conditions on k and c. We then prove a ( 3 k ) / 2 standard approximation for the Min Metric k DTSPMS , where k is a universal constant, and other approximation results for various versions of the problem. We finally present a matching-based heuristic for the 2 DTSPMS , which is a special case with k = 2 rows, when the distances are symmetric. This yields a 1 / 2 − o ( 1 ) , 3 / 4 − o ( 1 ) and 3 / 2 + o ( 1 ) standard approximation for respectively Max 2 DTSPMS , its restriction Max 2 DTSPMS ( 1 , 2 ) with distances 1 and 2, and Min 2 DTSPMS ( 1 , 2 ) , and a 1 / 2 − o ( 1 ) differential approximation for Min 2 DTSPMS and Max 2 DTSPMS .

The cycle embedding is an important problem of networks, which can determine the fault tolerance of the networks. A network can be viewed as a graph. Let m be an integer with m ≥ 4 , G be a graph and w ∈ V ( G ) be an arbitrary vertex. The graph G is vertex-pancyclic if G has a cycle C l of length l with w ∈ V ( C l ) for every l ∈ { 3 , 4 , ⋯ , | V ( G ) | } and G is m-weak-vertex-pancyclic if G has a cycle C l of length l with w ∈ V ( C l ) for every l ∈ { m , m + 1 , ⋯ , | V ( G ) | } . Let G ′ be a bipartite graph and w ′ ∈ V ( G ′ ) be an arbitrary vertex. The graph G ′ is vertex-bipancyclic if G ′ has a cycle C h of length h with w ′ ∈ V ( C h ) for any even integer h with 4 ≤ h ≤ | V ( G ′ ) | . In this paper, we study the cycle embedding in the ( n , k ) -bubble-sort network B n , k . We obtain that (1) B n , 1 is vertex-pancyclic for n ≥ 3 . (2) B n , n − 1 is vertex-bipancyclic for n ≥ 4 . (3) B 4 , 2 and B 5 , 2 are 6-weak-vertex-pancyclic and B 5 , 3 is vertex-pancyclic. (4) B n , k is vertex-pancyclic for n ≥ 6 with 2 ≤ k ≤ n − 2 and every constructed cycle of B n , k contains a residual edge for n ≥ 4 with 2 ≤ k ≤ n − 2 .

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.

In the buffer minimization in multiprocessor systems with conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors. Incoming workload is stored in an input buffer and a machine that is running reduces its workload at a constant rate. The goal is to find a schedule that minimizes the maximum workload over all machines and over time. We consider the special case where the graph is a path. We give upper and lower bounds on the competitive ratio for paths of various lengths. We also consider online algorithms that have resource augmentation on their speed (processing rate), and give a ( 1 + 2 e ) -speed ( 1 / e + 2 ) -competitive algorithm.

This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in R d , when restricted to the corresponding Voronoi diagram imposed on S. The diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR+Voronoi diagram. Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e.g., the station reception zones are convex and “fat”. In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively 5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d ≥ 1 . The convexity property also holds for every SINR threshold β > 0 , and the effective fatness property holds for any β > 1 . These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices. We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P , it is required to find the power assignment that optimizes the SINR threshold of the transmission station s i for any given reception point p ∈ P in its Voronoi cell . The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case.

A total dominating set of a graph G = ( V , E ) is a subset D of V such that every vertex in V is adjacent to at least one vertex of the set D. A total dominating set D of G is a differentiating-total dominating set of G if for every pair of distinct vertices u , v ∈ V , N G [ u ] ∩ D ≠ N G [ v ] ∩ D . Given a graph G, Minimum Differentiating-Total Domination is to find a differentiating-total dominating set of minimum cardinality of G and Decide Differentiating-Total Domination is the decision version of Minimum Differentiating-Total Domination . In this paper, we initiate the algorithmic study of Minimum Differentiating-Total Domination . We show that Decide Differentiating-Total Domination is NP -complete for chordal graphs, chordal bipartite graphs, star-convex bipartite graphs, and planar graphs. On the positive side, we propose an O ( log ⁡ Δ ) factor approximation algorithm for Minimum Differentiating-Total Domination for any graph G with maximum degree Δ. We match the above upper bound by showing that for general graphs as well as for bipartite graphs Minimum Differentiating-Total Domination cannot be approximated within a factor of ( 1 2 − e ) ln ⁡ | V | for any e > 0 unless P = NP . Finally, we show that Minimum Differentiating-Total Domination is APX -complete for bounded degree bipartite graphs.

The red-blue median problem considers a set of red facilities, a set of blue facilities, and a set of clients located in some metric space. The goal is to open k r red facilities and k b blue facilities such that the sum of the distance from each client to its nearest opened facility is minimized, where k r , k b ≥ 0 are two given integers. Designing approximation algorithms for this problem remains an active area of research due to its applications in various fields. However, in many applications, the existence of noisy data poses a big challenge for the problem. In this paper, we consider the prize-collecting red-blue median problem, where the noisy data can be removed by paying a penalty cost. The current best approximation guarantee for the prize-collecting red-blue median problem is a ratio of 24, which was obtained by LP-rounding. We deal with this problem using a local search algorithm. We construct a layered structure of the swap pairs, which yields a ( 9 + ϵ ) -approximation for the prize-collecting red-blue median problem. Our techniques generalize to a more general prize-collecting τ-color median problem, where the facilities have τ different types, and give a ( 4 τ + 1 + ϵ ) -approximation for the case where τ is a constant.

An incidence of a graph G is a vertex-edge pair ( v , e ) such that the vertex v is incident with the edge e. A proper incidence k-coloring of a graph is a coloring of its incidences involving k colors so that two incidences ( u , e ) and ( w , f ) receive distinct colors if and only if u = w , or e = f , or u w ∈ { e , f } . In this paper, we present some idea of using the incidence coloring to model a kind of multi-frequency assignment problem, in which each transceiver can be simultaneously in both sending and receiving modes, and then establish some theoretical and algorithmic aspects of the incidence coloring. Specifically, we conjecture that if G is the Mycielskian of some graph then it has a proper incidence ( Δ ( G ) + 2 ) -coloring. Actually, our conjecture is motivated by the “ ( Δ + 2 ) conjecture” of Brualdi and Quinn Massey in 1993, which states that every graph G has a proper incidence ( Δ ( G ) + 2 ) -coloring, and was disproved in 1997 by Guiduli, who pointed out that the Paley graphs with large maximum degree are counterexamples (yet they are all known counterexamples to the “ ( Δ + 2 ) conjecture”, and are not Mycielskians of any graph). To support our conjecture, we prove in this paper that if G is the Mycielskian of a graph H with | H | ≥ 3 Δ ( H ) + 2 , then we can construct a proper incidence ( Δ ( G ) + 1 ) -coloring of G in cubic time, and if G is the Mycielskian of an incidence ( Δ ( H ) + 1 ) -colorable graph H with | H | ≤ 2 Δ ( H ) , or the Mycielskian of an incidence ( Δ ( H ) + 2 ) -colorable graph H with | H | ≥ 2 Δ ( H ) + 1 , then G has a proper incidence ( Δ ( G ) + 2 ) -coloring. The minimum positive integer k such that the Mycielskian of a cycle or a path has a proper incidence k-coloring is also determined.

Recently, an innovative hypercube-variant network called bicube, denoted as B Q n , has been proposed to possess both short diameter and symmetry advantages. Unlike other existing hypercube-variant networks, they lose their symmetry in pursuit of short diameters. For solving the problems of fault-tolerant transmission and secure message distribution in a reliable network, one solution suggested a dual-CIST (two completely independent spanning trees) to design a multi-path routing (e.g., a recently proposed secure-protection routing). We can make the construction using the standard arrangement guideline (SAG) like the hypercubes to obtain a dual-CIST with a diameter of 2 n − 1 on B Q n . This paper proposes a newly generic adjustment scheme (GAS) for reducing the diameter of the dual-CIST under this construction. As a result, the diameter of T i for i = 1 , 2 we constructed for B Q n are as follows: diam ( T i ) = { 7 if n = 4 ; 2 n − 2 if n ⩾ 5 and n is odd ; 2 n − 3 if n ⩾ 6 and n is even .

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.

Hedonic games are coalition formation games where players only specify preferences over coalitions they are part of. We introduce and systematically study three local fairness notions in hedonic games called max-min fairness, grand-coalition fairness, and min-max fairness. To this end, we define suitable threshold coalitions for these three concepts. A coalition structure (i.e., a partition of the players into coalitions) is considered locally fair if all players' coalitions in this structure are each at least as good as their threshold coalitions. Based on this approach, we then introduce three specific notions of local fairness by suitably adapting fairness notions from fair division. We show that they form a proper hierarchy and how they are related to previously studied solution concepts in hedonic games. We also study the computational aspects of finding threshold coalitions and of deciding whether fair coalition structures exist in additively separable hedonic games, and we investigate the related price of local fairness.

Reaction system is a computing model inspired by the biochemical interaction taking place within the living cells. Various extended or modified frameworks motivated by biological, physical, or purely mathematically considerations have been proposed and received significant amount of attention, notably in the recent years. This study, however, takes after particular early works that concentrated on the mathematical nature of minimal reaction systems in the context-free basic framework and motivated by a recent result on the sufficiency of strictly minimal reaction systems to simulate every reaction system. This paper focuses on the largest reaction system rank attainable by strictly minimal reaction systems, where the rank pertains to the minimum size of a functionally equivalent reaction system. Precisely, we provide a very detailed study for specific strictly minimal reaction system induced by permutations, up to the quaternary alphabet. Along the way, we obtain a general result about reaction system rank for Cartesian product of functions specified by reaction systems.

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.