2023/06/30 by Berthe, Gaétan, Bougeret, Marin, Gonçalves, Daniel +1 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2306.17710
In this paper we investigate the existence of subexponential parameterized algorithms of three fundamental cycle-hitting problems in geometric graph classes. The considered problems, Triangle Hitting (TH), Feedback Vertex Set (FVS), and Odd Cycle Transversal (OCT) ask for the existence in a graph G of a set X of at most k vertices such that G-X is, respectively, triangle-free, acyclic, or bipartite. Such subexponential parameterized algorithms are known to exist in planar and even H-minor free graphs from bidimensionality theory [Demaine et al., JACM 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of "fat" objects ([Grigoriev et al., FOCS 2022] and [Lokshtanov et al., SODA 2022]). In this paper we focus on "thin" objects by considering intersection graphs of segments in the plane with d possible slopes (d-DIR graphs) and contact graphs of segments in the plane. Assuming the ETH, we rule out the existence of algorithms: - solving TH in time 2o(n) in 2-DIR graphs; and - solving TH, FVS, and OCT in time 2o(√(n)) in K2,2-free contact 2-DIR graphs. These results indicate that additional restrictions are necessary in order to obtain subexponential parameterized algorithms for %these problems. In this direction we provide: - a 2^O(k3/4⋅ log k)nO(1)-time algorithm for FVS in contact segment graphs; - a 2^O(√ d⋅ t2 log t⋅ k2/3log k) nO(1)-time algorithm for TH in Kt,t-free d-DIR graphs; and - a 2^O(k7/9log3/2k) nO(1)-time algorithm for TH in contact segment graphs.