In this paper, we study the maximum clique problem on hyperbolic random graphs. A hyperbolic random graph is a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. We propose a simple algorithm for finding a maximum clique in hyperbolic random graph. We first analyze the running time of our algorithm theoretically. We can compute a maximum clique on a hyperbolic random graph $G$ in $O(m + n^{4.5(1-α)})$ expected time if a geometric representation is given or in $O(m + n^{6(1-α)})$ expected time if a geometric representation is not given, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively, and $α$ denotes a parameter controlling the power-law exponent of the degree distribution of $G$. Also, we implemented and evaluated our algorithm empirically. Our algorithm outperforms the previous algorithm [BFK18] practically and theoretically. Beyond the hyperbolic random graphs, we have experiment on real-world networks. For most of instances, we get large cliques close to the optimum solutions efficiently.

In this paper, we study the Planar Disjoint Paths problem: Given an undirected planar graph G with n vertices and a set T of k pairs (si, ti)ki=1 of vertices, the goal is to find a set P of k pairwise vertex-disjoint paths connecting si and ti for all indices i ∈ {1,…, k}. We present a 2O(k2)n-time algorithm for the Planar Disjoint Paths problem. This improves the two previously best-known algorithms: 22O(k)-time algorithm [Discrete Applied Mathematics 1995] and 2O(k2)n6-time algorithm [STOC 2020]. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.03341 † This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.2020R1C1C1012742).