Search

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]

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]

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]

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]

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]

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]

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 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]

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]

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]

Consider a graph G with vertex set V(G) and edge set E(G). A subset D of V(G) is said to be a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. If, in addition, every vertex not in a dominating set R of G is adjacent to at least one vertex in V (G) - R , then R is called a restrained dominating set of G. A paired restraint dominating set S of a graph G is a restrained dominating set of G satisfying that the induced subgraph by S contains a perfect matching. The problems of computing the dominating set, restrained dominating set, and paired restraint dominating set with minimum cardinality are referred to as the domination, restrained domination, and paired restraint domination problems, respectively. The paired restraint domination problem and its applications are first proposed here. Our focus is on examining the complexity of the proposed problem on extended supergrid graphs and their subclasses, which include grid, diagonal supergrid, and (original) supergrid graphs. The domination problem is known to be NP-complete on grid graphs and, therefore, also on extended supergrid graphs. Our previous research demonstrated that the domination and restrained domination problems on diagonal and original supergrid graphs are NP-complete. However, the complexity of the paired restraint domination problem on grid, diagonal supergrid, and original supergrid graphs remains unknown. The NP-completeness of the paired restraint domination problem on diagonal supergrid graphs is demonstrated in this paper, and this finding is also applicable to the original supergrid graphs and planar graphs with maximum degree 4. We then examine a subclass of diagonal and original supergrid graphs known as rectangular supergrid graphs. These graphs are distinguished by a rectangular shape consisting of m rows and n columns of vertices. Specifically, we address the paired restraint domination problem on R m × n and develop a linear time algorithm for 3 ⩾ m ⩾ 1 and n ⩾ m . Then, when n ⩾ m ⩾ 4 , we obtain a tight upper bound on the minimum size of the paired restraint dominating set of R m × n and then use this upper bound to establish one lower bound. [ABSTRACT FROM AUTHOR]

This paper explores the computational challenges of clique transversal problems in d-degenerate graphs, which are commonly encountered across theoretical computer science and various network applications. We examine d-degenerate graphs to highlight their utility in representing sparse structures and assess several variations of clique transversal problems, including the b-fold and { b } -clique transversal problems, focusing on their computational complexities for different graph categories. Our analysis identifies that certain instances of these problems are polynomial-time solvable in specific graph classes, such as 1-degenerate or 2-degenerate graphs. However, for d-degenerate graphs where d ≥ 2 , these problems generally escalate to NP-completeness. We also explore the parameterized complexity, pinpointing specific conditions that render these problems fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time. [ABSTRACT FROM AUTHOR]

The aim of this paper is to optimize the allocation of multiple advertisements on a Web banner, where the price of an advertisement depends on the location at the banner. This problem can be defined as a two-dimensional single orthogonal knapsack problem with a location-based pixel-price model. A formulation is proposed in which the problem is specified as a 0–1 integer programming problem. As this problem is NP-complete, we mainly focus on a heuristic approach to solve the problem. We propose two new heuristic algorithms: the reactive GRASP algorithm and the partitioning left-justified algorithm. Next to that, we present an exact algorithm that is able to solve small problem instances in a reasonable time. These newly presented algorithms are compared with respect to efficiency and effectiveness to existing algorithms that solve the problem without a location-based pixel-price model. To test the quality of the algorithms, we have executed two experiments. The results of these experiments show that overall the reactive GRASP algorithm is the most effective algorithm, whereas the greedy stripping algorithm is the most efficient. [ABSTRACT FROM AUTHOR]

Data masking is a common technique for sanitizing sensitive data maintained in database systems which is becoming increasingly important in various application areas, such as in record linkage of personal data. This work formalizes the Pattern Masking for Dictionary Matching (PMDM) problem: given a dictionary D of d strings, each of length ℓ , a query string q of length ℓ , and a positive integer z, we are asked to compute a smallest set K ⊆ { 1 , ... , ℓ } , so that if q[i] is replaced by a wildcard for all i ∈ K , then q matches at least z strings from D . Solving PMDM allows providing data utility guarantees as opposed to existing approaches. We first show, through a reduction from the well-known k-Clique problem, that a decision version of the PMDM problem is NP-complete, even for binary strings. We thus approach the problem from a more practical perspective. We show a combinatorial O ((d ℓ) | K | / 3 + d ℓ) -time and O (d ℓ) -space algorithm for PMDM for | K | = O (1) . In fact, we show that we cannot hope for a faster combinatorial algorithm, unless the combinatorial k-Clique hypothesis fails (Abboud et al. in SIAM J Comput 47:2527–2555, 2018; Lincoln et al., in: 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018). Our combinatorial algorithm, executed with small |K|, is the backbone of a greedy heuristic that we propose. Our experiments on real-world and synthetic datasets show that our heuristic finds nearly-optimal solutions in practice and is also very efficient. We also generalize this algorithm for the problem of masking multiple query strings simultaneously so that every string has at least z matches in D . PMDM can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PMDM data structure with string q and z = 1 , one obtains the minimal number of mismatches of q with any string from D . The query time or space of all known data structures for the more restricted problem of dictionary matching with at most k mismatches incurs some exponential factor with respect to k. A simple exact algorithm for PMDM runs in time O (2 ℓ d) . We present a data structure for PMDM that answers queries over D in time O (2 ℓ / 2 (2 ℓ / 2 + τ) ℓ) and requires space O (2 ℓ d 2 / τ 2 + 2 ℓ / 2 d) , for any parameter τ ∈ [ 1 , d ] . We complement our results by showing a two-way polynomial-time reduction between PMDM and the Minimum Union problem [Chlamtáč et al., ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017]. This gives a polynomial-time O (d 1 / 4 + ϵ) -approximation algorithm for PMDM, which is tight under a plausible complexity conjecture. This is an extended version of a paper that was presented at International Symposium on Algorithms and Computation (ISAAC) 2021. [ABSTRACT FROM AUTHOR]

We study the efficiency of the reaction systems in solving NP-complete problems. Due to the fact that standard reaction systems are qualitative, in order to accomplish our aim, in this paper we consider communicating reaction systems with direct communication extended with duration for resources and a mutual exclusion relation between reactions forbidding two reactions to be used in the same step, in parallel. We show that these systems, working in a non-deterministic way, are powerful enough to provide polynomial-time solutions to the subset sum and SAT problems. We consider a semi-uniform approach by constructing a system for each instance of the subset sum and SAT problems and embedding the parameters into the constructed systems. [ABSTRACT FROM AUTHOR]

Let V(G) be the vertex set of a simple and connected graph G. A subset S ⊆ V(G) is a distance-equalizer set of G if, for every pair of vertices u, v ∈ V(G) \ S, there exists a vertex in S that is equidistant to u and v. The minimum cardinality among the distance-equalizer sets of G is the equidistant dimension of G, denoted by ξ(G). In this paper, we studied the problem of finding ξ(G◦H), where G◦H denotes the lexicographic product of two graphs G and H. The aim was to express ξ(G◦H) in terms of parameters of G and H. In particular, we considered the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. Furthermore, we showed that ξ(G) ≤ ξ(G ◦ H) ≤ ξ(G)|V(H)| for every connected graph G and every graph H and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard. [ABSTRACT FROM AUTHOR]

Exponential-time algorithms for solving intractable problems are considered inefficient when compared to polynomial-time algorithms for solving tractable problems. The reason being that the execution time for former grows rapidly as problem size increases. A problem is considered NP- complete when a problem is non-deterministic polynomial (NP) and all other NP-problems are polynomial-time reducible to it. The partition problem is one of the simplest NP- complete problems. Many real-life applications can be modeled as NP-complete problems, and it is important for software developers to understand the limitations of existing algorithms that can solve those problems. Solving the partition problem is a time-consuming endeavor. Exact algorithms can find solutions, in a reasonable amount of time, only for small instances of these problems. Large instances of NP-hard problems will take so long to solve with exact algorithms, that for practical purposes those large instances should be considered intractable. The execution time required to find a solution to instances of the partition problem is greatly reduced by using parallel processing counterparts such as Graphics Processing Unit (GPU) and Field Programmable Gate Array (FPGA). In this paper, we talk about the use of the NVIDIA T4 GPU and PYNQ FPGA board in conjunction with an overlay to accelerate the execution of a function that evaluates if a partition is a solution to an instance of the partition problem. To assist with the evaluation, four different overlays are created for FPGA and performance comparison among them with GPU using python and the numba/cuda library is then presented in the paper. [ABSTRACT FROM AUTHOR]

In this paper, we develop the theoretical provisions of symmetric cryptographic algorithms based on the polynomial residue number system for the first time. The main feature of the proposed approach is that when reconstructing the polynomial based on the method of undetermined coefficients, multiplication is performed not on the found base numbers but on arbitrarily selected polynomials. The latter, together with pairwise coprime residues of the residue class system, serve as the keys of the cryptographic algorithm. Schemes and examples of the implementation of the developed polynomial symmetric encryption algorithm are presented. The analytical expressions of the cryptographic strength estimation are constructed, and their graphical dependence on the number of modules and polynomial powers is presented. Our studies show that the cryptanalysis of the proposed algorithm requires combinatorial complexity, which leads to an NP-complete problem. [ABSTRACT FROM AUTHOR]

Partite, 3-uniform hypergraphs are 3-uniform hypergraphs in which each hyperedge contains exactly one point from each of the 3 disjoint vertex classes. We consider the degree sequence problem of partite, 3-uniform hypergraphs, that is, to decide if such a hypergraph with prescribed degree sequences exists. We prove that this decision problem is NP-complete in general, and give a polynomial running time algorithm for third almost-regular degree sequences, that is, when each degree in one of the vertex classes is k or k − 1 for some fixed k, and there is no restriction for the other two vertex classes. We also consider the sampling problem, that is, to uniformly sample partite, 3-uniform hypergraphs with prescribed degree sequences. We propose a Parallel Tempering method, where the hypothetical energy of the hypergraphs measures the deviation from the prescribed degree sequence. The method has been implemented and tested on synthetic and real data. It can also be applied for χ2 testing of contingency tables. We have shown that this hypergraph-based χ2 test is more sensitive than the standard χ2 test. The extra sensitivity is especially advantageous on small data sets, where the proposed Parallel Tempering method shows promising performance. [ABSTRACT FROM AUTHOR]

Using assembly theory, we investigate the assembly pathways of binary strings (bitstrings) of length N formed by joining bits present in the assembly pool and the bitstrings that entered the pool as a result of previous joining operations. We show that the bitstring assembly index is bounded from below by the shortest addition chain for N, and we conjecture about the form of the upper bound. We define the degree of causation for the minimum assembly index and show that, for certain N values, it has regularities that can be used to determine the length of the shortest addition chain for N. We show that a bitstring with the smallest assembly index for N can be assembled via a binary program of a length equal to this index if the length of this bitstring is expressible as a product of Fibonacci numbers. Knowing that the problem of determining the assembly index is at least NP-complete, we conjecture that this problem is NP-complete, while the problem of creating the bitstring so that it would have a predetermined largest assembly index is NP-hard. The proof of this conjecture would imply P ≠ NP since every computable problem and every computable solution can be encoded as a finite bitstring. The lower bound on the bitstring assembly index implies a creative path and an optimization path of the evolution of information, where only the latter is available to Turing machines (artificial intelligence). Furthermore, the upper bound hints at the role of dissipative structures and collective, in particular human, intelligence in this evolution. [ABSTRACT FROM AUTHOR]

This work solves 3SAT, a classical NP-complete problem, on a CMOS-based Ising hardware chip with all-to-all connectivity. The paper addresses practical issues in going from algorithms to hardware. It considers several degrees of freedom in mapping the 3SAT problem to the chip—using multiple Ising formulations for 3SAT; exploring multiple strategies for decomposing large problems into subproblems that can be accommodated on the Ising chip; and executing a sequence of these subproblems on CMOS hardware to obtain the solution to the larger problem. These are evaluated within a software framework, and the results are used to identify the most promising formulations and decomposition techniques. These best approaches are then mapped to the all-to-all hardware, and the performance of 3SAT is evaluated on the chip. Experimental data shows that the deployed decomposition and mapping strategies impact SAT solution quality: without our methods, the CMOS hardware cannot achieve 3SAT solutions on SATLIB benchmarks. Under the assumption of some hardware improvements, our chip-based 3SAT solver demonstrates a remarkable 250 × acceleration compared to Tabu search in dwave-hybrid on a CPU. [ABSTRACT FROM AUTHOR]

The optimal PMU placement problem is placing the minimum number of PMUs in the network to ensure complete network observability. It is an NP-complete optimization problem. PMU placement based on cost and critical nodes is solved separately in the literature. This paper proposes a novel approach, a degree of centrality in the objective function, to combine the effect of both strategies to place PMUs in the power network optimally. The contingency analysis and the effect of zero-injection buses are solved to ensure the reliability of network monitoring and attain a minimum number of PMUs. Integer linear programming is used on the IEEE 7-bus, IEEE 14-bus, IEEE 30-bus, New England 39-bus, IEEE 57-bus, and IEEE 118-bus systems to solve this problem. The results are evaluated based on two performance measures: the bus observability index (BOI) and the sum of redundancy index (SORI). On comparison, it is found that the proposed methodology has significantly improved results, i.e., a reduced number of PMUs and increased network overall observability (SORI). This methodology is more practical for implementation as it focuses on critical nodes. Along with improvement in the results, the limitations of existing indices are also discussed for future work. [ABSTRACT FROM AUTHOR]

Many variations of the classical graph coloring model have been intensively studied due to their multiple applications; scheduling problems and aircraft assignments, for instance, motivate the robust coloring problem. This model gets to capture natural constraints of those optimization problems by combining the information provided by two colorings: a vertex coloring of a graph and the induced edge coloring on a subgraph of its complement; the goal is to minimize, among all proper colorings of the graph for a fixed number of colors, the number of edges in the subgraph with the endpoints of the same color. The study of the robust coloring model has been focused on the search for heuristics due to its NP-hard character when using at least three colors, but little progress has been made in other directions. We present a new approach on the problem obtaining the first collection of non-heuristic results for general graphs; among them, we prove that robust coloring is the model that better approaches the equitable partition of the vertex set, even when the graph does not admit a so-called equitable coloring. We also show the NP-completeness of its decision problem for the unsolved case of two colors, obtain bounds on the associated robust coloring parameter, and solve a conjecture on paths that illustrates the complexity of studying this coloring model. [ABSTRACT FROM AUTHOR]

Joint replenishment problems constitute an important class of models in inventory management. They exhibit aspects of possible coordination among multiple products to save costs. Their computational complexity had been open even if there are just two products that need to be synced. In "Integer factorization: Why two-item joint replenishment is hard," Schulz and Telha present a simple framework based on integer factorization to establish the computational hardness of two variants of the joint replenishment problem with two items. Whereas difficult to solve in practice and not believed to be solvable in polynomial time, integer factorization is not as difficult as NP-complete problems. The authors show that a similar technique can be used to show even the NP-completeness of one variant of the joint replenishment problem (again with just two items). Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two items is at least as difficult as integer factorization. To the best of the authors' knowledge, this is the first time integer factorization is used to explain the computational hardness of any optimization problem. We can even prove that the two-item joint replenishment problem with possibly empty joint-ordering points is NP-complete under randomized reductions. This implies that even quantum computers may not be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish the (integer-factorization) hardness of additional periodic problems in supply chain management and beyond, whose computational complexity has not been resolved yet. Funding: The first author gratefully acknowledges the support of the Alexander von Humboldt Foundation and the German Federal Ministry of Education and Research. The second author gratefully acknowledges the support of Agencia Nacional de Investigación y Desarrollo [Grant ANID/FONDECYT Iniciación 11200616] and Programa Regional STIC AMSUD [Grant 22-STIC-09]. [ABSTRACT FROM AUTHOR]

The graph traversal edit distance (GTED), introduced by Ebrahimpour Boroojeny et al. (2018), is an elegant distance measure defined as the minimum edit distance between strings reconstructed from Eulerian trails in two edge-labeled graphs. GTED can be used to infer evolutionary relationships between species by comparing de Bruijn graphs directly without the computationally costly and error-prone process of genome assembly. Ebrahimpour Boroojeny et al. (2018) propose two ILP formulations for GTED and claim that GTED is polynomially solvable because the linear programming relaxation of one of the ILPs always yields optimal integer solutions. The claim that GTED is polynomially solvable is contradictory to the complexity results of existing string-to-graph matching problems. We resolve this conflict in complexity results by proving that GTED is NP-complete and showing that the ILPs proposed by Ebrahimpour Boroojeny et al. do not solve GTED but instead solve for a lower bound of GTED and are not solvable in polynomial time. In addition, we provide the first two, correct ILP formulations of GTED and evaluate their empirical efficiency. These results provide solid algorithmic foundations for comparing genome graphs and point to the direction of heuristics. The source code to reproduce experimental results is available at https://github.com/Kingsford-Group/gtednewilp/. [ABSTRACT FROM AUTHOR]

Phase-encoded oscillating neural networks offer compelling advantages over metal-oxide-semiconductor-based technology for tackling complex optimization problems, with promising potential for ultralow power consumption and exceptionally rapid computational performance. In this work, we investigate the ability of these networks to solve optimization problems belonging to the nondeterministic polynomial time complexity class using nanoscale vanadium-dioxide-based oscillators integrated onto a Silicon platform. Specifically, we demonstrate how the dynamic behavior of coupled vanadium dioxide devices can effectively solve combinatorial optimization problems, including Graph Coloring, Max-cut, and Max-3SAT problems. The electrical mappings of these problems are derived from the equivalent Ising Hamiltonian formulation to design circuits with up to nine crossbar vanadium dioxide oscillators. Using sub-harmonic injection locking techniques, we binarize the solution space provided by the oscillators and demonstrate that graphs with high connection density (η > 0.4) converge more easily towards the optimal solution due to the small spectral radius of the problem's equivalent adjacency matrix. Our findings indicate that these systems achieve stability within 25 oscillation cycles and exhibit power efficiency and potential for scaling that surpasses available commercial options and other technologies under study. These results pave the way for accelerated parallel computing enabled by large-scale networks of interconnected oscillators. Oscillating neural networks promise ultralow power consumption and rapid computation for tackling complex optimization problems. Here, the authors demonstrate VO2 oscillators to solve NP-complete problems with projected power consumption of 13 µW/oscillator. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a connected, basic, and finite graph. A subset T = u 1 , u 2 , ... , u k of V(G) is said to be a resolving set if for any y ∈ V(G), the code of y with regards to T, represented by C T y , which is defined as C T y = d u 1 , y , d u 2 , y , ... , d u k , y , is different for various y. The dimension of G is the smallest cardinality of a resolving set and is denoted by dim(G). If, for any t ∈ V – S, there exists r ∈ S such that S – r ∪ t is a resolving set, then the resolving set S is secure. The secure metric dimension of is the cardinal number of the minimum secure resolving set. Determining the secure metric dimension of any given graph is an NP-complete problem. In addition, there are several uses for the metric dimension in a variety of fields, including image processing, pattern recognition, network discovery and verification, geographic routing protocols, and combinatorial optimization. In this paper, we determine the secure metric dimension of special graphs such as a globe graph G l n , flag graph F l n , H- graph of path P n , a bistar graph B n , n 2 , and tadpole graph T 3 , m . Finally, we derive the explicit formulas for the secure metric dimension of tadpole graph T n , m , subdivision of tadpole graph S T 3 , m , and subdivision of tadpole graph S T n , m . [ABSTRACT FROM AUTHOR]

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson in his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee, and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still unknown. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4. [ABSTRACT FROM AUTHOR]

Purpose: Advancement in optimization of VLSI circuits involves reduction in chip size from micrometer to nanometer level as well as fabrication of a billions of transistors in a single die where global routing problem remains significant with a trade-off of power dissipation and interconnect delay. This paper aims to solve the increased complexity in VLSI chip by minimization of the wire length in VLSI circuits using a new approach based on nature-inspired meta-heuristic, invasive weed optimization (IWO). Further, this paper aims to achieve maximum circuit optimization using IWO hybridized with particle swarm optimization (PSO). Design/methodology/approach: This paper projects the complexities of global routing process of VLSI circuit design in mapping it with a well-known NP-complete problem, the minimum rectilinear Steiner tree (MRST) problem. IWO meta-heuristic algorithm is proposed to meet the MRST problem more efficiently and thereby reducing the overall wire-length of interconnected nodes. Further, the proposed approach is hybridized with PSO, and a comparative analysis is performed with geosteiner 5.0.1 and existing PSO technique over minimization, consistency and convergence against available benchmark. Findings: This paper provides high performance–enhanced IWO algorithm, which keeps in generating low MRST value, thereby successful wire length reduction of VLSI circuits is significantly achieved as evident from the experimental results as compared to PSO algorithm and also generates value nearer to geosteiner 5.0.1 benchmark. Even with big VLSI instances, hybrid IWO with PSO establishes its robustness over achieving improved optimization of overall wire length of VLSI circuits. Practical implications: This paper includes implications in the areas of optimization of VLSI circuit design specifically in the arena of VLSI routing and the recent developments in routing optimization using meta-heuristic algorithms. Originality/value: This paper fulfills an identified need to study optimization of VLSI circuits where minimization of overall interconnected wire length in global routing plays a significant role. Use of nature-based meta-heuristics in solving the global routing problem is projected to be an alternative approach other than conventional method. [ABSTRACT FROM AUTHOR]

Aiming to increase throughput in Wireless Networks, such as in Wireless Sensor Network and the Internet of Things, platforms emerged in which devices have two radios, and also data transfer protocols that prioritize maximum throughput and energy efficiency, using two different paths simultaneously. The usage of dual radios allowed simultaneous transmissions between wireless devices, which, besides increasing network throughput, can also improve network stability, delivery rate, transmission cost, and energy consumption per transmitted byte. However, one path may be much longer than the other, causing high latency. First, in this work, we present the problem formulation to find two disjoint paths with the same parity size for platforms with two heterogeneous radios to reach the network maximum flow, while also minimizing the longest path, which reduces latency. Second, we show that the problem is NP-Complete. Next, we present a solution based on integer linear programming. Moreover, we tested the solution on almost 5,700 instances obtained from an actual testbed and the results show a reduction in latency while maintaining the high throughput. [ABSTRACT FROM AUTHOR]

The Hamiltonian path is a well-known NP-complete problem. This problem has been studied for solid supergrid graphs, in some special cases, and recently for 3-connected solid supergrid graphs. In this paper, we extend the previous result to general solid supergrid graphs, and present an O(n²)-time algorithm where n is the number of the vertices of the input graph. [ABSTRACT FROM AUTHOR]

Current real-time systems applications are mostly large-scale, where tasks are intrinsically time-constrained and meaningfully dependent. Nevertheless, while the initial partitioning solution has a huge impact on scheduling results, most tasks-allocation problems are NP-complete and lack binding semantics. The scheduling analysis strategies are inevitably required to validate the system scheduling before its actual deployment. However, once the proposed scheduling is invalid, no possible corrections are provided, and a costing NP-complete partitioning regeneration is provoked as the only possible correction action. Whereas, sometimes nearby task re-allocations guarantee the scheduling correction. This paper proposes an approach to efficiently correct initial dependent task partitioning solutions while considering their allocation semantics. The ultimate objective is to conduct a correct schedule for multiprocessor real-time systems by means of a driven task re clustering and/or re-allocation without the need for extra complex partitioning regeneration. Simulation results show that our proposed approach is faster than classic partitioning regeneration, ameliorates the partitioning semantic results, and gives efficient scheduling results. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in algorithms that take in input an arbitrary graph G , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of G which fulfil a given property Π. All over this paper, we study several different properties Π , and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, maximal induced cographs and maximal threshold graphs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal stable sets of an auxiliary graph. For cographs and threshold graphs, the algorithms rely on a framework recently introduced by Conte & Uno (2019) called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property Π that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every non-trivial hereditary property Π. We extend the hardness result to some specific edge version of the extension problem. [ABSTRACT FROM AUTHOR]

For k ∈ N , a k -acyclic colouring of a graph G is a function f : V (G) → { 0 , 1 , ... , k − 1 } such that (i) f (u) ≠ f (v) for every edge u v of G , and (ii) there is no cycle in G bicoloured by f. For k ∈ N , the problem k - Acyclic Colourability takes a graph G as input and asks whether G admits a k -acyclic colouring. Ochem (EuroComb 2005) proved that 3- Acyclic Colourability is NP-complete for bipartite graphs of maximum degree 4. Mondal et al. (2013) proved that 4- Acyclic Colourability is NP-complete for graphs of maximum degree five. We prove that for k ≥ 3 , k - Acyclic Colourability is NP-complete for bipartite graphs of maximum degree k + 1 , thereby generalising the NP-completeness result of Ochem, and adding bipartiteness to the NP-completeness result of Mondal et al.. In contrast, k - Acyclic Colourability is polynomial-time solvable for graphs of maximum degree at most 0. 38 k 3 / 4 . Hence, for k ≥ 3 , the least integer d such that k - Acyclic Colourability in graphs of maximum degree d is NP-complete, denoted by L a (k) , satisfies 0. 38 k 3 / 4 < L a (k) ≤ k + 1. We prove that for k ≥ 4 , k - Acyclic Colourability in d -regular graphs is NP-complete if and only if L a (k) ≤ d ≤ 2 k − 3. We also show that it is coNP-hard to check whether an input graph G admits a unique k -acyclic colouring up to colour swaps (resp. up to colour swaps and automorphisms). [ABSTRACT FROM AUTHOR]

Interval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper) thinness, and several variations, for the classes of cographs, crowns graphs and grid graphs. We provide the exact values for several variants of thinness (proper, independent, complete, precedence, and combinations of them) for the crown graphs CRn. For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of n × n grids GRn and m×n grids GRm,n, proving that n−1/3 ⌈ n − 1 3 ⌉ $\textstyle\lceil\frac{n-1}3\rceil$ ≤ thin(GRn) ≤ n+1/2 ⌈ n + 1 2 ⌉ $\textstyle\lceil\frac{n+1}2\rceil$. Regarding the precedence thinness, we prove that prec-thin(GRn,2) = n+1/2 ⌈ n + 1 2 ⌉ $\textstyle\lceil\frac{n+1}2\rceil$ and that n− 1 + 3/2 ⌈ n − 1 3 ⌉ ⌈ n − 1 2 ⌉ + 1 $\textstyle{\lceil\frac{n-1}3\rceil}{\lceil\frac{n-1}2\rceil}+1$ ≤ prec-thin(GRn) ≤ n− 1 2 ⌈ n − 1 2 ⌉ 2 + 1 $\textstyle{\lceil\frac{n-1}2\rceil}^2+1$. As applications, we show that the k-coloring problem is NP-complete for precedence 2-thin graphs and for proper 2-thin graphs, when k is part of the input. On the positive side, it is polynomially solvable for precedence proper 2-thin graphs, given the order and partition. [ABSTRACT FROM AUTHOR]

In this paper, given a fixed reference point and a fixed intersection of finitely many equal radii balls, we consider the problem of finding a point in the said set which is the most distant, under Euclidean distance, to the said reference point. This proble is NP-complete in the general setting. We give sufficient conditions for the existence of an algorithm of polynomial complexity which can solve the problem, in a particular setting. Our algorithm requires that any point in the said intersection to be no closer to the given reference point than the radius of the intersecting balls. Checking this requirement is a convex optimization problem hence one can decide if running the proposed algorithm enjoys the presented theoretical guarantees. We also consider the problem where a fixed initial reference point and a fixed polytope are given and we want to find the farthest point in the polytope to the given reference point. For this problem we give sufficient conditions in which the solution can be found by solving a linear program. Both these problems are known to be NP-complete in the general setup, i.e the existence of an algorithm which solves any of the above problem without restrictions on the given reference point and search set is undecided so far. [ABSTRACT FROM AUTHOR]

The multiple-unmanned-aerial-vehicle (multi-UAV) mobile edge network is a promising networking paradigm that uses multiple resource-limited and trajectory-planned unmanned aerial vehicles (UAVs) as edge servers, upon which on-demand virtual network functions (VNFs) are deployed to provide low-delay virtualized network services for the requests of ground users (GUs), who often move randomly and have difficulty accessing the Internet. However, VNF deployment and UAV trajectory planning are both typical NP-complete problems, and the two operations have a strong coupling effect: they affect each other. Achieving optimal virtualized service provision (i.e., maximizing the number of accepted GU requests under a given period T while minimizing the energy consumption and the cost of accepting the requests in all UAVs) is a challenging issue. In this paper, we propose an improved online deep reinforcement learning (DRL) scheme to tackle this issue. First, we formulate the joint optimization of the two operations as a nonconvex mixed-integer nonlinear programming problem, which can be viewed as a sequence of one-frame joint VNF deployment and UAV-trajectory-planning optimization subproblems. Second, we propose an online DRL based on jointly optimizing discrete (VNF deployment) and continuous (UAV trajectory planning) actions to solve each subproblem, whose key idea is establishing and achieving the coupled influence of discrete and continuous actions. Finally, we evaluate the proposed scheme through extensive simulations, and the results demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

Background: Scaffolding is an intermediate stage of fragment assembly. It consists in orienting and ordering the contigs obtained by the assembly of the sequencing reads. In the general case, the problem has been largely studied with the use of distances data between the contigs. Here we focus on a dedicated scaffolding for the chloroplast genomes. As these genomes are small, circular and with few specific repeats, numerous approaches have been proposed to assemble them. However, their specificities have not been sufficiently exploited. Results: We give a new formulation for the scaffolding in the case of chloroplast genomes as a discrete optimisation problem, that we prove the decision version to be NP -Complete. We take advantage of the knowledge of chloroplast genomes and succeed in expressing the relationships between a few specific genomic repeats in mathematical constraints. Our approach is independent of the distances and adopts a genomic regions view, with the priority on scaffolding the repeats first. In this way, we encode the structural haplotype issue in order to retrieve several genome forms that coexist in the same chloroplast cell. To solve exactly the optimisation problem, we develop an integer linear program that we implement in Python3 package khloraascaf. We test it on synthetic data to investigate its performance behaviour and its robustness against several chosen difficulties. Conclusions: We succeed to model biological knowledge on genomic structures to scaffold chloroplast genomes. Our results suggest that modelling genomic regions is sufficient for scaffolding repeats and is suitable for finding several solutions corresponding to several genome forms. [ABSTRACT FROM AUTHOR]