What type of study is this?

This is a Quantitative Study study.

October 20, 2025Open Access

Hardness and Algorithmic Results for Roman \3\-Domination

Key Points

The roman 3-domination problem is NP-complete on split graphs, showing high complexity.
A polynomial-time algorithm exists for block graphs, providing a significant resolution to an open question.
This work expands upon known NP-completeness on other graph classes like bipartite and chordal graphs.
The problem is also W[2]-hard when parameterized by weight, indicating further computational challenges.

Abstract

A Roman \3\-dominating function on a graph G = (V, E) is a function f: V \0, 1, 2, 3\ such that for each vertex u V, if f (u) = 0 then ₕ ₍ (ₔ) f (v) 3 and if f (u) = 1 then ₕ ₍ (ₔ) f (v) 2. The weight of a Roman \3\-dominating function f is ₔ ₕ f (u). The objective of is to compute a Roman \3\-dominating function of minimum weight. The problem is known to be NP-complete on chordal graphs, star-convex bipartite graphs and comb-convex bipartite graphs. In this paper, we study the complexity of and show that the problem is NP-complete on split graphs. In addition, we prove that the problem is W2-hard parameterized by weight. On the positive front, we present a polynomial-time algorithm for block graphs, thereby resolving an open question posed by Chaudhary and Pradhan Discrete Applied Mathematics, 2024.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Sangam Balchandar Reddy (Sun,) studied this question.

synapsesocial.com/papers/68f6379bb481a140a36cf4d2 https://doi.org/https://doi.org/10.48550/arxiv.2509.23615

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark

View Full Paper