Pith. sign in

REVIEW 4 major objections 4 minor 49 references

Parameterized Complexity of (d,r)-Domination via Modular Decomposition

T0 review · 4 major / 4 minor · reviewed 2026-08-11 · 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 (d,r)-domination is fixed-parameter tractable in modular width plus demand, and gives polynomial compressions for two wider decomposition measures.

desk verdict Solid FPT algorithm for (d,r)-domination by modular width plus demand, but the polynomial compressions rest on unproved or false lemmas; the itp-based compression is broken as written. read the letter →

arxiv 2412.15671 v2 pith:4RKRSDZL submitted 2024-12-20 cs.CC cs.DMcs.DSmath.CO

Gennaro Cordasco , Luisa Gargano , Adele A. Rescigno This is my paper · ORCID
classification cs.CCcs.DMcs.DSmath.CO MSC 05C6968Q2705C85
keywords (dr)-dominationdominatingsetparameterizedcomplexitymodulardecompositionwidthneighborhooddiversityiteratedtypepartitionpolynomialkernel
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

This paper asks how hard it is to find a small set of vertices that covers every other vertex at least $d$ times within distance $r$, the $(d,r)$-domination problem. Its main answer is that modular structure plus demand makes the problem tractable: the problem is fixed-parameter tractable parameterized by modular width plus $d$, and it admits polynomial compressions and a polynomial kernel for the wider iterated-type-partition and neighborhood-diversity parameters. Since a $(d,r)$-dominating set of $G$ is exactly a $(d,1)$-dominating set of the $r$-th power $G^r$, the results are channeled through one reduction, assuming that taking powers does not enlarge the decomposition parameters. The stated motivation is immunization against misinformation: a small $(d,r)$-dominating set identifies people who, within a trust radius $r$ and after $d$ exposures, can debunk a false narrative.

What carries the argument

The load-bearing mechanism is a bottom-up cost computation on the modular parse tree. For each module $M$, the algorithm keeps $c_M(t)$ for $t=0,1,\dots,d$, the minimum size of a $(t,1)$-dominating set of $G[M]$. A module whose children are $G_1,\dots,G_\ell$ is solved by an integer program with at most $\ell$ variables, picking how much each child module contributes and how many extra vertices inside it are selected; the fixed-variable integer programming bound gives the $O(\ell^{2.5\ell+o(\ell)}\log|V(G)|)$ factor. The compression results reuse the same costs in an integer program over the outline graph and shrink its coefficients with simultaneous Diophantine approximation. The bridge to radius $r$ is the power-graph lemma: since $(d,r)$-dominating sets equal $(d,1)$-dominating sets of $G^r$, the same machinery applies to $G^r$.

What would settle it

Exhaustively enumerate all connected graphs on at most seven vertices, computing $mw(G)$ and $mw(G^2)$ by brute force; the first example with $mw(G^2)>mw(G)$ refutes Lemma 1 and, with it, the power-graph reductions for $r\ge 2$. A structural probe is to take a module $M$ of $G$ and check whether two vertices of $M$ acquire different external neighborhoods in $G^r$; if they do, $M$ is no longer a module of the power graph.

Watch

Extended reading notes

Core claim

The central claim is that $(d,r)$-domination becomes tractable once the graph's modular structure and the demand are small. A $(d,r)$-dominating set of $G$ is exactly a $(d,1)$-dominating set of the $r$-th power $G^r$, and the paper's Lemma 1 states that modular-width and the restricted modular cardinality do not grow when passing to $G^r$. Under that premise, the paper proves $(d,r)$-DOMINATION is fixed-parameter tractable parameterized by $mw(G)+d$, with running time $O(mw^{2.5mw+o(mw)} d(d+1)^{mw}|V(G)| \log |V(G)|)$. It also proves a polynomial compression for $(1,r)$-domination parameterized by modular width, a polynomial compression parameterized by $itp(G)+d$, and a polynomial kernel parameterized by $nd(G)+d$, the last by pruning every module to $2d$ vertices.

Load-bearing premise

The load-bearing premise is Lemma 1, stated without proof in Section 2.1: for every connected graph $G$, $mw(G^r)\le mw(G)$ and the restricted modular cardinality of $G^r$ is at most that of $G$. Every radius-$r$ result in the paper is obtained by passing to $G^r$, so if this monotonicity ever fails, the entire generalization from $r=1$ to arbitrary $r$ collapses.

Editorial extensions

If this is right

  • If the results are correct, $(d,r)$-domination is fixed-parameter tractable in $mw(G)+d$, so graphs with small modular structure and small demand are solvable even when the optimum is large.
  • Because the power-graph step is assumed to be free, the radius $r$ adds no new parameter: the same algorithm covers every distance.
  • For $d=1$, the problem has a polynomial compression parameterized by modular width on connected graphs, a boundary that is known to fail for the unrestricted input class.
  • The combined parameter $itp(G)+d$ yields a polynomial compression, while $nd(G)+d$ yields a polynomial kernel whose graph has at most $2d\cdot nd(G)$ vertices.

Reading between the lines

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

  • The most direct extension is to test Lemma 1 computationally on small graphs; since it is stated without proof, a single counterexample would split the paper's results into a radius-1 half and a radius-unknown half.
  • The module-pruning rule behind the neighborhood-diversity kernel is a general recipe: any domination variant where only the count of chosen vertices inside a module matters can likely be kernelized by truncating each module to $O(d)$ vertices.
  • The cost-recursion with an integer program over child modules looks adaptable to weighted vertices or non-uniform per-vertex demands, at the price of a larger cost array $c_M(t)$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper studies the (d,r)-Domination problem, in which every vertex outside the selected set must have at least d selected vertices within distance r. The main results are: (1) an FPT algorithm parameterized by modular-width plus demand, based on a bottom-up dynamic program over the modular decomposition tree with a small ILP at each node; (2) a polynomial compression for (1,r)-Domination parameterized by modular-width on connected graphs; (3) a polynomial compression for (d,r)-Domination parameterized by iterated type partition number plus demand; and (4) a polynomial kernelization for (d,r)-Domination parameterized by neighborhood diversity plus demand. A central lemma asserts that modular-width and G-modular cardinality do not increase when passing to the r-th power G^r, which the paper uses to reduce all radius-r results to the radius-1 case.

Significance. If correct, the FPT algorithm in Section 3 would be a concrete and useful contribution: it gives an explicit, checkable ILP-based algorithm for a parameter that can be small on dense graphs, and the compression and kernelization results would extend known kernelization results for Dominating Set to richer structural parameters. The Section 3 algorithm is specified in enough detail to be credible and appears sound. However, the paper currently contains a false ILP in Section 4, and several load-bearing statements (Theorem 3, Lemma 5, Lemma 6, and Lemma 1) are either unproved or, in the case of Lemma 1(i), false in the stated generality. The significance is therefore contingent on substantial revision.

major comments (4)
  1. [Section 4, ILP (1)-(4), Lemma 5, Theorem 6] The ILP in Section 4 has no variables for selecting a non-minimum number of vertices from a module when those vertices are needed only to dominate neighboring modules. It can only choose a minimum (t,1)-dominating set of size c_Mi(t) for one value of t, or no set at all. In the Section 3 algorithm this gap is filled by the extra-vertex variables x_i; Section 4 drops them. This is not a cosmetic omission. For G=K_{3,3} with d=1, the two sides are independent-set modules of size 3, so c_Mi(1)=3. The set consisting of one vertex from each side is a (1,1)-dominating set of size 2, but the ILP only permits 0 or 3 selected vertices per module and therefore declares the size-2 solution infeasible. Hence the claimed equivalence in Lemma 5 is false and Theorem 6 is unsupported. The ILP must be extended with extra-vertex variables as in Section 3 before applying the Frank-Tardos compression.
  2. [Section 3.1, Theorem 3] Theorem 3, which states that Dominating Set admits a polynomial compression parameterized by modular-width on connected graphs, is the entire basis for the claimed PC for (1,r)-Domination in Theorem 4, but it is stated without proof. The problem COLORED DOMINATION is defined, but no reduction from Dominating Set to it is described, and no argument shows how the modular structure is used to obtain a polynomial bound. Since the known non-existence results in [40,45] are for disconnected graphs, the connected case is a genuine new claim rather than a routine corollary. A complete proof must be supplied before this result can be accepted.
  3. [Section 5, Lemma 6] The kernelization in Theorem 7 depends on Lemma 6, which asserts that there is an optimal (d,r)-dominating set using at most 2d-1 vertices from each clique or independent-set module. The lemma is stated without proof. The subsequent pruning argument only shows that, if such a solution exists, its cardinalities can be preserved after pruning; it does not prove the bound. In particular, for r>1 one must argue that selected vertices in a module contribute uniformly to vertices at distance at most r, including paths that pass through the module. Please add a proof or a precise exchange argument.
  4. [Section 2.1, Lemma 1] Lemma 1 is asserted without proof and is used to pass from (d,1)-domination to (d,r)-domination in Theorem 1, Corollary 1, and Theorems 2, 4, 6, and 7. Part (i) is false in the stated generality. Let G be the graph class consisting of all cliques together with C6. Then K is contained in G and G-mc(C6)=1 because C6 is in G. However, C6^2 is K_{3,3}, whose proper modules are contained in one side of the bipartition; since the sides are independent sets and not cliques or C6, any G-modular partition of C6^2 needs at least three parts. Thus G-mc(C6^2)>1. The authors should either restrict the statement to the classes actually used (K union I and the cograph class) and prove the monotonicity for those classes, or formulate a correct general condition. Part (ii) also needs a proof.
minor comments (4)
  1. [Table 1] The row for mw is misaligned; it is difficult to tell which entries correspond to (1,1), (1,r), (d,1), and (d,r).
  2. [Section 2] There is a typo in the sentence introducing the neighborhood: 'by2 N(v)' should be 'by N(v)'.
  3. [References] Reference [14] is listed as arXiv:0710.3901 with year 2024; the publication year should be corrected to the original year of the paper.
  4. [Section 3, Lemma 2] The proof of Lemma 2 would benefit from a sentence explaining why the ILP computes c_M(t) and not merely a lower bound; the current text jumps from the ILP statement to the runtime bound.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the new FPT/PC/PK results are reductions via modular decomposition and ILP, with at most minor non-load-bearing self-citation.

full rationale

The derivation chain is not circular. The central reduction from (d,r)-domination to (d,1)-domination uses the exact identity that a (d,r)-dominating set of G is a (d,1)-dominating set of G^r; this is a definition-based reduction, not an input that already contains the target result. Lemma 1, bounding mw(G^r) and G-mc(G^r) in terms of mw(G) and G-mc(G), is load-bearing for Theorems 1, 2, 4, 6, and 7, and it is stated without proof in Section 2.1; that is an omitted proof or correctness gap, not a circular step, because the lemma is not defined in terms of the domination results. The Section 3 FPT algorithm computes c_M(t) bottom-up using an ℓ-variable ILP that includes extra-vertex variables x_i; it does not fit parameters to the queried dominating-set sizes. Section 4's PC construction is presented as an exact ILP characterization using precomputed c_{M_i}(t), and Section 5's PK proof is self-contained via pruning each module to 2d vertices; neither reduces by its own equations to the quantity being derived. The only self-citation is [13] for the iterated type partition and earlier dominating-set kernel results, but the new central claims do not rest on [13] as their sole justification, and Theorem 7's kernel argument is explicitly constructed in the paper. A separate correctness concern, namely that the Section 4 ILP appears to omit the extra-vertex variables used in Section 3 and may therefore reject valid solutions on examples such as K_{3,3}, is a potential flaw in Lemma 5 and Theorem 6, but it is not a circularity finding under the requested definitions.

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

The paper introduces no fitted numerical parameters. It relies on standard ILP and Diophantine-compression machinery, on prior FPT algorithms for dominating set variants, on the connectedness assumption, and on two internal structural lemmas, Lemma 1 and Lemma 6, that are stated without proof. No invented entities are introduced; the auxiliary COLORED DOMINATION problem in Section 3.1 is a proof gadget rather than an independent entity.

assumptions (6)
  • domain assumption The input graph is connected, stated at the end of Section 1, so the problem can be solved independently per connected component.
    The paper explicitly assumes connected input graphs throughout; the PC for (1,r)-DOM by modular-width relies on connectedness.
  • standard math Fixed-dimension integer linear programming is solvable in time O(ell^{2.5ell+o(ell)} L), due to Lenstra [23,43].
    Used in Algorithm 1 and Lemma 2 to compute module costs with ell variables.
  • standard math Frank and Tardos' rational-vector compression [29] can be applied as in Corollary 2 of [21] without changing the set of feasible 0/1 solutions.
    Used in Section 4 to bound the encoding length of the ILP for the itp+d compression.
  • standard math Prior FPT algorithms for DOMINATING SET parameterized by mw [48], itp [13], and nd [46], and for (d,1)-DOMINATION parameterized by nd [39], are correct.
    The new results build on these algorithms via the graph-power reduction and modular decomposition; the abstract and Section 1 cite them.
  • ad hoc to paper Lemma 1: for every connected graph G and graph class G with K subset of G, G-mc(G^r) <= G-mc(G), and mw(G^r) <= mw(G).
    Stated in Section 2.1 with no proof; used in Theorems 1, 2, 4, 6, and 7 to reduce radius r to radius 1 on the graph power.
  • ad hoc to paper Lemma 6: for any nd module, a clique or independent set, there is an optimal (d,r)-dominating set containing at most 2d-1 vertices from that module.
    Stated in Section 5 with no proof; the polynomial kernel in Theorem 7 prunes each module to 2d vertices based on this bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Complexity of (d,r)-Domination via Modular Decomposition." pith.science (2026). https://pith.science/paper/4RKRSDZL

@misc{pith2026241215671,
  author       = {Pith},
  title        = {Pith review of: Parameterized Complexity of (d,r)-Domination via Modular Decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4RKRSDZL}},
  note         = {Machine review of arXiv:2412.15671}
}
abstract

With the rise of social media, misinformation has significant negative effects on the decision-making of individuals, organizations and communities within society. Identifying and mitigating the spread of fake information is a challenging issue. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, through an awareness process, can prevent the spreading of fake narratives. The considered problem, named \textsc{$(d,r)$-Domination} generalizes both distance and multiple domination. We study the parameterized complexity of the problem according to standard and structural parameters. We give fixed-parameter algorithms as well as polynomial compressions/kernelizations for some variants of the problem and parameter combinations.

Figures

Figures reproduced from arXiv: 2412.15671 by the authors.

Figure 1
Figure 1. (a) A graph G. (b) The parse tree T(G) associated with a decomposition of G into modules. The width of the presented decomposition is 5. (c) A hierarchical representation of the decomposition of G into modules. Definition 4. [39]. Let G be a graph class. For a graph G (not necessarily in G), a modular partition M = {M1, . . . , Mℓ} of G is called a G-modular partition if each G[Mi ] belongs to G. The G-modular cardi… view at source ↗
Figure 2
Figure 2. (a)-(c) A graph G with iterated type partition number 5 and its iterative identification. Dashed circles describe the identified clique or independent set modules. (d) The parse tree T(G) associated with a decomposition of G into modules. Apart from the root, all internal vertices use only operations (O2) and (O3). 2.1 Modular Decomposition on Power Graphs The r-th graph power of a graph G = (V, E), denoted by Gr , … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 41 canonical work pages

  1. [13]

    Cordasco, L

    G. Cordasco, L. Gargano, A.A. Rescigno. Parameterized complexity for iterated type partitions and modular-width. In Discrete Applied Mathematics, 350, (2024)

    2024

  2. [1]

    Bakhshesh, M

    D. Bakhshesh, M. Farshi, M. Hasheminezhad. Complexity results for k-domination and α-domination problems and their variants. arXiv:1702 .00533[cs .CC], (2017)

    work page 2017

  3. [2]

    Albert, H

    R. Albert, H. Jeong, A.-L. Barabási. Error and attack tolerance of complex networks. Nature 404, 378–382, (2000)

    2000

  4. [3]

    Bean, M.A

    J.T. Bean, M.A. Henning, H.C. Swart. On the integrity of distance domination in graphs. Australian Journal of Combinatorics, 10, 29–43, (1994)

    work page 1994

  5. [4]

    Borradaile and H

    G. Borradaile and H. Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In Proc. of IPEC’16, 8:1–8:23, (2016)

    work page 2016

  6. [5]

    Chang, G.L

    G.J. Chang, G.L. Nemhauser. The k-domination and k-stability problem on graphs. Tech. Report 540, Cornell Univ., (1982)

    work page 1982

  7. [6]

    Cicalese, M

    F. Cicalese, M. Milanic, U. Vaccaro. On the approximability and exact algorithms for vector domination and related problems in graphs. Discrete Appl. Math. 161(6), 750–767, (2013)

    work page 2013

  8. [7]

    Cicalese, G

    F. Cicalese, G. Cordasco, L. Gargano, M. Milanic, U. Vaccaro. Latency-bounded target set selection in social networks. Theor. Comput. Sci. 535, 1–15, (2014)

    work page 2014

Show all 49 references
  1. [8]

    Cordasco, L

    G. Cordasco, L. Gargano and A.A. Rescigno. On finding small sets that influence large networks. Social Network Analysis and Mining 6(11), (2016)

    2016

  2. [9]

    Cordasco, L

    G. Cordasco, L. Gargano, M. Mecchia, A.A. Rescigno, U. Vaccaro. Discovering Small Target Sets in Social Networks: A Fast and Effective Algorithm. Algorithmica 80(6), 1804–1833, (2018)

    2018

  3. [10]

    Cordasco, L

    G. Cordasco, L. Gargano, A.A. Rescigno, U. Vaccaro. Evangelism in social networks: Algorithms and complexity. Networks 71(4): 346–357, (2018)

    2018

  4. [11]

    Cordasco, L

    G. Cordasco, L. Gargano, A.A. Rescigno. Active influence spreading in social networks. Theoretical Computer Science 764, 15–29, (2019). 15 Parameterized Complexity of (d, r)-Domination A PREPRINT

    2019

  5. [12]

    Cordasco, L

    G. Cordasco, L. Gargano, M. Lafond, L. Narayanan, A. A. Rescigno, U. Vaccaro, K. Wu. Whom to befriend to influence people. Theoretical Computer Science 810, 26–42, (2020)

    2020

  6. [14]

    Corneil, M

    D. Corneil, M. Habib, C. Paul and M. Tedder. A recursive linear time modular decomposition algorithm via LexBFS. arXiv:0710.3901[cs.DM], (2024)

    2024 arXiv

  7. [15]

    Das and V

    B. Das and V . Bharghavan. Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets. Interna- tional Conference on Communications, Montreal, Canada, (1997)

    1997

  8. [16]

    Datta, L

    A. Datta, L. Larmore, S. Devismes, K. Heurtefeux, Y . Rivierre. Competitive self-stabilizing k-clustering. In Proc. of ICDCS’12, 476–485, (2012)

    2012

  9. [17]

    M. Dom, D. Lokshtanov, S. Saurabh. Incompressibility through colors and IDs. In Proc. of 36th ICALP, LNCS 5555, Springer, 378–389, (2009)

    2009

  10. [18]

    Downey and M.R

    R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness. Congressus Numerantium, 87:161–187, (1992)

    1992

  11. [19]

    Downey and M.R

    R.G. Downey and M.R. Fellows. Parameterized complexity. Springer-Verlag, New York, (1999)

    1999

  12. [20]

    Drange, M

    P.G. Drange, M. Dregi, F.V . Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. Sánchez Villaamil, S. Saurabh, S. Siebertz, and S. Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In Proc of STACS’16, LIPIcs 47, 31:1–31:14, (2016)

    2016

  13. [21]

    Etscheid, S

    M. Etscheid, S. Kratsch, M. Mnich and H. Röglin. Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1–10, (2017)

    2017

  14. [22]

    Einarson, F

    C. Einarson, F. Reidl. A General Kernelization Technique for Domination and Independence Problems in Sparse Classes. In Proc of IPEC 2020, LIPIcs 180, 11:1–11:15, (2020)

    2020

  15. [23]

    M. R. Fellows, D. Lokshtanov, N. Misra, F. A. Rosamond and S. Saurabh. Graph layout problems parameterized by vertex cover. In Proc. of International Symposium on Algorithms and Computation (ISAAC 2008), LNCS 5369, pp. 294–305, (2008)

    2008

  16. [24]

    Fischer, M

    N. Fischer, M. Kunnemann, M. Redzic. The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties. CoRR abs/2312.14593, (2023)

    2023 arXiv

  17. [25]

    Fink, M.S

    J.F. Fink, M.S. Jacobson. n-Domination in graphs. Graph theory with applications to algorithms and computer science. John Wiley & Sons, 283–300, (1985). 16 Parameterized Complexity of (d, r)-Domination A PREPRINT

    1985

  18. [26]

    Flum and M

    J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, (2006)

    2006

  19. [27]

    Fomin, D

    F.V . Fomin, D. Lokshtanov, S. Saurabh, D.M. Thilikos. Linear kernels for (Connected) Dominating Set on graphs with excluded topological subgraphs. In Proc. of STACS, 20, LIPIcs 20, 92–103, (2013)

    2013

  20. [28]

    Fomin, D

    F.V . Fomin, D. Lokshtanov, S. Saurabh, M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, (2019)

    2019

  21. [29]

    Frank, É

    A. Frank, É. Tardos. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65, (1987)

    1987

  22. [30]

    T. W. Haynes, S. T. Hedetniemi and P. J. Slater. Fundamentals of domination in graphs, New York: Marcel Dekker, Inc, 1998

    1998

  23. [31]

    Gajarský, M

    J. Gajarský, M. Lampis, S. Ordyniak. Parameterized Algorithms for Modular-Width. In Proc. of IPEC, LNCS 8246, 163–176, (2013)

    2013

  24. [32]

    T. Gallai. Transitiv orientierbare Graphen. In Acta Mathematica Academiae Scientiarum Hungarica 18, pp. 26–66, (1967)

    1967

  25. [33]

    Harutyunyan

    L. Harutyunyan. On the total (k,r)-domination number of random graphs. arXiv:1511.07249, (2015)

    2015 arXiv

  26. [34]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi, P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker. Inc., New York, (1998)

    1998

  27. [35]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi and P.J. Slater. Domination in Graphs - Advanced Topics. Marcel Dekker. Inc., New York, (1998)

    1998

  28. [36]

    M.A. Henning. Distance Domination in Graphs. In Topics in Domination in Graphs. Developments in Mathematics, 64, 10.1007/978-3-030-51117-3_7, (2020)

    2020 doi

  29. [37]

    Ishii, H

    T. Ishii, H. Ono, Y . Uno. (Total) Vector domination for graphs with bounded branchwidth. Discrete Applied Mathematics 207, 80–89, (2016)

    2016

  30. [38]

    Jothilakshmi, A.P

    G. Jothilakshmi, A.P. Pushpalatha, S. Suganthi, V . Swaminathan. (k,r)-Domination in Graphs. Int. J. Contemp. Math. Sci. 6 (29), 1439–1446, (2011)

    2011

  31. [39]

    Lafond, W

    M. Lafond, W. Luo. Parameterized Complexity of Domination Problems Using Restricted Modular Partitions. In MFCS 2023, 61:1–61:14, (2023)

    2023

  32. [40]

    Lafond, W

    M. Lafond, W. Luo. Preprocessing complexity for some graph problems parameterized by structural parameters. In Proceedings of LAGOS’23, 130–139, (2023)

    2023

  33. [41]

    M. Lampis. Algorithmic meta-theorems for restrictions of treewidth. In Algorithmica 64, 19–37, (2012). 17 Parameterized Complexity of (d, r)-Domination A PREPRINT

    2012

  34. [42]

    Lan, G.J

    J.K. Lan, G.J. Chang. Algorithmic aspects of the k-domination problem in graphs. Discrete Appl. Math. 161(10–11), 1513–1520, (2013)

    2013

  35. [43]

    H. W. Lenstra. Integer programming with a fixed number of variables. In Mathematics of Operations Research 8(4), pp. 538–548, (1983)

    1983

  36. [44]

    Y . Lu, X. Hou, J.-M. Xu. On the (2,2)-domination number of trees. Discussiones Mathematicae Graph Theory 30.2, 185–199, (2010)

    2010

  37. [45]

    W. Luo. Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width. In Proceedings of Computing and Combinatorics (COCOON’23). LeNCS 14422, Springer, (2023)

    2023

  38. [46]

    Koutecký

    M. Koutecký. Solving hard problems on Neighborhood Diversity. Master Thesis. Charles University in Prague, (2013)

    2013

  39. [47]

    Newman, S

    M.E.J. Newman, S. Forrest, J. Balthrop. Email networks and the spread of computer viruses. Physical Review E 66, (2002)

    2002

  40. [48]

    M. Románek. Parameterized algorithms for modular-width. Bachelor’s Thesis, Masaryk University, (2013)

    2013

  41. [49]

    P.J. Slater. R-domination in graphs. J. Assoc. Comp. Mach. 23(3), 446–450, (1976). 18

    1976

Pith tools

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