Maximum Clique and Minimum Clique Partition in Visibility Graphs

In an alternative approach to "characterizing" the graph class of visibility graphs of simple polygons, we study the problem of finding a maximum clique in the visibility graph of a simple polygon with n vertices. We show that this problem is very hard, if the input polygons are allowed to contain holes: a gap-preserving reduction from the maximum clique problem on general graphs implies that no polynomial time algorithm can achieve an approximation ratio of n1=8; for any >0, 4 unless NP = P.To demonstrate that allowing holes in the input polygons makes a major di erence, we propose an O(n³) algorithm for the maximum clique problem on visibility graphs for polygons without holes (other O(n³) algorithms for this problem are already known [3, 6, 7]). Our algorithm also nds the maximum weight clique, if the polygon vertices are weighted. We then proceed to study the problem of partitioning the vertices of a visibility graph of a polygon into a minimum number of cliques. This problem is AP X-hard for polygons without holes (i.e., there exists a constant >0 such that no polynomial time algorithm can achieve an approximation ratio of 1 +). We present anapproximation algorithm for the problem that achieves a logarithmic approximation ratio by iteratively applying the algorithm for nding maximum weighted cliques. Finally, we show that the problem of partitioning the vertices of a visibility graph of a polygon with holes cannot be approximated with a ratio of n1=14; for any >0 by proposing a gap-preserving reduction. 4 Thus, the presence of holes in the input polygons makes this partitioning problem provably harder