pith. sign in

arxiv: 2605.17982 · v2 · pith:U4JKBJA2new · submitted 2026-05-18 · 🧮 math.OC

A Benders Decomposition Approach for the k-Defensive Domination Problem

Bilge Varol , T{\i}naz Ekim , K\"ubra Tan{\i}nm{\i}\c{s} This is my paper

Pith reviewed 2026-05-21 08:33 UTC · model grok-4.3

classification 🧮 math.OC
keywords k-defensive dominationBenders decompositionfeasibility cutsinteger programmingnetwork securityclique cover heuristicgraph algorithms
0
0 comments X

The pith

Benders decomposition with new cut strategies and heuristics solves k-defensive domination instances that standard methods cannot.

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

The paper develops a Benders decomposition method for the k-defensive domination problem to find efficient ways to protect networks against simultaneous attacks on multiple nodes. It introduces combinatorial cut generation, simultaneous addition of multiple cuts, theoretical results on cut strength, a clique-cover heuristic that finds good initial solutions, and an initial cut generation heuristic that sometimes solves problems without branching. Experiments on Erdos-Renyi, chordal, and Barabasi-Albert graphs show the full combination outperforms classical integer programming formulations and plain Benders decomposition on harder cases.

Core claim

By embedding combinatorial cut generation, simultaneous cut addition, a clique-cover-based heuristic for feasible solutions, and an initial cut generation heuristic inside Benders decomposition applied to an integer programming formulation, the resulting algorithm solves instances of the k-defensive domination problem that remain out of reach for direct solvers and standard Benders approaches.

What carries the argument

Benders decomposition on the integer programming model of k-defensive domination, generating and strengthening feasibility cuts combinatorially while using heuristics to obtain strong initial solutions and cuts.

If this is right

  • The method supplies a practical computational tool for network security and emergency management models involving multiple simultaneous threats.
  • The clique-cover heuristic supplies the first feasible-solution method for the problem and improves the trivial upper bound by up to 98 percent.
  • Initial cut generation resolves some instances without further branching.
  • Theoretical results establish the validity and relative strength of the generated feasibility cuts.
  • The approach scales to larger instances across random, chordal, and scale-free graph families than prior formulations allow.

Where Pith is reading between the lines

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

  • The same cut-strengthening ideas could be tested on other multi-attack domination variants or interdiction problems on graphs.
  • The heuristics might transfer to dynamic or online versions of the problem where attacks arrive over time.
  • Combining the decomposition with column generation or other relaxations could push the solvable instance sizes even higher.
  • Real-world networks with community structure might expose whether the clique-cover heuristic retains its reported speed advantage.

Load-bearing premise

The k-defensive domination problem has a compact integer programming formulation whose Benders subproblems produce useful feasibility cuts that can be strengthened and generated efficiently with the proposed strategies.

What would settle it

On the largest chordal or Barabasi-Albert instances in the test set, run the full enhanced algorithm side-by-side with a standard Benders implementation and a direct integer programming solver; if the enhanced version alone finds optimal solutions within the time limit on instances where the others time out or return no solution, the claim holds.

Figures

Figures reproduced from arXiv: 2605.17982 by Bilge Varol, K\"ubra Tan{\i}nm{\i}\c{s}, T{\i}naz Ekim.

Figure 1
Figure 1. Figure 1: Performance comparison of IP to BBMC++ on the same Erd˝os–R´enyi graphs: [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performance comparison of IP, Benders and all BBMC variants on chordal graphs: [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance comparison of IP, Benders and all BBMC variants on Barab´asi-Albert [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
read the original abstract

The k-defensive domination problem is a powerful modeling tool for strategic decision-making in network security and disaster/emergency management, where multiple nodes may be simultaneously under attack. Despite its practical relevance, the problem has been poorly studied, largely due to its high computational difficulty. This study investigates the application of Benders decomposition to the k-defensive domination problem, aiming to improve computational efficiency over standard integer programming formulations. Several cut generation strategies, including a combinatorial approach and the simultaneous addition of multiple cuts, are proposed. Theoretical results on the strength of feasibility cuts are presented. In addition, two novel enhancement strategies are proposed: a clique-cover-based heuristic, the first feasible solution method in the literature for this problem, achieving up to 98% improvement over the trivial upper bound, and an initial cut generation heuristic that in some cases resolves the problem without further branching. Experiments on Erdos-Renyi, chordal, and Barabasi-Albert instances show that the algorithm variant involving all of the proposed components is able to solve instances that remain out of reach for classical formulations and standard Benders decomposition.

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

2 major / 2 minor

Summary. The manuscript develops a Benders decomposition algorithm for the k-defensive domination problem, an integer program arising in network security. It introduces strengthened feasibility cuts with accompanying theoretical analysis, a clique-cover heuristic that produces the first known feasible solutions in the literature (up to 98% improvement over the trivial upper bound), and an initial-cut heuristic. Experiments on Erdős-Rényi, chordal, and Barabási-Albert graphs are reported to demonstrate that the full combination of components solves instances that remain out of reach for both the compact IP formulation and plain Benders decomposition.

Significance. If the performance claims are substantiated by controlled experiments, the work would provide a useful algorithmic advance for a computationally hard problem with direct applications in strategic network defense. The theoretical results on cut strength and the novel clique-cover heuristic constitute concrete contributions; however, the overall significance hinges on whether the reported gains can be isolated from solver heuristics and instance selection.

major comments (2)
  1. [Computational Experiments] Computational experiments section: the central claim that the full algorithm (Benders + strengthened cuts + clique-cover heuristic + initial-cut heuristic) solves instances unreachable by classical IP and standard Benders is load-bearing, yet the manuscript provides no table or subsection that, for each unsolved baseline instance, records the precise time limit, solver version, hardware, and whether the baseline runs used identical cut pools, branching rules, or presolve settings. Without this isolation, the performance edge cannot be confidently attributed to the proposed Benders machinery.
  2. [Theoretical Analysis of Cuts] Section on theoretical results: the abstract states that theoretical results on the strength of feasibility cuts are presented, but the manuscript does not explicitly locate the relevant theorem(s) or state the precise conditions (graph class, value of k) under which the strengthened cuts dominate the standard feasibility cuts. This weakens the ability to assess the novelty and generality of the cut analysis.
minor comments (2)
  1. [Formulation and Algorithm] Notation for the defensive domination number and the auxiliary variables in the master and subproblems should be made fully consistent across the formulation, algorithm description, and experimental tables.
  2. [Heuristics] The manuscript should clarify whether the reported 98% improvement of the clique-cover heuristic is measured against the trivial upper bound on every instance or only on a subset; a per-instance breakdown would strengthen the claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. We address each major comment below and indicate the revisions planned for the next version of the manuscript.

read point-by-point responses

  1. Referee: Computational experiments section: the central claim that the full algorithm (Benders + strengthened cuts + clique-cover heuristic + initial-cut heuristic) solves instances unreachable by classical IP and standard Benders is load-bearing, yet the manuscript provides no table or subsection that, for each unsolved baseline instance, records the precise time limit, solver version, hardware, and whether the baseline runs used identical cut pools, branching rules, or presolve settings. Without this isolation, the performance edge cannot be confidently attributed to the proposed Benders machinery.

    Authors: We agree that the current presentation does not provide sufficient detail to isolate the contribution of the proposed components from solver defaults. In the revised manuscript we will add a dedicated subsection (and an accompanying table) that records, for every instance, the solver version, hardware platform, time limit, and explicit confirmation that all baseline runs used identical presolve, branching, and cut-pool settings. This will allow readers to attribute performance differences directly to the Benders machinery. revision: yes

  2. Referee: Section on theoretical results: the abstract states that theoretical results on the strength of feasibility cuts are presented, but the manuscript does not explicitly locate the relevant theorem(s) or state the precise conditions (graph class, value of k) under which the strengthened cuts dominate the standard feasibility cuts. This weakens the ability to assess the novelty and generality of the cut analysis.

    Authors: The dominance proofs appear in Section 3. We acknowledge that the abstract and introduction do not currently contain an explicit pointer or a clear statement of the conditions. In the revision we will (i) add a direct reference to the relevant theorems in the abstract and (ii) insert a sentence stating that the strengthened cuts dominate the standard feasibility cuts for every undirected graph and every integer k >= 1. This will make the scope and novelty of the analysis immediately clear. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces a compact IP formulation for the k-defensive domination problem and applies standard Benders decomposition, proposing combinatorial cut generation, theoretical results on feasibility cut strength, a clique-cover heuristic, and an initial-cut heuristic. These elements are derived from established optimization techniques and problem-specific combinatorial arguments rather than self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The performance improvements are attributed to the algorithmic additions on new instances, with the derivation remaining self-contained against external benchmarks and not reducing to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard assumption that the k-defensive domination problem has a valid mixed-integer linear programming formulation whose Benders subproblems produce valid feasibility cuts; no new free parameters or invented entities are introduced beyond the algorithmic components.

axioms (1)
  • domain assumption The k-defensive domination problem admits a mixed-integer linear programming formulation whose Benders decomposition yields valid feasibility cuts.
    Invoked implicitly when the authors apply Benders decomposition and discuss cut strength.

pith-pipeline@v0.9.0 · 5739 in / 1342 out tokens · 55913 ms · 2026-05-21T08:33:27.480286+00:00 · methodology

Review history (2 revisions) →

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

41 extracted references · 41 canonical work pages

  1. [1]

    2013 , publisher=

    Fundamentals of domination in graphs , author=. 2013 , publisher=

    work page 2013

  2. [2]

    2014 , publisher=

    Total Domination in Graphs , author=. 2014 , publisher=

    work page 2014

  3. [3]

    2020 , publisher=

    Topics in domination in graphs , author=. 2020 , publisher=

    work page 2020

  4. [4]

    2023 , publisher=

    Domination in graphs: Core concepts , author=. 2023 , publisher=

    work page 2023

  5. [5]

    Wiley Encyclopedia of Operations Research and Management Science

    Benders decomposition , author=. Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons, Malden (MA) , year=

    work page

  6. [6]

    Congressus Numerantium , volume=

    Defensive domination , author=. Congressus Numerantium , volume=. 2004 , publisher=

    work page 2004

  7. [7]

    Discrete Mathematics , volume=

    The complexity of the defensive domination problem in special graph classes , author=. Discrete Mathematics , volume=. 2020 , publisher=

    work page 2020

  8. [8]

    Discrete Applied Mathematics , volume=

    Defensive domination in proper interval graphs , author=. Discrete Applied Mathematics , volume=. 2023 , publisher=

    work page 2023

  9. [9]

    2004 , publisher=

    Polyhedral studies in domination graph theory (I) , author=. 2004 , publisher=

    work page 2004

  10. [10]

    Annals of Operations Research , volume=

    A decomposition approach for solving a broadcast domination network design problem , author=. Annals of Operations Research , volume=. 2013 , publisher=

    work page 2013

  11. [11]

    arXiv preprint arXiv:2312.04526 , year=

    Algorithms for the Global Domination Problem , author=. arXiv preprint arXiv:2312.04526 , year=

    work page arXiv

  12. [12]

    arXiv preprint arXiv:2311.06490 , year=

    Integer Programming Formulations and Probabilistic Bounds for Some Domination Parameters , author=. arXiv preprint arXiv:2311.06490 , year=

    work page arXiv

  13. [13]

    Mathematical Methods of Operations Research , volume=

    Binary programming formulations for the upper domination problem , author=. Mathematical Methods of Operations Research , volume=. 2023 , publisher=

    work page 2023

  14. [14]

    INFORMS Journal on Computing , volume=

    An integer programming approach for fault-tolerant connected dominating sets , author=. INFORMS Journal on Computing , volume=. 2015 , publisher=

    work page 2015

  15. [15]

    Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012

    Solving the connected dominating set problem and power dominating set problem by integer programming , author=. Combinatorial Optimization and Applications: 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings 6 , pages=. 2012 , organization=

    work page 2012

  16. [16]

    INFORMS Journal on Computing , volume=

    Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem , author=. INFORMS Journal on Computing , volume=. 2014 , publisher=

    work page 2014

  17. [17]

    2022 IEEE Wireless Communications and Networking Conference (WCNC) , pages=

    Integer programs for contention aware connected dominating sets in wireless multi-hop networks , author=. 2022 IEEE Wireless Communications and Networking Conference (WCNC) , pages=. 2022 , organization=

    work page 2022

  18. [18]

    International conference on network optimization , pages=

    The minimum connected dominating set problem: Formulation, valid inequalities and a branch-and-cut algorithm , author=. International conference on network optimization , pages=. 2011 , organization=

    work page 2011

  19. [19]

    Optimization Methods and Software , volume=

    Integer linear programming formulations for double roman domination problem , author=. Optimization Methods and Software , volume=. 2022 , publisher=

    work page 2022

  20. [20]

    Optimization Letters , volume=

    Modelling and solving the perfect edge domination problem , author=. Optimization Letters , volume=. 2020 , publisher=

    work page 2020

  21. [21]

    Computers & Operations Research , volume=

    Exact and heuristic algorithms for the weighted total domination problem , author=. Computers & Operations Research , volume=. 2021 , publisher=

    work page 2021

  22. [22]

    European Journal of Operational Research , volume=

    The weighted independent domination problem: Integer linear programming models and metaheuristic approaches , author=. European Journal of Operational Research , volume=. 2018 , publisher=

    work page 2018

  23. [23]

    Applied Mathematics and Computation , volume=

    Integer linear programming models for the weighted total domination problem , author=. Applied Mathematics and Computation , volume=. 2019 , publisher=

    work page 2019

  24. [24]

    Journal of Combinatorial Optimization , volume=

    Roman domination on strongly chordal graphs , author=. Journal of Combinatorial Optimization , volume=. 2013 , publisher=

    work page 2013

  25. [25]

    Theory and Applications of Mathematics & Computer Science , volume=

    A Mixed Integer Linear Programming Formulation for Restrained Roman Domination Problem , author=. Theory and Applications of Mathematics & Computer Science , volume=. 2015 , publisher=

    work page 2015

  26. [26]

    arXiv preprint arXiv:2305.00730 , year=

    Integer Linear Programming Formulations for Triple and Quadruple Roman Domination Problems , author=. arXiv preprint arXiv:2305.00730 , year=

    work page arXiv

  27. [27]

    Soft Computing , volume=

    Improved integer linear programming formulation for weak Roman domination problem , author=. Soft Computing , volume=. 2018 , publisher=

    work page 2018

  28. [28]

    On the evolution of random graphs , author=. Publ. Math. Inst. Hungar. Acad. Sci , volume=. 1960 , publisher=

    work page 1960

  29. [29]

    Conditional graph-theory. 4. dominating sets , author=. Utilitas Mathematica , volume=. 1995 , publisher=

    work page 1995

  30. [30]

    Discrete Applied Mathematics , volume=

    More on the complexity of defensive domination in graphs , author=. Discrete Applied Mathematics , volume=. 2025 , publisher=

    work page 2025

  31. [31]

    International Conference on Combinatorial Optimization and Applications , pages=

    Approximation Algorithm and Hardness Results for Defensive Domination in Graphs , author=. International Conference on Combinatorial Optimization and Applications , pages=. 2021 , organization=

    work page 2021

  32. [32]

    Numerische Mathematik , volume=

    Partitioning procedures for solving mixed-variables programming problems , author=. Numerische Mathematik , volume=

    work page

  33. [33]

    New methods to color the vertices of a graph , year =

    Br\'. New methods to color the vertices of a graph , year =. doi:10.1145/359094.359101 , journal =

    work page doi:10.1145/359094.359101

  34. [34]

    Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph , journal =

    Gavril, F. Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph , journal =. 1972 , doi =

    work page 1972

  35. [35]

    and Johnson, David S

    Garey, Michael R. and Johnson, David S. , title =. 1990 , isbn =

    work page 1990

  36. [36]

    Theoretical Computer Science , volume=

    Cops, a fast robber and defensive domination on interval graphs , author=. Theoretical Computer Science , volume=. 2019 , publisher=

    work page 2019

  37. [37]

    50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) , pages =

    Chaplick, Steven and Gutowski, Grzegorz and Krawczyk, Tomasz , title =. 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) , pages =. 2025 , volume =

    work page 2025

  38. [38]

    science , volume=

    Emergence of scaling in random networks , author=. science , volume=. 1999 , publisher=

    work page 1999

  39. [39]

    RAIRO-Operations Research , volume=

    Generation of random chordal graphs using subtrees of a tree , author=. RAIRO-Operations Research , volume=. 2022 , publisher=

    work page 2022

  40. [40]

    Chordal: GitHub repository , year=

    Oylum. Chordal: GitHub repository , year=

    work page

  41. [41]

    2026 , note =

    Bilge Varol , title =. 2026 , note =

    work page 2026