A subsequence of a word w is a word u such that u = w [ i 1 ] w [ i 2 ] … w [ i k ] , for some set of indices 1 ≤ i 1 < i 2 < … < i k ≤ | w | . A word w is k -subsequence universal over an alphabet Σ if every word in Σ k appears in w as a subsequence. In this paper, we study the intersection between the set of k -subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k- ∃ -subsequence universal if there exists a k -subsequence universal word in L , and k- ∀ -subsequence universal if every word of L is k -subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k- ∃ -subsequence universal and, respectively, if it is k- ∀ -subsequence universal , for a given k . The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k ; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O ( log ⁡ n ) . Moreover, we show that the problem of deciding if a given regular language is k- ∃ -subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k -subsequence universal words (paths) accepted by a given deterministic (respectively, non-deterministic) finite automaton, and ranking an input word (path) within the set of k -subsequence universal words accepted by a given finite automaton.

In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for both star graphs (for k ≥ 2 robots), and planar graphs (for any number of robots). Finally, we provide positive results for path, cycle, and tadpole graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal duration of a path of length n in O ( k m n ) , O ( k m n 2 ) time, and O ( k 3 m 4 n ) time respectively.

Abstract We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. (2022), we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. (2022). In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.

Graph colouring is a fundamental problem in computer science, with a large body of research dedicated to both the general colouring problem and restricted cases. Harmonious colourings are one such restriction, where each edge must contain a globally unique pair of colours, i.e. if an edge connects a vertex coloured x with a vertex coloured y , then no other pair of connected vertices can be coloured x and y . Finding such a colouring in the traditional graph setting is known to be NP-hard, even in trees. This paper considers the generalisation of harmonious colourings to Temporal Graphs , specifically -Temporal matchings , a class of temporal graphs where the underlying graph is a matching (a collection of disconnected components containing pairs of vertices), each edge can appear in at most t timesteps, and each timestep can contain at most k other edges. We provide a complete overview of the complexity landscape of finding temporal harmonious colourings for -matchings. We show that finding a Temporal Harmonious Colouring , a colouring that is harmonious in each timestep, is NP-hard for (k,t)-Temporal Matchings when , or when and . We further show that this problem is inapproximable for and an unbounded value of k , and that the problem of determining the temporal harmonious chromatic number of a -temporal matching can be determined in linear time. Finally, we strengthen this result by a set of upper and lower bounds of the temporal harmonious chromatic number both for individual temporal matchings and for the classes of -temporal matchings, paths, and cycles.

A subsequence of a word w is a word u such that u = w[i₁] w[i₂] … w[i_k], for some set of indices 1 ≤ i₁ < i₂ < … < i_k ≤ |w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ^k appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O(log n). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, nondeterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton.

The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k^2 n^4), where k is the size of the alphabet and n is the length of the considered bracelets. The key part of the algorithm is to compute the rank of any word with respect to the set of bracelets by finding three other ranks: the rank over all necklaces, the rank over palindromic necklaces, and the rank over enclosing apalindromic necklaces. The last two concepts are introduced in this paper. These ranks are key components to our algorithm in order to decompose the problem into parts. Additionally, this ranking procedure is used to build a polynomial-time unranking algorithm.

Crystal Structure Prediction (CSP) is one of the central and most challenging problems in materials science and computational chemistry. In CSP, the goal is to find a configuration of ions in 3D space that yields the lowest potential energy. Finding an efficient procedure to solve this complex optimisation question is a well known open problem. Due to the exponentially large search space, the problem has been referred in several materials-science papers as “NP-Hard and very challenging” without a formal proof. This paper fills a gap in the literature providing the first set of formally proven NP-Hardness results for a variant of CSP with various realistic constraints. In particular, we focus on the problem of removal: the goal is to find a substructure with minimal potential energy, by removing a subset of the ions. Our main contributions are NP-Hardness results for the CSP removal problem, new embeddings of combinatorial graph problems into geometrical settings, and a more systematic exploration of the energy function to reveal the complexity of CSP. In a wider context, our results contribute to the analysis of computational problems for weighted graphs embedded into the three-dimensional Euclidean space.