{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidct32dzegsxzxcyzhjlovc4dn64fs7xcoxbmyku5l35ztfjmbqqa",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mibqfsbsdpf2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.26176v1",
  "publishedAt": "2026-03-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ryosuke Yamano",
    "Tetsuo Shibuya"
  ],
  "textContent": "**Authors:** Ryosuke Yamano, Tetsuo Shibuya\n\nThe Shortest Common Superstring (SCS) problem is a fundamental task in sequence analysis. In genome assembly, however, the double-stranded nature of DNA implies that each fragment may occur either in its original orientation or as its reverse complement. This motivates the Shortest Common Superstring with Reverse Complements (SCS-RC) problem, which asks for a shortest string that contains, for each input string, either the string itself or its reverse complement as a substring. The previously best-known approximation ratio for SCS-RC was $\\frac{23}{8}$. In this paper, we present a new approximation algorithm achieving an improved ratio of $\\frac{8}{3}$. Our approach computes an optimal constrained cycle cover by reducing the problem, via a novel gadget construction, to a maximum-weight perfect matching in a general graph. We also investigate the computational hardness of SCS-RC. While the decision version is known to be NP-complete, no explicit inapproximability results were previously established. We show that the hardness of SCS carries over to SCS-RC through a polynomial-time reduction, implying that it is NP-hard to approximate SCS-RC within a factor better than $\\frac{333}{332}$. Notably, this hardness result holds even for the DNA alphabet.",
  "title": "Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements"
}