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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Roman Cycle Hitting Set

  • Satyabrata Jana,
  • Sounak Modak,
  • Saket Saurabh,
  • Kushal Singanporia

摘要

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.