Continuous Defensive Domination Problems

Christoph Gr\"une; Tom Jan{\ss}en

arxiv: 2605.10607 · v1 · submitted 2026-05-11 · 💻 cs.CC

Continuous Defensive Domination Problems

Christoph Gr\"une , Tom Jan{\ss}en This is my paper

Pith reviewed 2026-05-12 05:22 UTC · model grok-4.3

classification 💻 cs.CC

keywords continuous defensive coveringcomputational complexityNP-completenessSigma2P-completenessgraph facility locationdiscretizationmatching within distance

0 comments

The pith

Attacks limited to vertices make continuous defensive δ-covering Σ²_P-complete for large δ, while any-point attacks make it NP-complete.

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

The paper determines the computational complexity of finding a small set of defense points on a unit-edge graph that can match and neutralize any attack set of a given size within distance δ. When attacks are forced to occur only at vertices, the problem sits in the second level of the polynomial hierarchy for sufficiently large δ. When attacks may instead occupy any interior point on an edge, the problem falls into NP. The proofs rely on showing that both optimal defenses and attacks can always be chosen from a finite, regularly spaced set of candidate positions, turning the continuous problem into a discrete one that can be classified. Allowing repeated use of the same defense location leaves the complexity unchanged, but repeated attack locations at the same spot often lowers it.

Core claim

The Defensive δ-Covering problem is Σ²_P-complete when attacks are restricted to vertices and δ is large, yet NP-complete when attacks may consist of arbitrary points on the graph. Containment holds because discretization arguments guarantee that solutions with regular structure always exist, reducing the infinite point choices to a finite enumeration. Complexity is unaffected by allowing defenses to be multisets, while allowing attacks to be multisets frequently simplifies the problem to a lower class.

What carries the argument

A perfect matching of attack points to defense points with each matched pair at distance at most δ, where the defense has size at most ℓ and must work against every possible attack of size at most k.

If this is right

Vertex-attack instances require an NP oracle for verification, placing them in the polynomial hierarchy.
Continuous-attack instances admit short certificates that can be checked in polynomial time.
Any optimal solution can be found by testing a finite list of regularly spaced candidate locations on each edge.
Multiset defenses preserve the same hardness results; multiset attacks often drop the problem into a lower class.

Where Pith is reading between the lines

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

Modelers of network defense might deliberately treat attacks as continuous to obtain an NP formulation rather than a higher-level one.
The same regular-structure reduction could be tested on other continuous domination or covering problems on graphs.
Approximation schemes for the NP-complete continuous version become a natural next target for scaling to large networks.

Load-bearing premise

Optimal defenses and attacks always exist using only a regular, discrete collection of candidate positions on vertices and edge interiors.

What would settle it

A concrete graph together with ℓ, k and δ values for which the minimal defense size changes when points are forced to lie at irrational fractions of edge lengths instead of the regular candidate positions.

read the original abstract

The problem Defensive $\delta$-Covering, for some covering range $\delta > 0$, is a continuous facility location problem on undirected graphs where all edges have unit length. It is a generalization of Defensive Dominating Set and $\delta$-Covering. An attack and defense are sets of points, which are on vertices or on the interior of an edge. A defense counters an attack, if there is a matching of the points in the defense to the points in the attack, such that any matched points have distance at most $\delta$, and every point in the attack is matched. The task is, given a graph $G$ and numbers $\ell, k \in \mathbb N$, to find a defense of size at most $\ell$ that counters every possible attack of size at most $k$. We study the complexity of this problem in various different settings. We show that if the attack is restricted to vertices, the problem is $\Sigma^P_2$-complete for large $\delta$, but if the attack may consist of any points on the graph, it is NP-complete. Additionally, we analyze how the complexity changes if the attacks or defenses may be a multiset. If the defense is allowed to be a multiset, the complexity does not change in any case we consider, while if the attack is allowed to be a multiset, the problem often becomes easier. To show containment in the various complexity classes, we introduce a number of discretization arguments, which show that solutions with a regular structure must always exist.

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.

Desk Editor's Note private letter to a colleague

The paper cleanly separates complexity for continuous defensive δ-covering: Σ²_P-complete when attacks are vertex-restricted, NP-complete when attacks can be any points on the edges.

read the letter

The main thing to know is that this work gives a complexity separation between vertex attacks and arbitrary point attacks in the continuous defensive covering model on unit-edge graphs. For large δ the vertex case is Σ²_P-complete while the general-point case drops to NP-complete. They also track how allowing multisets for attacks or defenses shifts the classes, with attack multisets often making things easier and defense multisets leaving complexity unchanged. That separation and the multiset analysis are the concrete new pieces relative to prior discrete defensive domination results. The discretization arguments they introduce to prove membership are the part that actually makes the upper bounds go through; they show that optimal solutions always admit a regular structure so the continuous problem reduces to a finite, polynomially describable case. That is useful technical work and it is presented directly. The soft spot is exactly the one the stress-test flags: the discretization step for the continuous-attack NP case rests on the claim that regular-structure optima always exist. If that fails for some δ or graph families where optimal placements force irrational or arbitrarily fine positions, the certificate size or the universal quantifier over attacks would not stay polynomial, and the membership proof would not hold. The abstract states the arguments exist, but without the full reductions it is impossible to judge how robust they are. This paper is for people who work on complexity of domination, covering, and facility-location problems on graphs. A reader already familiar with the discrete versions will see the continuous extension and the hardness landscape clearly. It deserves a serious referee because the results are new, the model is well-defined, and the technical approach is systematic even if the discretization details need verification. I would send it to peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript studies the complexity of Continuous Defensive δ-Covering on undirected unit-edge graphs, a continuous generalization of defensive domination. It claims that vertex-restricted attacks yield Σ²_P-completeness for large δ, while unrestricted continuous attacks (any points on vertices or edges) yield NP-completeness. It further shows that allowing multisets for defenses leaves the complexity unchanged, while multiset attacks often simplify the problem, and introduces discretization arguments establishing that optimal solutions always admit a regular structure to prove membership in the target classes.

Significance. If the discretization arguments hold, the results cleanly separate the complexity impact of continuity in attacks versus defenses and supply a reusable technique for reducing continuous facility-location problems on graphs to finite instances. This strengthens the bridge between discrete domination theory and continuous variants, with direct relevance to network interdiction and facility placement.

major comments (2)

[Discretization arguments] Discretization arguments (introduced to establish containment): the claim that 'solutions with a regular structure must always exist' is invoked to reduce both the existential defense and the universal attack quantifier to polynomially describable certificates. No explicit bound is given on the fineness of the discretization grid or on the bit-length of the rational coordinates needed when optimal matching distances are irrational or when δ is arbitrary; this directly affects whether the NP certificate (continuous-attack case) and the Σ²_P verifier (vertex-attack case) remain polynomial-time checkable.
[Complexity results for continuous attacks] Membership proofs for the continuous-attack case: the reduction to a finite attack set via discretization is load-bearing for NP membership, yet the manuscript provides only an outline. If there exist graph families and δ values where every optimal attack requires placements whose minimal description length grows super-polynomially, the claimed NP upper bound fails.

minor comments (2)

[Abstract] The abstract states results 'for large δ' without defining the threshold; a precise condition on δ (e.g., δ ≥ 1 or δ ≥ diam(G)/2) should appear in the statement of the Σ²_P-completeness theorem.
[Preliminaries] Notation for multisets versus sets is introduced late; early sections would benefit from a uniform convention distinguishing multiplicity-allowed attacks from ordinary sets.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the two major comments point by point below. Both concerns are valid and will be resolved by expanding the relevant sections in a revised version.

read point-by-point responses

Referee: [Discretization arguments] Discretization arguments (introduced to establish containment): the claim that 'solutions with a regular structure must always exist' is invoked to reduce both the existential defense and the universal attack quantifier to polynomially describable certificates. No explicit bound is given on the fineness of the discretization grid or on the bit-length of the rational coordinates needed when optimal matching distances are irrational or when δ is arbitrary; this directly affects whether the NP certificate (continuous-attack case) and the Σ²_P verifier (vertex-attack case) remain polynomial-time checkable.

Authors: We agree that the current presentation gives only an outline of the discretization arguments and does not supply explicit quantitative bounds. This omission affects the rigor of the membership proofs. In the revision we will add a self-contained subsection that (i) constructs an explicit polynomial-size discretization grid whose fineness depends only on the input size, the number of edges, and the binary length of δ, and (ii) proves that any optimal defense or attack can be replaced by one whose coordinates are rational with bit length polynomial in the input. The argument relies on a standard perturbation lemma for shortest-path distances on unit-edge graphs that preserves the ≤δ matching condition. With these bounds the NP certificate and the Σ²_P verifier become polynomial-time checkable. revision: yes
Referee: [Complexity results for continuous attacks] Membership proofs for the continuous-attack case: the reduction to a finite attack set via discretization is load-bearing for NP membership, yet the manuscript provides only an outline. If there exist graph families and δ values where every optimal attack requires placements whose minimal description length grows super-polynomially, the claimed NP upper bound fails.

Authors: We acknowledge that the outline must be expanded into a complete proof. In the revised manuscript we will prove that, for any attack, there exists an equivalent attack of polynomial size whose points lie at rational positions with polynomially bounded bit length. The proof proceeds by first applying the regular-structure lemma already stated in the paper and then invoking the same perturbation argument used for the defense side. Because all edges have unit length, the shortest-path distances admit a finite set of candidate “critical” positions whose number is polynomial in n and the bit length of δ; no super-polynomial description length arises. We will include this explicit construction so that the NP membership claim is fully supported. revision: yes

Circularity Check

0 steps flagged

No significant circularity; discretization arguments are introduced as independent proofs

full rationale

The paper's membership proofs for NP (continuous attacks) and Σ²_P (vertex attacks) rest on newly introduced discretization arguments showing existence of regular-structure optimal solutions that reduce to finite, polynomially describable instances. These are presented as original technical contributions rather than self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. Hardness results rely on standard reductions from prior literature. No equation or claim reduces by construction to its own inputs; the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph theory (unit edge lengths) and introduces discretization to bound the search space; no free parameters or invented entities are described in the abstract.

axioms (2)

domain assumption All edges have unit length
Stated in the problem definition to enable distance-based matching.
ad hoc to paper Discretization arguments show regular structured solutions always exist
Used to prove containment in complexity classes by reducing to finite candidate positions.

pith-pipeline@v0.9.0 · 5573 in / 1160 out tokens · 35018 ms · 2026-05-12T05:22:25.865087+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

A note on the complexity of defensive domination

1 Steven Chaplick, Grzegorz Gutowski, and Tomasz Krawczyk. A note on the complexity of defensive domination. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors,50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, August 25-29, 2025, Warsaw, Poland, volume 345 ofLIPIcs, pages 35:1–35:15. Schloss Dags...

work page 2025
[2]

2 Perino M

URL:https://doi.org/10.4230/ LIPIcs.MFCS.2025.35,doi:10.4230/LIPICS.MFCS.2025.35. 2 Perino M. Dearing and Richard Lane Francis. A minimax location problem on a network. Transportation Science, 8(4):333–343,

work page doi:10.4230/lipics.mfcs.2025.35 2025
[3]

org/10.1016/j.tcs.2018.09.031,doi:10.1016/J.TCS.2018.09.031

URL:https://doi. org/10.1016/j.tcs.2018.09.031,doi:10.1016/J.TCS.2018.09.031. 4 E. Drezner. Facility location: A survey of applications and methods.Journal of the Operational Research Society, 47(11):1421–1421,

work page doi:10.1016/j.tcs.2018.09.031 2018
[4]

6 Tínaz Ekim, Arthur M

URL: https://doi.org/10.1016/j.disc.2019.111665,doi:10.1016/J.DISC.2019.111665. 6 Tínaz Ekim, Arthur M. Farley, Andrzej Proskurowski, and Mordechai Shalom. Defensive domination in proper interval graphs.Discret. Appl. Math., 331:59–69,

work page doi:10.1016/j.disc.2019.111665 2019
[5]

7 Fabian Frei, Ahmed Ghazy, Tim A

URL:https: //doi.org/10.1016/j.dam.2023.01.016,doi:10.1016/J.DAM.2023.01.016. 7 Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, and Dániel Marx. From chinese postman to salesman and beyond: Shortest tourδ-covering all points on all edges. In Julián Mestre and Anthony Wirth, editors,35th International Symposium on Algorithms and Computation, ISA...

work page doi:10.1016/j.dam.2023.01.016 2023
[6]

8 Alexander Grigoriev, Tim A

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2024.31,doi:10.4230/LIPICS.ISAAC.2024.31. 8 Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dispersing obnoxious facilities on a graph.Algorithmica, 83(6):1734–1749,

work page doi:10.4230/lipics.isaac.2024.31 2024
[7]

9 Christoph Grüne and Lasse Wulf

URL:https://doi.org/ 10.1007/s00453-021-00800-3,doi:10.1007/S00453-021-00800-3. 9 Christoph Grüne and Lasse Wulf. The complexity of blocking all solutions.Theor. Comput. Sci., 1069:115820,

work page doi:10.1007/s00453-021-00800-3
[8]

10 Tim A

URL:https://doi.org/10.1016/j.tcs.2026.115820, doi:10.1016/ J.TCS.2026.115820. 10 Tim A. Hartmann and Tom Janßen. Approximatingδ-covering. In Marcin Bienkowski and Mat- thias Englert, editors,Approximation and Online Algorithms - 22nd International Workshop, WAOA 2024, Egham, UK, September 5-6, 2024, Proceedings, volume 15269 ofLecture Notes in Computer S...

work page doi:10.1016/j.tcs.2026.115820 2026
[9]

12 Tim A

URL:https://doi.org/10.4230/LIPIcs.MFCS.2022.55, doi: 10.4230/LIPICS.MFCS.2022.55. 12 Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Continuous facility loca- tion on graphs.Math. Program., 192(1):207–227,

work page doi:10.4230/lipics.mfcs.2022.55 2022
[10]

13 Michael A

URL:https://doi.org/10.1007/ s10107-021-01646-x,doi:10.1007/S10107-021-01646-X. 13 Michael A. Henning, Arti Pandey, and Vikash Tripathi. More on the complexity of defensive domination in graphs.Discret. Appl. Math., 362:167–179,

work page doi:10.1007/s10107-021-01646-x
[11]

1016/j.dam.2024.11.023,doi:10.1016/J.DAM.2024.11.023

URL:https://doi.org/10. 1016/j.dam.2024.11.023,doi:10.1016/J.DAM.2024.11.023. 14 David G. Kirkpatrick and Pavol Hell. On the complexity of general graph factor problems. SIAM J. Comput., 12(3):601–609, 1983.doi:10.1137/0212040. 15 Nimrod Megiddo and Arie Tamir. New results on the complexity of p-center problems.SIAM J. Comput., 12(4):751–758, 1983.doi:10....

work page doi:10.1016/j.dam.2024.11.023 2024
[12]

Propositional truth maintenance systems: Classification and complexity analysis.Ann

18 Vladislav Rutenburg. Propositional truth maintenance systems: Classification and complexity analysis.Ann. Math. Artif. Intell., 10(3):207–232, 1993.doi:10.1007/BF01530952. 19 Alexander Schrijver et al.Combinatorial optimization: polyhedra and efficiency, volume

work page doi:10.1007/bf01530952 1993
[13]

21 Arie Tamir

URL:https://doi.org/10.1287/moor.12.2.340, doi:10.1287/MOOR.12.2.340. 21 Arie Tamir. Obnoxious facility location on graphs.SIAM J. Discret. Math., 4(4):550–567, 1991.doi:10.1137/0404048

work page doi:10.1287/moor.12.2.340 1991

[1] [1]

A note on the complexity of defensive domination

1 Steven Chaplick, Grzegorz Gutowski, and Tomasz Krawczyk. A note on the complexity of defensive domination. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors,50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, August 25-29, 2025, Warsaw, Poland, volume 345 ofLIPIcs, pages 35:1–35:15. Schloss Dags...

work page 2025

[2] [2]

2 Perino M

URL:https://doi.org/10.4230/ LIPIcs.MFCS.2025.35,doi:10.4230/LIPICS.MFCS.2025.35. 2 Perino M. Dearing and Richard Lane Francis. A minimax location problem on a network. Transportation Science, 8(4):333–343,

work page doi:10.4230/lipics.mfcs.2025.35 2025

[3] [3]

org/10.1016/j.tcs.2018.09.031,doi:10.1016/J.TCS.2018.09.031

URL:https://doi. org/10.1016/j.tcs.2018.09.031,doi:10.1016/J.TCS.2018.09.031. 4 E. Drezner. Facility location: A survey of applications and methods.Journal of the Operational Research Society, 47(11):1421–1421,

work page doi:10.1016/j.tcs.2018.09.031 2018

[4] [4]

6 Tínaz Ekim, Arthur M

URL: https://doi.org/10.1016/j.disc.2019.111665,doi:10.1016/J.DISC.2019.111665. 6 Tínaz Ekim, Arthur M. Farley, Andrzej Proskurowski, and Mordechai Shalom. Defensive domination in proper interval graphs.Discret. Appl. Math., 331:59–69,

work page doi:10.1016/j.disc.2019.111665 2019

[5] [5]

7 Fabian Frei, Ahmed Ghazy, Tim A

URL:https: //doi.org/10.1016/j.dam.2023.01.016,doi:10.1016/J.DAM.2023.01.016. 7 Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, and Dániel Marx. From chinese postman to salesman and beyond: Shortest tourδ-covering all points on all edges. In Julián Mestre and Anthony Wirth, editors,35th International Symposium on Algorithms and Computation, ISA...

work page doi:10.1016/j.dam.2023.01.016 2023

[6] [6]

8 Alexander Grigoriev, Tim A

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2024.31,doi:10.4230/LIPICS.ISAAC.2024.31. 8 Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dispersing obnoxious facilities on a graph.Algorithmica, 83(6):1734–1749,

work page doi:10.4230/lipics.isaac.2024.31 2024

[7] [7]

9 Christoph Grüne and Lasse Wulf

URL:https://doi.org/ 10.1007/s00453-021-00800-3,doi:10.1007/S00453-021-00800-3. 9 Christoph Grüne and Lasse Wulf. The complexity of blocking all solutions.Theor. Comput. Sci., 1069:115820,

work page doi:10.1007/s00453-021-00800-3

[8] [8]

10 Tim A

URL:https://doi.org/10.1016/j.tcs.2026.115820, doi:10.1016/ J.TCS.2026.115820. 10 Tim A. Hartmann and Tom Janßen. Approximatingδ-covering. In Marcin Bienkowski and Mat- thias Englert, editors,Approximation and Online Algorithms - 22nd International Workshop, WAOA 2024, Egham, UK, September 5-6, 2024, Proceedings, volume 15269 ofLecture Notes in Computer S...

work page doi:10.1016/j.tcs.2026.115820 2026

[9] [9]

12 Tim A

URL:https://doi.org/10.4230/LIPIcs.MFCS.2022.55, doi: 10.4230/LIPICS.MFCS.2022.55. 12 Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Continuous facility loca- tion on graphs.Math. Program., 192(1):207–227,

work page doi:10.4230/lipics.mfcs.2022.55 2022

[10] [10]

13 Michael A

URL:https://doi.org/10.1007/ s10107-021-01646-x,doi:10.1007/S10107-021-01646-X. 13 Michael A. Henning, Arti Pandey, and Vikash Tripathi. More on the complexity of defensive domination in graphs.Discret. Appl. Math., 362:167–179,

work page doi:10.1007/s10107-021-01646-x

[11] [11]

1016/j.dam.2024.11.023,doi:10.1016/J.DAM.2024.11.023

URL:https://doi.org/10. 1016/j.dam.2024.11.023,doi:10.1016/J.DAM.2024.11.023. 14 David G. Kirkpatrick and Pavol Hell. On the complexity of general graph factor problems. SIAM J. Comput., 12(3):601–609, 1983.doi:10.1137/0212040. 15 Nimrod Megiddo and Arie Tamir. New results on the complexity of p-center problems.SIAM J. Comput., 12(4):751–758, 1983.doi:10....

work page doi:10.1016/j.dam.2024.11.023 2024

[12] [12]

Propositional truth maintenance systems: Classification and complexity analysis.Ann

18 Vladislav Rutenburg. Propositional truth maintenance systems: Classification and complexity analysis.Ann. Math. Artif. Intell., 10(3):207–232, 1993.doi:10.1007/BF01530952. 19 Alexander Schrijver et al.Combinatorial optimization: polyhedra and efficiency, volume

work page doi:10.1007/bf01530952 1993

[13] [13]

21 Arie Tamir

URL:https://doi.org/10.1287/moor.12.2.340, doi:10.1287/MOOR.12.2.340. 21 Arie Tamir. Obnoxious facility location on graphs.SIAM J. Discret. Math., 4(4):550–567, 1991.doi:10.1137/0404048

work page doi:10.1287/moor.12.2.340 1991