Search

Over the last decades, scheduling theory has been put into practice so as to tackle production process as a combinatorial optimisation problem and specifically as a PFSP (Permutation Flowshop Scheduling Problem). Often, NP-completeness of PFSP leads numerous research towards suggesting heuristic algorithms. The objective is to propose an optimal or near-to-optimal order of n jobs processing on m machines with a minimum completion time of all jobs. In this paper, a two-phase heuristic algorithm will be presented, named IFRS (Improved FRS). FRS, within the first phase, is going to be used to find a superior order of jobs out of Taillard's instances; then the order of jobs will be improved again in phase 2. While running IFRS, a completely new idea, named Pixelation of time matrices, will be used for the very first time and provide a final pattern, which can be used in any heuristic algorithm with makespan criterion. After using the hard benchmark instances of Taillard, the superiority of IFRS over 20 algorithms is going to be shown by tables and statistical graphics. Due to its low makespan values, IFRS benefits flow production, as does NEH. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , a non-empty set A of k distinct vertices, is called a k - attack on G. The vertices in the set A are considered to be under attack. A set D ⊆ V can defend or counter the attack A on G if there exists a one-to-one function f : A ⟼ D , such that either f (u) = u or there is an edge between u , and its image f (u) , in G. A set D is called a k - defensive dominating set if it defends against any k -attack on G. Given a graph G = (V , E) , the minimum k -defensive domination problem requires us to compute a minimum cardinality k -defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D ⊆ V is a k -defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain, and threshold graphs for any k. This paper mainly focuses on the problem when k > 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs; this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We establish a lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k -defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k > 0. Towards the end, we study a relationship between the defensive domination number and another well-studied domination parameter. [ABSTRACT FROM AUTHOR]

Nowadays, high energy amount is being wasted by computing servers and personal electronic devices, which produce a high amount of carbon dioxide. Thus, it is required to decrease energy usage and pollution. Many applications are utilised by green computing to save energy. Scheduling of tasks acts as an important process to reach the mentioned goals. It is worth stating that the vital characteristic of task scheduling in green clouds is the load balancing of tasks on virtual machines. Efficient load balancing moves tasks from overloaded to underloaded virtual machines to maintain the Quality of Service (QoS). This issue is an NP-complete problem, so this research suggests a new technique based on the behavioural structure of artificial bee behaviour. This method aims to improve QoS while lowering energy usage in green computing. In addition, the honey bees are considered the removed tasks from overloaded virtual machines and a candidate for migrating selected tasks with the lowest priority. The CloudSim testing findings demonstrate that the technique is successful in QoS, makespan, and energy usage compared to other ways. [ABSTRACT FROM AUTHOR]

The Vertex Graph Coloring problem (VGC ) is a well-known difficult combinatorial optimization problem. It is one of Karp's 21 NP-complete problems. It consists in assigning a color to each vertex of a graph in such a way that any two neighboring vertices do not share the same color, and the number of the used colors is minimized. VGC is used to solve a variety of real-world problems such as time tabling and scheduling, radio frequency assignment, and computer register allocation. To deal with this problem on large graphs, the emerging large graph processing frameworks are an excellent promising candidate. Giraph is one of the most popular large graph processing frameworks both in industry and academia. In this work, two novel graph coloring algorithms are introduced. These algorithms designed to reap the benefit of the simple parallelization model offered by any vertex-centric frameworks, such as Giraph. The algorithms are based on well-known sequential heuristic techniques namely Largest-First (LF) and Saturation Largest-First (SLF). We have compared the performances of the proposed algorithms to previous Giraph based graph coloring algorithms, with regard to their solution quality and executing time, using benchmark graphs from the SNAP library. The obtained experimental results have revealed that the proposed algorithms are much more efficient than the existing Giraph algorithms. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V, a dominating set S ⊆ V is a co-secure dominating set of G if for every vertex u ∈ S , there is a vertex v ∈ V \ S adjacent to u such that (S \ { u }) ∪ { v } is a dominating set of G. The minimum co-secure dominating set (or, for short, MCSDS) problem asks to find an MCSDS in a given graph. In this paper, first we show that the decision version of the problem is NP-complete in grid graphs and supergrid graphs. Consequently, we show that the problem remains NP-complete for unit disk and unit square graphs. Secondly, we show that the MCSDS problem is APX-hard in d-box graphs for any fixed integer d ≥ 2 . Finally, we give an O (n + m) time 2 (t - 1) -approximation algorithm for the MCSDS problem in several geometric intersection graphs which are K 1 , t -free for some integer t ≥ 3 . [ABSTRACT FROM AUTHOR]

Let i be a positive integer, an i -star denoted by S i is a complete bipartite graph K 1 , i. An { S 2 , S 3 } -packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 2-star or a 3-star. The maximum { S 2 , S 3 } -packing problem is to find an { S 2 , S 3 } -packing of a given graph containing the maximum number of vertices. The { S 2 , S 3 } -factor problem is to answer whether there is an { S 2 , S 3 } -packing containing all vertices of the given graph. The { S 2 , S 3 } -factor problem is NP-complete in cubic graphs. In this paper we design a quadratic-time algorithm for finding an { S 2 , S 3 } -packing of G that covers at least thirteen-sixteenths of its vertices with only a few exceptions. We also present some (2 , 3) -regular graphs with their maximum { S 2 , S 3 } -packings covering exactly thirteen-sixteenths of their vertices. [ABSTRACT FROM AUTHOR]

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and meta-heuristic sequencing, which has the problems of complex solving rules and high time cost. In this study, the similarity measurement method based on the twin neural network model is used to evaluate the similarity of pieces in the source task and the target task. The reusability evaluation of packing tasks is designed to select appropriate source task knowledge. The transfer operator is used to transfer the piece sequence knowledge from the source task to complete the reuse of packing knowledge in the target task. The bottom-left algorithm is improved to complete the placement of 2D irregular pieces. The computational experiments show that the proposed algorithm for the bin packing problem using knowledge reuse and improved heuristic (KRIH) has good robustness. The KRIH algorithm can obtain 8 equal or better results on 16 instances in a relatively short time compared with some classical heuristic algorithms, which has good application potential. [ABSTRACT FROM AUTHOR]

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph G = (V,E) is function f : V →{0, 1, 2, 3, 4} having the property that (i) if f(v) = 0, then v must have either a neighbor assigned 4 or two neighbors one of which is assigned 3 and the other at least 2 or v has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if f(v) = 1, then v must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if f(v) = 2, then v must have one neighbor assigned at least 2. The weight of an OI[3]RDF is the sum of its function value over the whole set of vertices, and the outer-independent triple Roman domination number of G is the minimum weight of an OI[3]RDF on G. In this paper, we continue the study of outer-independent triple Roman domination number of graphs by first presenting two sharp lower bounds for the outer-independent triple Roman domination number of trees. Then we strengthen the NP-complete result of the outer-independent triple Roman domination problem for bipartite graphs by showing that the problem remains NP-complete for a subclass of bipartite graphs, namely tree convex bipartite graphs, where two special trees are considered. [ABSTRACT FROM AUTHOR]

Given a graph G without isolated vertices, a function f : V (G) → { 0 , 1 , 2 } is a covering total Italian dominating function if (i) the set of vertices labeled with 0 forms an independent set; (ii) every vertex labeled with 0 is adjacent to two vertices labeled with 1 or to one vertex labeled with 2; and (iii) the set of vertices labeled with 1 or 2 forms a total dominating set. The covering total Italian domination number of G is the smallest possible value of the sum ∑ v ∈ V (G) f (v) among all possible covering total Italian dominating functions f on V (G). The concepts above are introduced in this article, and the study of its combinatorial and computational properties is initiated. Specifically, we show several relationships between such parameter and other domination related parameters in graphs. We also prove the NP-completeness of the related decision problem for bipartite graphs, and present some approximation results on computing our parameter. In addition, we compute the exact value of the covering total Italian domination number of some graphs with emphasis on some Cartesian products. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

Proper edge 3-coloring of a cubic graph is an NP-complete problem, which can be used in order to model several interesting practical problems. A method for correct and efficient assigning of variables used in the program to registers of the system, scheduling of a set of tasks to a set of processors while each task has to be executed on a number of processors simultaneously, or frequency assignment of radio stations without interference are all typical instances of problems modelled by graph coloring. When considering cubic graphs, which consist of vertices incident to precisely three edges, we can identify two distinct graph groups divided by their chromatic index, a minimal number of colors needed for the proper coloring of such graph. In the research presented in this article, we conduct a comparative study of the effectiveness of machine learning classifiers in the task of determining the chromatic index of cubic graphs, present an evaluation of the accuracy and precision of these models, and use the Shapley Additive Explanations model for the identification of graph attributes and their values crucial in the models' decision making. [ABSTRACT FROM AUTHOR]

Perfect Roman Dominating Functions and Unique Response Roman Dominating Functions are two ways to translate perfect code into the framework of Roman Dominating Functions. We also consider the enumeration of minimal Perfect Roman Dominating Functions and show a tight relation to minimal Roman Dominating Functions. Furthermore, we consider the complexity of the underlying decision problems Perfect Roman Domination and Unique Response Roman Domination on special graph classes. For instance, split graphs are the first graph class for which Unique Response Roman Domination is polynomial-time solvable, while Perfect Roman Domination is NP-complete. Beyond this, we give polynomial-time algorithms for Perfect Roman Domination on interval graphs and for both decision problems on cobipartite graphs. However, both problems are NP-complete on chordal bipartite graphs. We show that both problems are W [ 1 ] -complete if parameterized by solution size and FPT if parameterized by the dual parameter or by clique width. [ABSTRACT FROM AUTHOR]

The problem of nesting frequently arises in the industrial environment, and it has a strong ecological and economic impact in the manufacturing processes. It basically consists of placing a set of pieces (polygons) on a material sheet, making sure that the pieces do not overlap and that they do not exceed the boundaries of the sheet. With regard to irregular 2D polygons, the problem is NP-complete. Therefore, different heuristics have been developed so as to cope with the problem. In this paper, the application of the Jaya metaheuristic algorithm to the nesting problem is proposed. This algorithm has been already applied to several engineering problems and has generally demonstrated better results than most metaheuristic algorithms. In this paper, the Jaya algorithm has been adapted to the specific features of the nesting problem so as to optimize the placement of pieces on a sheet, with the objective of minimizing material waste and computational time. The results of our experimentation demonstrate the algorithm's effectiveness in reducing the convex hull area across various datasets, showing potential in solving complex, irregular shape nesting problems. This research provides a new application of the Jaya algorithm and opens ways for future work in optimization techniques and parameter-free heuristic algorithms for nesting. [ABSTRACT FROM AUTHOR]

We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous nondeterministic polynomial-time complete (NP-complete) problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented. [ABSTRACT FROM AUTHOR]

The task scheduler belongs to the NP-complete problem, so it is very challenging in the cloud environment to develop one with reasonable performance and computation speed. Several studies take into account some important factors of the users or providers when addressing cloud task scheduling. This paper models cloud task scheduling as a Multi-objective Optimization Problem (MOP) that maximizes load balancing and execution times. Based on ring topology, we present a new multi-objective particle swarm optimization approach that utilizes intuitionistic fuzzy set to enhance evenness and diversity. The diversity and spread of the Pareto solution is adjusted using a Balanced Intuitionistic Fuzzy Crowding-Distance (BIF-CD) and Intuitionistic Fuzzy non-dominance sorting (IF-dominance). In order to identify the best compromise solution and in decision space and adjust evenness in objective space, ring topology is employed to identify a larger number of Pareto-optimal solutions. Experimental results for 25 benchmark multi-objective functions demonstrate the superiority of the proposed IF-MO-Ring-PSO over four state-of-the-art algorithms. We compare different quantitative measures to assess the uniformity and quality of Pareto fronts (PFs) found by our compared methods. The performance of the proposed method is evaluated on the benchmark test suites ZDT, DTLZ, CF, mDTLZ, and MMF, using the delta and space metrics and the progression metrics. According to the proposed method, ZDT test suite reduced space and delta metric by 13.36 and 15.11% respectively compared to other methods. The Wilcoxon's test and two-sample Mann Whitney's test are used to analyze the performance of proposed method on CF test suit. The analysis shows that the proposed method has better ability to generate quality PF with uniformity on constraint test suits. In comparison to four scheduling algorithms, the proposed scheduler also shows better performance according to load balancing, makespan, and resource utilization based on two datasets (i.e., HCSP and GoCJ). [ABSTRACT FROM AUTHOR]

A vertex v of a simple graph G = (V , E) ve-dominates every edge incident to v as well as every edge adjacent to these incident edges. A set D ⊆ V is a total vertex-edge dominating set if every edge of E is ve-dominated by a vertex of D and the subgraph induced by D has no isolated vertex. The total vertex-edge domination problem is to find a total vertex-edge dominating set of minimum cardinality. In this paper, we first show that the total vertex-edge domination problem is NP-complete for chordal graphs. Then we provide a linear-time algorithm for this problem in trees. Moreover, we show that the minimum total vertex-edge domination problem cannot be approximated within (1 −) ln | V | for any > 0 unless NP ⊆ DTIME (| V | O (log log | V |) ). Finally, we prove that the minimum total vertex-edge domination problem is APX-complete for bounded-degree graphs. [ABSTRACT FROM AUTHOR]

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k, and the task is to partition the vertex set into k nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821--2837] initiated the study of FPT-approximation for the Min k-Cut problem and gave a 1.9997-approximation algorithm running in time 2\scrO (k6)n\scrO (1). Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113--123] designed a (1 + \epsilon)-approximation algorithm that runs in time (k/\epsilon)\scrO (k)nk+\scrO (1) and a 1.81-approximation algorithm running in time 2\scrO (k2)n\scrO (1). More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990--999] gave a (5/3+\epsilon)-approximation for Min k-Cut running in time 2\scrO (k2 log k)n\scrO (1). In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every \epsilon > 0, the algorithm obtains a (1 + \epsilon)-approximate solution in time (k/\epsilon)\scrO (k)n\scrO (1). The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s\scrO (k)n\scrO (1) on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest. [ABSTRACT FROM AUTHOR]

A cloud load balancer should be proficient to modify it's approach to handle the various task kinds and the dynamic environment. In order to prevent situations where computing resources are excess or underutilized, an efficient task scheduling system is always necessary for optimum or efficient utilization of resources in cloud computing. Task Scheduling can be thought of as an optimization problem. As task scheduling in the cloud is an NP-Complete problem, the best solution cannot be found using gradient-based methods that look for optimal solutions to NP-Complete problems in a reasonable amount of time. Therefore, the task scheduling problem should be solved using evolutionary and meta-heuristic techniques. This study proposes a novel approach to task scheduling using the Cuckoo Optimization algorithm. With this approach, the load is effectively distributed among the virtual machines that are available, all the while keeping the total response time and average task processing time(PT) low. The comparative simulation results show that the proposed strategy performs better than state-of-the-art techniques such as Particle Swarm optimization, Ant Colony optimization, Genetic Algorithm and Stochastic Hill Climbing. [ABSTRACT FROM AUTHOR]

A pendant vertex is one of degree one and an isolated vertex has degree zero. A neighborhood star-free (NSF for short) graph is one in which every vertex is contained in a triangle except pendant vertices and isolated vertices. This class has been considered before for several contexts. In the present paper, we study the complexity of the dominating induced matching (DIM) problem and the perfect edge domination (PED) problem for NSF graphs. We prove the corresponding decision problems are NP-Complete for several of its subclasses. As an added value of this study, we show three connected variants of planar positive 1in3SAT are also NP-Complete. Since these variants are more basic in complexity theory context than many graph problems, these results can be useful to prove that other problems are NP-Complete. [ABSTRACT FROM AUTHOR]

An r-dominating set (r-total dominating set) of G is a subset S of V (G) for which Nr(u)∩S is non-empty for all u not in S (for all u in V (G)). An r-locating-dominating set (r-locating-total dominating set) of G is an r-dominating set (r-total dominating set) S of G for which Nr(u) ∩S is different from Nr(v) ∩S for all u and v not in S. This paper presents an extension of the locating-total dominating set of G. Further, we establish a lower bound on r-locating-dominating set and r-locating-total dominating set for k-regular graphs, as well as demonstrate that r-locating-total dominating set is an NP-complete problem. Furthermore, the r-locating-dominating set and r-locating-total dominating set problems are discussed for some standard graphs. [ABSTRACT FROM AUTHOR]

One of the primary challenges in distributed systems, such as cloud computing, lies in ensuring that data objects are accessible within a reasonable timeframe. To address this challenge, the data objects are replicated across multiple servers. Estimating the minimum quantity of data replicas and their optimal placement is considered an NP-complete optimization problem. The primary objectives of the current research include minimizing data processing costs, reducing the quantity of replicas, and maximizing the applied algorithms' reliability in replica placement. This paper introduces a hybrid chaos-based swarm approach using the modified shuffle-frog leaping algorithm with a new local search strategy for replicating data in distributed systems. Taking into account the algorithm's performance in static settings, the introduced method reduces the expenses associated with replica placement. The results of the experiment conducted on a standard data set indicate that the proposed approach can decrease data access time by about 33% when using approximately seven replicas. When executed several times, the suggested method yields a standard deviation of approximately 0.012 for the results, which is lower than the result existing algorithms produce. Additionally, the new approach's success rate is higher in comparison with existing algorithms used in addressing the problem of replica placement. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and a set S ⊆ V 2 of terminal pairs, the minimum multicut problem asks for a minimum edge set δ ⊆ E such that there is no s-t-path in G - δ for any { s , t } ∈ S . For | S | = 1 this is the well known s-t-cut problem, but in general the minimum multicut problem is NP-complete, even if the input graph is a tree. The multicut polytope M U L T C □ (G , S) is the convex hull of all multicuts in G; the multicut dominant is given by M U L T C (G , S) = M U L T C □ (G , S) + R ≥ 0 E . The latter is the relevant object for the minimization problem. While polyhedra associated to several cut problems have been studied intensively there is only little knowledge for multicut. We investigate properties of the multicut dominant and in particular derive results on liftings of facet-defining inequalities. This yields a classification of all facet-defining path- and edge inequalities. Moreover, we investigate the effect of graph operations such as node splitting, edge subdivisions, and edge contractions on the multicut-dominant and its facet-defining inequalities. In addition, we introduce facet-defining inequalities supported on stars, trees, and cycles and show that the former two can be separated in polynomial time when the input graph is a tree. [ABSTRACT FROM AUTHOR]

A binary constant weight code is a type of error-correcting code with a wide range of applications. The problem of finding a binary constant weight code has long been studied as a combinatorial optimization problem in coding theory. In this paper, we propose a quantum search algorithm for binary constant weight codes. Specifically, the search problem is formulated as a polynomial binary optimization problem and Grover adaptive search is used for providing the quadratic speedup. Focusing on the inherent structure of the problem, we derive an upper bound on the minimum of the objective function value and a lower bound on the exact number of solutions. By exploiting these two bounds, we successfully reduced the constant overhead of the algorithm, although the overall query complexity remains exponential due to the NP-complete nature of the problem. In our algebraic analysis, it was found that this proposed algorithm is capable of reducing the number of required qubits, thus enhancing the feasibility. Additionally, our simulations demonstrated that it reduces the average number of classical iterations by 63% as well as the average number of total Grover rotations by 31%. The proposed approach may be useful for other quantum search algorithms and optimization problems. [ABSTRACT FROM AUTHOR]

Our work is motivated by the challenges presented in preparing arrays of atoms for use in quantum simulation. The recently-developed process of loading atoms into traps results in approximately half of the traps being filled. To consolidate the atoms so that they form a dense and regular arrangement, such as all locations in a grid, atoms are rearranged using moving optical tweezers. Time is of the essence, as the longer that the process takes and the more that atoms are moved, the higher the chance that atoms will be lost in the process. Viewed as a problem on graphs, we wish to solve the problem of reconfiguring one arrangement of tokens (representing atoms) to another using as few moves as possible. Because the problem is NP-complete on general graphs as well as on grids, we focus on the parameterized complexity for various parameters, considering both undirected and directed graphs, and tokens with and without labels. For unlabelled tokens, the problem is fixed-parameter tractable when parameterized by the number of tokens, the number of moves, or the number of moves plus the number of vertices without tokens in either the source or target configuration, but intractable when parameterized by the difference between the number of moves and the number of differences in the placement of tokens in the source and target configurations. When labels are added to tokens, however, most of the tractability results are replaced by hardness results. [ABSTRACT FROM AUTHOR]

The allocation of tasks among multiple Autonomous Underwater Vehicles (AUVs) with energy constraints in underwater environments presents an NP-complete problem with far-reaching consequences for marine exploration, environmental monitoring, and underwater construction. This paper critically examines the contemporary methodologies and technologies in the task allocation for multiple AUVs, with a particular focus on strategies that optimize navigation time with energy consumption constraints. By conceptualizing the multiple AUVs task allocation issue as a Capacitated Vehicle Routing Problem (CVRP) and addressing it using the SCIP solver, this study seeks to identify effective task allocation strategies that enhance the operational efficiency and minimize the mission duration in energy-restricted underwater settings. The findings of this research provide valuable insights into efficient task allocation under energy constraints, providing useful theoretical implications and practical guidance for optimizing task planning and energy management in multiple AUVs systems. These contributions are demonstrated through the improved solution quality and computational efficiency. [ABSTRACT FROM AUTHOR]

We prove that, for any hyperbolic group, the compressed word and the compressed conjugacy problems are solvable in polynomial time. As a consequence, the word problem for the (outer) automorphism group of a hyperbolic group is solvable in polynomial time. We also prove that the compressed simultaneous conjugacy and the compressed centraliser problems are solvable in polynomial time. Finally, we prove that, for any infinite hyperbolic group, the compressed knapsack problem is NP-complete. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) with n = | V | vertices, the graph coloring problem is defined as Find a color vector C = (c (v)) , where c (v) ∈ { 1 , 2 , ... , n } denotes the color of vertex v ∈ V , such that no monochromatic edge exists in G and the span , the total number of distinct colors in C , is minimized. Since the problem is NP-complete, a greedy coloring is commonly used for solving it. Greedy coloring visits the vertices of G following an order S , and while visiting a vertex v , it puts the minimum color absent in all neighbors of v. We show that the orders producing span ≤ k , where k ≤ n is a positive integer, can be partitioned into disjoint subsets of equivalent orders. Next, we propose a selective search (SS) algorithm, which takes ρ as an input parameter, selects ≥ ρ orders each from a different set of equivalent orders with high probability, applies greedy coloring on them, and returns the color vector with minimum span. We analytically show that SS performs better than greedy coloring with high probability by evaluating the same number of orders. We propose an incremental search heuristic (ISH), which ρ 1 times execute SS with parameter ρ 2 and returns the color vector with minimum span. A parallel version of ISH called PISH is also proposed, executing ρ 1 SS calls in parallel. We show that ISH hits an optimum coloring for a graph G = (V , E) with χ (G) (Δ (G) + 1) ≤ n e in expected O (| V | + | E |) time and space complexities. We have evaluated ISH and PISH on 136 challenging benchmarks and shown that they significantly outperform 10 existing state-of-the-art algorithms. Finally, we validated our theoretical findings by evaluating ISH and greedy coloring on random graphs. [ABSTRACT FROM AUTHOR]

In our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the s − t -path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm. [ABSTRACT FROM AUTHOR]

Sumplete is a logic puzzle generated by ChatGPT in March 2023. The puzzle consists of a rectangular grid, with each cell containing an integer. Each row and column also has an integer called target value assigned to it. The objective of this puzzle is to cross out some numbers in the grid such that the sum of uncrossed numbers in each row and column is equal to the corresponding target value. In this paper, we prove that Sumplete is NP-complete. We also propose a physical zero-knowledge proof protocol for the puzzle using physical cards. [ABSTRACT FROM AUTHOR]

The security of traditional public key cryptography algorithms depends on the difficulty of the underlying mathematical problems. Asymmetric topological encryption is a graph-dependent encryption algorithm produced to resist attacks by quantum computers on these mathematical problems. The security of this encryption algorithm depends on two types of NP-complete problems: subgraph isomorphism and graph coloring. Topological coding technology refers to the technology of generating key strings or topology signature strings through topological coding graphs. We take odd-graceful labeling and set-ordered odd-graceful labeling as limiting functions, and propose two kinds of topological coding generation technique, which we call the random leaf-adding operation and randomly adding edge-removing operation. Through these two techniques, graphs of the same scale and larger scales can be generated with the same type of labeling so as to derive more number strings, expand the key space, and analyze the topology and property of the generated graphs. [ABSTRACT FROM AUTHOR]

We present an epistemic language for representing an artificial player's beliefs and actions in the context of the Yōkai board game. Yōkai is a cooperative game which requires a combination of Theory of Mind (ToM), temporal and spatial reasoning to be played effectively by an artificial agent. We show that the language properly accounts for these three dimensions and that its satisfiability problem is NP-complete. This opens up the possibility of exploiting SAT techniques for automating reasoning of an artificial player in the context of the Yōkai board-game. [ABSTRACT FROM AUTHOR]

A strong geodetic set of a graph G = (V, E) is a vertex set S⊆V (G) in which it is possible to cover all the remaining vertices of V (G) ∖S by assigning a unique shortest path between each vertex pair of S. In the Strong Geodetic problem (SG) a graph G and a positive integer k are given as input and one has to decide whether G has a strong geodetic set of cardinality at most k. This problem is known to be NP-hard for general graphs. In this work we introduce the Strong Geodetic Recognition problem (SGR), which consists in determining whether a given vertex set S⊆V (G) is strong geodetic. We demonstrate that this version is NP-complete. We investigate and compare the computational complexity of both decision problems restricted to some graph classes, deriving polynomial-time algorithms, NP-completeness proofs, and initial parameterized complexity results, including an answer to an open question in the literature for the complexity of SG for chordal graphs. [ABSTRACT FROM AUTHOR]

Linear least squares is one of the most widely used regression methods in many fields. The simplicity of the model allows this method to be used when data is scarce and allows practitioners to gather some insight into the problem by inspecting the values of the learnt parameters. In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. We show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem. We show the correctness of the exact method and compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (when the number of partitions is small). We also provide a branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large as well as a proof of NP-completeness of the optimization problem. [ABSTRACT FROM AUTHOR]

In this paper, we perform statistical analysis for the decisional problem which is fundamental for the security of the key exchange protocol based on matrix power function. We have proven previously that the considered decisional problem is NP-complete and hence our proposal could potentially be quantum-safe. However, we did not explore the dependence of the complexity of the considered problem on the security parameters. Here we show that for small matrices certain information could be gained from the distribution of the entries of the public key matrices. On the other hand, we show that as the size of the matrices grows, the public key matrices are indistinguishable from truly random matrices. [ABSTRACT FROM AUTHOR]

A vertex partition π = {V1,V2,…,Vk} of G is called a transitive partition of size k if Vi dominates Vj for all 1 ≤ i < j ≤ k. For two disjoint subsets A and B of V, we say A strongly dominates B if for every vertex y ∈ B, there exists a vertex x ∈ A, such that xy ∈ E and degG(x) ≥degG(y). A vertex partition π = {V1,V2,…,Vk} of G is called a strong transitive partition of size k if Vi strongly dominates Vj for all 1 ≤ i < j ≤ k. The maximum strong transitivity problem involves finding a strong transitive partition of a given graph with the maximum number of parts. In this paper, we initiate the study of this variation of transitive partition from an algorithmic point of view. We show that the decision version of this problem is NP-complete for chordal graphs. On the positive side, we prove that this problem can be solved in linear time for trees and split graphs. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph with no isolated vertices. A dominating set S of G is said to be a cosecure dominating set of G, if for every vertex v ∈ S there exists a vertex u ∈ V ∖S such that uv ∈ E and (S∖{v}) ∪{u} is a dominating set of G. The Minimum Cosecure Domination problem is to find a minimum cardinality cosecure dominating set of G. In this paper, we show that the decision version of the problem is NP-complete for split graphs, undirected path graphs (subclasses of chordal graphs), and circle graphs. We also present a linear-time algorithm to compute the cosecure domination number of cographs (subclass of circle graphs). In addition, we present a few results on the approximation aspects of the problem. [ABSTRACT FROM AUTHOR]

Exact subgraph matching is fundamental to numerous graph data applications. The inherent NP-completeness of subgraph isomorphism poses significant challenges in developing efficient matching algorithms. Current methods show limited success, particularly in their filtering and verification stages. Selecting an optimal vertex-searching order can greatly improve a subgraph searching algorithm's effectiveness, yet a comprehensive theory for this selection is lacking. In this paper, we introduce the Multistage Graph Search Model (MGSM), a novel approach addressing this gap. MGSM provides insights for identifying the most efficient vertex-searching order and offers a systematic framework for evaluating existing algorithms. Using MGSM, we identify two main challenges in optimizing the search order and present a new matching algorithm "Tps" noted for its strategic vertex-searching order. Extensive experiments demonstrate the superior performance of Tps and its effectiveness and soundness in optimizing search orders. [ABSTRACT FROM AUTHOR]

Cloud computing has evolved into an indispensable tool for facilitating scientific research due to its ability to efficiently distribute and process workloads in a virtual environment. Scientific tasks that involve complicated task dependencies and user-defined constraints related to quality of service (QoS) and time constraints require the efficient use of cloud resources. Planning these scientific workflow tasks represents an NP-complete problem, prompting researchers to explore various solutions, including conventional planners and evolutionary optimization algorithms. In this study, we present a novel, multistage algorithm specifically designed to schedule scientific workflows in cloud computing contexts. This approach addresses the challenges of efficiently mapping complex workflows onto distributed cloud resources while considering factors like resource heterogeneity, dynamic workloads, and stringent performance requirements. The algorithm uses the whale optimization algorithm (WOA) with a two-phase approach to shorten execution time, minimize financial costs, and effectively maintain load balancing. [ABSTRACT FROM AUTHOR]

Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph G are contaminated initially, before the process starts. By the q -forcing rule, a contaminated vertex having at most q uncontaminated neighbors enforces all the neighbors to become contaminated, while by the p -percolation rule, an uncontaminated vertex becomes contaminated if at least p of its neighbors are contaminated. If given a set S of initially contaminated vertices all vertices eventually become contaminated when continuously applying the q -forcing rule (respectively the p -percolation rule), S is called a q -forcing set (respectively, a p -percolating set) in G. In this paper, we consider sets S that are at the same time q -forcing sets and p -percolating sets, and call them (p , q) -spreading sets. Given positive integers p and q , the minimum cardinality of a (p , q) -spreading set in G is a (p , q) -spreading number, σ (p , q) (G) , of G. While q -forcing sets have been studied in a dozen of papers, the decision version of the corresponding graph invariant has not been considered earlier, and we fill the gap by proving its NP-completeness. This, in turn, enables us to prove the NP-completeness of the decision version of the (p , q) -spreading number in graphs for an arbitrary choice of p and q. Again, for every p ∈ N and q ∈ N ∪ { ∞ } , we find a linear-time algorithm for determining the (p , q) -spreading number of a tree, where in the case p ≥ 2 we apply Riedl's algorithm from [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] on p -percolation in trees. In addition, we present a lower and an upper bound on the (p , q) -spreading number of a tree and characterize extremal families of trees. In the case of square grids, we combine some results of Bollobás from [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006], and the AIM Minimum Rank-Special Graphs Work Group from [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 2008 1628–1648], and new results on (2 , 1) -spreading and (4 , q) -spreading to obtain σ (p , q) (P m □ P n) for all (p , q) ∈ (N ∖ { 3 }) × (N ∪ { ∞ }) and all m , n ∈ N. [ABSTRACT FROM AUTHOR]

In k-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) k-Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question of what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. In the directed sense perhaps the most natural notion of distance to acyclicity is directed feedback vertex set. It is already known that, for all k ≥ 2, k-Digraph Coloring is NP-hard on digraphs of directed feedback vertex set of size at most k + 4. We strengthen this result to show that, for all k ≥ 2, k-Digraph Coloring is already NP-hard for directed feedback vertex set of size exactly k. This immediately provides a dichotomy, as k-Digraph Coloring is trivial if directed feedback vertex set has size at most k − 1. Refining our reduction we obtain three further consequences: (i) 2-Digraph Coloring is NP-hard for oriented graphs of directed feedback vertex set at most 3; (ii) for all k ≥ 2, k-Digraph Coloring is NP-hard for graphs of feedback arc set of size at most k2; interestingly, this leads to a second dichotomy, as we show that the problem is FPT by k if feedback arc set has size at most k2 − 1; (iii) k-Digraph Coloring is NP-hard for graphs of directed feedback vertex k, even if the maximum degree Δ is at most 4k − 1; we show that this is also almost tight, as the problem becomes FPT for digraphs of directed feedback vertex set of size k and Δ ≤ 4k − 3. Since these results imply that the problem is also NP-hard on graphs of bounded directed treewidth, we then consider parameters that measure the distance from acyclicity of the underlying graph. On the positive side, we show that k-Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is (tw!)ktw. Since this is considerably worse than the ktw dependence of (undirected) k-Coloring, we pose the question of whether the tw! factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for k = 2. Specifically, we show that an FPT algorithm solving 2-Digraph Coloring with dependence tdo(td) would contradict the ETH. Then, we consider the class of tournaments. It is known that deciding whether a tournament is 2-colorable is NP-complete. We present an algorithm that decides if we can 2-color a tournament in O ∗ ( 6 3 n) time. Finally, we explain how this algorithm can be modified to decide if a tournament is k-colorable. [ABSTRACT FROM AUTHOR]

The enhancement of software system quality is achieved through a process called software testing, which is a time and cost-intensive stage of software development. As a result, automating software tests is recognized as an effective solution that can simplify time-consuming and arduous testing activities. Generating test data with maximum branch coverage and fault discovery capability is an NP-complete optimization problem. Various methods based on heuristics and evolutionary algorithms have been suggested to create test suites that provide the most feasible coverage. The main disadvantages of past approaches include inadequate branching coverage, fault detection rate, and unstable results. The main objectives of the current research are to improve the branch coverage rate, fault detection rate, success rate, and stability. This research has suggested an efficient technique to produce test data automatically utilizing a hybrid version of Olympiad Optimization Algorithms (OOA) in conjunction with genetic algorithm (GA) operators theory. Maximum coverage, fault detection capability, and success rate are the main characteristics of produced test data. Various experiments have been conducted on the nine standard benchmark programs. Regarding the results, the suggested method provides 99.92% average coverage, a success rate of 99.20%, an average generation of 5.76, and an average time of 7.97 s. Based on the fault injection experiment's results, the proposed method can discover about 89% of the faults injected by mutation testing tools such as MuJava. [ABSTRACT FROM AUTHOR]

The classic spiking neural P (SN P) systems abstract the real biological neural network into a simple structure based on graphs, where neurons can only communicate on the plane. This study proposes the hypergraph-based numerical spiking neural membrane (HNSNM) systems with novel repartition protocols. Through the introduction of hypergraphs, the HNSNM systems can characterize the high-order relationships among neurons and extend the traditional neuron structure to high-dimensional nonlinear spaces. The HNSNM systems also abstract two biological mechanisms of synapse creation and pruning, and use plasticity rules with repartition protocols to achieve planar, hierarchical and spatial communications among neurons in hypergraph neuron structures. Through imitating register machines, the Turing universality of the HNSNM systems is proved by using them as number generating and accepting devices. A universal HNSNM system consisting of 41 neurons is constructed to compute arbitrary functions. By solving NP-complete problems using the subset sum problem as an example, the computational efficiency and effectiveness of HNSNM systems are verified. [ABSTRACT FROM AUTHOR]

Graph generative models often lack a proper reconstruction loss to evaluate the distance between the generated graph and the target graph. This is particularly important for molecular graph generators based on autoencoders, which should reconstruct the input graphs as precisely as possible. Though, the distance estimation can be useful for any graph generator based on reconstruction, including sequential methods relying on Graph Neural Networks. Since graphs are discrete entities by nature, general graph spaces lack a reliable, general, and computationally affordable distance function. Graph Edit Distance is of course an exact, general, and permutation–invariant method for evaluating the difference between two graphs defined in the same graph space. Since it needs all the possible combinations of pairs of nodes from the two graphs, its exact computation is a NP-complete problem and cannot be carried out for graphs larger than ten nodes. As a consequence, a comprehensive soft–estimation method for Graph Edit Distance based on siamese Graph Neural Networks is proposed. A theoretical discussion is carried out, showing that the proposed method can provide a reliable and precise soft–estimation of the Graph Edit Distance on molecular graphs. Molecular graph generators can therefore use this distance estimation as a powerful non–permutation–invariant reconstruction loss. Moreover, the experimental results show that the distance estimation is accurate, with a very low Mean Squared Error loss value. [ABSTRACT FROM AUTHOR]

A novel quantum-safe key encapsulation algorithm, called Multivariate Polynomial Public Key (MPPK), was recently proposed by Kuang, Perepechaenko, and Barbeau. Security of the MPPK key encapsulation mechanism does not rely on the prime factorization or discrete logarithm problems. It builds upon the NP-completeness of the modular Diophantine equation problem, for which there are no known efficient classical or quantum algorithms. Hence, it is resistant to known quantum computing attacks. The private key of MPPK comprises a pair of multivariate polynomials. In a companion paper, we analyzed the performance of MPPK when these polynomials are quadratic. The analysis highlighted the MPPK high decapsulation time. We found that, while maintaining the security strength, the polynomials can be linear. Considerable performance gains are obtained for the decapsulation process. In this article, we benchmark the linear case and compare the results with the previous quadratic case. [ABSTRACT FROM AUTHOR]

The role of knowledge graph encompasses the representation, organization, retrieval, reasoning, and application of knowledge, providing a rich and robust cognitive foundation for artificial intelligence systems and applications. When we learn new things, find out that some old information was wrong, see changes and progress happening, and adopt new technology standards, we need to update knowledge graphs. However, in some environments, the initial knowledge cannot be known. For example, we cannot have access to the full code of a software, even if we purchased it. In such circumstances, is there a way to update a knowledge graph without prior knowledge? In this paper, We are investigating whether there is a method for this situation within the framework of Dalal revision operators. We first proved that finding the optimal solution in this environment is a strongly NP-complete problem. For this purpose, we proposed two algorithms: Flaccid_search and Tight_search, which have different conditions, and we have proved that both algorithms can find the desired results. [ABSTRACT FROM AUTHOR]

Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as possible. This approach is crucial in many disciplines like engineering, biology, astronomy, and economics. In this paper, we consider the following dimensionality reduction instance: Given an n-dimensional probability distribution p and an integer m < n , we aim to find the m-dimensional probability distribution q that is the closest to p, using the Kullback–Leibler divergence as the measure of closeness. We prove that the problem is strongly NP-hard, and we present an approximation algorithm for it. [ABSTRACT FROM AUTHOR]

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]