The Complexity of Maximal Common Subsequence Enumeration

Summary: Enumerating maximal common subsequences across multiple strings is not output-polynomial unless P=NP, extending LCS hardness to maximal frequent subsequence mining. The work then analyzes parameterized complexity w.r.t. alphabet size, number of strings, and string length, yielding tractability insights for practical algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2018
Venue: PODS
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,654 | 26.91%
DOI: 10.1145/3725252

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Giovanni Buzzega (University of Pisa)
2. Alessio Conte (University of Pisa)
3. Yasuaki Kobayashi (Hokkaido University)
4. Kazuhiro Kurita (Nagoya University)
5. Giulia Punzi (University of Pisa)

BibTeX Citation

@inproceedings{buzzega_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{The Complexity of Maximal Common Subsequence Enumeration}},
        url = {https://dl.acm.org/doi/10.1145/3725252},
        doi = {10.1145/3725252},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Buzzega, Giovanni and Conte, Alessio and Kobayashi, Yasuaki and Kurita, Kazuhiro and Punzi, Giulia},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006567919
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.6029996e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,472	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation	2019	PODS
2	7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB
3	9,232	Window-Accumulated Subsequence matching Problem is linear	1999	PODS
4	9,703	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD
5	3,324	Mining Compressed Frequent-Pattern Sets	2005	VLDB
6	8,780	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB
7	10,163	Optimal Enumeration of Regular Pattern Matches	2026	PODS
8	8,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD
9	6,230	Mining Periodic Patterns with Gap Requirement from Sequences	2005	SIGMOD
10	7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS