Pith. sign in

REVIEW 1 major objections 2 minor 13 references

Stable structure on safe set problems in vertex-weighted graphs

T0 review · 1 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A connected bipartite graph has stable safe sets exactly when it belongs to one of five explicit families of graphs.

desk verdict Real bipartite classification with credible proof architecture, but Lemma 3.6 contains a wrong displayed inequality that needs a one-line fix before acceptance. read the letter →

arxiv 1909.02718 v2 pith:7AF4GEL2 submitted 2019-09-06 math.CO

Shinya Fujita , Tadashi Sakuma , Boram Park This is my paper · ORCID
classification math.CO MSC 05C6905C7505C38
keywords weightedsafesetconnectednumberbipartitegraphdominatingcliqueedgecontractionchordalbook
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines the complete family of connected bipartite graphs for which the cheapest 'safe' vertex set can always be chosen connected, no matter what positive weights are assigned to the vertices. Here a set is safe if each of its components carries at least as much weight as every adjacent component outside the set. The answer is a short list of five types: even cycles, double stars, book graphs, $K_{3,3}$ with one edge deleted, and two families $D(m,n;p,q)$ and $D^*(m,n;p,q)$ built around a dominating edge. The interest is that the equality $s(G,w)=cs(G,w)$ means the protected region never has to pay an extra capacity premium for being connected; the proof manufactures separating weights from forbidden quotient shapes, then forces any minimal counterexample into the listed forms.

What carries the argument

The key object is the quotient $\beta(G,S)$, whose vertices are the components of the chosen set $S$ and of its complement $G-S$, with adjacency when components touch; Lemma 2.1 shows that if $S$ is a minimum safe set witnessing $s<cs$, then $\beta(G,S)\notin\mathcal{G}_{cs}$, so forbidden quotients propagate down to smaller graphs. The main exclusion mechanism is Lemma 3.6: any connected graph contractible to $K_{m,n}$ with $m\neq n$ and at most one connected bag of size at least two is not in $\mathcal{G}_{cs}$, because one can weigh the two sides so that every cheap safe set must split across them. Corollary 3.8 turns this into a local obstruction: a high-degree vertex whose neighborhood is independent, whose neighbors all have degree at least two, and whose closed neighborhood does not disconnect the graph forces $G\notin\mathcal{G}_{cs}$. The rest of the proof shows that a minimal counterexample would have to be one of the two $D/D^*$ shapes, whose middle layer is either complete bipartite or a double star with a dominating edge, an edge whose endpoints together touch every vertex.

What would settle it

The theorem is false if any listed graph, say $K_{3,3}$ minus an edge, has a positive weight with $s<cs$, or if any unlisted connected bipartite graph has $s=cs$ for every positive weight. A direct check: with all weights equal to 1 on $K_{3,3}$ minus an edge, both numbers should be 3; and for the key lemma, search for a graph contractible to $K_{m,n}$ with $m\neq n$ and a single connected non-singleton bag that nevertheless satisfies equality on every tested weight.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.5: a connected bipartite graph $G$ lies in $\mathcal{G}_{cs}$ if and only if $G$ is one of (I) an even cycle $C_{2n}$ with $n\geq 2$; (II) a double star, meaning a tree of diameter at most three; (III) a book graph $B_n$ with $n\geq 1$; (IV) $K_{3,3}$ with one edge deleted; or (V) a graph $D(m,n;p,q)$ or $D^*(m,n;p,q)$ with $m\geq 2$, $n\neq 1$, and $p,q\geq 0$. Here $\mathcal{G}_{cs}$ is the family of graphs for which $s(G,w)=cs(G,w)$ for every positive weight function $w$. The 'if' direction verifies each listed family directly; the 'only if' direction takes a minimal counterexample and uses contraction obstructions to force its structure into exactly one of the five forms.

Load-bearing premise

The completeness proof leans on Lemma 3.6, which asserts that any graph contractible to $K_{m,n}$ with $m\neq n$ and at most one connected bag of size at least two is outside $\mathcal{G}_{cs}$; if that lemma has an exception, the list of Theorem 1.5 could be missing a graph.

Editorial extensions

If this is right

  • Every connected bipartite graph outside the five families has some positive vertex weights for which $s(G,w)<cs(G,w)$; the paper constructs those weights rather than merely asserting their existence.
  • Inside the listed families, connectivity is never a liability: for every positive $w$, some connected safe set attains the same minimum weight as the best safe set.
  • Membership in $\mathcal{G}_{cs}$ for bipartite graphs becomes decidable by checking a short list of structural conditions; the paper's companion work supplies a linear-time recognition algorithm for that list.
  • For chordal graphs, Theorem 1.3 gives the same stability exactly when a dominating clique exists, equivalently when the diameter is at most three.
  • For triangle-free graphs that are not cycles, Theorem 1.4 bounds the diameter by three, so any future search for non-bipartite examples can restrict attention to diameter three.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Going beyond the paper, a natural testable conjecture is that every graph in $\mathcal{G}_{cs}$ either contains a dominating clique or is an even cycle; the chordal and bipartite classifications both fit this pattern, and it would reduce the general problem to a finite obstruction search.
  • Read as a network statement, the theorem says that in any non-listed bipartite network an adversary can choose vertex capacities so that the cheapest safe refuge is fragmented, while a connected refuge requires strictly more capacity; this gives an exact characterization of when connectivity is free.
  • The quotient-contraction lemmas suggest a recognition strategy for the general family: look for $K_{2,3}$-like quotients with single connected bags. If the same obstruction works beyond bipartite graphs, the problem may have a finite forbidden-quotient characterization.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. The paper studies the family Gcs of connected vertex-weighted graphs for which the weighted safe number equals the connected weighted safe number for every positive weight function. The main result, Theorem 1.5, gives a complete classification of connected bipartite graphs in Gcs: even cycles, double stars, book graphs, K_{3,3} minus an edge, and the two families D(m,n;p,q) and D*(m,n;p,q). The proof strategy combines contraction lemmas (Section 3), a chordal-graph characterization (Theorem 1.3), structural analysis of bipartite graphs with dominating edges (Section 4), and a minimal-counterexample argument (Section 5.2).

Significance. If correct, Theorem 1.5 settles the bipartite case of Problem 1.1 raised in [7] and provides a finite, checkable list with a clean structural description. The paper additionally proves Theorem 1.3 for chordal graphs and Theorem 1.4 for triangle-free graphs, and it carefully states its dependence on published results such as [10] and [12]. The contraction-based method is natural for the problem, and the overall proof is organized and detailed. A repaired proof of Lemma 3.6 would make the classification a substantial contribution to the safe-set literature, potentially useful for algorithmic work on connected safe sets.

major comments (1)
  1. [Section 3.2, proof of Lemma 3.6, after Claim 3.7] The displayed inequality w(S) >= w((X'∪Y)\S) >= w(X'∪Y) - w(S) = alpha(m+n-1) - epsilon(|Z|-1) - w(S) is algebraically incorrect. Since w(X'∪Y) = alpha(m+n-1), the final equality wrongly subtracts epsilon(|Z|-1); the correct identity is w((X'∪Y)\S) = alpha(m+n-1) - w(S) + w(S∩Z), because S may contain vertices of Z. In the case under consideration, the assumption that (X'∪{z}∪Y)\S is not contained in one component forces S∩Z ≠ ∅, so substituting the correct identity gives 2w(S) >= alpha(m+n-1) + w(S∩Z) > alpha(m+n-1), which already contradicts w(S) <= alpha min{m,n} for every m ≠ n. Thus the conclusion of Lemma 3.6 is valid, but the printed argument for |m-n| >= 2 is incomplete. Since Lemma 3.6 powers Corollary 3.8 and is applied repeatedly in the minimal-counterexample proof of Theorem 1.5 in Section 5.2, this gap must be repaired in the final version.
minor comments (2)
  1. [Section 1, definition of cs] In the sentence defining a minimum connected weighted safe set, "w(S) = (G,w)" should read "w(S) = cs(G,w)".
  2. [Section 5.2, Case |X|=2] The phrase "such all pendant vertices in Y" is grammatically awkward; it should be "all such pendant vertices in Y".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from internal lemmas and independent published results.

full rationale

The paper does not fit parameters and rename them as predictions. The only-if direction of Theorem 1.5 is obtained by a minimal-counterexample argument relying on internally proved contraction lemmas (Lemmas 3.1–3.3 and 3.6), Propositions 2.4 and 2.5, Lemma 4.1, and the structural claims in Section 5; the if-direction checks the listed graphs using Theorem 1.2, Corollary 4.4, Proposition 4.5, and Proposition 4.6. The citations to [10] and [12] are external published theorems, and the citation to [7] supplies the problem formulation and the already-published cycle result, not the bipartite classification itself; [9] is a companion manuscript not used in any proof. No equation is definitionally equal to its conclusion, and no self-citation chain forces the list. A possible algebraic slip in the proof of Lemma 3.6 (the extra -epsilon(|Z|-1) term in the second case) is a correctness concern, not circularity, and does not change this verdict.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; the integers m,n,p,q in the graph families D and D* are structural parameters in the definition, not fitted values. No new physical or mathematical entities are postulated: D and D* are explicit graph constructions. The axioms used are standard finite-graph theory plus three published results: the cycle membership theorem from [7], the chordal-contraction theorem of [10], and the dominating-clique characterization of [12]. Proposition 2.4, which extends the family to nonnegative weights, is proved within the paper.

assumptions (4)
  • standard math Every connected chordal graph can be contracted to a path of length diam(G) so that each bag is connected (Theorem 4.2 of [10]).
    Invoked in the proof of Theorem 1.3 to show that chordal graphs with diameter at least 4 are not in Gcs.
  • standard math A connected chordal graph has a dominating clique if and only if its diameter is at most 3 (Theorem 4.3 of [12]).
    Used in the proof of Theorem 1.3 to connect the dominating-clique condition to diameter, and thus to membership in Gcs.
  • standard math The weighted safe number of a cycle equals its connected weighted safe number (Theorem 1.2 of [7]).
    Used in the 'if' direction of the main theorem to include even cycles in Gcs and in Claim 4.7 to identify C4 and other cycle-based graphs.
  • standard math Finite simple graph theory: standard terminology, positive real weights, and the ZFC background for graph-theoretic arguments.
    Basis for all proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stable structure on safe set problems in vertex-weighted graphs." pith.science (2026). https://pith.science/paper/7AF4GEL2

@misc{pith2026190902718,
  author       = {Pith},
  title        = {Pith review of: Stable structure on safe set problems in vertex-weighted graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7AF4GEL2}},
  note         = {Machine review of arXiv:1909.02718}
}
abstract

Let $G$ be a graph, and let $w$ be a positive real-valued weight function on $V(G)$. For every subset $S$ of $V(G)$, let $w(S)=\sum_{v \in S} w(v).$ A non-empty subset $S \subset V(G)$ is a weighted safe set of $(G,w)$ if, for every component $C$ of the subgraph induced by $S$ and every component $D$ of $G-S$, we have $w(C) \geq w(D)$ whenever there is an edge between $C$ and $D$. If the subgraph of $G$ induced by a weighted safe set $S$ is connected, then the set $S$ is called a connected weighted safe set of $(G,w)$. The weighted safe number $\mathrm{s}(G,w)$ and connected weighted safe number $\mathrm{cs}(G,w)$ of $(G,w)$ are the minimum weights $w(S)$ among all weighted safe sets and all connected weighted safe sets of $(G,w)$, respectively. Note that for every pair $(G,w)$, $\mathrm{s}(G,w) \le \mathrm{cs}(G,w)$ by their definitions. Recently, it was asked which pair $(G,w)$ satisfies the equality and shown that every weighted cycle satisfies the equality. In this paper, we give a complete list of connected bipartite graphs $G$ such that $\mathrm{s}(G,w)=\mathrm{cs}(G,w)$ for every weight function $w$ on $V(G)$.

Figures

Figures reproduced from arXiv: 1909.02718 by the authors.

Figure 1
Figure 1. Examples of graphs D(m, n; p, q) or D∗ (m, n; p, q). B2 B3 B4 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Examples of book graphs. (III) a book graph Bn with n ≥ 1; (IV) a graph obtained from K3,3 by deleting an edge; (V) D(m, n; p, q) or D∗ (m, n; p, q), with m ≥ 2, n 6= 1 and p, q ≥ 0, From our main theorem, we see that if a bipartite graph G belongs to G cs, then G is an even cycle or G has a dominating edge. When considering a safe set S of a graph G, note that we always observe the bipartite structure between G[S] … view at source ↗
Figure 3
Figure 3. An example of β(G, S). Lemma 2.1. Let G be a connected graph not in G cs. If S is a minimum safe set of (G, w) for some weight function w on V (G) such that s(G, w) < cs(G, w), then β(G, S) 6∈ Gcs . Proof. Let β := β(G, S) and let wβ be a weight function on V (β) defined by wβ(D) := w(D) for each vertex D of β. Let S be the set of the components of G[S]. Then clearly, S is a safe set of (β, wβ), and therefore, s(β, … view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: All subgraphs of K2,3 not in G cs . Here are several assumptions and common notation throughout this sub￾section (in Lemmas 3.1 - 3.3). We assume that G is a connected graph which is contractible to Hi for some i ∈ {1, 2, 3}, and let Vj be the bag correspond￾ing to uj …
Figure 5
Figure 5. Figure 5: K3,3 − e, where e = x1y3. a dominating edge, we may assume that x2, x3 ∈ S and y1, y2 6∈ S by Lemma 4.1 (i). If y3 ∈ S, then, for G[S] being disconnected, x1 ∈ S and so S = {x1, x2, x3, y3}, which implies that β(G, S) is a cycle of length four and so β ∈ Gcs by Theorem…
Figure 6
Figure 6. Figure 6: A graph G, where G[X2 ∪ Y1] induces either Kn+1,m+1 or a double star. Claim 4.8. It holds that β = G. Proof. Note that m ≥ 2 by Claim 4.7 and so one of (a) or (b) holds. Suppose that β 6= G. First we claim that some edge of G0 is contracted to obtain β. If not, then β …
Figure 7
Figure 7. Figure 7: An illustration for the proof of Subclaim 4.9 (ii). [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: An illustration for (Case 1) of Claim 5.2. [PITH_FULL_IMAGE:figures/full_fig_p027_8.png]
Figure 9
Figure 9. Figure 9: An illustration for (Case 2) of Claim 5.2. [PITH_FULL_IMAGE:figures/full_fig_p028_9.png]
Figure 10
Figure 10. Figure 10: An illustration for Claim 5.4. Proof. Without loss of generality, we may assume that a = u. Let A2 = NG[u], A3 be the component of Hu such that v ∈ A3, and A1 = V (G) \ (A2 ∪ A3). Then (i) and (ii) follow immediately. We will show (iii). Take a component D of Hu other…
Figure 4
Figure 4. Figure 4: Then G 6∈ Gcs by Lemma 3.2, which is a contradiction. Secondly, suppose that Hv is disconnected. Then there is a partition {A (v) 1 , A(v) 2 , A(v) 3 } of V (G) satisfying (i)-(iii) of Claim 5.4, by applying the claim for the vertex v. Let V1 = A (u) 1 , V2 = A (u) 2 ,…
Figure 11
Figure 11. Figure 11: An illustration for (Case 1) of the proof of Theorem 1.5. [PITH_FULL_IMAGE:figures/full_fig_p034_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [7]

    Fujita S., Jensen T., Park B., and Sakuma T., On weighted safe set problem on paths and cycles, Journal of Combinatorial Optimization , 37 (2019), 685–701

    work page 2019

  2. [10]

    Heggerners P., van’t Hof P., L´ evˆ eque B., Paul C., Contracting chordal graphs and bipartite graphs to paths and trees, Discrete Applied Math- ematics, 164 (2014), 444–449

    work page 2014

  3. [12]

    Kratsch D., Damaschke P., and Lubiw A., Dominating cliques in chordal graphs, Discrete Mathematics, 128 (1994), 269–275

    work page 1994

  4. [1]

    Journal of Combinatorial Optimization , 36 (2018), 1221-1242

    ´Agueda R., Cohen N., Fujita S., Legay S., Manoussakis Y., Matsui Y., Montero L., Naserasr R., Ono H., Otachi Y., Sakuma T., Tuza Zs., Xu R., Safe sets in graphs: Graph classes and structural parameters. Journal of Combinatorial Optimization , 36 (2018), 1221-1242

    work page 2018

  5. [2]

    B., Fujita S., Legay S., Manoussakis Y., Matsui Y., Sakuma T

    Bapat R. B., Fujita S., Legay S., Manoussakis Y., Matsui Y., Sakuma T. and Tuza Zs., Weighted safe set problem on trees, Networks, 71 (2018), 81–92

    work page 2018

  6. [3]

    Belmonte, R., Hanaka T., Katsikarelis, I., Lampis M., Ono H., Otachi Y., Parameterized complexity of safe set, ArXiv:1901.09434 (2019)

    work page Pith review arXiv 2019

  7. [4]

    and Zhang P., Graphs and Digraphs , 5th ed., Chapman and Hall, London, 2011

    Chartrand G., Lesniak L. and Zhang P., Graphs and Digraphs , 5th ed., Chapman and Hall, London, 2011

    work page 2011

  8. [5]

    Approximating Connected Safe Sets in Weighted Trees

    Ehard S. and Rautenbach D., Approximating connected safe sets in weighted trees, ArXiv:1711.11412v2 (2017)

    work page Pith review arXiv 2017

Show all 13 references
  1. [6]

    and Furuya M., Safe number and integrity of graphs, Discrete Applied Mathematics, 247 (2018), 398–406

    Fujita S. and Furuya M., Safe number and integrity of graphs, Discrete Applied Mathematics, 247 (2018), 398–406

    2018

  2. [8]

    and Sakuma T., Safe set problem on graphs, Discrete Applied Mathematics , 215 (2016), 106–111

    Fujita S., MacGillivray G. and Sakuma T., Safe set problem on graphs, Discrete Applied Mathematics , 215 (2016), 106–111. 37

    2016

  3. [9]

    Fujita S., Park B., and Sakuma T., Stable networks and connected safe set problem, Manuscript

  4. [11]

    Kang B., Kim S-R., Park B., On the safe sets of Cartesian product of two complete graphs, Ars Combinatoria, 141 (2018), 243–257

    2018

  5. [13]

    and Vygen J., Combinatorial Optimization , 5th ed., Springer- Verlag Berlin Heidelberg, 2011

    Korte B. and Vygen J., Combinatorial Optimization , 5th ed., Springer- Verlag Berlin Heidelberg, 2011. 38

    2011

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.