Roman Cycle Hitting Set
摘要
The variant of Dominating Set known as Roman Domination has been extensively studied in the fields of graph theory and graph algorithms. Fernau and Mann [arXiv:2302.11417] introduced the concept of Roman Vertex Cover and developed a fixed-parameter tractable (FPT) algorithm for the problem with running time of \(\mathcal {O}^* (2^k)\) , where k is the solution size. Building on this work, we investigate the parameterized algorithms for Roman Feedback Vertex Set (RFVS) and Roman Odd Cycle Transversal (ROCT), and demonstrate that they are also FPT. Our approach to RFVS is similar to the best-known algorithm for the non-Roman variant. However, the algorithm for ROCT is significantly different and utilizes the technique of recursive understanding and structural insights on unbreakable graphs.