Classical and parameterized complexity of covering problems in line segment arrangements
M. Rema, R. Subashini, Subhasree Methirumangalath, Varun Rajan · International Journal of Computer Mathematics Computer Systems Theory · 2025
We study two covering problems on line segment arrangements – Cell Cover for Segments (CCS) and Guarding a Set of Segments (GSS) – by modelling these arrangements as planar graphs. In the CCS problem, the goal is to cover all segments using the minimum number of cells in the arrangement. We prove that the decision version of CCS is NP-complete. The GSS problem, previously shown to be NP-complete (Brimkov et al., Guarding a set of line segments in the plane. Theor. Comput. Sci. 412 (2011), pp. 1313–1324), seeks to cover all segments with the fewest number of vertices. For GSS, we present a FPT algorithm with runtime O∗(k2k), where k is the solution size. Additionally, we show that GSS can be solved in O∗(4k) when the underlying graph is outerplanar. We also introduce a new structural parameter, face density (d), and provide an O∗(dk) FPT algorithm for GSS problem.