Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable

2013/05/03 by Laurent Bulteau, Christian Komusiewicz, Bulteau, Laurent +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms

paper · doi:10.48550/arxiv.1305.0649

openalex publication_date 2013/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The NP-hard Minimum Common String Partition problem asks whether two strings x and y can each be partitioned into at most k substrings, called blocks, such that both partitions use exactly the same blocks in a different order. We present the first fixed-parameter algorithm for Minimum Common String Partition using only parameter k.

Cited by

• Designing Compact ILPs via Fast Witness Verification

Related

• A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications
• Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
• On Solving the Minimum Common String Partition Problem by Decision Diagrams
• Solving the Minimum Common String Partition Problem with the Help of Ants
• Parameterized Tractability of the Maximum-Duo Preservation String Mapping Problem