2023/02/12 by Sergey Bereg, Bereg, Sergey, Yuya Higashikawa +9 · 1 citation
Computer Science · #68 #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2302.05937
openalex publication_date 2023/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set P of 2n points in the plane, and two sites c1 and c2, compute two n-stars S1 and S2 centered at c1 and c2 respectively such that the maximum weight of S1 and S2 is minimized. This problem is strongly NP-hard by a reduction from Equal-size Set-Partition with Rationals. Then we consider two variations of the Two-Squirrel problem, namely the Two-MST and Two-TSP problem, which are both NP-hard. The NP-hardness for the latter is obvious while the former needs a non-trivial reduction from Equal-size Set-Partition with Rationals. In terms of approximation algorithms, for Two-MST and Two-TSP we give factor 3.6402 and 4+ε approximations respectively. Finally, we also show some interesting polynomial-time solvable cases for Two-MST.