pith. sign in

arxiv: 2604.22720 · v1 · submitted 2026-04-24 · 🧮 math.CO

Approximation algorithms and ratios for multiple domination in graphs

Lukas Dijkstra , Vadim Zverovich , Andrei Gagarin This is my paper

Pith reviewed 2026-05-08 11:03 UTC · model grok-4.3

classification 🧮 math.CO
keywords domination in graphsk-tuple dominationk-dominationapproximation algorithmsgreedy heuristicsgraph theorymultiple domination
0
0 comments X

The pith

The minimum k-tuple domination problem can be approximated within ln(Δ+1)+1 using a greedy heuristic.

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

This paper establishes approximation guarantees for the classical domination problem and two multiple-domination variants in graphs. It first supplies a short self-contained proof that the standard minimum domination problem admits an approximation ratio of ln(Δ+1)+1. It then applies similar greedy analysis to repair a gap in earlier work, proving the identical ratio for the k-tuple domination problem. Finally, it shows that the previously known ratio ln(2Δ)+1 for the k-domination problem can be strictly improved. These bounds matter because they give efficient, degree-dependent algorithms for finding near-optimal sets that dominate each vertex a prescribed number of times.

Core claim

We prove that the minimum k-tuple domination problem indeed can be approximated within the ratio of ln(Δ+1)+1. The proof is self-contained, direct, and much shorter than the existing proof, which contains the gap. We also show that the known approximation ratio of ln(2Δ)+1 for the minimum k-domination problem can be improved to a better ratio.

What carries the argument

A greedy heuristic that repeatedly selects a vertex covering the largest number of still-uncovered domination demands, with the ratio obtained by bounding the total cost via a sum over at most Δ+1 uncovered neighbors.

Load-bearing premise

The greedy heuristic analyses assume that the selection order and coverage counting rules behave exactly as described in the proofs without hidden dependencies on specific graph families beyond maximum degree Δ.

What would settle it

A graph with maximum degree Δ in which the size of the set returned by the greedy algorithm for k-tuple domination exceeds ln(Δ+1)+1 times the size of the optimal k-tuple dominating set.

read the original abstract

We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-contained proof of the known result that the minimum domination problem in any graph $G$ with maximum degree $\Delta$ can be solved within the approximation ratio of ${\ln(\Delta+1)+1}$. The proof is based on an analysis of a simple greedy heuristic. Then, by analysing more advanced greedy heuristic techniques and using ideas from our self-contained proof for the classical domination number, we fix a gap in the existing proof of a similar result for the $k$-tuple domination number. That is, we prove that the minimum $k$-tuple domination problem indeed can be approximated within the ratio of $\ln(\Delta+1)+1$. The proof of this result is self-contained, direct, and much shorter than the existing proof, which contains the gap. Finally, we show that the known approximation ratio of $\ln(2\Delta)+1$ for the minimum $k$-domination problem can be improved to a better ratio.

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

1 major / 2 minor

Summary. The manuscript provides a short self-contained proof that a simple greedy heuristic approximates the minimum domination number within ln(Δ+1)+1. It then uses an advanced greedy analysis, building on the same counting ideas, to correct a gap in prior work and establish the same ln(Δ+1)+1 ratio for the minimum k-tuple domination number. Finally, it improves the known ln(2Δ)+1 ratio for the minimum k-domination problem to a strictly better guarantee.

Significance. If the proofs are correct, the results supply simpler, self-contained derivations for tight approximation ratios on two multiple-domination variants and a modest improvement for k-domination. These problems are NP-hard and arise in network monitoring and resource placement; closing the cited gap with a direct argument is a useful clarification for the approximation-algorithms literature.

major comments (1)
  1. [§3] §3 (proof of the k-tuple domination theorem): the central counting argument asserts that each greedy selection reduces the total remaining demand by at least 1 while charging at most Δ+1 units, yielding the harmonic-sum bound ln(Δ+1)+1. The analysis must explicitly verify that this per-selection decrement bound continues to hold when neighborhoods overlap arbitrarily; the skeptic’s observation that shared vertices can cause demand decrements to interact in ways that effectively enlarge the charged set size is load-bearing for the claimed ratio and is not yet addressed by an auxiliary inequality or worst-case example.
minor comments (2)
  1. [Abstract] The abstract states that the k-domination ratio is improved to “a better ratio” but does not state the new explicit bound; the main text should give the precise expression (e.g., ln(Δ+1)+c for some c<1) already in the abstract or introduction.
  2. [Introduction] The prior paper whose gap is being closed should be cited by number and year in the introduction so readers can locate the original argument.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the manuscript. The significance assessment is appreciated. We address the single major comment below and will incorporate the requested clarification.

read point-by-point responses

  1. Referee: [§3] §3 (proof of the k-tuple domination theorem): the central counting argument asserts that each greedy selection reduces the total remaining demand by at least 1 while charging at most Δ+1 units, yielding the harmonic-sum bound ln(Δ+1)+1. The analysis must explicitly verify that this per-selection decrement bound continues to hold when neighborhoods overlap arbitrarily; the skeptic’s observation that shared vertices can cause demand decrements to interact in ways that effectively enlarge the charged set size is load-bearing for the claimed ratio and is not yet addressed by an auxiliary inequality or worst-case example.

    Authors: The reduction per selection is at least 1 because the algorithm terminates only when total remaining demand reaches zero; otherwise the greedy choice selects a vertex whose closed neighborhood intersects at least one vertex with positive remaining demand. Charging is performed exclusively to the vertices in N[v] of the selected vertex v, a set whose size is at most Δ+1 by the definition of Δ. Overlaps among neighborhoods affect only the current remaining-demand vector but cannot increase |N[v]| for the chosen v. Consequently the per-selection charge remains bounded by Δ+1 independently of overlaps. We will add a short clarifying paragraph together with a small illustrative example exhibiting overlapping neighborhoods while preserving the bound. revision: yes

Circularity Check

0 steps flagged

Self-contained direct proofs via greedy counting arguments exhibit no circularity

full rationale

The paper first gives an explicit self-contained proof for the classical domination ratio ln(Δ+1)+1 based on analysis of a simple greedy heuristic. It then extends similar direct counting techniques to fix and reprove the k-tuple domination result with the same ratio, and separately improves the k-domination bound. All steps rely on incremental potential or coverage counting that is derived from the algorithm description and maximum-degree bound, without reducing any claimed ratio to a fitted parameter, self-referential definition, or load-bearing prior self-citation. The proofs are presented sequentially within the single manuscript and do not invoke external uniqueness theorems or ansatzes from the authors' previous work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard graph-theoretic assumptions and the correctness of greedy selection counting; no free parameters, new entities, or ad-hoc axioms are introduced beyond the problem definitions.

axioms (1)
  • domain assumption The input is a simple undirected graph with finite maximum degree Δ.
    Invoked throughout the problem statements and ratio statements.

pith-pipeline@v0.9.0 · 5486 in / 1112 out tokens · 71799 ms · 2026-05-08T11:03:16.397926+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Alimonti and V

    P. Alimonti and V. Kann, Hardness of approximating problems on cubic graphs,Theoret. Com- put. Sci.237(2000) 123–134

    work page 2000

  2. [2]

    Cicalese, M

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

    work page 2013

  3. [3]

    Corcoran and A

    P. Corcoran and A. Gagarin, Heuristics fork-domination models of facility location problems in street networks, Computers & Operations Research133(2021), no. 105368, 11 pages

    work page 2021

  4. [4]

    Dijkstra, A

    L. Dijkstra, A. Gagarin, P. Corcoran and R. Lewis, Greedy and randomized heuristics for opti- mization ofk-domination models in digraphs and road networks. arXiv:2409.04226, 2024

    work page arXiv 2024

  5. [5]

    Downey and M.R

    R.G. Downey and M.R. Fellows,Parameterized Complexity, Springer, 1999

    work page 1999

  6. [6]

    Favaron, A

    O. Favaron, A. Hansberg and L. Volkmann, Onk-domination and minimum degree in graphs. J. Graph Theory57(2008) 33–40

    work page 2008

  7. [7]

    Feige, A threshold of lnnfor approximation set cover.Journal of ACM45(4) (1998) 634–652

    U. Feige, A threshold of lnnfor approximation set cover.Journal of ACM45(4) (1998) 634–652

    work page 1998

  8. [8]

    Gagarin and V.E

    A. Gagarin and V.E. Zverovich, A generalized upper bound for thek-tuple domination number. Discrete Math.308(5-6) (2008) 880–885

    work page 2008

  9. [9]

    Garey and D.S

    M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP- Completeness, New York, W.H. Freeman & Co., 1979

    work page 1979

  10. [10]

    Haynes, S.T

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

    work page 1998

  11. [11]

    Johnson, Approximation algorithms for combinatorial problems.JCSS9(1974) 256–278

    D.S. Johnson, Approximation algorithms for combinatorial problems.JCSS9(1974) 256–278

    work page 1974

  12. [12]

    Klasing and C

    R. Klasing and C. Laforest, Hardness results and approximation algorithms ofk-tuple domination in graphs.Inform. Process. Letters89(2004) 75–83

    work page 2004

  13. [13]

    Liao and G.J

    C.-S. Liao and G.J. Chang,k-Tuple domination in graphs.Inform. Process. Letters87(2003) 45–50

    work page 2003

  14. [14]

    Lan and G.J

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

    work page 2013

  15. [15]

    Rautenbach and L

    D. Rautenbach and L. Volkmann, New bounds on thek-domination number and thek-tuple domination number.Applied Math. Letters20(2007) 98–102

    work page 2007

  16. [16]

    Zverovich,Modern Applications of Graph Theory, Oxford University Press, Oxford, 2021

    V.E. Zverovich,Modern Applications of Graph Theory, Oxford University Press, Oxford, 2021. 14

    work page 2021