Search

The first definition of space complexity for P systems was based on a hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space.

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e. do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks., SCOPUS: ar.j, info:eu-repo/semantics/published

Online sequential extreme learning machine (OS-ELM) has become a popular online learning strategy for single-hidden layer feedforward neural networks, and complex-valued signals are ubiquitous in real applications. In order to cater for complex-valued signals, especially for noncircular signals, in this paper we extend OS-ELM to complex domain, and propose two augmented online sequential complex ELM models by incorporating the conjugates of the network input and the hidden layer respectively. In this way, the proposed models are equipped with the capability to capture the complete second-order statistics of noncircular signals, which results in the enhanced generalization ability. The corresponding regularized models are derived to avoid the possible overfitting problem. By exploiting the algebra structure resulted from the augmented architecture, several approaches to reducing the computational complexity are also proposed. Simulation results validate the efficiency of the proposed algorithms.

Non-orthogonal multiple access (NOMA) has been recognized as an essential technology for beyond fifth-generation (beyond-5G) wireless networks to increase connectivity, spectral efficiency, cell-edge throughput, and user fairness. In this paper, we propose two subcarrier-user assignment algorithms (SUAAs) for the downlink NOMA system to enhance the spectral efficiency, the fairness, the data rate of weak users, and the outage probability. The assignment order of the first proposed SUAA is based on the worst subcarrier first (WSF) to avoid selecting a user with the worst channel gain with any subcarrier and called (WSF-SUAA). On the other hand, the second proposed SUAA is based on spectral efficiency maximization (SEM) and called (SEM-SUAA), but requires exhaustive search. The assignment process of both algorithms is based on making the channel gain of the selected paired users per subcarrier as high as possible to increase the data rate of each user. Besides, the assignment process of strong users for all subcarriers is performed before the assignment process of weak users to increase the total system sum-rate. It is exposed throughout the simulation that the two proposed SUAAs can attain significant improvement in the total spectral efficiency, weak user data rate, outage probability, and user fairness compared to the existing algorithms. While the performances of the two proposed SUAAs are convergent, the computational complexity of WSF-SUAA is significantly lower than that of SEM-SUAA and slightly higher than that of the existing algorithms.

The paper discusses adaptive filtering using Least Mean Square (LMS) and Recursive Least Square (RLS) algorithms. An algorithm for adjusting the coefficients of an adaptive digital filter in the Residue Number System and a procedure of developed algorithm applying depending on filter length and signal length are proposed. Mathematical modeling of the considered algorithms is performed. Examples are presented to demonstrate how the proposed technique can help the designer in the adjustment of the filter coefficients without the need for extensive trial-and-error procedures. The analysis of the denoising quality and computational complexity is made. Synthetic and real data (earthquake recording) were used while testing. The proposed algorithm surpasses the existing ones like LMS and RLS, and their modifications in a number of parameters: adaptation (denoising) quality, ease of implementation, execution time. The main difference between the developed algorithm is the sequential adaptation of each coefficient with zero error. In the known algorithms, the entire vector of coefficients is iteratively adapted, with some specified accuracy. The iterations (steps) number is determined by the input signal length for all algorithms.

In this paper we study the question of parallelization of a variant of Branch-and-Bound method for solving of the subset sum problem which is a special case of the Boolean knapsack problem. The following natural approach to the solution of this question is considered. At the first stage one of the processors (control processor) performs some number of algorithm steps of solving a given problem with generating some number of subproblems of the problem. In the second stage the generated subproblems are sent to other processors for solving (one subproblem per processor). Processors solve completely the received subproblems and return their solutions to the control processor which chooses the optimal solution of the initial problem from these solutions. For this approach we define formally a model of parallel computing (frontal parallelization scheme) and the notion of complexity of the frontal scheme. We study the asymptotic behavior of the complexity of the frontal scheme for two special cases of the subset sum problem.

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

The distributed FxLMS algorithm based on acoustic sensor networks can solve the problem of the increased computational complexity caused by a large-scale active noise control (ANC) system. Firstly, the distributed algorithm is deduced theoretically. In the ANC process based on sensor networks, the iteration of partial weight coefficients is replaced by the real-time communication of weight coefficients among nodes. Then the convergence characteristics of the distributed algorithm in its mean and mean square senses are analyzed and verified with simulation. Finally, the noise reduction effects of different algorithms are compared. The results show that the distributed algorithm, with its computational complexity reduced, can achieve the same noise reduction effects as the centralized ANC system.

11th International Conference on Algorithms and Complexity ( 2019: Rome; Italy ), Hedonic games are a prominent model of coalition formation, in which each agent’s utility only depends on the coalition she resides. The subclass of hedonic games that models the formation of general partnerships [21], where output is shared equally among affiliates, is called hedonic games with common ranking property (HGCRP). Aside from their economic motivation, HGCRP came into prominence since they are guaranteed to have core stable solutions that can be found efficiently [2]. Nonetheless, a core stable solution is not necessarily a socially desirable (Pareto optimal) outcome. We improve upon existing results by proving that every instance of HGCRP has a solution that is both Pareto optimal and core stable. We establish that finding such a solution is, however, - by proving the stronger statement that finding any Pareto optimal solution is. We show that the gap between the total utility of a core stable solution and that of the socially optimal solution (OPT) is bounded by |N|, where N is the set of agents, and that this bound is tight. Our investigations reveal that finding a solution, whose total utility is within a constant factor of that of OPT, is intractable. © 2019, Springer Nature Switzerland AG.

Despite the importance of cyber-security for networked control systems, no suitable cryptosystem exists for networked control systems that guarantees stability and has low computational complexity. This study proposes a novel dynamic ElGamal cryptosystem for encrypted control systems. The proposed cryptosystem is a multiplicative homomorphic cryptosystem, and it updates key pairs and ciphertexts by simple updating rules with modulo operations at every sampling period. Furthermore, the authors modify the proposed cryptosystem by using a dynamic encoder and decoder so that the asymptotic stability of the encrypted control systems is guaranteed. Numerical simulations demonstrate that the encrypted controller with the proposed cryptosystem achieves asymptotic stability while randomly updating key pairs and ciphertexts. The feasibility of the proposed encrypted control system is evaluated through regulation control with a positioning table testbed. The processing time of the proposed encrypted control system is on the order of milliseconds, indicating that the system achieves real-time control.

In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: PSpace-complete in general, and NLogSpace-complete for predicates of bounded arity. These complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest.

Since it was invented, Elliptic Curve Cryptography (ECC) is considered an ideal choice for implementing public key cryptography in resource constrained devices, thanks to its small keys. Scalar point multiplication is the central and the complex operation in the cryptographic computations of ECC that requires a lot of optimizations on execution time and energy consumption especially in low computing power devices such as embedded systems. Thus, many scalar point multiplication algorithms are proposed, each using their own computational techniques and mathematical formulas. In this paper, we have combined the computational techniques with some optimized mathematical formulas and we have implemented them on some Elliptic Curves scalar point multiplication algorithms over finite field. The aim of this work is to identify the most efficient algorithm that combine the best computational technique and the mathematical formulas, and consequently offer less-memory requirements and faster field arithmetic operations. The results show that Montgomery ladder algorithm in co-Z addition with update formula gives better results compared to the other algorithms implemented in this paper.

Generalized Operational Perceptron (GOP) was proposed to generalize the linear neuron model used in the traditional Multilayer Perceptron (MLP) by mimicking the synaptic connections of biological neurons showing nonlinear neurochemical behaviours. Previously, Progressive Operational Perceptron (POP) was proposed to train a multilayer network of GOPs which is formed layer-wise in a progressive manner. While achieving superior learning performance over other types of networks, POP has a high computational complexity. In this work, we propose POPfast, an improved variant of POP that signicantly reduces the computational complexity of POP, thus accelerating the training time of GOP networks. In addition, we also propose major architectural modications of POPfast that can augment the progressive learning process of POP by incorporating an information preserving, linear projection path from the input to the output layer at each progressive step. The proposed extensions can be interpreted as a mechanism that provides direct information extracted from the previously learned layers to the network, hence the term “memory”. This allows the network to learn deeper architectures and better data representations. An extensive set of experiments in human action, object, facial identity and scene recognition problems demonstrates that the proposed algorithms can train GOP networks much faster than POPs while achieving better performance compared to original POPs and other related algorithms.

The problem of computing the Sparse Fast Fourier Transform(sFFT) of a $K$ -sparse signal of size $N$ has received significant attention for a long time. The first stage of sFFT is hashing the frequency coefficients into $B(\approx {K})$ buckets named frequency bucketization. The process of frequency bucketization is achieved through the use of filters: Dirichlet kernel filter, aliasing filter, flat filter, etc. The frequency bucketization through these filters can decrease runtime and sampling complexity in low dimensions. It is a hot topic about sFFT algorithms using the flat filter because of its convenience and efficiency since its emergence and wide application. The next stage of sFFT is the spectrum reconstruction by identifying frequencies that are isolated in their buckets. Up to now, there are more than thirty different sFFT algorithms using the sFFT idea as mentioned above by their unique methods. An important question now is how to analyze and evaluate the performance of these sFFT algorithms in theory and practice. In this paper, it is mainly discussed about sFFT algorithms using the flat filter. In the first part, the paper introduces the techniques in detail, including two types of frameworks, five different methods to reconstruct spectrum and corresponding algorithms. We get the conclusion of the performance of these five algorithms, including runtime complexity, sampling complexity and robustness in theory. In the second part, we make three categories of experiments for computing the signals of different SNR, different $N$ , and different $K$ by a standard testing platform and record the run time, percentage of the signal sampled, and $L_{0},L_{1},L_{2}$ error both in the exactly sparse case and general sparse case. The result of experiments is consistent with the inferences obtained in theory. It can help us to optimize these algorithms and use them correctly in the right areas.

Radio resource management (RRM) for future fifth-generation (5G) heterogeneous networks (HetNets) has emerged as a critical area due to the increased density of small-cell networks and radio access technologies. Recent research has mostly concentrated on resource management, including spectrum utilization and interference mitigation, but the complexities of these resources have been given little attention. This paper provides an overview of the issues arising from future 5G systems and highlights their importance. The different approaches used in recently published surveys categorizing RRM schemes are discussed, and the survey method is presented. We report on a survey of HetNet RRM schemes that have been studied recently, with a focus on the joint optimization of radio resource allocation with other mechanisms. These RRM schemes were subcategorized according to their optimization metrics and qualitatively analyzed and compared. An analysis of the complexity of RRM schemes in terms of implementation and computation is presented. Several potential scopes of research for future RRM in 5G HetNets are also identified.

The alternating direction method of multipliers (ADMM) is one of most foundational algorithms for linear constrained composite minimization problems. For different specific problems, variations of ADMM (like linearized ADMM, proximal ADMM) are developed. By using the Bregman distances, lots of ADMMs can be formulated into a uniform mathematical scheme. Although variational inequalities have been well used to study ADMMs, the use for BADMM has still been missing. In this paper, we study the convergence of BADMM by variational inequalities. We present a proof framework for BADMMs. And then, we present very concise convergence proof for the basic BADMM. As applications, we consider several variations of BADMM and obtain corresponding convergence results.

Fulcrum coding combines a high-field outer Random Linear Network Coding (RLNC) that generates outer coding expansion packets with a small-field inner RLNC that combines the source packets and the outer coding expansion packets. This two-layer Fulcrum coding allows flexible decoding in receivers with heterogeneous computational capabilities. Fulcrum coding has so far only been studied for conventional dense RLNC, which randomly selects all coding coefficients, and only for a statically fixed number of outer expansion packets. However, the probability that the coding coefficient row of a newly received packet is linearly independent of prior received coding coefficient rows (a prerequisite for successful decoding) is highly dynamic. We propose to exploit the dynamics of this probability to reduce the computational complexity of Fulcrum coding. In particular, we vary the density of non-zero coding coefficients, i.e., equivalently, the sparsity of coding coefficients, and the number of outer expansion packets to keep the complexity low while maintaining a reasonably high decoding probability. We introduce the general principles of dynamic sparsity and expansion packets (DSEP) for Fulcrum coding as well as two specific example DSEP policies. Our evaluations indicate that DSEP Fulcrum can increase the encoding throughput tenfold and increase the decoding throughput 1.4 to 4.3 fold while achieving decoding probabilities that are typically less than 1% lower than the conventional Fulcrum decoding probabilities. We also find that DSEP achieves somewhat higher encoding and decoding throughputs than the CodornicesRq (Release 2.1) implementation of RaptorQ block coding for small blocks (generations) of source packets, while RaptorQ is substantially faster for large generation sizes. Furthermore, we develop and evaluate an elementary DSEP recoding mechanism that achieves a recoding throughput more than double the decoding throughput.

Cognitive radio sensor network (CRSN) is an intelligent and reasonable combination of cognitive radio and wireless sensor networks. Clustering is an effective method to manage the network topology of CRSN. In order to solve the optimal cluster head selection problem in clustering which is proved to be NP-hard, inspired by ions motion optimization (IMO) algorithm, a novel centralized clustering routing protocol, i.e., IMO-based clustering routing protocol (IMOCRP) which can adapt to the dynamic characteristics of CRSN is presented in this paper. Optimal number of clusters and identity of cluster heads are automatically determined by combining the excellent characteristics of IMO algorithm and the rich resource, comprehensive information at the sink together. Thanks to its centralized structure, IMOCRP proposed in this paper avoids excessive overhead in cluster head selection and cluster formation, which in turn helps conserve energy. Available channel list at each living node is taken into consideration to perform reasonable channel allocation for clusters, and the probability of collisions with primary users can be reduced, which promotes more successful information delivery. Simulation results have shown that IMOCRP can balance network lifetime and effective information collection capability, and it is superior to other competing protocols.

This study investigates the task assignment problem where a fleet of dispersed vehicles needs to visit multiple target locations in a time-invariant drift field with obstacles while trying to minimise the vehicles' total travel time. The vehicles have different capabilities, and each kind of vehicles can visit a certain type of the target locations; each target location might require to be visited more than once by different kinds of vehicles. The task assignment problem has been proven to be NP-hard. A path planning algorithm is first designed to minimise the time for a vehicle to travel between two given locations through the drift field while avoiding any obstacle. The path planning algorithm provides the travel cost matrix for the target assignment, and generates routes once the target locations are assigned to the vehicles. Then, a distributed algorithm is proposed to assign the target locations to the vehicles using only local communication. The algorithm guarantees that all the visiting demands of every target will be satisfied within a total travel time that is at worst twice of the optimal when the travel cost matrix is symmetric. Numerical simulations show that the algorithm can lead to solutions close to the optimal.

Here, a simplified algorithm to calculate log-likelihood ratio (LLR) for m-QAM demodulation is proposed. Traditional method calculating LLR for m-QAM demodulation is supposed to do distance computing between any two constellation points so that the high complexity of the hardware implementation is not acceptable. This simplified method is different from the traditional ways that the distance calculation between any two points in a plane can be omitted, indicating that there is an advantage in the amount of computation in this simplified method. Finally, the simplified method is compared with traditional methods from the perspective of complexity and system performance. The simulation results show that the simplified method can greatly reduce the amount of calculation and have little effect on the performance of the system.

We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic.

With precise angle measurement, traditional monopulse techniques for forward-looking imaging can acquire exact angle information of one single target within a radar beam. However, when multiple targets exist in a beam, it is difficult to resolve them. To address this problem, a novel monopulse forward-looking imaging algorithm based on Levenberg–Marquardt (LM) optimisation is proposed. The core idea of this algorithm is to solve maximum likelihood estimation problem based on LM optimisation (ML-LM) to obtain the direction of arrival (DOA) estimation of unresolved targets. First, the echo model of two targets within a forward-looking radar beam is established, then the imaging framework of the proposed algorithm is introduced. Finally, the advantages of ML-LM are illustrated based on a series of evaluation criterion, including angle measurement error for various values of signal-to-noise ratio (SNR), angle interval adaptability and computational efficiency. The simulation results show that two targets within a forward-looking radar beam can be resolved and relocated accurately utilising the proposed algorithm. Meanwhile, the comparison with other algorithms shows it has higher DOA estimation accuracy, less computational complexity and a wider range of angle interval adaptability.

The problem of DOA estimation for sub-array multiple-input multiple-output radar is concerned. Employing compressive sampling concept and the minimum mean-square error (MMSE) technology, the proposed algorithm alternates between updating sample covariance matrix and the MMSE filter bank values until convergence. Simplified array manifolds are considered to decrease the computational complexity. The core idea of the algorithm is to determine the DOA by calculating the spatial distribution of signal power adaptively. Simulation results show that the new algorithm performs well both in a wide SNR range and limited samples, compared with the MUSIC, PIAA-APES, and OGSBI algorithms. The most outstanding advantage of the new algorithm is that it can maintain high estimation accuracy under limited samples without knowing the number of targets.

Image restoration and denoising is an essential preprocessing step for almost every subsequent task in computer vision. Markov Random Fields offer a well-founded, sophisticated approach for this purpose, but unfortunately the associated computation procedures are not sufficiently fast, due to a high-dimensional optimization problem. While the increase of computing power could not solve this runtime issue appropriately, we address it in a mathematical way: we suggest an analytical solution for the optimum of the inference problem, which provides desirable mathematical properties. In practice, our new method accelerates the runtime via reducing the computational complexity of the image restoration task by orders of magnitude, independent from the smoothing intensity. As a result, Markov Random Fields can be considered for modern big data problems in computer vision, especially if numerous images with equal sizes are processed.

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.

Matrix constant false alarm rate (M-CFAR) detector based on information geometry provides a novel scheme to the detection of target in sea clutter environment for pulse Doppler radar with small bunch of pulses. The detection performance of the existing M-CFAR detectors is greatly influenced by the geometric measures on the matrix manifold. Different geometrical measures lead to different detection performance, some of which are not satisfactory. Motivated by this, the authors utilise Root-Euclidean, Power-Euclidean, Cholesky-Euclidean and new Riemannian measure to design several kinds of detection schemes, which improve the detection performance. Finally, simulation results verify that the designed detectors achieve a better detection performance with a relatively lower computational complexity.

Question-answering systems like Watson beat humans when it comes to processing speed and memory. But what happens if we compensate for this? What are the fundamental differences in power between human and artificial agents in question answering? We explore this issue by defining new computational models for both agents and comparing their computational efficiency in interactive sessions. Concretely, human agents are modeled by means of cognitive automata, augmented with a form of background intelligence which gives the automata the possibility to query a given Turing machine and use the answers from one interaction to the next. On the other hand, artificial question-answering agents are modeled by QA-machines, which are Turing machines that can access a predefined, potentially infinite knowledge base (‘advice’) and have a bounded amount of learning space at their disposal. We show that cognitive automata and QA-machines have exactly the same potential in realizing question-answering sessions, provided the resource bounds in one model are sufficient to match the abilities of the other. In particular, polynomially bounded cognitive automata with background intelligence (i.e. human agents) prove to be equivalent to polynomially bounded QA-machines with logarithmic learning space. It generalizes Pippenger's theorem on the computational power of switching circuits (without background intelligence) to a foundational result for question answering in cognitive science. The framework reveals why QA-machines have a fundamental advantage.

Target localisation using frequency diverse array (FDA) has drawn much attention owing to the additional degree of freedom in the range dimension. However, the Doppler effect was often ignored in previous FDA works because of the stationary target assumption, and in contrast, even stationary target localisation could be of quite a high computational complexity. In this study, a method is proposed that can jointly estimate range, angle, and Doppler for FDA multiple-input-multiple-output radar with low computational complexity. First, Doppler is estimated independently by utilising unstructured maximum likelihood method. Next, traditional two-dimensional (2D) MUSIC is divided into multiple one-dimensional (1D) MUSIC to estimate the angle. Then substituting the estimated angle into the former 2D MUSIC results in a 1D searching over range dimension to get the range estimation. The advantage of the proposed method was verified by simulation results.

We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation.

This study introduces a two-level strategy for efficient execution of multiple sequence alignment (MSA) of complex heterogeneous sequences. The two levels of the proposed technique are comprised of: designing the discrete firefly algorithm (DFFA) for the formation and implementation of makespan minimisation on parallel machines, followed by performing Ctrie-based caching for pairwise alignment to reduce the load on the data servers for handling multiple queries. The proposed strategy addresses a multi-client problem that aims to acquire the full advantage of the computational power of parallel connected machines. Further, it is shown that the inclusion of Ctrie as caching mechanism successively improves the performance of the system with accretion in several sequences. Performance of proposed DFFA is also compared with discrete versions of four swarm intelligence based algorithms at the criteria of makespan minimisation and the rate of convergence on two kinds of complex and diverse datasets. The work is unique in this sense: it is the first swarm-intelligence-based implementation for the addressed problem; it is so far the first approach for Ctrie based caching of the MSA on the scheduled parallel machines; hybridisation of DFFA with Ctrie for caching the MSA results is also a novel implementation.

In this study, a three-dimensional model with multi-parameter order reduction is applied to the thermal modelling of power electronics modules with complex geometries. Finite element or finite difference method can be used to establish accurate mathematical models for thermal analyses. Unfortunately, the resulting computational complexity hinders the analysis in parametric studies. This study proposes a parametric order reduction technique that can significantly increase simulation efficiency without significant penalty in the prediction accuracy. The method, based on the block Arnoldi method, is illustrated with reference to a multi-chip SiC power module mounted on a forced air-cooled finned heat sink with a variable mass flow rate.

In linear optics, photons are scattered in a network through passive optical elements including beam splitters and phase shifters, leading to many intriguing applications in physics, such as Mach–Zehnder interferometry, the Hong–Ou–Mandel effect, and tests of fundamental quantum mechanics. Here we present the fundamental limit in the transition amplitudes of bosons, applicable to all physical linear optical networks. Apart from boson sampling, this transition bound results in many other interesting applications, including behaviors of Bose–Einstein condensates (BEC) in optical networks, counterparts of Hong–Ou–Mandel effects for multiple photons, and approximating permanents of matrices. In addition, this general bound implies the existence of a polynomial-time randomized algorithm for estimating the transition amplitudes of bosons, which represents a solution to an open problem raised by Aaronson and Hance (Quantum Inf Comput 2012; 14: 541–59). Consequently, this bound implies that computational decision problems encoded in linear optics, prepared and detected in the Fock basis, can be solved efficiently by classical computers within additive errors. Furthermore, our result also leads to a classical sampling algorithm that can be applied to calculate the many-body wave functions and the S-matrix of bosonic particles.

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data-driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithm based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (with respect to the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state of the art. Our experimental work extensively covers various scenarios ranging from bandit settings to multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability. IEEE

Revealed preference theory is a domain within economics that studies rationalizability of behavior by (certain types of) utility functions. Given observed behavior in the form of choice data, testing whether certain conditions are satisfied gives rise to a variety of computational problems that can be analyzed using operations research techniques. In this survey, we provide an overview of these problems, their theoretical complexity, and available algorithms for tackling them. We focus on consumer choice settings, in particular individual choice, collective choice and stochastic choice settings.

The modular multilevel converter (MMC) with large-scale sub-modules has the advantage of simpler modulation, lower switching frequency, and lower harmonic component, thus would be very promising in voltage source converter (VSC)–high voltage direct current transmission systems. Conventional capacitor voltage balancing algorithm suffers from insufficient grouping and sorting techniques. Therefore, it might result in excessive computation and high switching frequency of power electronic devices. To address the problem, a modified capacitor voltage balancing sorting algorithm is proposed in this paper. The proposed algorithm could avoid sorting all the module capacitor voltages by selecting only a certain number of the largest or smallest module capacitor voltages, and thus reduces time complexity greatly without losing control precision. Furthermore, the proposed algorithm focuses on the sub-modules whose capacitor voltage exceeds the limits, while the switching states of the other sub-modules are maintained to some degrees by employing the maintaining factor. Therefore, the switching frequency of the power electronic devices is further reduced. The performance of the proposed algorithm is evaluated through a time-domain MMC–HVDC simulation in PSCAD/EMTDC. Results show that the proposed algorithm is able to balance the module voltage with lower computation and reduce the switching frequency of power devices significantly, without noticeably increasing the capacitor voltage ripples.

Regularized zero forcing (RZF) precoding is an efficient linear precoding scheme for combating interference in a single-cell massive multiple-input-multiple-output (MIMO) systems. Inaccurate channel state information (CSI) due to channel aging will reduce the performance of the precoder over time. The channel aging determines how often we need to estimate the channels, and thus how frequently we need to send pilots in order to maximize the overall data rate. Channel prediction is one way to improve the CSI accuracy in the downlink, without having to send new pilots but it requires frequent re-computation of the matrix inverse in the RZF precoder, which has high-computational complexity. In this paper, we consider massive MIMO-OFDM systems and propose an algorithm called inverse extrapolation that extrapolates the channel and inverse matrix coefficients separately. The RZF coefficients are then obtained with comparably low complexity with no need for matrix inversion. We compare this algorithm with the traditional way of computing the RZF coefficients through prediction of the channel matrix followed by matrix inversion. The simulation results show that the two predictors have the same performance when the number of antennas is large, and thus the proposed scheme is preferable since it can reduce the complexity. For example, a scenario is shown, where the complexity is reduced by 61.84% without a significant degradation in performance. Funding Agencies|Beijing Natural Science Foundation [L182038]; National Natural Science Foundation for Distinguished Young Scholars of China [61325006]; Swedish Research Council (VR); ELLIIT

The planning and scheduling of container terminal logistics systems (CTLS) are the multi-objective and multiple strong constraints combinatorial optimization challenges under the uncertain environments, and those are provided with high goal orientation, dynamics, context-sensitivity, coupling, timeliness, and complexity. The increasingly sophisticated decision-making for CTLS is one of the most pressing problems for the programming and optimization method available. This paper discusses CTLS in terms of logistics generalized computation complexity based on computational thinking, great principles of computing, and computational lens, which three are abbreviated with 3CTGPL, and makes a definition of container terminal oriented logistics generalized computational complexity (CTO-LGCC) and container terminal logistics generalized computation comprehensive performance perspective (CTL-GCCPP) from the dimensions of time, space, communication, processor, and memory access. Both can analyze, generalize, migrate, translate, localize, modificate, and evaluate the above-complicated problems and lay solid foundations and establish a feedback improvement framework for the computational model and scheduling algorithms of the CTLS, which is an essential complement to the modeling and optimization methodology and solutions to CTLS with computational logistics. Finally, aimed at the logistics service cases for a large-scale container terminal, the simulation is designed and implemented for different scheduling algorithms, and the qualitative and quantitative comprehensive analysis is executed for the concomitant CTO-LGCC that demonstrates and verifies the feasibility and credibility of the CTO-LGCC and CTL-GCCPP from the viewpoint of the practice of container terminal decision-making support on the tactical level.

We propose SmartGrid, a new video-retargeting method that preserves a shape of the salient object and maintains a temporal coherence for the static background regions in the video. Previous methods mainly focus on preserving the shape of the salient object or maintaining the temporal coherence for each region. However, these methods do not explicitly adjust the sizes of the grids corresponding to the salient objects and the static background regions. Thus, they have difficulty in maintaining the consistency of the salient object shape and the temporal coherence for the static background regions. The basic idea of SmartGrid is to maintain the consistency of the contents in consecutive frames by analyzing the degree of the spatiotemporal consistency. Compared to the best results obtained using eight previous methods, SmartGrid achieved improvements of 1.19× in Bidirectional Similarity Measure, 7.59× in Jittery Metric 1, and 13.16× in Jittery Metric 2, and reduced the average computation time per pixel by 6.14×.

The Fermat method is considered to be the best for factorization of numbers N=p×q in case of close p and q. Computational complexity of the basic algorithm of the method is determined by the number of check values of X when solving equation Y2=X2‑N, as well as by complexity of the arithmetic operations. To reduce it, it is proposed to consider admissible those of test values X, for which (X2–N)modbb is quadratic residue modulo bb, called basic. Application of basic foundation of module bb makes it possible to decrease the number of check X by the number of times, close to Z=bb/bb*, where bb* is the number of elements of set Т of the roots of equation (Ymodb)2modb=((Xmodb)2–Nmodb)modb, and Z is the acceleration coefficient.It was determined that magnitude Z(N, bb) is affected by the value of residues Nmodp (at p=2, Nmod8 residues are used). The statement of the problem of finding bb with a maximum Z(N, bb) at restrictions for the amount of memory of the computer, where exponents of prime numbers – multipliers bb – are determined, and the method of its solution were proposed.To decrease the number of arithmetic operations with big numbers, it was proposed that instead of them to perform the operations with the values of differences between the nearest values of elements T. Then arithmetic operations of multiplication and addition with big numbers are performed only in rare cases. And if we derive the square root of X2–N only in cases, where the values of (X2–N)modb will be quadratic residues for many foundations of module b, other than bb, the computational complexity of this operation can be neglected.It was established that the proposed modified algorithm of the Fermat method for numbers 21024 ensures a decrease in computational complexity compared to the basic algorithm on average by 107 times, Метод Ферма считается лучшим при факторизации чисел N=p×q в случае близьких p и q. Вычислительная сложность базового алгоритма метода определяется количеством пробных значений Х при решении уравнения Y2=X2‑N, а также сложностью арифметических операций. Для ее снижения предлагается в качестве допустимых рассматривать те из пробных Х, для которых (X2-N)modbb является квадратичным остатком по модулю bb, названного базовым. Применение базового основания модуля bb позволяет уменшить число пробных Х в число раз, близкое к Z=bb/bb*, где bb* – число элементов множества Т корней уравнения (Ymodb)2modb=((Xmodb)2-Nmodb)modb, а Z – коэффициент ускорения.Определено, что на величину Z(N,bb) влияют значения остатков Nmodp (при р=2 используются остатки Nmod8). Предложена постановка задачи поиска bb с максимальным Z(N,bb) при ограничениях на объем памяти ЭВМ, где определяются показатели степеней простых чисел – множителей bb, и способ ее решения.Для уменьшения числа арифметических операций с большими числами предложено вместо таких выполнять операции со значениями разностей между ближайшими значениями элементов Т. Тогда арифметические операции умножения и сложения с большими числами выполняются только в редких случаях. А если квадратный корень из X2-N определять только в случаях, когда значения (X2-N)modb будут квадратичными остатками для многих оснований модуля b, отличных от bb, то вычислительной сложностью этой операции можно пренебречь.Установлено, что тогда предложенный модифицированный алгоритм метода Ферма для чисел 21024 обеспечивает снижение вычислительной сложности по сравнению с базовым алгоритмом в среднем в 107 раз, Метод Ферма вважається кращим при факторизації чисел N=p×q у випадку близьких p і q. Обчислювальна складність базового алгоритму методу визначається кількістю пробних значень Х при вирішенні рівняння Y2=X2‑N, а також складністю арифметичних операцій. Для її зниження запропоновано в якості допустимих розглядати ті з пробних Х, для яких (X2-N)modbb є квадратним залишком по модулю bb, названого базовым. При використанні базової основи модуля bb число пробних Х зменшується в число раз, близьке до Z(N,bb)=bb/bb*, де bb* – число елементів множини Т коренів рівняння (Ymodb)2modb=((Xmodb)2-Nmodb)modb, а Z – коефіцієнт прискорення.Визначено, що на величину Z(N,bb) впливають значения залишків Nmodp (при р=2 використовуються залишки Nmod8). Запропоновано постановку задачі пошуку bb з максимальным Z(N,bb) при обмеженях на обсяг пам’яті ЕОМ, де визначаються показники степенів простих чисел – множників bb, та спосіб її вирішення.Для зменшення числа арифметичних операцій з великими числами попонується замість таких виконувати операції зі значеннями різниць між найближчими значеннями елементів множини Т. Тоді арифметичні операції множення і додавання з великими числами виконуються рідко. А якщо квадратний корінь з X2-N визначати тільки у випадках, коли значення (X2-N)modb будуть квадратними залишками для багатьох різних основ модуля b, то обчислювальною складністю цієї операції можна знехтувати.Встановлено, що тоді запропонований модифікований алгоритм методу Ферма для чисел 21024 забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 107 раз

Generalized spatial modulation (GSM) maps its information to the index of the transmit antenna combination, making simultaneous transmission of multiple symbol possible. However, SM outperform GSM scheme in terms of error performance of the same data rate, due to average power effect. Transmit and receive diversity or the combination of both allow huge improvement in mimo systems in terms of error performance. In this paper, we investigate a near optimal low-complexity Euclidean distance antenna selection (LC-EDAS) technique in GSM system, to further improve the performance of the conventional GSM system. The LC-EDAS technique independently search across signal and spatial dimension to eliminate the worse channel prior to transmission. Secondly, we investigate a sub-optimal low-complexity transmit antenna selection (LCTAS) in the GSM system to further reduce the computational complexity (CC) imposed by LC-EDAS. The Monte Carlo simulation results obtained reveals a trade-off between the GSM scheme with LC-EDAS and GSM scheme with sub-optimal transmit antenna selection in terms of error performance and CC. ABSTRAK: Modulasi Spatial Keseluruhan (GSM) menghubung informasi kepada indeks kombinasi antena yang dipancarkan, membuatkan pemancaran keseluruhan simbol dapat dilakukan. Walau bagaimanapun, SM lebih bagus daripada skim GSM pada prestasi kesilapan pada kadar data yang sama, kerana kesan purata kuasa. Kepelbagaian penghantaran dan penerimaan ataupun kombinasi keduanya memberi pembaharuan yang lebih besar dalam sistem mimo pada prestasi kesalahan. Penyelidikan ini akan mengkaji optima terdekat Euclidean kurang rumit, melalui teknik (LC-EDAS) pilihan jarak antenna dalam sistem GSM, bagi menambah prestasi sistem GSM sedia ada. Teknik LC-EDAS secara sendiri mencari signal dan dimensi separa bagi mengurangkan saluran lebih teruk semasa penghantaran. Kedua, kami mengkaji sub-optima proses pemilihan kurang rumit penyebaran antena (LCTAS) dalam sistem GSM bagi mengurangkan kerumitan pengiraan (CC) yang dikenakan oleh LC-EDAS. Keputusan simulasi Monte Carlo yang diperoleh menunjukkan timbangan antara skim GSM dan LC-EDAS dan skim GSM bersama sub-optima proses pemilihan penyebaran antena berdasarkan kesilapan prestasi dan CC.

The characteristics of the pole-to-pole fault in the tree-structured DC system are complicated, and the transient analytic expressions of high-order current and voltage can make the calculation difficulty increase significantly. In response to this phenomenon, on the one hand, when the parameters are the same, the impact of the changes of the number about the terminals on the waveform is considered. On the other hand, when the number of terminals is fixed, the influence of the change of the parameter on the waveform is studied. Taking the interaction between different ports into account, correct the short-circuit current and voltage expression of single-ended DC system and the calculation method of short-circuit current and voltage expression for multi-ended DC system is proposed. This method can reduce the computational complexity of transient expression for multi-ended DC system. The calculation results are verified by MATLAB/Simulink simulation tool. The calculated transient expressions of voltage and current are in good agreement with the results of simulation, which provide the theoretical basis for the fault location and calculation of setting value.

We consider two variations of graph total domination, namely, k-tuple total domination and total {k}-domination (for a fixed positive integer k). Their related decision problems are both NP-complete even for bipartite graphs. In this work, we study some subclasses of bipartite graphs. We prove the NP-completeness of both problems (for every fixed k) for bipartite planar graphs and we provide an APX-hardness result for the total domination problem for bipartite subcubic graphs. In addition, we introduce a more general variation of total domination (total (r,m)-domination) that allows us to design a specific linear time algorithm for bipartite distance-hereditary graphs. In particular, it returns a minimum weight total {k}-dominating function for bipartite distance-hereditary graphs. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentina

Objective: The 2017 PhysioNet/CinC Challenge focused on automatic classification of atrial fibrillation (AF) in short ECGs. This study aimed to evaluate the use of the data and results from the challenge for detection of AF in longer ECGs, taken from three other PhysioNet datasets. Approach: The used data-driven models were based on features extracted from ECG recordings, calculated according to three solutions from the challenge. A Random Forest classifier was trained with the data from the challenge. The performance was evaluated on all non-overlapping 30 s segments in all recordings from three MIT-BIH datasets. Fifty-six models were trained using different feature sets, both before and after applying three feature reduction techniques. Main Results: Based on rhythm annotations, the AF proportion was 0.00 in the MIT-BIH Normal Sinus Rhythm (N = 46083 segments), 0.10 in the MIT-BIH Arrhythmia (N = 2880), and 0.41 in the MIT-BIH Atrial Fibrillation (N = 28104) dataset. For the best performing model, the corresponding detected proportions of AF were 0.00, 0.11 and 0.36 using all features, and 0.01, 0.10 and 0.38 when using the 15 best performing features. Significance: The results obtained on the MIT-BIH datasets indicate that the training data and solutions from the 2017 Physionet/Cinc Challenge can be useful tools for developing robust AF detectors also in longer ECG recordings, even when using a low number of carefully selected features. The use of feature selection allows significantly reducing the number of features while preserving the classification performance, which can be important when building low-complexity AF classifiers on ECG devices with constrained computational and energy resources.

Nature-inspired computing is a type of human-designed computing motivated by nature, which is based on the employ of paradigms, mechanisms, and principles underlying natural systems. In this article, a versatile and vigorous bio-inspired branch of natural computing, named membrane computing is discussed. This computing paradigm is aroused by the internal membrane function and the structure of biological cells. We first introduce some basic concepts and formalisms of membrane computing, and then some basic types or variants of P systems (also named membrane systems ) are presented. The state-of-the-art computability theory and a pioneering computational complexity theory are presented with P system frameworks and numerous solutions to hard computational problems (especially NP -complete problems) via P systems with membrane division are reported. Finally, a number of applications and open problems of P systems are briefly described.

The partial transmit sequences (PTS) is regarded as a promising scheme for inhibiting ‎the high peak-to-average power ratio (PAPR) problem in the orthogonal frequency division ‎multiplexing (OFDM) systems. The PTS scheme relies on partitioning the ‎data sequence into subsets and weighting these subsets by a group of the phase rotation ‎factors. Although the PTS can efficiently reduce the high PAPR value, a great ‎computational complexity (CC) level restricts the utilization of the PTS scheme in practical ‎applications. In PTS, there are three common types of segmentation schemes; ‎interleaving (IL-PTS), pseudo-random (PR-PTS), and adjacent (Ad-PTS) schemes. This ‎paper presents a new algorithm named hybrid pseudo-random and interleaving cosine wave shape ‎‎(H-PRC-PTS) by combining the PR-PTS scheme and the symmetrical ‎interleaving cosine wave shape (S-IL-C-PTS) scheme which was proposed in our previous ‎work. The results indicate that the suggested algorithms can ‎diminish the PAPR value like the PR-PTS scheme, whereas the CC level is reduced significantly.

Virtually all molecular interaction networks (MINs), irrespective of organism or physiological context, have a majority of loosely-connected ‘leaf’ genes interacting with at most 1-3 genes, and a minority of highly-connected ‘hub’ genes interacting with at least 10 or more other genes. Previous reports proposed adaptive and non-adaptive hypotheses describing sufficient but not necessary conditions for the origin of this majority-leaves minority-hubs (mLmH) topology. We modeled the evolution of MINs as a computational optimization problem which describes the cost of conserving, deleting or mutating existing genes so as to maximize (minimize) the overall number of beneficial (damaging) interactions network-wide. The model 1) provides sufficient and, assuming , necessary conditions for the emergence of mLmH as a software adaptation to circumvent computational intractability, 2) predicts the percentage number of genes having d interacting partners, and 3) when employed as a fitness function in an evolutionary algorithm, produces mLmH-possessing synthetic networks whose degree distributions match those of equal-size MINs.SummaryOur results indicate that the topology of molecular interaction networks is a selected-for software adaptation that minimizes the evolutionary cost of re-wiring the network in response to an evolutionary pressure to conserve, delete or mutate existing genes and interactions.

Weak reflected signal is one of the main problems in a recent developing remote sensing tool&mdash, passive GNSS-based radar (GNSS radar). To address this issue, an enhanced GNSS radar imaging scheme on the basis of coherently integrating multiple satellites is proposed. In the proposed scheme, to avoid direct signal interference at surveillance antenna, the satellites that used as transmission of opportunity are in backscattering geometry model. To coherently accumulate echo signal magnitudes of the scene center in the targeted sensing region illuminated by the selected satellites, after performing the paralleled range compressions, a coordinates alignment operator is performed to the respective range domains, in which, pseudorandom noise (PRN) code phases are aligned. Thereafter, the coordinates aligned range compressed signals of the selected satellites are coherently integrated along azimuth domain so that imaging gain is improved and azimuth processing can be accomplished in only one state operation. The theoretical analysis and field proof-of-concept experimental results indicate that compared to both conventional bistatic imaging scheme and the state-of-the-art multi-image fusion scheme, the proposed scheme can provide a higher imaging gain, compared to the state-of-the-art multi-image fusion scheme, the proposed scheme has a less computational complexity and faster algorithm speed.

© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds, over the embedding of batch-processing workloads to the embedding of service function chains and come with different mapping restrictions for nodes and edges. The restrictions studied most often are node and edge capacities, node mapping and edge routing policies, and latency restrictions. While the VNEP has been studied intensively, complexity results are only known for specific models and this paper provides a first comprehensive study of the computational complexity of the VNEP by systematically analyzing its hardness for any combination of the above stated node and edge mapping restrictions. For all studied variants the NPcompleteness of their respective decision problems is shown. Furthermore, NP-completeness results for finding approximate embeddings, which may, e.g., violate capacity constraints by certain factors, are derived. Lastly, it is also shown that all these results pertain when restricting the request graphs to planar and degree-bounded graphs. While theoretic in nature, our results have severe practical implications. Firstly, any optimization variant of the VNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P=NP holds. Secondly, we uncover structural hardness properties: the VNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.

The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels., Comment: Extended version of a paper accepted to LATA 2020