Dominating Set on Intersection Graphs of Paths on a Grid

Saeed Mehrabi

Carleton University

Minimum dominating set is a well-known NP-hard problem, which cannot be approximated better than c log |V| for some c>0 unless P=NP. In fact, even for the intersection graphs of simple and widely used geometric objects such as axis-aligned rectangles, no constant-factor approximation is known. In this talk, I will show a constant-factor approximation algorithm for the problem on intersection graphs of one-bend axis-parallel paths in the plane. While finding improved approximation algorithms remains open, I will show that the problem is APX-hard even when the horizontal segment of every path in the graph intersects a vertical line.