The Complexity of Maximal Common Subsequence Enumeration
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita, Giulia Punzi · 2025
Read The Complexity of Maximal Common Subsequence Enumeration by Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita, Giulia Punzi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04757.txt.
Introduction
Giovanni Buzzega and co-authors study the hardness of listing maximal common subsequences, in a 2025 paper. The catalog title adds a publication note, so the head title governs. Pattern mining hunts for frequent patterns in data, and maximal ones give a compact summary of what matters.
A subsequence keeps order but can skip items, and the longest common form is a classic problem. The authors show that listing all maximal common subsequences across strings is hard in a strong sense. No method can run in time tied only to input plus output size, unless a major open claim fails. They then map how the problem behaves when parts of the input are held small.
Catalog record
| CREATOR | Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita, Giulia Punzi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04757
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Complexity of Maximal Common Subsequence Enumeration Note: This is the AAM version of the article accepted for publication, after peer review, at PODS 2025 (doi: https://doi.org/10.1145/3725252 ) Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita, Giulia Punzi Abstract . Frequent pattern mining is widely used to find “important” or “interesting” patterns in data. While it is not easy to mathematically define such patterns, maximal frequent patterns are promising candidates, as frequency is a natural indicator of relevance and maximality helps to summarize the output. As such, their mining has been studied on various data types, including itemsets, graphs, and strings. The complexity of mining maximal frequent itemsets and subtrees has been thoroughly investigated (e.g., [Boros et al., 2003], [Uno et al., 2004]) in the literature. On the other hand, while the idea of mining frequent subsequences in sequential data was already introduced in the seminal paper [Agrawal et al., 1995], the complexity of the problem is still open. In this paper, we investigate the complexity of the maximal common subsequence enumeration problem, which is both an important special case of maximal frequent subsequence mining and a generalization of the classic longest common subsequence (LCS) problem. We show the hardness of enumerating maximal common subsequences between multiple strings, ruling out the possibility of an output-polynomial time enumeration algorithm under 𝖯 ≠ 𝖭𝖯 {\mathsf{P}}\neq{\mathsf{NP}} , that is, an algorithm that runs in time poly ( | ℐ | + N ) {\rm poly}(|\mathcal{I}|+N) , where | ℐ | |\mathcal{I}| and N N are the size of the input and number of output solutions, respectively. To circumvent this intractability, we also investigate the parameterized complexity of the problem, and show several results when the alphabet size, the number of strings, and the length of a string are taken into account as parameters. Journal: PACMMOD Volume: 3 2 (PODS) 115 5 DOI: 10.1145/3725252 CCS: Mathematics of computing Enumeration CCS: Theory of computation Complexity classes † † cc-license: by 1. Introduction Frequent pattern mining problems are a central topic in data mining. Mining algorithms typically aim to find “interesting” or “important” patterns, but mathematically defining an interesting or important pattern is not easy. A reasonable implementation of this concept, that has been widely studied, is using frequency as an indicator of importance, and enumerating all high-frequency patterns. In particular, structures such as itemsets, graphs, and strings are often sought after ( 2 , 39 , 32 ) . The fundamental problem of frequent itemset mining , for example, can be formulated as follows. Given a transaction database \mathcal{T}=\{T_{1},\ldots,T_{k}\} and a threshold t , enumerate all sets V that are frequent, i.e., contained in at least t transactions in \mathcal{T} . When the database is a collection of graphs, the problem is called frequent subgraph mining ( 25 , 28 ) , and when it is a collection of strings, it is called frequent subsequence mining , where a subsequence of a string S is a string that can be obtained by deleting arbitrary occurrences of characters of S . In the frequent subsequence mining problem, each element of a sequence can sometimes be defined as a subset of a given itemset. In this paper, we consider the less general case in which each element of a sequence is a simple character. Frequency, however, is not the end of the story, as high-frequency patterns are not always all useful. For example, a frequent pattern that is simply a subset of another frequent pattern may not be considered useful, as its information is subsumed by the bigger pattern. Thus, research in the field focused on additional constraints for pruning redundant information, such as closedness and maximality: a frequent pattern is called maximal if no other frequent pattern strictly contains it, and it is called closed if it is only contained in patterns with lower frequency than itself. Discarding non-maximal or non-closed patterns greatly reduces the number of patterns, with minimal loss of information, but comes at a computational cost, as enumerating just the maximal or closed patterns can be significantly more challenging. To analyze this cost, we typically have to look at the output size: the number of solutions may be exponential in the size of the input, so we seek algorithms that run, at the very least, in time polynomial in the output size ( 41 ) . We call these algorithms output-polynomial , or output-sensitive . For the itemset mining problem, the output-sensitive enumeration of maximal/closed frequent itemset has been thoroughly studied ( 7 , 34 ) . For closed frequent itemset mining, Uno et al. ( 34 ) proposed a linear-delay enumeration algorithm, where the delay is the maximum time elapsed between outputs. In contrast, the enumeration of maximal frequent itemsets is known to be intractable ( 7 ) . More precisely, Boros et al. showed that the decision problem of determining, given a set of maximal frequent itemsets, whether there exists another one or not, is \mathsf{NP} -complete. This hardness result implies that no output-polynomial time algorithm for enumerating maximal frequent itemsets can exist unless {\mathsf{P}}={\mathsf{NP}} . In the case of subgraph mining, computing frequency often leads to \mathsf{NP} -complete graph problems, e.g., maximum clique, subgraph isomorphism, Hamiltonian path, and so on ( 25 , 24 ) . Moreover, the maximal/closed frequent subgraph mining is intractable even if the graphs are two trees ( 28 ) . Thus, the maximal/closed frequent subgraph mining is hard even when frequency can be computed in polynomial time. As for maximal/closed frequent subsequence mining, due to its countless applications in domains such as text analysis or biological data, many practical algorithms have been developed ( 37 , 4 , 19 , 38 , 33 ) . Surprisingly, however, there are still no results on its theoretical complexity. In this paper, we seek to characterize this complexity, and to do so we start from the problem of enumerating maximal common subsequences, hereafter MCS Enumeration . For a set of strings \mathcal{S}=\{S_{1},\ldots,S_{k}\} and a string S , the frequency of S is the number of strings in \mathcal{S} that contain S as a subsequence. MCS Enumeration asks for every string S whose frequency is exactly k , i.e., is common to all strings in \mathcal{S} , and that is maximal in the sense that S is not a subsequence of any other common subsequence of \mathcal{S} . MCSs are a more general variant of the classic longest common subsequence (LCS) problem, as LCSs are simply MCSs of maximum length, and their complexity was thoroughly investigated ( 1 ) . In turn, MCSs are a special case of the closed frequent subsequences, that are all the strings S whose superstrings have lower frequency then S , and its complexity remains open. The main result of this paper is a negative one, as we prove that no efficient enumeration algorithm exists for MCS Enumeration unless {\mathsf{P}}={\mathsf{NP}} . Moreover, we investigate restricted instances of the problem, as well as how this complexity affects related problems such as counting, assessment and indexing. A summary of the problems studied and our results is given in Section 1.2 . 1.1. Enumeration, counting, assessment, and indexing Enumeration problems are related to, but still fundamentally