{"id":"21f060f5-bbee-4d91-bb44-6c3721c309f7","arxiv_id":"1908.06664","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves NP-hardness for minimum safe sets in traceable acyclic digraphs and tournaments, gives a polynomial algorithm for tournaments with small strong components, but its ETH lower bound for slightly larger components is invalid.","lead":"This paper introduces safe sets for directed graphs and analyzes how hard it is to find the smallest one. The main advertised near-optimality claim under ETH is not proven; the NP-hardness and polynomial algorithms for restricted classes appear sound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's padding inequality is false: n' = 9m exceeds log^(1+ε)(N) for N = ceil(2(n')^(1/(1+ε))), so the ETH lower bound is unproven.","rationale":"The reader correctly identifies the weakest point: Theorem 4.2's reduction only works if the padded tournament belongs to T(log^(1+ε)(N)), and the proof's only justification for this membership is the false inequality n' <= log^(1+ε)(N). The arithmetic is not a minor typo; it breaks the applicability of the alleged polynomial-time algorithm. The paper's other contributions—the in-dominating-set hardness for traceable acyclic digraphs, NP-completeness for tournaments, the dynamic program for semicomplete digraphs, and the tournament bounds—appear independent of the flawed ETH argument and may be sound. But the abstract's headline near-optimality claim is precisely the ETH lower bound, and since that claim fails as written, the reader's REJECT verdict remains appropriate. No additional load-bearing concern is needed.","tokens_in":16733,"tokens_out":4422,"duration_ms":46721,"concrete_test":"Recompute the class-membership step of Theorem 4.2: fix ε = 1 and take m = 1000, so n' = 9000, N = ceil(2*sqrt(9000)) = 190, and log^2(N) ≈ 27.6; then n' = 9000 > 27.6. More generally, check that n' / log^(1+ε)(ceil(2(n')^(1/(1+ε)))) tends to infinity as n' grows. If this ratio diverges, the constructed tournament cannot be guaranteed to lie in T(log^(1+ε)(N)), and the ETH lower bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The ETH lower bound in Theorem 4.2 depends on the assertion that for n' = 9m and N = ceil(2(n')^(1/(1+ε))), we have n' <= log^(1+ε)(N). This inequality is false. Since N is polynomial in n' of degree 1/(1+ε), log^(1+ε)(N) = O((log n')^(1+ε)) = n^{o(1)}, whereas n' is linear in m. For example, with ε = 1 and n' = 10^6, N is about 2000 while log^2(N) is about 58; n' is far larger. The padded tournament has order N, but its largest strong component is at least the largest strong component of the FVST-reduction tournament on n' vertices, which the proof never bounds below n' and which is Θ(n') in the standard construction. Hence the constructed tournament need not belong to T(log^(1+ε)(N)), so the hypothetical algorithm A cannot be invoked. The later running-time contradiction to ETH therefore does not follow. This is an internal inconsistency in the reduction, not a disagreement with a consensus hypothesis: the advertised lower bound is unsupported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16780,"tokens_out":26290,"duration_ms":251978,"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":[{"comment":"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.","section":"Theorem 4.2, proof of the ETH lower bound"}],"minor_comments":[{"comment":"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.","section":"Theorem 4.2, statement"},{"comment":"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.","section":"Corollary 4.4"},{"comment":"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.","section":"Lemma 3.2"},{"comment":"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.","section":"Proof of Theorem 4.3"},{"comment":"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.","section":"Theorem 5.3, even-n construction"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Theorem 4.2 is real for the literal text, but it appears to be a typographical error in the definition of N rather than a conceptual flaw: the running-time calculation only makes sense with N = 2^{(n′)^{1/(1+ε)}}, and with that correction the proof goes through. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nMy recommendation: send it to review, expect major revision, and judge the revised version on whether the ETH claim gets fixed.","headline":"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.","tokens_in":17486,"tokens_out":8470,"would_cite":true,"duration_ms":79964,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C69","05C85","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["safe set","digraph","tournament","in-dominating set","NP-hardness","dynamic programming","exponential time hypothesis","feedback vertex set"],"falsifier":"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.","tokens_in":16360,"feed_emoji":"🛡️","tokens_out":9683,"duration_ms":98196,"temperature":0.7,"pith_summary":"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.","feed_headline":"Minimum safe sets: NP-hard for tournaments, easy on small cores","feed_subtitle":"The paper pins down when minimum safe sets in tournaments are easy, and claims a near-optimal ETH barrier.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the NP-complete set cover and feedback vertex set problems that seed both hardness reductions.","marker":"[17]"},{"why":"It proves that feedback vertex set is NP-complete on tournaments, which the tournament safe-set reduction builds on.","marker":"[21]"},{"why":"It supplies the formulation of the Exponential Time Hypothesis used to state the lower bound.","marker":"[4]"},{"why":"It gives the standard 3-SAT to Vertex Cover reduction chain that fixes the size of the tournament in the ETH argument.","marker":"[8]"},{"why":"It supplies the domination bound for acyclic digraphs that powers the bounded-independence polynomial algorithm.","marker":"[13]"},{"why":"It supplies the complementary-cycle theorem for 2-strong tournaments used for the safe-number upper bound.","marker":"[19]"},{"why":"It extends the complementary-cycle result to all lengths, also used for the upper bound.","marker":"[20]"}],"fun_headline_variants":["Safe sets: NP-hard for traceable acyclic digraphs and tournaments","Tournament safe sets: NP-hard, but polynomial if strong components are small","Safe-set dichotomy: NP-hard for tournaments, ETH barrier beyond log-small cores","Minimum safe set: hard for tournaments, easy when components are logarithmic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Safe sets: NP-hard for traceable acyclic digraphs and tournaments","Tournament safe sets: NP-hard, but polynomial if strong components are small","Safe-set dichotomy: NP-hard for tournaments, ETH barrier beyond log-small cores","Minimum safe set: hard for tournaments, easy when components are logarithmic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001234,"raw_usage":{"total_tokens":5143,"prompt_tokens":1093,"completion_tokens":4050,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":3969}},"tokens_in":709,"tokens_out":4050,"duration_ms":32014,"temperature":1.0,"reasoning_tokens":3969,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:38:19.014923+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Karp, Reducibility among combinatorial problems","cited_arxiv_id":null,"evidence_quote":"It supplies the NP-complete set cover and feedback vertex set problems that seed both hardness reductions."},{"cited_title":"Speckenmeyer, On feedback problems in digraphs, in Proc","cited_arxiv_id":null,"evidence_quote":"It proves that feedback vertex set is NP-complete on tournaments, which the tournament safe-set reduction builds on."},{"cited_title":"Cygan, F","cited_arxiv_id":null,"evidence_quote":"It supplies the formulation of the Exponential Time Hypothesis used to state the lower bound."},{"cited_title":"Cormen, C.E","cited_arxiv_id":null,"evidence_quote":"It gives the standard 3-SAT to Vertex Cover reduction chain that fixes the size of the tournament in the ETH argument."},{"cited_title":"Gy´ arf´ as, G","cited_arxiv_id":null,"evidence_quote":"It supplies the domination bound for acyclic digraphs that powers the bounded-independence polynomial algorithm."},{"cited_title":"Reid, Two complementary circuits in two-connected tourna ments, Annals of Discrete Math- ematics 27 (1985) 321-334","cited_arxiv_id":null,"evidence_quote":"It supplies the complementary-cycle theorem for 2-strong tournaments used for the safe-number upper bound."},{"cited_title":"Song, Complementary cycles of all lengths in tournaments, Journal of Combinatorial Theory Ser","cited_arxiv_id":null,"evidence_quote":"It extends the complementary-cycle result to all lengths, also used for the upper bound."}],"review_version":1}