109
Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints
arXiv:2512.18223v1 Announce Type: new
Abstract: A geometric intersection graph is constructed over a set of geometric objects, where each vertex represents a distinct object and an edge connects two vertices if and only if the corresponding objects intersect. We examine the problem of finding a maximum clique in the intersection graphs of segments and disks under grounded and stabbed constraints. In the grounded setting, all objects lie above a common horizontal line and touch that line. In the stabbed setting, all objects can be stabbed with a common line.
- We prove that finding a maximum clique is NP-hard for the intersection graphs of upward rays. This strengthens the previously known NP-hardness for ray graphs and settles the open question for the grounded segment graphs. The hardness result holds in the stabbed setting.
- We show that the problem is polynomial-time solvable for intersection graphs of grounded unit-length segments, but NP-hard for stabbed unit-length segments.
- We give a polynomial-time algorithm for the case of grounded disks. If the grounded constraint is relaxed, then we give an $O(n^3 f(n))$-time $3/2$-approximation for disk intersection graphs with radii in the interval $[1,3]$, where $n$ is the number of disks and $f(n)$ is the time to compute a maximum clique in an $n$-vertex cobipartite graph. This is faster than previously known randomized EPTAS, QPTAS, or 2-approximation algorithms for arbitrary disks. We obtain our result by proving that pairwise intersecting disks with radii in $[1,3]$ are 3-pierceable, which extends the 3-pierceable property from the long known unit disk case to a broader class.
Abstract: A geometric intersection graph is constructed over a set of geometric objects, where each vertex represents a distinct object and an edge connects two vertices if and only if the corresponding objects intersect. We examine the problem of finding a maximum clique in the intersection graphs of segments and disks under grounded and stabbed constraints. In the grounded setting, all objects lie above a common horizontal line and touch that line. In the stabbed setting, all objects can be stabbed with a common line.
- We prove that finding a maximum clique is NP-hard for the intersection graphs of upward rays. This strengthens the previously known NP-hardness for ray graphs and settles the open question for the grounded segment graphs. The hardness result holds in the stabbed setting.
- We show that the problem is polynomial-time solvable for intersection graphs of grounded unit-length segments, but NP-hard for stabbed unit-length segments.
- We give a polynomial-time algorithm for the case of grounded disks. If the grounded constraint is relaxed, then we give an $O(n^3 f(n))$-time $3/2$-approximation for disk intersection graphs with radii in the interval $[1,3]$, where $n$ is the number of disks and $f(n)$ is the time to compute a maximum clique in an $n$-vertex cobipartite graph. This is faster than previously known randomized EPTAS, QPTAS, or 2-approximation algorithms for arbitrary disks. We obtain our result by proving that pairwise intersecting disks with radii in $[1,3]$ are 3-pierceable, which extends the 3-pierceable property from the long known unit disk case to a broader class.
Anonymous
No comments yet.