Safe sets in digraphs

Anders Yeo; J{\o}rgen Bang-Jensen; Shinya Fujita; Yandong Bai

REVIEW 1 major objections 5 minor 21 references

Safe sets in digraphs

T0 review · 1 major / 5 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 Minimum safe sets in digraphs are NP-hard for tournaments and traceable acyclic digraphs, with a polynomial dynamic program when strong components have logarithmic size.

desk verdict Solid NP-hardness and DP results, but the advertised ETH lower bound rests on a false padding inequality; a simple fix probably saves the theorem, so treat as major revision rather than reject. read the letter →

arxiv 1908.06664 v1 pith:KMT3J3RR submitted 2019-08-19 cs.CC cs.DMmath.CO

Yandong Bai , J{o}rgen Bang-Jensen , Shinya Fujita , Anders Yeo This is my paper · ORCID

classification cs.CCcs.DMmath.CO MSC 05C2005C6905C8568Q1768Q25

keywords safesetdigraphtournamentin-dominatingNP-hardnessdynamicprogrammingexponentialtimehypothesisfeedbackvertex

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 introduces the directed version of safe sets: vertex sets that dominate every strongly connected component left outside while never being outnumbered by a component they receive an arc from. It shows that finding a minimum safe set is NP-hard even in two very restricted classes: acyclic digraphs that have a Hamiltonian path (where safe sets coincide with in-dominating sets), and tournaments. On the positive side, it gives a dynamic programming algorithm that finds a minimum safe set in any semicomplete digraph in time $O(n^2 + nL2^L)$, where $L$ is the size of the largest strong component; for tournaments with $L \le c\log n$ this is polynomial. It also claims that, under the Exponential Time Hypothesis, no polynomial algorithm can exist when the allowed component size is raised to $\log^{1+\epsilon}(n)$, which would make the logarithmic algorithm essentially optimal, and it pins down extremal safe-number bounds for $k$-strong tournaments.

What carries the argument

The central objects are the safe-set definition itself, the equivalence between safe sets and in-dominating sets on acyclic digraphs, and the condensation of a semicomplete digraph into an ordered list of strong components $C_1,\dots,C_p$ with all arcs between earlier and later components going in one direction. The load-bearing algorithmic device is the dynamic-programming table $S^*(a,b)$, which stores the smallest safe set inside the suffix $V_a = C_a \cup \cdots \cup C_p$ whose own smallest strong component has size $b$. The table is filled from the last component backwards by trying every subset $W$ of the current component and gluing it to a previously computed suffix set, subject to the size-comparison condition; the $2^{\mathrm{lsc}(D)}$ factor in the running time comes from enumerating at most that many subsets per component.

What would settle it

Take a 3-SAT instance with $m$ clauses, run the paper's chain of reductions to obtain a tournament $T$ on $n'=9m$ vertices, and pad it to $N=\lceil 2(n')^{1/(1+\varepsilon)}\rceil$ vertices. The ETH proof requires the largest strong component of the padded tournament to be at most $\log^{1+\varepsilon}(N)$; a direct computation that it is instead $\Omega(m)$ would show the lower-bound claim is not supported by the construction.

Watch

Extended reading notes

Core claim

The paper establishes three main facts about minimum safe sets in digraphs. First, on acyclic digraphs a safe set is exactly an in-dominating set, and the minimum remains NP-hard to find even when the acyclic digraph is traceable, i.e. has a Hamiltonian path; the proof builds a traceable acyclic digraph from a specially constructed 4-SAT instance. Second, minimum safe set is NP-complete for tournaments, obtained by reducing feedback vertex set in tournaments to safe set. Third, for semicomplete digraphs whose largest strong component has size $L$, a dynamic program finds a minimum safe set in $O(n^2 + nL2^L)$ time, so tournaments with $L \le c\log n$ are solvable in polynomial time. The paper further claims, under the Exponential Time Hypothesis, that no polynomial algorithm exists when the largest strong component may be as large as $\log^{1+\epsilon}(n)$, which would make the logarithmic algorithm close to best possible.

Load-bearing premise

The ETH lower bound stands on the claim that the tournament built from a 3-SAT formula belongs to the class whose largest strong component is at most $\log^{1+\epsilon}(N)$, with $N$ only polynomial in the formula size.

Editorial extensions

If this is right

Minimum safe set is NP-complete for tournaments, so the problem inherits the hardness of feedback vertex set in tournaments.
For traceable acyclic digraphs the problem is NP-complete, so the easy transitive-tournament case does not extend to acyclic digraphs with a Hamiltonian path.
For every fixed $c>0$, the dynamic program runs in polynomial time on tournaments whose largest strong component has size at most $c\log n$, with running time $O(n^2 + c\log n \cdot n^{1+c})$.
If the ETH reduction is correct, the $c\log n$ algorithm is essentially the best polynomial guarantee one can hope for under ETH.
For $k$-strong tournaments the paper determines the minimum possible safe number and strong safe number for every $k$, and shows that for $n \ge 3k \ge 9$ these parameters range between roughly $n/2$ and $n/2$.
The dynamic programming method works for the larger class of semicomplete digraphs, not only tournaments.

Reading between the lines

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

A natural next step is to re-run the dynamic program with the largest strong component treated as a parameter, asking whether this yields a fixed-parameter tractable algorithm and whether a matching parameterized lower bound exists.
The ETH near-optimality claim would be on firmer ground if the construction were padded so the reduced tournament provably lies in the class with largest strong component at most $\log^{1+\epsilon}(N)$; the current proof's parameter check is the point to verify.
The extremal bounds for $k$-strong tournaments likely extend to other dense digraph classes with complementary-cycle structure, such as semicomplete digraphs.
If the parameter containment can be repaired, the resulting dichotomy is clean: polynomial for logarithmic strong components and, under ETH, impossible for $\log^{1+\epsilon}$-sized strong components.

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.

Desk Editor's Note

read the letter

Two things you should know about arXiv:1908.06664. First, the ETH lower bound in Theorem 4.2 is not proven as written: the padding N = ceil(2(n')^{1/(1+ε)}) is only polynomial in n', so log^{1+ε}(N) is polylogarithmic, and the constructed tournament's largest strong component is typically n' = 9m, far above the allowed bound. This is a real error, not a mismatch with a convention. The good news is that it is easily repaired: taking N exponential in (n')^{1/(1+ε)} makes log^{1+ε}(N) ≥ n', and the reduction then runs in subexponential time, which is still enough to contradict ETH. The paper would need to state explicitly that the reduction is subexponential, but the theorem likely survives.

The rest of the paper is in much better shape. The traceable acyclic in-dominating set reduction (Theorem 3.3) is intricate and appears correct; it genuinely strengthens known NP-hardness for in-dominating sets. The dynamic program for semicomplete digraphs (Theorem 4.3) is a real new algorithm, and the running time O(n^2 + n·L·2^L) is consistent with the described procedure. The correctness proof is terse but holds up on inspection. The safe-number bounds in Section 5 are less central but look plausible.

The load-bearing soft spot is Theorem 4.2. The abstract and introduction advertise the ETH result as the reason the O(c log n) algorithm is nearly optimal, so the false padding inequality undermines a headline claim. That said, this is a fixable flaw, not a fundamental one. I would not reject the paper; I would ask for a major revision that repairs the padding and makes the subexponential reduction explicit. The citation pattern is clean: the reductions are anchored to standard results (FVS in tournaments, Reid/Song cycle-factor theorem, ETH), and I see no fitting or self-referential issues. The paper is written for people working on safe sets, domination in digraphs, and complexity dichotomies on tournaments, and it deserves a serious referee. The core results are solid enough that the ETH flaw is worth living through a revision cycle.

My recommendation: send it to review, expect major revision, and judge the revised version on whether the ETH claim gets fixed.

Referee Report

1 major / 5 minor

Summary. The paper initiates the study of safe sets in digraphs, a directed analogue of the undirected safe set notion. It shows that finding a minimum in-dominating set (equivalently, a minimum safe set) is NP-hard even for traceable acyclic digraphs, and that Safe Set is NP-complete for tournaments. It then gives a dynamic programming algorithm that finds a minimum safe set in a semicomplete digraph in time O(n^2 + n · lsc(D) · 2^{lsc(D)}), where lsc(D) is the size of the largest strong component; in particular, this is polynomial for tournaments whose largest strong component has size O(log n). The paper further claims an ETH-based lower bound stating that, for every ε > 0, no polynomial-time algorithm exists for tournaments with largest strong component at most log^{1+ε}(n), and it closes with extremal bounds on the safe number and strong safe number of tournaments.

Significance. If the results stand, this is a useful contribution to the algorithmic theory of safe sets in directed graphs. The NP-hardness reductions are standard but carefully assembled, and the dynamic programming algorithm for semicomplete digraphs is explicit and gives a concrete polynomial running time for tournaments with polylogarithmic strong components. The extremal bounds in Section 5 also add value. However, the advertised ETH lower bound in Theorem 4.2, which is the main selling point for optimality of the algorithm, is stated with an incorrect formula for the padded order N; as written, the proof is invalid. The intended argument is recoverable with a one-character correction to the definition of N, so the central claim is defensible, but the submitted text needs a substantive fix in a load-bearing proof step.

major comments (1)

[Theorem 4.2, proof of the ETH lower bound] As printed, the definition of the padded order is N = ⌈2(n′)^{1/(1+ε)}⌉, which is polynomial in n′. For this value the asserted inequality n′ ≤ log^{1+ε}(N) is false for all sufficiently large n′; for example, with ε = 1 and n′ = 10^6, N ≈ 2000 while log^2(N) ≈ 58. Consequently the constructed tournament T is not shown to belong to T(log^{1+ε}(N)), and the hypothetical polynomial-time algorithm A cannot be invoked on T. The subsequent displayed identity (2(n′)^{1/(1+ε)})^c = 2^{c·(n′)^{1/(1+ε)}} is also inconsistent with the printed definition of N. The intended argument evidently requires N = ⌈2^{(n′)^{1/(1+ε)}}⌉, for which n′ = log^{1+ε}(N) holds up to rounding and the running-time calculation becomes valid. The proof should be corrected accordingly, and it should explicitly note that constructing T takes O(N^2) time, which is absorbed in the subexponential bound.

minor comments (5)

[Theorem 4.2, statement] The notation log(1+ε)(n) in the theorem statement should be written as log^{1+ε}(n) to match the abstract and the rest of the paper.
[Corollary 4.4] The displayed running time is missing a superscript: it should read O(n^2 + n · c log n · 2^{c log n}) = O(n^2 + c n^{1+c} log n), with the exponent on n made explicit.
[Lemma 3.2] The phrase that G(F) contains two isomorphic copies of B(F′) is imprecise: the induced subgraphs also contain clause-clause edges, so they are not exactly copies of the bipartite incidence graph. Since only the matching edges are used, the argument is unaffected, but the wording should be corrected.
[Proof of Theorem 4.3] The case W = ∅ is used in the dynamic program (e.g., in the example with C3), but the definition of sW as the size of a smallest strong component in D[W] is undefined for empty W. The intended convention sW = ∞ should be stated explicitly.
[Theorem 5.3, even-n construction] In the paragraph constructing T∗, the notation confuses S with its complement: the safe set displayed as {v0, v1, ..., v_{k′−1}, v_{k′+1}} should be denoted consistently, and the complement should not be written as S when S was already used for the safe set.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: reductions and algorithms are based on external hardness results and self-contained proofs.

full rationale

The paper's derivations are not circular. The safe-set definitions are foundational, and the algorithmic results (Theorems 2.2, 4.3, 4.4) are proved directly by dynamic programming over strong components, with no fitted parameters and no quantity defined in terms of the target. NP-hardness is established by explicit polynomial reductions from set cover and from feedback vertex set in tournaments, which are cited external results (Karp 1972; Speckenmeyer 1989), and the ETH lower bound is anchored in the standard 3-SAT-to-Clique-to-Vertex-Cover-to-FVST chain, not in the paper's own conclusions. Self-citations (e.g., to Fujita et al. for the origin of safe sets or to Bang-Jensen and Gutin for notation) are motivational or terminological and are not load-bearing. The proof of Theorem 4.2 contains a questionable padding inequality (the claim that n' = 9m is at most log^(1+epsilon)(N) for N = ceil(2(n')^(1/(1+epsilon))) appears false), but that is a correctness flaw in a reduction, not a circularity: it does not make the theorem's conclusion equivalent to its assumptions. Accordingly, no circular step meets the evidentiary bar.

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

The paper's proofs rest on standard complexity-theoretic and combinatorial results. No free parameters are fitted to data, and no new entities are invented. The only fragile dependency is the incorrect inequality in the ETH lower bound proof.

assumptions (7)

domain assumption Exponential Time Hypothesis (ETH): no algorithm solves 3-SAT in time O(2^(delta(n+m))) for a universal delta > 0
Used in Theorem 4.2 to derive the claimed lower bound; the theorem is invalid but ETH is a standard complexity hypothesis.
standard math NP-completeness of set cover (Karp)
Used in Section 2 to prove NP-hardness of in-dominating sets in acyclic digraphs.
standard math NP-completeness of Feedback Vertex Set in tournaments (Speckenmeyer)
Used in the proofs of Theorems 4.1 and 4.2.
standard math Hall's theorem
Used in Lemma 3.1 to reduce 3-SAT instances to irreducible instances.
domain assumption Theorem of Reid and Song: every 2-strong tournament not the unique 7-tournament has a cycle factor with cycles of lengths t and n-t
Used in the upper bound proof of Theorem 5.3.
standard math Reduction chain 3-SAT <=_p Clique <=_p Vertex Cover
Used in Theorem 4.2 to translate 3-SAT instances into Vertex Cover instances with 3m vertices.
standard math Theorem of Gyarfas et al.: for acyclic digraphs with independence number alpha, gamma(D) <= alpha
Used in Theorem 2.2 to bound the search space for acyclic digraphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Safe sets in digraphs." pith.science (2026). https://pith.science/paper/KMT3J3RR

@misc{pith2026190806664,
  author       = {Pith},
  title        = {Pith review of: Safe sets in digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KMT3J3RR}},
  note         = {Machine review of arXiv:1908.06664}
}

abstract

A non-empty subset $S$ of the vertices of a digraph $D$ is called a {\it safe set} if \begin{itemize} \item[(i)] for every strongly connected component $M$ of $D-S$, there exists a strongly connected component $N$ of $D[S]$ such that there exists an arc from $M$ to $N$; and \item[(ii)] for every strongly connected component $M$ of $D-S$ and every strongly connected component $N$ of $D[S]$, we have $|M|\leq |N|$ whenever there exists an arc from $M$ to $N$. \end{itemize} In the case of acyclic digraphs a set $X$ of vertices is a safe set precisely when $X$ is an {\it in-dominating set}, that is, every vertex not in $X$ has at least one arc to $X$. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality in-dominating set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant $c$, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on $n$ vertices in which no strong component has size more than $c\log{}(n)$. Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every $\epsilon>0$ there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most $\log^{1+\epsilon}(n)$. We also discuss bounds on the cardinality of safe sets in tournaments.

Figures

Figures reproduced from arXiv: 1908.06664 by the authors.

**Figure 1.** A semicomplete digraph, D, where the arcs between distinct Ci ’s are not shown, but go from Ci to Cj if and only if i < j. Note that lsc(D) = 5. 2A digraph D is semicomplete if there is at least one arc between any pair of distinct vertices. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

[1]

´Agueda, N

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

work page 2018
[2]

Bang-Jensen and G

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, in: Springer Monographs in Mathematics, Springer Verlag, London, 2008

work page 2008
[3]

Bang-Jensen and C

J. Bang-Jensen and C. Thomassen, A polynomial algorithm for th e 2-path problem for semicom- plete digraphs, SIAM Journal on Discrete Mathematics 5 (1992) 366-376

work page 1992
[4]

Cygan, F

M. Cygan, F. V. Fomin, L.Kowalik, D. Lokshtanov, D. Marx, M. Pilipc zuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Springer Verlag 2016

work page 2016
[5]

Ehard and D

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

arXiv 2017
[6]

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

work page 2018
[7]

Belmonte, T

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

arXiv 2019
[8]

Cormen, C.E

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduct ion to algorithms 3rd edition, MIT press, Cambridge Massachusetts, 2009

work page 2009

Show all 21 references

[9]

Fujita and M

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

2018
[10]

Fujita, T

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

2019
[11]

Fujita, G

S. Fujita, G. MacGillivray, T. Sakuma, Safe set problem on graph s, Discrete Applied Mathematics 215 (2016) 106-111

2016
[12]

Ganian, P

R. Ganian, P. Hlineny, J. Kneis, A. Langer, J. Obdrzalek and P. R ossmanith, Digraph width measures in parametrized algorithmics, Discrete Applied Mathematics. 168 (2014) 88-107

2014
[13]

Gy´ arf´ as, G

A. Gy´ arf´ as, G. Simonyi, ´A. T´ oth, Gallai colorings and domination in multipartite digraphs, Journal of Graph Theory 71 (2012) 278-292

2012
[14]

H¨ aggkvist, C

R. H¨ aggkvist, C. Thomassen, On pancyclic digraphs, Journal of Combininatorial Theory Ser. B 20 (1976) 20-40

1976
[15]

Hosteins, A compact mixed integer linear formulation for safe set problems, preprint

P. Hosteins, A compact mixed integer linear formulation for safe set problems, preprint
[16]

Kang, S-R

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

2018
[17]

Karp, Reducibility among combinatorial problems

R.M. Karp, Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (eds.), Complexity of computer computations , Plenum Press New York (1972) 85-103

1972
[18]

Megiddo and U

N. Megiddo and U. Vishkin, On ﬁnding a mimimum dominating set in a tou rnament, Theoretical Computer Science 61 (1988) 307-316

1988
[19]

Reid, Two complementary circuits in two-connected tourna ments, Annals of Discrete Math- ematics 27 (1985) 321-334

K.B. Reid, Two complementary circuits in two-connected tourna ments, Annals of Discrete Math- ematics 27 (1985) 321-334

1985
[20]

Song, Complementary cycles of all lengths in tournaments, Journal of Combinatorial Theory Ser

Z.M. Song, Complementary cycles of all lengths in tournaments, Journal of Combinatorial Theory Ser. B 57 (1993) 18-25

1993
[21]

Speckenmeyer, On feedback problems in digraphs, in Proc

E. Speckenmeyer, On feedback problems in digraphs, in Proc. 1 5 WG 89, Springer-Verlag, Lecture Notes in Comput. Science , 411 (1989), pp. 218-231. 15

1989

Pith tools

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

[1] [1]

´Agueda, N

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

work page 2018

[2] [2]

Bang-Jensen and G

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, in: Springer Monographs in Mathematics, Springer Verlag, London, 2008

work page 2008

[3] [3]

Bang-Jensen and C

J. Bang-Jensen and C. Thomassen, A polynomial algorithm for th e 2-path problem for semicom- plete digraphs, SIAM Journal on Discrete Mathematics 5 (1992) 366-376

work page 1992

[4] [4]

Cygan, F

M. Cygan, F. V. Fomin, L.Kowalik, D. Lokshtanov, D. Marx, M. Pilipc zuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Springer Verlag 2016

work page 2016

[5] [5]

Ehard and D

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

arXiv 2017

[6] [6]

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

work page 2018

[7] [7]

Belmonte, T

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

arXiv 2019

[8] [8]

Cormen, C.E

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduct ion to algorithms 3rd edition, MIT press, Cambridge Massachusetts, 2009

work page 2009