Solving the maximum duo-preservation string mapping problem with linear programming

Abstract In this paper, we introduce the maximum duo-preservation string mapping problem (MPSM), which is complementary to the minimum common string partition problem (MCSP). When each letter occurs at most k times in any input string, the version of MPSM is called k -MPSM. In order to design approximation algorithms for MPSM, we also introduce the constrained maximum induced subgraph problem (CMIS) and the constrained minimum induced subgraph (CNIS) problem. We show that both CMIS and CNIS are NP-complete. We also study the approximation algorithms for the restricted version of CMIS, which is called k -CMIS ( k ⩾ 2 ). Using Linear Programming method, we propose an approximation algorithm for 2-CMIS with approximation ratio 2 and an approximation algorithm for k -CMIS ( k ⩾ 3 ) with approximation ratio k 2 . Based on approximation algorithms for k -CMIS, we get approximation algorithms for k -MPSM with the same approximation ratio.