(Independent) Roman Domination Parameterized by Distance to Cluster

Arti Pandey; Gautam K. Das; Kaustav Paul; Pradeesha Ashok; Subhabrata Paul

REVIEW 3 major objections 4 minor 14 references

(Independent) Roman Domination Parameterized by Distance to Cluster

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that Roman Domination and Independent Roman Domination, parameterized by the number k of vertices whose deletion leaves a cluster graph, are fixed-parameter tractable with running time 4^k n^{O(1)}, and that the 4^k base…

desk verdict The Roman Domination half is solid; the Independent variant's FPT DP has a genuine exact-one bug that sinks Theorem 19 as written. read the letter →

arxiv 2411.13141 v1 pith:A2EYPQY4 submitted 2024-11-20 cs.CC cs.DMcs.DSmath.CO

Pradeesha Ashok , Gautam K. Das , Arti Pandey , Kaustav Paul , Subhabrata Paul This is my paper · ORCID

classification cs.CCcs.DMcs.DSmath.CO MSC 05C6968Q2768R10

keywords RomanDominationIndependentdistancetoclustervertexdeletionfixed-parametertractabilitySETHkernelization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Roman domination asks for a labeling of vertices by 0, 1, 2 with minimum total weight in which every 0-labeled vertex has a 2-labeled neighbor; independent Roman domination adds the requirement that the non-zero labels form an independent set. This paper studies both problems on graphs that are k vertex deletions away from a cluster graph, i.e., graphs with a set S of k vertices whose removal leaves a disjoint union of cliques. It proves that both problems are fixed-parameter tractable with parameter k, solvable in 4^k $n^{{O(1)}}$ time. The same paper shows that the running-time base 4 cannot be lowered to $2^{{εk}}$ for Roman Domination unless SETH fails, and that the problem admits no polynomial kernel unless NP⊆coNP/poly.

What carries the argument

The central object is a partition-respecting set cover that the paper calls Set-CoverWithPartition (and its independent variant Independent-Set-CoverWithPartition). Candidate sets are the neighborhoods inside S of individual vertices of G−S; vertices of the same clique form one block, and each block carries a flag 1 or 2 recording whether that clique has one vertex, or two or more vertices, not already protected by S2. The DP state OPT[W,j,b] holds the minimum cost of covering W⊆S using the first j candidate sets while the flag of the current block is temporarily b; transitions charge 2 for picking a set, add 1 for every flag-1 block left untouched, and reset earlier blocks to their original flags. This flag bookkeeping is what allows the algorithm to remember, in only 3·$2^{{|S|}}$·m states, which cliques still demand a picked vertex.

What would settle it

Take a small graph with cluster deletion set S of size 2 or 3 and three cliques in G−S whose flags force a flag-1 block to be left empty while a later flag-2 block is filled; run the DP from Theorem 12 and compare its answer with a brute-force enumeration of all 3^n labelings. Any instance where the two disagree on the minimum Roman domination weight falsifies the recurrence.

Watch

Extended reading notes

Core claim

For a graph G with a cluster vertex deletion set S of size k, the paper establishes that Roman Domination (RD-CVD) and Independent Roman Domination (IRD-CVD) can be solved in 4^k $n^{{O(1)}}$ time. The algorithm guesses the two sets S1,S2 of vertices of S that receive labels 1 and 2 in an optimal solution, then exploits the structural fact that in any clique of G−S having two vertices unprotected by S2, some vertex of that clique can be assumed to carry label 2. This converts the residual problem into a partition-respecting set cover: each clique becomes a block of candidate subsets of S, flagged by whether it must contain at least one (or exactly one, in the independent case) chosen vertex, and the cost is 2 per chosen vertex plus 1 per flag-1 block left empty. A dynamic program indexed by subsets W⊆S and positions among the candidate sets solves each converted instance in $2^{{|S|}}$ $n^{{O(1)}}$ time, and summing over all guesses of S1,S2 yields 4^k $n^{{O(1)}}$. The lower-bound section constructs a split graph from a d-hitting-set instance so that a hitting set of size t corresponds exactly to a Roman dominating function of weight 2t, which transfers both the SETH lower bound and the no-polynomial-kernel result.

Load-bearing premise

The correctness claim for both algorithms rests on the DP recurrences' assumption that resetting earlier blocks to their original flags while tracking only the current block's modified flag correctly handles every pattern of empty and non-empty cliques; if that state compression misses any combination, the computed optimum could be wrong.

Editorial extensions

If this is right

Roman Domination and Independent Roman Domination are both fixed-parameter tractable when the parameter is the distance to a cluster graph, with running time 4^k n^{O(1)}.
A cluster vertex deletion set of size k is the only global structure needed; the algorithms do not require bounded treewidth or any property beyond the deletion set itself.
Under SETH, the 4^k factor cannot be improved all the way to 2^{εk} for Roman Domination parameterized by distance to cluster, so the exponential base is not an accident.
Unless NP⊆coNP/poly, Roman Domination parameterized by distance to cluster has no polynomial kernel, so no polynomial-time preprocessing can compress the instance to size polynomial in k.
The same lower bounds hold for Roman Domination parameterized by vertex cover number, because the constructed graph is a split graph whose clique side U is a vertex cover.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The flag-compression DP is likely to transfer to other 'choose vertices with block constraints' covering problems on cluster graphs, such as variants of domination that only require one protected vertex per clique.
The conditional lower bound does not rule out an O((4−δ)^k n^{O(1)}) algorithm; the next natural target is whether the state space can be reduced below 2^{|S|} per guess.
A similar SETH lower bound should hold for the independent variant, since the same split-graph gadget with an independent-set condition admits an analogous reduction, though the paper only proves the lower bound for Roman Domination.
Because the cluster part is solved by set cover over the k deletion vertices, the algorithm's practical bottleneck is the 2^k DP over subsets of S; structural parameters that shrink k, such as neighborhood diversity, may be the more useful way to attack real instances.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

Two things you should know about this paper. First, the RD-CVD side looks genuinely good: the 4^k FPT algorithm, the SETH lower bound, and the no-polynomial-kernel result are all plausible and the reduction from d-HITTING SET is clean. The set-cover-with-partition framework and the T0/T1/T2 clique classification are a sensible adaptation from Goyal et al., and the non-independent version (Theorem 12/14) holds up on inspection apart from a minor summation typo that omits empty S1/S2 guesses.

Second, the Independent Roman Domination half has a real bug. The ISCP DP in Theorem 17 claims to enforce "exactly one set from each flag-2 block," but the recurrence does not track whether a set from the current block was already selected. When S_{j+1} is not the first set of its block, the pick option calls OPT[W\S_{j+1}, j, 0], resetting the block's flag to 0. Nothing prevents that subproblem from containing an earlier set from the same block, so adding S_{j+1} gives two sets from a flag-2 block, violating condition (a). The concrete counterexample works: U={a,b}, F={S1={a}, S2={b}}, one flag-2 block. No valid solution exists, but the DP returns 4 by picking both sets. This is not a contrived edge case; it arises naturally after the IRD-CVD reduction. The recurrence also uses b=0 in subproblems even though b was defined only over {1,2}. I believe this is a genuine gap, not a typo.

So the paper deserves a serious referee, but not acceptance in its current form. The RD-CVD results and the lower bounds are worth publishing; the IRD-CVD claim is unproven. A fix would require an extra state bit or a different DP formulation, and the authors should also clarify the summation and the duplicate E2 definition.

My recommendation: send to peer review, but expect major revision. The referees should focus on Theorem 17 and the ISCP recurrence.

Best, [Your name]

Referee Report

3 major / 4 minor

Summary. The paper studies Roman Domination (RD) and Independent Roman Domination (IRD) parameterized by the distance k to a cluster graph. It claims FPT algorithms running in 4^k n^{O(1)} for both problems, a SETH-based lower bound excluding 2^{εk} n^{O(1)} for RD, and a polynomial-kernel lower bound for RD. The algorithms guess the restriction of the solution to the deletion set S and reduce the remaining problem to set-cover variants with block constraints, solved by dynamic programming over subsets of S. The lower bounds are obtained by a reduction from d-HITTING SET.

Significance. If the FPT algorithms were correct, the paper would be a useful contribution to structural parameterizations of Roman Domination, complementing the lower bounds. The lower-bound part (Theorems 20-25) is sound and clearly presented, and the IRD side of the positive results appears salvageable. The SCP/ISCP DP framework is promising, but the RD-CVD algorithm as written is not correct: the base case of the SCP DP rejects valid solutions, and Theorem 14's summation skips empty guesses. These are load-bearing issues that require a substantive revision of the positive section before the main FPT claims can be accepted.

major comments (3)

[Section 3.1, Theorem 12 (base cases)] The DP has a false negative for the first block. Take U={a,b,c,d}, one block β1={S1,S2} with S1={a,b}, S2={c,d}, and flag f1=2. The solution F'={S1,S2} covers U, satisfies F'∩β1≠∅, and has cost 4, so the SCP optimum is at most 4. However, the base case for W≠∅ requires W⊆S_i for some i≤j, hence OPT[{a,b,c,d},2,2]=∞; the recurrence is only invoked for S_{j+1} not in β1, so this value is never corrected. This SCP instance is realized as an RD-DisjointCluster instance produced by the S2=S1=∅ guess for the graph with S={a,b,c,d} and one cluster clique {x,y,z} where x is adjacent only to a,b and y only to c,d; that graph has γ_R=4. Thus the proof of Theorem 14 relies on a subroutine that is false for a valid guess. The base case must be replaced by a correct DP over the first block (for example, by using a dummy previous block and the same recurrence).
[Section 3.1, Theorem 14 (summation range)] The double summation runs i1=1..k and i2=1..k-i1, so guesses with S1=∅ or S2=∅ are never considered. The optimal RD function in the counterexample above has S1=S2=∅, and such cases are natural for this problem. The index ranges should start at 0; as written, the 4^k time bound does not cover all relevant subproblems, even if the SCP DP were corrected.
[Section 3.2, Theorem 17 (statement generality)] I checked the stress-test counterexample and it does not produce a false positive for the IRD-CVD instances: for U={a,b} and a single flag-2 block {S1={a},S2={b}}, the base case (all sets are in β1) returns ∞ for W={a,b}, not 4. The DP does enforce the exact-one condition for the instances delivered by the IRD-CVD reduction. However, Theorem 17 as stated is false for general ISCP because flag-1 blocks may contain multiple sets, and the recurrence for a non-first set of a block jumps to the previous block after a pick, preventing more than one selection from a flag-1 block; the ISCP problem imposes no such limit. Since the reduction creates only singleton flag-1 blocks, the IRD-CVD result is not affected, but the theorem statement overclaims and should be restricted accordingly.

minor comments (4)

[Section 4, Theorem 21] In the construction of the graph G, the edge set E2 is defined twice; the second definition should be E3.
[Section 2.3] The heading contains a typo: 'Defenitions' should be 'Definitions'.
[Abstract and Section 2.4] The phrase 'can not be solved' should be 'cannot be solved', and 'adaption' should be 'adaptation'.
[Section 3.1, Observation 10] Observation 10 proves only that some optimal solution has at least one selected vertex in each T2 clique; the DP's handling of multiple selections from a block is not explained, which contributed to the base-case error in Theorem 12. A short explanatory lemma about the structure of optimal solutions would improve the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: algorithms derive from definitions and lower bounds rely on external SETH/d-HITTING SET results.

full rationale

The paper's derivation chain is self-contained rather than circular. The upper-bound algorithms (Theorems 12, 14, 17, 19) start from the definitions of Roman Domination and Independent Roman Domination, guess the labels of the k vertices in the cluster vertex deletion set, and then solve the remaining problem via reductions to Set-Cover-with-Partition and Independent-Set-Cover-with-Partition. The DP recurrences are stated explicitly in terms of universe subsets and flags, with no fitted parameter renamed as a prediction and no target theorem used as an input. The lower bounds (Theorems 20, 21, 23, 25) are reductions from d-HITTING SET, whose SETH hardness and kernel lower bound are cited from external literature (Cygan et al. and Dom et al.); the reduction in Theorem 21 is a genuine polynomial-time equivalence with both directions proved, not a renaming of the target quantity. The paper cites prior work [10] for technique adaptation, but the cited authors are not the present authors and the cited result is not the theorem being derived, so there is no self-citation load-bearing chain. The skeptical concern about Theorem 17's DP possibly failing to enforce the 'exactly one' condition for flag-2 blocks is a potential correctness defect, not circularity: even if the DP is wrong, it is wrong because of missing state information, not because it assumes the answer it claims to compute. Since no equation reduces to another by construction and no prediction is statistically forced by a fit, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters or new entities. It relies on standard complexity conjectures (SETH) and cited theorems for lower bounds, plus a cited algorithm for finding the CVD set. The algorithmic results themselves are derived from first principles.

assumptions (4)

domain assumption Strong Exponential Time Hypothesis (SETH) as stated in Conjecture 8
Used to derive the lower bound that RD-CVD cannot be solved in 2^{εk} n^{O(1)} for ε<1. This is a standard conjecture, stated explicitly and not proven.
standard math Theorem 20: equivalence between SETH and the non-existence of O(2^{εn}) algorithms for d-HITTING SET (Cygan et al. 2016)
Used to transfer the SETH lower bound to RD-CVD via the reduction in Theorem 21. Cited from prior work.
standard math Theorem 24: d-HITTING SET parameterized by universe size has no polynomial kernel unless NP ⊆ coNP/poly (Dom et al. 2014)
Used with the polynomial parameter transformation to conclude that RD-CVD has no polynomial kernel unless NP ⊆ coNP/poly.
standard math Existence of a 1.92^k n^{O(1)} FPT algorithm for finding a cluster vertex deletion set (Boral et al. 2016)
Ensures the algorithm can obtain the cluster vertex deletion set S if it is not given as input. Cited in Section 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of (Independent) Roman Domination Parameterized by Distance to Cluster." pith.science (2026). https://pith.science/paper/A2EYPQY4

@misc{pith2026241113141,
  author       = {Pith},
  title        = {Pith review of: (Independent) Roman Domination Parameterized by Distance to Cluster},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A2EYPQY4}},
  note         = {Machine review of arXiv:2411.13141}
}

abstract

Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is said to be a \emph{Roman Dominating function} (RDF) if for every $v\in V$ with $f(v)=0$, there exists a vertex $u\in N(v)$ such that $f(u)=2$. A Roman Dominating function $f$ is said to be an \emph{Independent Roman Dominating function} (IRDF), if $V_1\cup V_2$ forms an independent set, where $V_i=\{v\in V~\vert~f(v)=i\}$, for $i\in \{0,1,2\}$. The total weight of $f$ is equal to $\sum_{v\in V} f(v)$, and is denoted as $w(f)$. The \emph{Roman Domination Number} (resp. \emph{Independent Roman Domination Number}) of $G$, denoted by $\gamma_R(G)$ (resp. $i_R(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 $\gamma_R(G)$ (resp. $i_R(G)$) is defined as the \emph{Roman Domination problem} (resp. \emph{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 $4^kn^{O(1)}$. In terms of lower bounds, we show that the Roman Domination number can not be computed in time $2^{\epsilon k}n^{O(1)}$, for any $0<\epsilon <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 $\subseteq$ coNP$/$poly.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages

[1]

Fellows, and Rolf Niedermeier

Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM , 51(3):363--384, 2004

work page 2004
[2]

Bodlaender, St \' e phan Thomass \' e , and Anders Yeo

Hans L. Bodlaender, St \' e phan Thomass \' e , and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. , 412(35):4570--4578, 2011

work page 2011
[3]

A fast branching algorithm for cluster vertex deletion

Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. , 58(2):357--376, 2016

work page 2016
[4]

On problems as hard as cnf-sat

Marek Cygan, Holger Dell, Daniel Lokshtanov, D\' a niel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstr\" o m. On problems as hard as cnf-sat. ACM Trans. Algorithms , 12, may 2016

work page 2016
[5]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

2015
[6]

Kernelization lower bounds through colors and ids

Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Trans. Algorithms , 11, 2014

work page 2014
[7]

Downey and Michael R

Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1] . Theor. Comput. Sci. , 141(1 & 2):109--131, 1995

work page 1995
[8]

ROMAN DOMINATION: a parameterized perspective

Henning Fernau. ROMAN DOMINATION: a parameterized perspective. Int. J. Comput. Math. , 85(1):25--38, 2008

work page 2008

Show all 14 references

[9]

Fomin and Dieter Kratsch

Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010

2010
[10]

Parameterized complexity of dominating set variants in almost cluster and split graphs

Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, and Venkatesh Raman. Parameterized complexity of dominating set variants in almost cluster and split graphs. CoRR , abs/2405.10556, 2024

2024 arXiv
[11]

Which problems have strongly exponential complexity? J

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. , 63(4):512--530, 2001

2001
[12]

Mohanapriya, P

A. Mohanapriya, P. Renjith, and N. Sadagopan. Roman k-domination: Hardness, approximation and parameterized results. In Chun - Cheng Lin, Bertrand M. T. Lin, and Giuseppe Liotta, editors, WALCOM: Algorithms and Computation - 17th International Conference and Workshops, WALCOM ...

2023
[13]

Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond

Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms , 9(1):11:1--11:23, 2012

2012
[14]

Defend the roman empire! Scientific American , 281:136--138, 1999

Ian Stewart. Defend the roman empire! Scientific American , 281:136--138, 1999

1999

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Fellows, and Rolf Niedermeier

Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM , 51(3):363--384, 2004

work page 2004

[2] [2]

Bodlaender, St \' e phan Thomass \' e , and Anders Yeo

Hans L. Bodlaender, St \' e phan Thomass \' e , and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. , 412(35):4570--4578, 2011

work page 2011

[3] [3]

A fast branching algorithm for cluster vertex deletion

Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. , 58(2):357--376, 2016

work page 2016

[4] [4]

On problems as hard as cnf-sat

Marek Cygan, Holger Dell, Daniel Lokshtanov, D\' a niel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstr\" o m. On problems as hard as cnf-sat. ACM Trans. Algorithms , 12, may 2016

work page 2016

[5] [5]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

2015

[6] [6]

Kernelization lower bounds through colors and ids

Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Trans. Algorithms , 11, 2014

work page 2014

[7] [7]

Downey and Michael R

Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1] . Theor. Comput. Sci. , 141(1 & 2):109--131, 1995

work page 1995

[8] [8]

ROMAN DOMINATION: a parameterized perspective

Henning Fernau. ROMAN DOMINATION: a parameterized perspective. Int. J. Comput. Math. , 85(1):25--38, 2008

work page 2008