pith. sign in

arxiv: 2512.23989 · v2 · pith:ELM6W7JPnew · submitted 2025-12-30 · 💻 cs.DM

Secure Domination in Bisplit graphs -- A Structural and algorithmic study

Swathi D , N Sadagopan This is my paper

Pith reviewed 2026-05-25 06:59 UTC · model grok-4.3

classification 💻 cs.DM
keywords secure dominationbisplit graphsNP-completenessapproximation hardnesschain graphschordal graphsdominating sets
0
0 comments X

The pith

Secure domination is NP-complete on bisplit graphs and inapproximable within a logarithmic factor.

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

The paper studies the minimum secure domination problem, in which a dominating set must remain dominating after any single swap of a set member with a non-member. It proves that deciding whether a secure dominating set of a given size exists is NP-complete on bisplit graphs via explicit reductions. The same graphs admit no polynomial-time approximation better than (1-ε)ln|V| unless NP collapses into a specific sub-exponential class. When bisplit graphs are further restricted to be chordal, the complexity splits into polynomial or NP-complete cases according to the permitted cycle lengths; the problem becomes polynomial-time solvable on the subclass of chain graphs.

Core claim

The decision version of the secure domination problem is NP-complete on bisplit graphs. Moreover, the problem cannot be approximated within a factor of (1-ε)ln|V| for any ε>0 unless NP ⊆ DTIME(|V|^O(log log |V|)). The problem is polynomial-time solvable on chain graphs, and its complexity on chordal bisplit graphs depends on the allowed cycle lengths.

What carries the argument

Explicit polynomial-time reductions from known NP-complete problems onto secure domination instances restricted to bisplit graphs, together with dynamic-programming recurrences that exploit the bipartition and chain structure of the target classes.

If this is right

  • Secure domination cannot be solved in polynomial time on general bisplit graphs unless P=NP.
  • No polynomial-time algorithm can approximate the secure domination number of a bisplit graph within (1-ε)ln n for any ε>0, under the stated complexity assumption.
  • Secure domination admits an efficient algorithm on every chain graph.
  • On chordal bisplit graphs the problem is polynomial-time solvable exactly when the graphs forbid cycles of certain lengths.

Where Pith is reading between the lines

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

  • The same reduction technique may extend hardness to other split-graph subclasses that contain bisplit graphs as an induced subclass.
  • Chordality interacts with domination parameters by eliminating long induced cycles that encode the hard instances.
  • Similar P-versus-NP-C dichotomies could be sought for other secure-domination variants on the same graph families.

Load-bearing premise

The precise structural definition of bisplit graphs permits the claimed reductions and the dynamic-programming recurrences without the constructions violating the graph class or the domination condition.

What would settle it

A polynomial-time algorithm that computes a minimum secure dominating set on an arbitrary bisplit graph, or a polynomial-time approximation algorithm achieving ratio better than (1-ε)ln n for some ε>0, would falsify the respective claims.

Figures

Figures reproduced from arXiv: 2512.23989 by N Sadagopan, Swathi D.

Figure 1
Figure 1. Figure 1: DD in split ≤p SDD in split k1 k2 k3 k4 kn . . . x Associated star (a) star convexity on K i2 i3 i4 i5 in i1 y . . . Associated star (b) star convexity on I i2 i1 i3 i4 in−1 in y . . . Associated comb (c) comb convexity on I [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convexity on Split graphs Claim 1.1. G∗ is a star-convex split graph with convexity on K∗ . Proof. We show that G∗ is a star-convex split graph by defining an imaginary star S on K∗ . Note that for each u ∈ I ∗ its neighbourhood NG(u) contains x. There exist an associated star S on vertices of K∗ with x as root and other vertices of K say k1, k2, . . . kn as leaves as shown in Figure 2a. Therefore, for eac… view at source ↗
Figure 3
Figure 3. Figure 3: DD in bisplit ≤p SDD in bisplit Proof. Yes instance of DD in G maps to Yes instance of SDD in G*: Let G have a domination set D of size atmost k. We shall prove that G∗ has a secure dominating set D∗ with |D∗ | ≤ k ∗ = k + 2. Consider D∗ = D ∪ {y, z}. Clearly D∗ is a dominating set as {y, z} dominates all vertices of G∗ (by construction). Now we need to show D∗ is a secure dominating set of G∗ . That is, w… view at source ↗
Figure 4
Figure 4. Figure 4: Structures associated with the vertex y1 7 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: SDD in chordal bipartite ≤p SDD in chordal bipartite bisplit Claim 6.1. G′ is a bipartite bisplit graph. Proof. We first show that G′ = X′ ∪ Y ′ ∪ Z ′ is a bisplit graph where X, Y and Z are three stable sets and Y ∪ Z forms a biclique. By our construction, X1 ∪ X2 induces a biclique. Also, no two vertices of Y1 ∪ Y2 are adjacent; hence it induces and independent set. Therefore, the graph G′ = X′ ∪ Y ′ ∪ Z… view at source ↗
read the original abstract

A dominating set $S$ of a graph $G(V,E)$ is called a \textit{secure dominating set} if each vertex $u \in V(G) \setminus S$ is adjacent to a vertex $v \in S$ such that $(S \setminus \{v\}) \cup \{u\}$ is a dominating set of $G$. The \textit{secure domination number} $\gamma_s(G)$ of $G$ is the minimum cardinality of a secure dominating set of $G$. The \textit{Minimum Secure Domination problem} is to find a secure dominating set of a graph $G$ of cardinality $\gamma_s(G)$. In this paper, the computational complexity of the secure domination problem on several graph classes is investigated. The decision version of secure domination problem was shown to be NP-complete on star(comb) convex split graphs and bisplit graphs. So we further focus on complexity analysis of secure domination problem under additional structural restrictions on bisplit graphs. In particular, by imposing chordality as a parameter, we analyse its impact on the computational status of the problem on bisplit graphs. We establish the P versus NP-C dichotomy status of secure domination problem under restrictions on cycle length within bisplit graphs. In addition, we establish that the problem is polynomial-time solvable in chain graphs. We also prove that the secure domination problem cannot be approximated for a bisplit graph within a factor of $(1-\epsilon)~ln~|V|$ for any $\epsilon > 0$, unless $NP \subseteq DTIME(|V|^{O(log~log~|V|)})$.

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 investigates the Minimum Secure Domination problem. It establishes that the decision version is NP-complete on bisplit graphs (and on star(comb) convex split graphs), proves a P versus NP-complete dichotomy for the problem on bisplit graphs when chordality or bounds on cycle lengths are imposed, gives a polynomial-time algorithm when the input is restricted to chain graphs, and shows that the problem cannot be approximated within a factor of (1-ε)ln|V| on bisplit graphs unless NP ⊆ DTIME(|V|^O(log log |V|)).

Significance. If the reductions and dynamic-programming procedures are correct, the results supply a fine-grained complexity classification of secure domination on bisplit graphs and their subclasses, including explicit tractability boundaries under chordality and cycle-length restrictions. The polynomial-time result on chain graphs and the inapproximability threshold are concrete contributions to the literature on domination variants in structured graph families.

major comments (2)
  1. [reduction sections (NP-completeness and inapproximability)] The NP-completeness and inapproximability reductions on bisplit graphs (the sections presenting the reductions from a known hard problem such as dominating set or set cover) must be checked to confirm that every constructed graph admits a partition into a clique K and independent set I satisfying the precise bisplit edge conditions defined in the structural preliminaries. If any output graph violates the bisplit characterization while the secure-domination equivalence is claimed, both the NP-completeness and the (1-ε)ln n hardness statements collapse.
  2. [dichotomy section] The claimed P versus NP-complete dichotomy under chordality and cycle-length restrictions on bisplit graphs relies on the additional structural constraints permitting either a polynomial dynamic program or a hardness reduction; the manuscript must exhibit an explicit recurrence or reduction that respects the bisplit partition for each case in the dichotomy.
minor comments (2)
  1. [abstract / preliminaries] The abstract refers to 'star(comb) convex split graphs' without a definition or citation; a brief structural definition or reference should be supplied in the preliminaries.
  2. [introduction] Notation for the secure domination number γ_s(G) and the decision problem should be introduced consistently before the complexity statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive comments on our manuscript. We address each major comment point by point below, providing clarifications on the reductions and dichotomy while committing to revisions where they strengthen the presentation.

read point-by-point responses

  1. Referee: [reduction sections (NP-completeness and inapproximability)] The NP-completeness and inapproximability reductions on bisplit graphs (the sections presenting the reductions from a known hard problem such as dominating set or set cover) must be checked to confirm that every constructed graph admits a partition into a clique K and independent set I satisfying the precise bisplit edge conditions defined in the structural preliminaries. If any output graph violates the bisplit characterization while the secure-domination equivalence is claimed, both the NP-completeness and the (1-ε)ln n hardness statements collapse.

    Authors: In the NP-completeness reduction from Dominating Set and the inapproximability reduction from Set Cover, each constructed graph is defined with an explicit partition: K is formed as the union of a clique on selected original vertices plus auxiliary vertices ensuring completeness within K, while I consists of the remaining vertices with no edges inside I. All cross edges between K and I are added or omitted exactly according to the bisplit definition (complete bipartite connections where required by the original instance). The correctness proofs verify that this partition satisfies the bisplit edge conditions and that secure domination numbers are preserved. We will insert an explicit verification paragraph immediately after each construction to restate the partition and confirm the edge conditions hold. revision: yes

  2. Referee: [dichotomy section] The claimed P versus NP-complete dichotomy under chordality and cycle-length restrictions on bisplit graphs relies on the additional structural constraints permitting either a polynomial dynamic program or a hardness reduction; the manuscript must exhibit an explicit recurrence or reduction that respects the bisplit partition for each case in the dichotomy.

    Authors: The P/NP-C cases are separated by whether the bisplit graph is chordal or has bounded cycle length. For polynomial cases we give DP whose states are subsets of K (the clique) and I (the independent set), with recurrences that exploit the fact that every vertex in I is adjacent to all or none of a given subset of K; the base cases and transitions are written explicitly in terms of this partition. For the NP-complete cases the reductions are modified to output only bisplit graphs obeying the chordality or cycle-length bound while preserving the partition. The manuscript already contains these recurrences and adapted reductions; however, we will add a short clarifying subsection that tabulates, for each dichotomy case, the precise recurrence (or reduction) and how it operates on the fixed K-I partition. revision: partial

Circularity Check

0 steps flagged

No circularity: standard reductions and structural restrictions establish complexity results independently

full rationale

The paper's claims rest on reductions from known NP-complete problems (such as dominating set) to bisplit graphs while preserving the clique-independent set partition and additional constraints, plus dynamic programming on further restricted subclasses like chain graphs. These are external constructions that do not define the secure domination number in terms of itself or rename fitted parameters as predictions. The mention of prior NP-completeness on bisplit graphs is a citation to an independent result rather than a load-bearing self-reference that collapses the new dichotomy or inapproximability proofs. No self-definitional equations, ansatz smuggling, or uniqueness theorems imported from the authors' own unverified work appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definitions of dominating sets, secure dominating sets, bisplit graphs, chain graphs, and chordal graphs; no free parameters, ad-hoc axioms, or invented entities appear in the abstract.

axioms (2)
  • standard math Standard definitions and basic properties of dominating sets and secure dominating sets in undirected graphs.
    The entire study is built on these established graph-theoretic notions.
  • domain assumption The structural partition that defines bisplit graphs and chain graphs.
    All complexity claims are conditioned on these graph classes.

pith-pipeline@v0.9.0 · 5823 in / 1387 out tokens · 29218 ms · 2026-05-25T06:59:46.891704+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

20 extracted references · 20 canonical work pages

  1. [1]

    Protection of a graph,

    E. Cockayne, P. Grobler, W. Grundlingh, J. Munganga, and J. van Vuuren, “Protection of a graph,”Util. Math., vol. 67, pp. 19–32, 2005

    work page 2005

  2. [2]

    On minimum secure dominating sets of graphs,

    A. Burger, A. de Villiers, and J. van Vuuren and, “On minimum secure dominating sets of graphs,” Quaestiones Mathematicae, vol. 39, no. 2, pp. 189–202, 2016

    work page 2016

  3. [3]

    Vertex covers and secure domination in graphs,

    A. Burger, M. Henning, and J. Vuuren, “Vertex covers and secure domination in graphs,”Quaestiones Mathematicae, vol. June 2008, pp. 163–171, 11 2009

    work page 2008

  4. [4]

    On secure domination in trees,

    Z. Li, Z. Shao, and J. Xu, “On secure domination in trees,”Quaest. Math., vol. 40, pp. 1–12, 2017

    work page 2017

  5. [5]

    On secure domination in graphs,

    H. B. Merouane and M. Chellali, “On secure domination in graphs,”Inform. Process. Lett., vol. 115, pp. 786–790, 2015

    work page 2015

  6. [6]

    Secure total domination number in maximal outerplanar graphs,

    Y. Aita and T. Araki, “Secure total domination number in maximal outerplanar graphs,”Discrete Applied Mathematics, vol. 353, pp. 65–70, 2024

    work page 2024

  7. [7]

    On the secure domination numbers of maximal outerplanar graphs,

    T. Araki and I. Yumoto, “On the secure domination numbers of maximal outerplanar graphs,”Discrete Applied Mathematics, vol. 236, pp. 23–29, 2018

    work page 2018

  8. [8]

    The complexity of secure domination problem in graphs,

    H. Wang, Y. Zhao, and Y. Deng, “The complexity of secure domination problem in graphs,”Discuss. Math. Graph Theory, vol. 38, pp. 385–396, 2018

    work page 2018

  9. [9]

    On computing a minimum secure dominating set in block graphs,

    D. Pradhan and A. Jha, “On computing a minimum secure dominating set in block graphs,”J. Comb. Optim., vol. 35, pp. 613–631, 2018

    work page 2018

  10. [10]

    A linear algorithm for secure domination in trees,

    A. Burger, A. de Villiers, and J. van Vuuren, “A linear algorithm for secure domination in trees,”Discrete Appl. Math., vol. 171, pp. 15–27, 2014

    work page 2014

  11. [11]

    Secure domination in proper interval graphs,

    T. Araki and H. Miyazaki, “Secure domination in proper interval graphs,”Discrete Appl. Math., vol. 247, pp. 70–76, 2018

    work page 2018

  12. [12]

    Correcting the algorithm for a minimum secure dominating set of proper interval graphs by zou, liu, hsu and wang,

    T. Araki and R. Saito, “Correcting the algorithm for a minimum secure dominating set of proper interval graphs by zou, liu, hsu and wang,”Discrete Applied Mathematics, vol. 334, pp. 139–144, 2023

    work page 2023

  13. [13]

    Secure domination in cographs,

    T. Araki and R. Yamanaka, “Secure domination in cographs,”Discrete Appl. Math., vol. 262, pp. 179–184, 2019

    work page 2019

  14. [14]

    Correcting the algorithm for the secure domination number of cographs by jha, pradhan, and banerjee,

    A. Kiˇ sek and S. Klavˇ zar, “Correcting the algorithm for the secure domination number of cographs by jha, pradhan, and banerjee,”Information Processing Letters, vol. 172, p. 106155, 2021

    work page 2021

  15. [15]

    Dominating sets for split and bipartite graphs,

    “Dominating sets for split and bipartite graphs,”Information Processing Letters, vol. 19, no. 1, pp. 37–40, 1984

    work page 1984

  16. [16]

    On convexity in split graphs: Complexity of steiner tree and domination,

    A. Mohanapriya, P. Renjith, and N. Sadagopan, “On convexity in split graphs: Complexity of steiner tree and domination,” 10 2022. 13

    work page 2022

  17. [17]

    Short cycles dictate dichotomy status of the steiner tree problem on bisplit graphs,

    A. Mohanapriya, P. Renjith, and N. Sadagopan, “Short cycles dictate dichotomy status of the steiner tree problem on bisplit graphs,” inAlgorithms and Discrete Applied Mathematics(A. Bagchi and R. Muthu, eds.), (Cham), pp. 219–230, Springer International Publishing, 2023

    work page 2023

  18. [18]

    Linear-time certifying recognition algorithms and forbidden induced sub- graphs,

    P. Heggernes and D. Kratsch, “Linear-time certifying recognition algorithms and forbidden induced sub- graphs,”Nordic J. of Computing, vol. 14, p. 87–108, Jan. 2007

    work page 2007

  19. [19]

    The complexity of secure domination problem in graphs,

    Y.-P. Deng, H. Wang, and Y. Zhao, “The complexity of secure domination problem in graphs,”Discussiones Mathematicae Graph Theory, vol. 38, p. 385, 01 2018

    work page 2018

  20. [20]

    The monadic second-order logic of graphs. i. recognizable sets of finite graphs,

    B. Courcelle, “The monadic second-order logic of graphs. i. recognizable sets of finite graphs,”Information and Computation, vol. 85, no. 1, pp. 12–75, 1990. 14

    work page 1990