Distance Vector Domination

Adele A. Rescigno; Gennaro Cordasco; Luisa Garagano

REVIEW 4 major objections 4 minor 51 references

Distance Vector Domination

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 Distance Vector Domination, a graph problem modeling immunization against fake narratives, is W[1]-hard with respect to neighborhood diversity even when all radii are 1, while several structural variants admit fixed-parameter algorithms.

desk verdict The modular-width RD algorithm (Theorem 5) is contradicted by a two-vertex instance, and the hardness proof relies on an unproved lemma; the paper needs major repair, but the DVD problem and the treewidth DP for VD are worth a serious look. read the letter →

arxiv 2412.15663 v1 pith:VBO32ZRK submitted 2024-12-20 cs.CC cs.DMcs.DSmath.CO

Gennaro Cordasco , Luisa Garagano , Adele A. Rescigno This is my paper · ORCID

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

keywords DistanceVectorDominationR-dominationparameterizedcomplexityneighborhooddiversitymodular-widthtreewidthW[1]-hardness

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

Distance Vector Domination (DVD) is a graph problem that asks for a small set of vertices such that every other vertex receives enough selected vertices within its personal radius, with a per-vertex demand. The paper's central negative result is that the special case with all radii equal to one, Vector Domination, is W[1]-hard when parameterized by neighborhood diversity, meaning that this structural measure does not make the problem fixed-parameter tractable. On the positive side, the paper gives fixed-parameter algorithms for radius-only domination parameterized by modular-width, for vector and distance-vector domination parameterized by modular-width together with solution size, and for the two one-sided variants parameterized by treewidth together with the maximum demand or the maximum radius. A reader should care because the problem models choosing a small set of individuals to immunize against fake narratives, and the results map which structural features of a network make that choice efficiently computable.

What carries the argument

The reduction is carried by three kinds of gadgets: bag (an independent set whose vertices share all neighbors) and clique building blocks arranged into selection gadgets (one per color), multiple gadgets (one per color pair), and incidence gadgets (two per unordered color pair). The demands inside the incidence gadgets are chosen so that only a vertex pair corresponding to an actual edge of the original graph can satisfy them; the budget forces exactly $q$ selected vertices and exactly one selected vertex per color. On the algorithmic side, the positive results run either on a modular decomposition parse tree, where modules are induced subgraphs whose vertices share all neighbors outside the module, or on a nice tree decomposition, where a dynamic program tracks binary states (selected or not) and residual demands for the vertices in each bag.

What would settle it

For a small $q$, build the gadget graph $G'$ described in the proof for a multicolored clique instance whose only $q$-cliques are known, solve the VD decision problem exactly, and compare the minimum solution size against the claimed budget; a mismatch would refute Lemma 1 and with it the W[1]-hardness claim.

Watch

Extended reading notes

Core claim

On its own terms, the paper shows that Vector Domination (VD), and therefore Distance Vector Domination, remains W[1]-hard with respect to neighborhood diversity even when every radius is 1. The proof reduces from Multicolored Clique, building a graph $G'$ from selection gadgets (two cliques and a bag per color), multiple gadgets (bags and cliques per color pair), and incidence gadgets (three bags per ordered color pair) whose demands encode vertex indices and edge endpoints; the budget is $k = qr + \binom{q}{2}(2r+3)s$. Lemma 1 asserts the constructed VD instance has a solution of size $k$ exactly when $G$ has a multicolored clique of size $q$, and the graph's neighborhood diversity is $O(q^2)$. The paper also contributes FPT algorithms: RD in time $O(mw\,2^{mw} n)$, VD in $O(mw\, k (k+1)^{mw} n^2)$, DVD in $O(mw^2 k (k+1)^{2mw} n^2)$, VD in $O(tw^2 2^{tw} (\tau+1)^{tw} n)$, and RD in $O(tw (2\delta+1)^{tw} (tw^2+n) n^2 \log n)$.

Load-bearing premise

Lemma 1 asserts the equivalence between a solution of size $k$ in the constructed VD instance and a multicolored clique of size $q$ in the original graph; it is stated without proof, and the W[1]-hardness theorem collapses if the gadget analysis fails.

Editorial extensions

If this is right

Unless FPT equals W[1], Vector Domination has no fixed-parameter algorithm parameterized only by neighborhood diversity, and the same holds for the more general Distance Vector Domination.
The hardness transfers to modular-width and clique-width, which are more general structural parameters than neighborhood diversity, so the negative result covers dense graph classes beyond the constructed instance.
Radius-only domination (R-domination) is tractable in FPT time on bounded modular-width graphs, with running time $O(mw\,2^{mw} n)$.
Adding the solution size $k$ to modular-width makes both vector and distance-vector domination FPT, with running times exponential only in $mw$ and polynomial in $n$.
On bounded-treewidth graphs, vector domination is FPT when the maximum demand is added as a parameter, and radius-only domination is FPT when the maximum radius is added.

Reading between the lines

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

A direct corollary the authors do not spell out is that the same construction, once Lemma 1 is supplied, should also rule out FPT algorithms for VD parameterized by any parameter that is upper-bounded by neighborhood diversity, beyond the modular-width and clique-width cases mentioned in the paper.
The open gap named in the paper, an FPT algorithm for DVD parameterized by treewidth together with $k$, $\tau$, or $\delta$, is a natural next target; the two treewidth algorithms here solve only the one-sided variants of the problem.
One testable extension would be to instantiate the reduction on small random graphs and solve the VD instance exactly, comparing the true minimum solution size against the claimed budget; that would provide an empirical check on the unproven Lemma 1.
The misinformation-motivated framing suggests an applied direction worth exploring: on graphs with small modular-width, the practical bottleneck for computing an immunizing set may be obtaining the modular decomposition itself rather than evaluating the domination condition.

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.

Desk Editor's Note

read the letter

Dear colleague,

The key fact you should know: the RD algorithm on modular-width (Theorem 5) is wrong. On K2 with modules {x} and {y} and d=(1,1), the unique optimal RD set has size 1 (e.g., {x}), but Algorithm 1 with the usual convention min∅=∞ rejects the single-module subsets because it includes the would-be selected vertex in the set A_i of vertices that must be dominated from inside the module. With min∅=0 it accepts an invalid solution on a star, selecting a leaf while the other leaf remains undominated. Lemma 3 is false and Theorem 5, together with the RD row of Table 1, does not survive.

The paper does have genuinely new material. The DVD problem is a reasonable unification of distance and multiple domination, and the claimed W[1]-hardness of Vector Domination with respect to neighborhood diversity would answer an open question if the proof were complete. The treewidth-plus-tau DP for VD (Theorem 8) looks plausible and improves the earlier branchwidth-based result. The hardness reduction is elaborate and may well be correct.

The soft spots are substantial. Lemma 1, the equivalence at the heart of the W[1]-hardness reduction, is asserted without proof. Theorem 9 is a one-line reference to Borradaile--Le with no algorithmic details. And the modular-width RD algorithm is not merely missing a proof; it is contradicted by a two-vertex example. That last defect is load-bearing. As written, the paper does not support its central claims.

Who should read this? Parameterized complexity researchers working on domination variants with dense structural parameters. If the authors fix the RD algorithm (or restrict it to cases where the flaw disappears, e.g., all d_v >= 2), supply the missing proof of Lemma 1, and give full details for Theorem 9, the paper could become solid. Right now it needs major revision.

Recommendation: reject in current form, but invite resubmission after the authors repair Theorem 5 and fill the proof gaps. I would still send it to a serious referee, because the hardness result and the treewidth DP are potentially valuable and deserve expert scrutiny.

Referee Report

4 major / 4 minor

Summary. The paper introduces Distance Vector Domination (DVD), a parameterized domination problem in which each vertex v has a demand t_v and a radius d_v, and a set S is valid when every non-selected vertex v has at least t_v selected vertices within distance d_v. The manuscript claims that the special case Vector Domination (VD) is W[1]-hard with respect to neighborhood diversity even when all radii are 1 (Theorem 3 and Corollary 1), and that several variants are fixed-parameter tractable: RD with modular-width (Theorem 5), VD with modular-width plus solution size k (Theorem 6), DVD with modular-width plus k (Theorem 7), VD with treewidth plus maximum demand (Theorem 8), and RD with treewidth plus maximum radius (Theorem 9). The proofs are based on a reduction from Multicolored Clique and on modular decomposition and treewidth dynamic programming.

Significance. If all claims were correct, the paper would be a useful contribution: it unifies distance and multiple domination in a single framework, and it extends the known parameterized complexity map for dense structural parameters such as neighborhood diversity and modular-width. The problem statement and the overview table are clear. However, the paper currently ships no machine-checked proofs or reproducible code, and its significance depends entirely on lemmas that are either unproved or contradicted by explicit instances. In particular, one of the advertised FPT algorithms (Theorem 5) is demonstrably wrong on a two-vertex graph, and the main hardness reduction rests on an unproved equivalence. The positive contributions are therefore not established in the present form.

major comments (4)

[Section 2, Lemma 1] Lemma 1 asserts an iff between a multicolored clique in (G,c,q) and a VD solution of size k in the constructed graph G', but no proof of this equivalence is given. This lemma is the entire basis for Theorem 3 and Corollary 1, so the main negative result is unverified. In particular, the demands in Equations (2) and (3) and the budget k are never shown to enforce that a solution selects one vertex per color, one edge per color pair, and consistent incidences between the selected vertices and edges.
[Section 3.1, Lemma 2] Lemma 2 states that for RD there exists an optimal solution selecting at most one vertex from each module V(G_i) of the modular decomposition. No proof is provided. Theorem 5 relies on this lemma to justify the exhaustive search over subsets S_H of [p], so the correctness of the modular-width FPT algorithm is not established even before considering the execution of Algorithm 1.
[Section 3.1, Algorithm 1 and Theorem 5] Algorithm 1 is incorrect for the problem defined in Definition 1. Take G = K2 with modules G1={x}, G2={y}, H=K2, and d_v=1 for every vertex. The set S={x} is a valid RD set of size 1, since y is covered by x and selected vertices need not be dominated. For S_H={1}, the algorithm computes ℓ_1 = min∅ = ∞ and A_1 = {x}; because N_{G1}(x)=∅, it returns false, and S_H={2} is rejected symmetrically. Only S_H={1,2} is accepted, so the reported optimum is 2. If one instead adopts the convention min∅=0, the algorithm accepts S_H={1} on the instance where G1 is an independent set {a,b}, G2={y}, and H=K2 with d=(1,1,1), selecting a while b remains undominated. Thus Lemma 3 is false under either convention for min∅, and Theorem 5, together with the RD row of Table 1, is contradicted by a two-vertex instance.
[Section 4, Theorem 9] The claimed FPT algorithm for RD parameterized by treewidth plus maximum radius d is not described. The text only says that the authors use 'a strategy similar to the one adopted in [8]' and then states the running time. No states, transition rules, correctness proof, or analysis of the dependency on d and tw are given. Since Table 1 advertises this as a contribution, the claim is currently unverified.

minor comments (4)

[Section 2, Neighborhood diversity] The text says 'two vertices u, v have the same same type'; this should be 'the same type'.
[Algorithm 1] The definition of ℓ_i uses a minimum over an empty set when |S_H|=1; the intended convention (∞) should be stated explicitly.
[Introduction, Theorem 2] The phrase 'approximated in polynomial time by a factor log n + 2' would be clearer as 'within a factor of log n + 2'.
[References] Reference [20] is dated 2024 for an arXiv preprint from 2007; please verify the year and version cited.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness reduction relies on external Multicolored Clique and the FPT algorithms use standard modular/tree decompositions; self-citations are not load-bearing.

full rationale

The paper's derivation chain is self-contained against external assumptions, so no circular step meets the evidentiary bar. Theorem 3 reduces VD with neighborhood diversity from Multicolored Clique (an external W[1]-hard problem), and the proof does not use any result of this paper as an input; the unproved Lemma 1 in Section 2 is a correctness/completeness gap, not a circular reduction. The FPT algorithms for RD, VD, and DVD (Theorems 5-9) are built on modular decomposition and nice tree decompositions with standard dynamic programming, not on the theorem statements themselves. Self-citations (e.g., [5], [11], [12]-[19]) appear only as background, motivation, or previously known parameterized results, and none is load-bearing for the new claims; [10], [23], [25], [39], [43], and [48] are external sources. The described defect in Algorithm 1 (Section 3.1), where a would-be selected vertex with d_v=1 is included in the set A_i that must be dominated from inside the module (e.g., K2), would make Lemma 3 and Theorem 5 incorrect as stated, but it is an algorithmic correctness issue rather than a case where a prediction reduces by construction to its inputs. Similarly, the omitted proof of Lemma 1 affects the soundness of the hardness theorem but does not make the theorem definitionally equivalent to its input. Accordingly, no fitted-parameter-renamed-as-prediction, no author-imported uniqueness theorem, and no ansatz-smuggled-by-citation pattern is present.

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

No empirical free parameters or invented physical entities. The only unverified inputs are the two unproved lemmas and the assumed strategy behind Theorem 9, listed as ad hoc axioms.

assumptions (5)

standard math Multicolored Clique is W[1]-hard parameterized by the number of colors q, and remains so when each color class has the same size and between every pair of color classes there are the same number of edges.
Invoked in Theorem 3's reduction; cited to [25] and [23].
standard math A nice tree decomposition of width tw can be computed in polynomial time and has O(tw n) nodes.
Used in Section 4 for the treewidth DP algorithms; cited to [42].
standard math A modular decomposition of width mw can be computed in linear time.
Used in Section 3; cited to [20].
ad hoc to paper Lemma 2: there exists an optimal RD solution with at most one selected vertex per module.
Stated without proof in Section 3.1; the RD algorithm's correctness depends on it, and it may fail if radii can be 0.
ad hoc to paper Lemma 1: the reduction from Multicolored Clique to VD is a yes/no equivalence.
Stated without proof in Section 2; the W[1]-hardness result depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distance Vector Domination." pith.science (2026). https://pith.science/paper/VBO32ZRK

@misc{pith2026241215663,
  author       = {Pith},
  title        = {Pith review of: Distance Vector Domination},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBO32ZRK}},
  note         = {Machine review of arXiv:2412.15663}
}

abstract

Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, named {\em Distance Vector Domination} generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are $1$. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations.

Figures

Figures reproduced from arXiv: 2412.15663 by the authors.

**Figure 1.** An overview of the reduction. Each circle represents a bag. Each square represents a clique. The number inside a bag (resp. clique) is the number of vertices of the bag (resp. clique). The value tv for a vertex v is displayed in red. between two cliques is a complete bipartite graph among the vertices in the cliques [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 47 canonical work pages

[1]

Albert, H

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

work page 2000
[8]

Borradaile and H

G. Borradaile and H. Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In Proc. of 11th International Symposium on Parameterized and Exact Computation, IPEC, LIPIcs 63, 8:1–8:23, (2016)

work page 2016
[2]

Arnborg, D.G

S. Arnborg, D.G. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth. 8, 277–284, (1987)

work page 1987
[3]

Banerjee, M

S. Banerjee, M. Jenamani, D.K. Pratihar. A survey on influence maximization in a social network. Knowl Inf Syst 62, 3417–3455, 10.1007/s10115-020-01461-4, (2020)

work page doi:10.1007/s10115-020-01461-4 2020
[4]

Ben-Zwi, D

O. Ben-Zwi, D. Hermelin, D. Lokshtanov, I. Newman. Treewidth governs the complexity of target set selection. Discrete Optimization 8(1), 87–96, (2011)

work page 2011
[5]

Bermond, L

J.-C. Bermond, L. Gargano, A.A. Rescigno. Gathering with minimum delay in tree sensor networks. Proc. of SIROCCO’08, LNCS 5058, 262–276, (2008)

work page 2008
[6]

Bodlaender and T

H.L. Bodlaender and T. Kloks. Better algorithms for the pathwidth and treewidth of graphs. Proc. of ICALP’91, LNCS 510, 544–555, (1991)

work page 1991
[7]

Betzler, R

N. Betzler, R. Bredereck, R. Niedermeier and J. Uhlmann. On Bounded-Degree Vertex Deletion parameterized by treewidth. Discrete Applied Mathematics 160(1-2), 53–60, (2012)

work page 2012

Show all 51 references

[9]

Chong, S.P

C.-Y . Chong, S.P. Kumar. Sensor networks: Evolution, opportunities, and challenges. Proceedings of the IEEE, 91 (8), 1247–1256, (2003)

2003
[10]

Cicalese, M

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

2013
[11]

Cicalese, G

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

2014
[12]

Cordasco, L

G. Cordasco, L. Gargano, M. Mecchia, A. A. Rescigno, U. Vaccaro. A fast and effective heuristic for discovering small target sets in social networks. In Proc. of the 9th Inter. Conf. on Comb. Opt. and Appl. (COCOA), (2015). 14 Distance Vector Domination A PREPRINT

2015
[13]

Cordasco, L

G. Cordasco, L. Gargano, A. A. Rescigno. Influence propagation over large scale social networks. In Proc. of IEEE/ACM Inter. Conf. on Advances in Social Networks Analysis and Mining (ASONAM’15), 1531–1538, (2015)

2015
[14]

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
[15]

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
[16]

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
[17]

Cordasco, L

G. Cordasco, L. Gargano, A. A. Rescigno. Active influence spreading in social networks. Theoretical Computer Science 764, 15–29, (2019)

2019
[18]

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
[19]

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
[20]

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
[21]

Courcelle, The monadic second-order logic of graphs recognizable sets of finite graphs, Inform

B. Courcelle, The monadic second-order logic of graphs recognizable sets of finite graphs, Inform. and Comput., 85 (1), 12–75, (1990)

1990
[22]

Courcelle and S

B. Courcelle and S. Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1), 77–114, (2000)

2000
[23]

Cygan, F.V

M. Cygan, F.V . Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, (2015)

2015
[24]

Dasgupta, M

K. Dasgupta, M. Kukreja, K. Kalpakis. Topology-aware placement and role assignment for energy-efficient information gathering in sensor networks. In Proc. of IEEE Symposium on Computers and Communications, 341–348, (2003)

2003
[25]

Downey, M.R

R.G. Downey, M.R. Fellows. Parameterized Complexity. Springer, Heidelberg, (1999)

1999
[26]

Dvorák, D

P. Dvorák, D. Knop, and T. Toufar. Target Set Selection in Dense Graph Classes. In Proc. of 29th International Symposium on Algorithms and Computation (ISAAC’18), 10.4230/LIPIcs.ISAAC.2018.18, (2018). 15 Distance Vector Domination A PREPRINT

2018 doi
[27]

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

1985
[28]

Gajarský, M

J. Gajarský, M. Lampis, S. Ordyniak. Parameterized Algorithms for Modular-Width. In Proc. of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS 8246, 163–176, (2013)

2013
[29]

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

1967
[30]

R. Ganian. Using Neighborhood Diversity to Solve Hard Problems. In arXiv 2012, arXiv:1201.3091, (2012)

2012 arXiv
[31]

Granovetter

M. Granovetter. Threshold models of collective behaviors. The American Journal of Sociology, 83(6), 1420–1443, (1978)

1978
[32]

Goddard, M.A

W. Goddard, M.A. Henning, Restricted domination parameters in graphs. Journal of Combinatorial Optimization 13 353–363, (2007)

2007
[33]

Haynes, S

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

1998
[34]

Haynes, S

T.W. Haynes, S. Hedetniemi, P. Slater (Eds.). Domination in Graphs: Advanced Topics, Marcel Dekker, (1998)

1998
[35]

Harant, A

J. Harant, A. Prochnewski, M. V oigt. On dominating sets and independent sets of graphs, Combinatorics. Probability and Computing 8, 547–553, (1999)

1999
[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
[37]

Impagliazzo and R

R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2), 367–375, 10.1006/jcss.2000.1727, (2001)

2001
[38]

Ishii, H

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

2016
[39]

Katsikarelis, M

I. Katsikarelis, M. Lampis, V . Th. Paschos. Structural parameters, tight bounds, and approximation for (k,r)-center. Discr. App. Math., 264, 90–117, (2019)

2019
[40]

Kempe, J

D. Kempe, J. Kleinberg, E. Tardos. Maximizing the spread of influence through a social network. In Proc. of KDD’03, 137–146, (2003)

2003
[41]

Kimura, K

M. Kimura, K. Saito, H. Motoda. Blocking links to minimize contamination spread in a social network. ACM Trans. on Knowledge Discovery from Data 3(2), (2009). 16 Distance Vector Domination A PREPRINT

2009
[42]

T. Kloks. Treewidth Computations and Approximations. LNCS 842, Springer-Verlag Berlin Heidelberg, ISSN 0302-9743, 10.1007/BFb0045375, (1994)

1994 doi
[43]

Lafond, W

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

2023
[44]

Lamblet Mafort, F

R. Lamblet Mafort, F. Protti. Vector Domination in split-indifference graphs. Information Processing Letters, 155, ISSN 0020-0190, (2020)

2020
[45]

M. Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19–37, (2012)

2012
[46]

P. Li, A. Wang, J. Shang. A simple optimal algorithm for k-tuple dominating problem in interval graphs. Journal of Combinatorial Optimization 45(14), (2023)

2023
[47]

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

2002
[48]

Raman, S

V . Raman, S. Saurabh, S. Srihari, Parameterized algorithms for generalized domination. In Proc of COCOA 2008, LNCS 5165, 116–126, (2008)

2008
[49]

M. Romanek. Parameterized algorithms for modular-width. Bachelor’s Thesis, (2016)

2016
[50]

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

1976
[51]

L.A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385–393 (1982) 17

1982

Pith tools

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

[1] [1]

Albert, H

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

work page 2000

[2] [8]

Borradaile and H

G. Borradaile and H. Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In Proc. of 11th International Symposium on Parameterized and Exact Computation, IPEC, LIPIcs 63, 8:1–8:23, (2016)

work page 2016

[3] [2]

Arnborg, D.G

S. Arnborg, D.G. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth. 8, 277–284, (1987)

work page 1987

[4] [3]

Banerjee, M

S. Banerjee, M. Jenamani, D.K. Pratihar. A survey on influence maximization in a social network. Knowl Inf Syst 62, 3417–3455, 10.1007/s10115-020-01461-4, (2020)

work page doi:10.1007/s10115-020-01461-4 2020

[5] [4]

Ben-Zwi, D

O. Ben-Zwi, D. Hermelin, D. Lokshtanov, I. Newman. Treewidth governs the complexity of target set selection. Discrete Optimization 8(1), 87–96, (2011)

work page 2011

[6] [5]

Bermond, L

J.-C. Bermond, L. Gargano, A.A. Rescigno. Gathering with minimum delay in tree sensor networks. Proc. of SIROCCO’08, LNCS 5058, 262–276, (2008)

work page 2008

[7] [6]

Bodlaender and T

H.L. Bodlaender and T. Kloks. Better algorithms for the pathwidth and treewidth of graphs. Proc. of ICALP’91, LNCS 510, 544–555, (1991)

work page 1991

[8] [7]

Betzler, R

N. Betzler, R. Bredereck, R. Niedermeier and J. Uhlmann. On Bounded-Degree Vertex Deletion parameterized by treewidth. Discrete Applied Mathematics 160(1-2), 53–60, (2012)

work page 2012