Domination above r-independence: does sparseness help?

Carl Einarson; Felix Reidl

arxiv: 1906.09180 · v1 · pith:FBRV4OH5new · submitted 2019-06-21 · 💻 cs.DS

Domination above r-independence: does sparseness help?

Carl Einarson , Felix Reidl This is my paper

Pith reviewed 2026-05-25 18:44 UTC · model grok-4.3

classification 💻 cs.DS

keywords dominating setr-independent setnowhere dense graphsbounded expansionfixed-parameter tractabilitykernelizationabove-guarantee parameterizationresidual parameter

0 comments

The pith

A maximal 3-independent set makes the dominating set problem FPT on nowhere dense graphs when parametrized by uncovered vertices.

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

The paper studies dominating set when the input includes a maximal r-independent set X that lower-bounds the solution size for r at least 2. It parametrizes the problem by the number of vertices outside the closed neighborhood of X. Results show that r equals 2 leaves the problem paraNP-complete even on apex and bounded-degree graphs, r equals 3 yields W[2]-hardness in general graphs yet FPT algorithms on nowhere dense classes plus linear kernels on bounded expansion classes, and r at least 4 collapses the parameter to the standard dominating set size.

Core claim

When a maximal 3-independent set X is supplied, dominating set parametrized by the size of the residual set R equals V(G) minus N[X] is W[2]-hard on general graphs, fixed-parameter tractable on nowhere dense graphs, and admits a linear kernel on bounded expansion graphs.

What carries the argument

The residual set R equals V(G) minus the closed neighborhood of a given maximal r-independent set X, which serves as the above-guarantee parameter measuring vertices not covered by the lower-bound witness.

If this is right

For r equals 3 the problem admits algorithms whose runtime depends only on the residual size on nowhere dense graphs.
Linear kernels exist for the r equals 3 case on bounded expansion graphs.
For r equals 2 no FPT algorithm exists on bounded-degree or apex graphs unless P equals NP.
For r at least 4 the above-guarantee parameter offers no additional power beyond the ordinary dominating-set parameter.

Where Pith is reading between the lines

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

The value of r appears to control how much the independent-set witness separates the lower bound from the actual solution size, interacting differently with sparsity.
Similar residual parameters might be tested on other domination-like problems restricted to sparse graph classes.
The separation between r equals 2 and r equals 3 suggests that small changes in the independence distance can shift a problem from intractable to tractable under sparsity assumptions.

Load-bearing premise

The input set X must be a maximal r-independent set that actually lower-bounds every dominating set of the graph.

What would settle it

An FPT algorithm for the r equals 3 case running in f of |R| times n to the c time on general graphs would contradict the stated W[2]-hardness.

read the original abstract

Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maximal r-independent set X (a set in which all vertices have pairwise distance at least r + 1) along the input graph G which, for r >= 2, lower-bounds the minimum size of any dominating set of G. In the spirit of gap-parameters, we consider a parametrisation by the size of the 'residual' set R := V (G) \ N [X]. Our work aims to answer two questions: How does the constant r affect the tractability of the problem and does the restriction to sparse graph classes help here? For the base case r = 2, we find that the problem is paraNP -complete even in apex- and bounded-degree graphs. For r = 3, the problem is W[2]-hard for general graphs but in FPT for nowhere dense classes and it admits a linear kernel for bounded expansion classes. For r >= 4, the parametrisation becomes essentially equivalent to the natural parameter, the size of the dominating set.

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 maps clean complexity thresholds for this gap parameterization of dominating set, with sparsity helping only at r=3.

read the letter

The main point is that this above-guarantee version of dominating set splits neatly by the choice of r: r=2 is already paraNP-complete even on apex and bounded-degree graphs, r=3 is W[2]-hard in general but FPT on nowhere dense graphs with a linear kernel on bounded expansion, and r>=4 collapses back to the usual solution-size parameterization. These thresholds are new and the matching positive and negative results on the sparse classes are the useful part of the work. The lower-bound property of the maximal r-independent set holds for r>=2 by the distance condition, so the setup is internally consistent. The techniques are standard parameterized reductions and the known meta-algorithms for nowhere dense and bounded expansion classes, which is appropriate here. The r>=4 equivalence is essentially immediate once neighborhoods overlap enough, so it functions more as an observation than a heavy lift. No load-bearing gaps appear in the high-level claims. This is a narrow but solid incremental result for people who track gap parameters or domination on sparse graphs. It is worth sending to peer review because the distinctions by r and by sparsity regime are precise enough to document.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the parameterized complexity of Dominating Set given a maximal r-independent set X as input, parameterized by the size of the residual set R = V(G) minus the closed 1-neighborhood of X. For r=2 the problem is shown to be paraNP-complete even on apex graphs and bounded-degree graphs. For r=3 it is W[2]-hard on general graphs, FPT on nowhere dense classes, and admits a linear kernel on bounded-expansion classes. For r>=4 the parameterization is equivalent to the standard solution-size parameterization.

Significance. If the stated complexity classifications hold, the work clarifies how the constant r modulates tractability under an above-guarantee parameterization and demonstrates that sparseness (nowhere dense / bounded expansion) yields algorithmic improvements only for specific small values of r. The results rely on standard parameterized reductions and kernelization techniques for sparse graphs; no machine-checked proofs or parameter-free derivations are claimed.

minor comments (2)

[Abstract] Abstract, opening paragraph: the sentence defining R contains an extraneous space (V (G)); this is a minor typographical issue but should be corrected for clarity.
[Abstract] Abstract: the claim that the parameterization 'becomes essentially equivalent' for r>=4 would benefit from a one-sentence justification (e.g., a short reduction showing |R| is bounded by a function of the domination number) even if the full argument appears later.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. The report accurately summarizes the main results of the manuscript. No specific major comments or requests for changes were raised.

Circularity Check

0 steps flagged

No significant circularity; results rely on standard parameterized reductions

full rationale

The paper defines the problem directly as Dominating Set parameterized by |R| where R = V(G) minus N[X] and X is a given maximal r-independent set. The lower-bound |X| <= gamma(G) for r >= 2 follows immediately from the definition of r-independence (pairwise distances >= r+1 imply disjoint closed neighborhoods), which is a basic graph-theoretic observation stated in the abstract and not derived from any fitted quantity or self-citation. All complexity claims (paraNP-completeness for r=2, W[2]-hardness/FPT/kernel results for r=3, equivalence for r>=4) are obtained via explicit reductions and algorithms on the stated graph classes; no step renames a fitted input as a prediction, imports uniqueness via self-citation, or reduces a central claim to a tautology by construction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions from graph theory and parameterized complexity theory; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)

standard math Standard definitions of dominating set, r-independent set, maximal independent set, and the parameterized complexity classes FPT, W[2], paraNP-complete.
Invoked to state the problem and the complexity claims throughout the abstract.

pith-pipeline@v0.9.0 · 5743 in / 1235 out tokens · 25441 ms · 2026-05-25T18:44:17.559456+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For r = 3, the problem is W[2]-hard for general graphs but in FPT for nowhere dense classes and it admits a linear kernel for bounded expansion classes.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We consider being provided with a maximal r-independent set X ... parametrisation by the size of the 'residual' set R := V(G) minus N[X].

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

28 extracted references · 28 canonical work pages · 1 internal anchor

[1]

Alber, H

J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica , 33(4):461--493, 2002

work page 2002
[2]

Alber, M

J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for Dominating Set . JACM , 51:363--384, 2004

work page 2004
[3]

N. Alon, G. Gutin, E. Jung Kim, S. Szeider, and A. Yeo. Solving max-r-sat above a tight lower bound. Algorithmica , 61(3):638--655, 2011

work page 2011
[4]

Alon and S

N. Alon and S. Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica , 54(4):544--556, 2009

work page 2009
[5]

Cygan, M

M. Cygan, M. Pilipczuk, M. Pilipczuk, and J.O. Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT , 5(1):3, 2013

work page 2013
[6]

Drange, M

P.G. Drange, M. Sortland Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S \' a nchez Villaamil , S. Saurabh, S. Siebertz, and S. Sikdar. Kernelization and sparseness: the case of dominating set. In STACS , volume 47 of LIPIcs , pages 31:1--31:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016

work page 2016
[7]

On distance r-dominating and 2r-independent sets in sparse graphs

Z. . On distance r -dominating and 2r -independent sets in sparse graphs. CoRR , abs/1710.10010, 2017. http://arxiv.org/abs/1710.10010 arXiv:1710.10010

work page internal anchor Pith review Pith/arXiv arXiv 2017
[8]

Testing first-order properties for subclasses of sparse graphs

Zdenek Dvorak, Daniel Kr \' a l, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. volume 60, pages 36:1--36:24, 2013

work page 2013
[9]

Eickmeyer, A

K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , pages 63:1--63:14, 2017

work page 2017
[10]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and kernels. In 21st , pages 503--510. SIAM, 2010

work page 2010
[11]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Linear kernels for (connected) dominating set on H-minor-free graphs. In 23rd , pages 82--93. SIAM, 2012

work page 2012
[12]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In 30th , volume 20 of , pages 92--103. , 2013

work page 2013
[13]

J. , P. , J. , S. Ordyniak, F. Reidl, P. Rossmanith, F. Villaamil , and S. Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. , 84:219--242, 2017

work page 2017
[14]

Grohe, S

M. Grohe, S. Kreutzer, and Siebertz S. Deciding first-order properties of nowhere dense graphs. J. ACM , 64(3):17:1--17:32, 2017

work page 2017
[15]

Gutin, E.J

G. Gutin, E.J. Kim, M. Lampis, and V. Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory of Computing Systems , 48(2):402--410, 2011

work page 2011
[16]

Gutin, E.J

G. Gutin, E.J. Kim, M. Mnich, and A. Yeo. Betweenness parameterized above tight lower bound. Journal of Computer and System Sciences , 76(8):872--878, 2010

work page 2010
[17]

Gutin, A

G. Gutin, A. Rafiey, S. Szeider, and A. Yeo. The linear arrangement problem parameterized above guaranteed value. Theory of Computing Systems , 41(3):521--538, 2007

work page 2007
[18]

Gutin, L

G. Gutin, L. van Iersel , M. Mnich, and A. Yeo. All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables. In Proc. of the 18th ESA , volume 6346 of Lecture Notes in Computer Science , pages 326--337. Springer, 2010

work page 2010
[19]

Habib, C

M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. In 25th , volume 08001 of , pages 25--38. , 2008

work page 2008
[20]

Lichtenstein

D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput. , 11(2):329--343, 1982

work page 1982
[21]

Lokshtanov, NS Narayanaswamy, V

D. Lokshtanov, NS Narayanaswamy, V. Raman, MS Ramanujan, and S. Saurabh. Faster parameterized algorithms using linear programming. TALG , 11(2):15, 2014

work page 2014
[22]

Mahajan and V

M. Mahajan and V. Raman. Parameterizing above guaranteed values: MaxSat and MaxCut . Journal of Algorithms , 31(2):335--354, 1999

work page 1999
[23]

Mahajan, V

M. Mahajan, V. Raman, and S. Sikdar. Parameterizing above or below guaranteed values. Journal of Computer and System Sciences , 75(2):137--153, 2009

work page 2009
[24]

J. and P. Ossona de Mendez . Sparsity: Graphs, Structures, and Algorithms , volume 28 of Algorithms and Combinatorics . Springer, 2012

work page 2012
[25]

Philip, V

G. Philip, V. Raman, and S. Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms , 9(1), 2012

work page 2012
[26]

F. Reidl. S tructural sparseness and complex networks . Dr., A achen, Techn. Hochsch., A achen, 2016. A achen, Techn. Hochsch., Diss., 2015

work page 2016
[27]

C. A. Tovey. A simplified NP -complete satisfiability problem. Discrete Applied Mathematics , 8(1):85--89, 1984

work page 1984
[28]

write newline

" write newline "" before.all 'output.state := FUNCTION fin.entry.original add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 i...

work page

[1] [1]

Alber, H

J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica , 33(4):461--493, 2002

work page 2002

[2] [2]

Alber, M

J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for Dominating Set . JACM , 51:363--384, 2004

work page 2004

[3] [3]

N. Alon, G. Gutin, E. Jung Kim, S. Szeider, and A. Yeo. Solving max-r-sat above a tight lower bound. Algorithmica , 61(3):638--655, 2011

work page 2011

[4] [4]

Alon and S

N. Alon and S. Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica , 54(4):544--556, 2009

work page 2009

[5] [5]

Cygan, M

M. Cygan, M. Pilipczuk, M. Pilipczuk, and J.O. Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT , 5(1):3, 2013

work page 2013

[6] [6]

Drange, M

P.G. Drange, M. Sortland Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S \' a nchez Villaamil , S. Saurabh, S. Siebertz, and S. Sikdar. Kernelization and sparseness: the case of dominating set. In STACS , volume 47 of LIPIcs , pages 31:1--31:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016

work page 2016

[7] [7]

On distance r-dominating and 2r-independent sets in sparse graphs

Z. . On distance r -dominating and 2r -independent sets in sparse graphs. CoRR , abs/1710.10010, 2017. http://arxiv.org/abs/1710.10010 arXiv:1710.10010

work page internal anchor Pith review Pith/arXiv arXiv 2017

[8] [8]

Testing first-order properties for subclasses of sparse graphs

Zdenek Dvorak, Daniel Kr \' a l, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. volume 60, pages 36:1--36:24, 2013

work page 2013

[9] [9]

Eickmeyer, A

K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , pages 63:1--63:14, 2017

work page 2017

[10] [10]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and kernels. In 21st , pages 503--510. SIAM, 2010

work page 2010

[11] [11]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Linear kernels for (connected) dominating set on H-minor-free graphs. In 23rd , pages 82--93. SIAM, 2012

work page 2012

[12] [12]

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In 30th , volume 20 of , pages 92--103. , 2013

work page 2013

[13] [13]

J. , P. , J. , S. Ordyniak, F. Reidl, P. Rossmanith, F. Villaamil , and S. Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. , 84:219--242, 2017

work page 2017

[14] [14]

Grohe, S

M. Grohe, S. Kreutzer, and Siebertz S. Deciding first-order properties of nowhere dense graphs. J. ACM , 64(3):17:1--17:32, 2017

work page 2017

[15] [15]

Gutin, E.J

G. Gutin, E.J. Kim, M. Lampis, and V. Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory of Computing Systems , 48(2):402--410, 2011

work page 2011

[16] [16]

Gutin, E.J

G. Gutin, E.J. Kim, M. Mnich, and A. Yeo. Betweenness parameterized above tight lower bound. Journal of Computer and System Sciences , 76(8):872--878, 2010

work page 2010

[17] [17]

Gutin, A

G. Gutin, A. Rafiey, S. Szeider, and A. Yeo. The linear arrangement problem parameterized above guaranteed value. Theory of Computing Systems , 41(3):521--538, 2007

work page 2007

[18] [18]

Gutin, L

G. Gutin, L. van Iersel , M. Mnich, and A. Yeo. All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables. In Proc. of the 18th ESA , volume 6346 of Lecture Notes in Computer Science , pages 326--337. Springer, 2010

work page 2010

[19] [19]

Habib, C

M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. In 25th , volume 08001 of , pages 25--38. , 2008

work page 2008

[20] [20]

Lichtenstein

D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput. , 11(2):329--343, 1982

work page 1982

[21] [21]

Lokshtanov, NS Narayanaswamy, V

D. Lokshtanov, NS Narayanaswamy, V. Raman, MS Ramanujan, and S. Saurabh. Faster parameterized algorithms using linear programming. TALG , 11(2):15, 2014

work page 2014

[22] [22]

Mahajan and V

M. Mahajan and V. Raman. Parameterizing above guaranteed values: MaxSat and MaxCut . Journal of Algorithms , 31(2):335--354, 1999

work page 1999

[23] [23]

Mahajan, V

M. Mahajan, V. Raman, and S. Sikdar. Parameterizing above or below guaranteed values. Journal of Computer and System Sciences , 75(2):137--153, 2009

work page 2009

[24] [24]

J. and P. Ossona de Mendez . Sparsity: Graphs, Structures, and Algorithms , volume 28 of Algorithms and Combinatorics . Springer, 2012

work page 2012

[25] [25]

Philip, V

G. Philip, V. Raman, and S. Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms , 9(1), 2012

work page 2012

[26] [26]

F. Reidl. S tructural sparseness and complex networks . Dr., A achen, Techn. Hochsch., A achen, 2016. A achen, Techn. Hochsch., Diss., 2015

work page 2016

[27] [27]

C. A. Tovey. A simplified NP -complete satisfiability problem. Discrete Applied Mathematics , 8(1):85--89, 1984

work page 1984

[28] [28]

write newline

" write newline "" before.all 'output.state := FUNCTION fin.entry.original add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 i...

work page