Summer Internship at IMSc - Chennai

Worked at Institute of Mathematical Sciences - Chennai (IMSc) as a summer intern under Professor Venkatesh Raman on proving W-hardness for Roman Dominating Functions and its variants.

Report

This project attempts to prove W-hardness for Roman Domination as well as Weak Roman Domination for Split Graphs through Parameter Preserving Reduction. It also tries to prove W-hardness for Bipartite Graphs in Roman Domination. The report contains the proofs for the following problems

• Parameter Preserving Reduction from Set Cover to Roman Domination on Split Graphs
• Parameter Preserving Reduction from Set Cover to 2-Redundant Set Cover
• Parameter Preserving Reduction from 2-Redundant Set Cover to Weak Roman Domination on Split Graphs
• Parameter Preserving Reduction from Set Cover to Roman Domination on Bipartite Graphs

The report that details all the definitions and proofs for all these problems can be found here