arXiv preprint ·
Near-Linear Time Maximum Clique in Circular Arc Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question posed by Bhattacharya and Kaller [J. Algorithms 1997] and Tiskin [CPM 2006]. Our algorithm runs in time $O(n\log^2 n)$, given $n$ circular arcs, where the graph is implicit. Previous approaches take at least quadratic time (unless the implicitly given graph is sparse). To overcome the quadratic barrier, we solve (structured and related) instances of bipartite matching by interpreting them as a single, offline 2D dominance problem, which in turn we model as a shortest paths problem in a planar grid graph. This allows for the final step, which builds on the theory of Monge matrices to obtain sparse representation and efficient distance computations in the grid graph. Additionally, we provide an observation about the structure of circular arc cliques that leads to an algorithm for the weighted version of the problem with a new parameter, the minimum load $d$, which we define as the minimum, over all points on the circle, of the number of arcs containing that point. The algorithm runs in time $O(dn\log\log n + n\log n)$. This is always at least as good as the previous best maximum weight clique algorithm, which runs in time $O(m\log\log n + n\log n)$, where $m$ denotes the number of edges in the implicit intersection graph, because the minimum load satisfies $d \le 2m/n$. [Abstract shortened to meet arXiv's requirements.]
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
Navigable Graphs for Low-Dimensional Hyperbolic Spaces
Splitting Planar Necklaces with Few Straight Cuts
Online geometric matching and segments block points
A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.