pith. sign in

arxiv: 2605.20970 · v1 · pith:F5QJ3OWRnew · submitted 2026-05-20 · 💻 cs.DM · math.CO

On the Complexity of Hop Domination and 2-Step Domination in Graph Classes

Sandip Das , Sweta Das , Sk Samim Islam This is my paper

Pith reviewed 2026-05-21 02:03 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords hop domination2-step dominationNP-completenessregular graphsclaw-free graphsunit disk graphsgraph dominationcomputational complexity
0
0 comments X

The pith

Hop domination and 2-step domination problems are NP-complete even on regular, claw-free, and unit disk graphs.

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

This paper investigates the computational complexity of two variants of the domination problem in graphs. It demonstrates that deciding whether a graph has a hop dominating set or a 2-step dominating set of size at most k is NP-complete. The hardness persists even when the input graphs are restricted to be d-regular for any d at least 3, to be claw-free, or to be unit disk graphs. A reader might care because these graph classes appear in applications like network design and geometric modeling, where finding small dominating sets is useful but now shown to be hard in the worst case.

Core claim

The authors prove NP-completeness of the Hop Domination problem and the 2-Step Domination problem by reductions that hold for d-regular graphs with d ≥ 3, claw-free graphs, and unit disk graphs.

What carries the argument

Polynomial time reductions from established NP-complete problems like the domination problem to these variants, while ensuring the resulting graphs belong to the desired classes.

If this is right

  • Both problems are NP-hard on all d-regular graphs for d at least 3.
  • The problems remain hard on claw-free graphs, which include many intersection graphs.
  • Unit disk graphs, modeling wireless networks, also make these problems NP-complete.
  • Exact solutions require exponential time in the worst case for these classes unless P=NP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar hardness results might hold for other distance-based domination problems in these graph families.
  • Researchers working on approximation algorithms for network coverage may need to focus on these restricted classes specifically.
  • Parameterized complexity analysis could reveal fixed-parameter tractable cases despite the NP-completeness.

Load-bearing premise

The constructed reductions from known NP-complete domination problems to hop and 2-step domination preserve the answer correctly for graphs in the restricted classes.

What would settle it

A polynomial-time algorithm that solves the hop domination problem on 3-regular graphs would disprove the NP-completeness claim for that class.

Figures

Figures reproduced from arXiv: 2605.20970 by Sandip Das, Sk Samim Islam, Sweta Das.

Figure 1
Figure 1. Figure 1: Planar embedding of a planar graph with max degree [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Gadget construction of G2 from G1 Thus, G has a vertex cover of size k if and only if G2 has a hop dominating set of size k + P (u,v)∈E(G) (4kuv −1), where kuv is the length of an edge between u and v in G1. Hence, the Hop Domination problem is NP-complete in unit disk graphs. 4.2 2-Step Domination We sketch a polynomial time transformation to the 2-Step Domination prob￾lem from Planar Vertex Cover restric… view at source ↗
Figure 3
Figure 3. Figure 3: Gadget construction of G2 from G1 segments that make up the edges are each of integer length 8. The vertices of G1 are modeled by circles of radius 1/2 centered at the locations of the vertices in this embedding. The edges of G1 are replaced by chains of radius-1/2 circles, augmented with gadgets attached at each interior integer coordinate point along the edge and with boundary gadgets attached near each … view at source ↗
Figure 4
Figure 4. Figure 4: Gadget construction of G2 from G1 Proof. Let us assume SG1 is a vertex cover of size at most k. Now we take SG2 = SG1 ∪ {bij , cij , d24 ij , d23 ij , e24 ij , e23 ij }, which is a hop dominating set. Conversely, let G2 have a hop dominating set SG2 of size at most k + 6m. We denote the induced subgraph of G2[{bij , dij , d1k ij , d2k ij }], where k = 1, 2, . . . , 6 as B and also the induced subgraph of G… view at source ↗
Figure 5
Figure 5. Figure 5: Gadget construction of G2 from G1 Lemma 3. G1 has a vertex cover of size at most k if and only if G2 has a 2-step dominating set of size at most k + 3m, where m = |E(G1)|. Proof. Let us assume SG1 is a vertex cover of size at most k. Now we take SG2 = SG1 ∪ {aij , bij , cij}, which is a 2-step dominating set. Conversely, let G2 have a 2-step dominating set SG2 of size at most k + 3m. To hop dominate c 12 i… view at source ↗
Figure 6
Figure 6. Figure 6: Gadget construction of G2 from G1, for example 4 regular graph 1. First, we take the set of vertices {u1, u2, . . . , un}, where each ui ∈ V (G2) corresponds to the vertex vi ∈ V (G1). 2. For each edge (vi , vj ) ∈ E(G1), where i < j, we add a new vertex uij and join it with ui and uj . 3. For each uij , we introduce (d − 2) new vertices u 1 ij , u2 ij , . . . , ud−2 ij and join each of them with uij . 4. … view at source ↗
Figure 7
Figure 7. Figure 7: Gadget construction of G2 from G1, for example 5-regular graph {v1, v2, . . . , vn}, we construct a new graph G2 as follows: 1. First, we take the set of vertex {u1, u2, . . . , un}, where each ui ∈ V (G2) corresponds to the vertex vi ∈ V (G1). 2. For each edge (vi , vj ) ∈ E(G1), where i < j, we add a new vertex uij and join with ui and uj . 3. For each uij , we introduce (d−2) new vertices u 1 ij , u2 ij… view at source ↗
Figure 8
Figure 8. Figure 8: Gadget construction of G2 from G1 In this subsection, we show that Hop Domination problem in a claw￾free graph is NP-complete, using the fact that the vertex cover problem Np￾Complete [1]. We reduce vertex cover problem to our problem. Consider any graph G1 with vertex set V (G1) = {v1, v2, . . . , vn} and edge set E(G1). We construct a new graph G2 in the following way: 1. We add a new vertex set {u1, u2,… view at source ↗
Figure 9
Figure 9. Figure 9: Gadget construction of G2 from G1 In this subsection, we show that 2-Step Domination problem in a claw￾free graph is NP-complete, using the fact that the vertex cover problem Np￾Complete [1]. We reduce vertex cover problem to our problem [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
read the original abstract

The domination problem is a well-studied problem in graph theory. In this paper, we study two natural variants: the hop domination problem and the $2$-step domination problem. Let $G$ be a graph with vertex set $V$ and edge set $E$. For a graph $G$, a subset $S \subseteq V(G)$ is called an \emph{hop dominating set} if every vertex not in $S$ lies at distance of exactly $2$ from at least one vertex in $S$. For $v\in V(G)$, let $N(v,2)$ denote the set of vertices in $V(G)$ that are at distance exactly $2$ from $v$. For a graph $G$, a subset $S \subseteq V(G)$ is called an \emph{$2$-step dominating set} if every vertex $v\in V(G)$ lies at a distance of exactly $2$ from at least one vertex in $S$. The \textsc{Hop Domination} (HD) problem and the \textsc{$2$-Step Domination} ($2$SD) problems ask whether a graph contains a hop domination set or a $2$-step domination set of size at most $k$, respectively. We study the computational complexity of these problems, and show that both are NP-complete, even when restricted to $d$-regular graphs for every $d\geq 3$, claw-free graphs and also unit disk graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the Hop Domination (HD) and 2-Step Domination (2SD) problems are NP-complete, even restricted to d-regular graphs for every d ≥ 3, claw-free graphs, and unit disk graphs. The proofs rely on polynomial-time reductions from known NP-complete problems (such as standard domination) that employ local gadgets explicitly designed to preserve d-regularity, claw-freeness, and unit-disk realizability via coordinate assignments, while maintaining yes/no correspondence through projection arguments between dominating sets in source and target instances.

Significance. These hardness results extend the complexity landscape for domination variants into practically relevant graph classes. The explicit gadget constructions that simultaneously enforce regularity, claw-freeness, and geometric realizability constitute a technical strength, as they permit direct verification of the preserved properties and support the claim of polynomial blow-up without hidden parameters.

minor comments (2)
  1. [§2] §2 (Definitions): The 2-step dominating set requires every vertex v (including those in S) to lie at distance exactly 2 from at least one member of S. This differs from standard domination variants; add a short paragraph comparing the definition to existing notions in the literature (e.g., 2-domination or total domination) to avoid reader confusion.
  2. [§4] §4 (Unit-disk reduction): While coordinate assignments are provided, the manuscript does not explicitly state the maximum coordinate magnitude or bit length; adding a sentence confirming that all coordinates remain polynomially bounded would strengthen the polynomial-time claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results and for recommending minor revision. The assessment accurately captures the scope of the NP-completeness proofs for Hop Domination and 2-Step Domination on the specified graph classes, including the use of local gadgets to preserve regularity, claw-freeness, and unit-disk realizability.

Circularity Check

0 steps flagged

No significant circularity in the claimed hardness results

full rationale

The paper proves NP-completeness of the Hop Domination and 2-Step Domination problems on d-regular graphs (d≥3), claw-free graphs, and unit disk graphs via explicit polynomial-time reductions from known NP-complete problems such as standard domination. These reductions are constructed using local gadgets that preserve the target graph properties and maintain a direct yes/no correspondence between instances, with polynomial size blow-up. No equations, fitted parameters, self-definitional steps, or load-bearing self-citations appear in the derivation chain; the results rest on independently established external hardness results and verifiable gadget constructions rather than any reduction to the paper's own inputs or prior self-referential claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and the assumption that the reductions are correctly constructed; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption NP-completeness proofs assume P ≠ NP and that the source problems used in reductions are NP-complete.
    This is the standard background assumption for all NP-completeness results in the field.

pith-pipeline@v0.9.0 · 5801 in / 1281 out tokens · 46210 ms · 2026-05-21T02:03:58.324196+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Alimonti and V

    P. Alimonti and V. Kann. Some apx-completeness results for cubic graphs.Theo- retical Computer Science, 237(1-2):123–134, 2000

    work page 2000

  2. [2]

    B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs.Discrete mathematics, 86(1-3):165–177, 1990

    work page 1990

  3. [3]

    S. Das, S. Das, and S. S. Islam. Parameterized complexity ofr-hop,r-step, and r-hop roman domination.arXiv preprint arXiv:2603.00692, 2026

    work page arXiv 2026

  4. [4]

    Erdős and T

    P. Erdős and T. Gallai. Gráfok előírt fokszámú pontokkal.Matematikai Lapok, 11:264–274, 1960

    work page 1960

  5. [5]

    Therectilinearsteinertreeproblemisnp-complete

    M.R.GareyandD.S.Johnson. Therectilinearsteinertreeproblemisnp-complete. SIAM Journal on Applied Mathematics, 32(4):826–834, 1977

    work page 1977

  6. [6]

    M. R. Garey and D. S. Johnson.Computers and intractability, volume 29. wh freeman New York, 2002

    work page 2002

  7. [7]

    S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. I.Journal of the Society for Industrial and Applied Mathematics (SIAM), 10(3):496–506, 1962

    work page 1962

  8. [8]

    V. Havel. A remark on the existence of finite graphs.Casopis Pest. Mat., 80:477– 480, 1955

    work page 1955

  9. [9]

    M. A. Henning, S. Pal, and D. Pradhan. Algorithm and hardness results on hop domination in graphs.Information Processing Letters, 153:105872, 2020

    work page 2020

  10. [10]

    M. A. Henning and N. J. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913–927, 2017

    work page 2017

  11. [11]

    A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982

    work page 1982

  12. [12]

    M. F. Jalalvand and N. J. Rad. On the complexity of k-step and k-hop dominating sets in graphs.Math. Montisnigri, 40:36–41, 2017

    work page 2017

  13. [13]

    Karthika, R

    D. Karthika, R. Muthucumaraswamy, S. Bhyravarapu, and P. Kumar. Hop domi- nation on subclasses of perfect graphs.Theoretical Computer Science, page 115547, 2025

    work page 2025

  14. [14]

    Karthika, R

    D. Karthika, R. Muthucumaraswamy, S. Bhyravarapu, and P. Kumar. Polynomial time algorithms for hop domination. InConference on Algorithms and Discrete Applied Mathematics, pages 85–96. Springer, 2025

    work page 2025

  15. [15]

    Natarajan and S

    C. Natarajan and S. Ayyaswamy. Hop domination in graphs-ii.Versita, 23(2):187– 199, 2015

    work page 2015

  16. [16]

    L. G. Valiant. Universality considerations in vlsi circuits.IEEE Transactions on Computers, 100(2):135–140, 1981

    work page 1981