In this paper, we study the problem of constructing a (1/ε)-well-separated pair decomposition (WSPD) for a point set of size n in the Massively Parallel Computation (MPC) model, where multiple machines work in parallel and communicate in synchronous rounds. We present an O(1)-round MPC algorithm that constructs a O(1/ε)-WSPD of size (1/ε)^O(ddim) ⋅ Õ(n) for point sets in a metric space of a constant doubling dimension ddim, with high probability, using (1/ε)^O(ddim) ⋅ Õ(n) total space and O(n^δ) space per machine for a constant δ ∈ (0,1). In the d-dimensional Euclidean space, we can improve the size of the WSPD and the total space to (1/ε)^O(d) n. This improves the best-known algorithm [FOCS'93] for computing a WSPD which requires O(log n) rounds and works only in Euclidean spaces. As a consequence, the following problems can be solved in O(1) rounds in the MPC model: computing a (1+ε)-spanner, a (1-ε)-approximation of the diameter, the closest pair, and the k-nearest neighbors (k-NN). While our k-NN algorithm is specific to Euclidean space, the other three problems can be solved in both Euclidean and doubling metric spaces.

Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph G, to find a minimum set S of vertices in G such that there is a unique minimum vertex cover of G containing S. We show that PAU-VC is fixed parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in polynomial time on split graphs and unit interval graphs.

In this paper, we study fundamental parameterized problems such as $k$-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs. Given a vertex set $V$ changing dynamically under vertex insertions and deletions, our goal is to maintain data structures so that the aforementioned parameterized problems on the unit disk graph induced by $V$ can be solved efficiently. Although dynamic parameterized problems on general graphs have been studied extensively, no previous work focuses on unit disk graphs. In this paper, we present the first data structures for fundamental parameterized problems on dynamic unit disk graphs. More specifically, our data structure supports $2^{O(\sqrt{k})}$ update time and $O(k)$ query time for $k$-Path/Cycle. For the other problems, our data structures support $O(\log n)$ update time and $2^{O(\sqrt{k})}$ query time, where $k$ denotes the output size.