2024/11/20 by Pradeesha Ashok, Gautam K. Das, Ashok, Pradeesha +7 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Benford’s Law and Fraud Detection #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2411.13141
openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G=(V,E), a function f:V→ \0,1,2\ is said to be a Roman Dominating function (RDF) if for every v∈ V with f(v)=0, there exists a vertex u∈ N(v) such that f(u)=2. A Roman Dominating function f is said to be an Independent Roman Dominating function (IRDF), if V1∪ V2 forms an independent set, where Vi=\v∈ V~\vert~f(v)=i\, for i∈ \0,1,2\. The total weight of f is equal to ∑v∈ V f(v), and is denoted as w(f). The Roman Domination Number (resp. Independent Roman Domination Number) of G, denoted by γR(G) (resp. iR(G)), is defined as min\w(f)~\vert~f is an RDF (resp. IRDF) of G\. For a given graph G, the problem of computing γR(G) (resp. iR(G)) is defined as the Roman Domination problem (resp. Independent Roman Domination problem). In this paper, we examine structural parameterizations of the (Independent) Roman Domination problem. We propose fixed-parameter tractable (FPT) algorithms for the (Independent) Roman Domination problem in graphs that are k vertices away from a cluster graph. These graphs have a set of k vertices whose removal results in a cluster graph. We refer to k as the distance to the cluster graph. Specifically, we prove the following results when parameterized by the deletion distance k to cluster graphs: we can find the Roman Domination Number (and Independent Roman Domination Number) in time 4knO(1). In terms of lower bounds, we show that the Roman Domination number can not be computed in time 2εknO(1), for any 0<ε<1 unless a well-known conjecture, SETH fails. In addition, we also show that the Roman Domination problem parameterized by distance to cluster, does not admit a polynomial kernel unless NP ⊆ coNP/poly.