{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigsf5dkh5u3hcyqyjysk4kex2qpky5tqyd6czugs7atdsu4tea7bm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mq4ofvwechx2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2607.06251v1",
  "publishedAt": "2026-07-08T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "A. Karim Abu-Affash",
    "Paz Carmi",
    "Joseph S. B. Mitchell"
  ],
  "textContent": "**Authors:** A. Karim Abu-Affash, Paz Carmi, Joseph S. B. Mitchell\n\nA circle graph is the intersection graph of a set of chords in a circle. A dominating set of a graph $G=(V,E)$ is a subset $D\\subseteq V$ such that every vertex in $V\\setminus D$ is adjacent to at least one vertex of $D$. Computing a minimum dominating set is known to be NP-hard on circle graphs. In this paper, we study the minimum dominating set problem on bipartite circle graphs, namely, circle graphs admitting a chord representation in which the chords can be partitioned into two color classes such that no two chords of the same color intersect. We prove that the problem remains NP-hard for this restricted graph class by a reduction from Planar Monotone 3-SAT. On the positive side, we present a polynomial-time 2-approximation algorithm and develop a polynomial-time approximation scheme (PTAS) based on local search.",
  "title": "The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation"
}