Geometry Seminar

---

The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation

Speaker: Karim Abu-Affash, Shamoon College of Engineering

Location: Online

Date: Tuesday, September 8, 2026, 2 p.m.

Synopsis:

A 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 work, 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.

Notes:

Only on Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.