{"id":"385d12c6-9c23-4444-a9ad-0eeccbe335e0","arxiv_id":"2507.07528","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Enumerating induced s-t hyperpaths and minimal s-t separators in directed hypergraphs is not output-polynomial unless P=NP, and s-t hyperpath enumeration on BF-hypergraphs is at least as hard as the 45-year-old minimal transversal enumeration problem.","lead":"This paper studies the cost of listing all paths and separators in directed hypergraphs, where a single connection step can require many input vertices. It shows that two classical graph enumeration problems become impossible to solve in output-polynomial time in this setting unless P=NP, and it ties one remaining case to a famous open problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7, underpinning Theorem 8, argues the wrong direction: the separator condition gives every clause a false literal, not a true one, and the forward witness can fail to be a separator. The lemma looks repairable, but the proof must be corrected.","rationale":"Reader's conditional verdict is appropriate. I read the paper's target as establishing three complexity claims: Theorems 6 and 8 (no output-polynomial enumeration unless P=NP), Theorem 10 (reduction from minimal transversals), and Theorem 13 (polynomial-delay for B-hypergraphs). The most load-bearing weak point is Lemma 7: the only NP-hardness proof for minimal separators. The current text's forward and reverse directions are each wrong in a specific way. I checked whether the lemma can be salvaged: for any satisfying assignment α, the complement assignment β=¬α makes every clause contain at least one false literal, and the set X of β-true literals blocks every clause hyperarc; a minimal separator contained in X is non-trivial. Conversely a non-trivial minimal separator gives, via the proof's αX, a clause-wise assignment with at least one false literal per clause, so its complement satisfies φ. Hence the statement is plausible and Theorem 8 may hold, but the submitted proof does not establish it. The definitional gap for induced hyperpaths is also real: the formal definition lacks minimality, although Lemma 5 relies on it; this affects Theorem 6, though again the intended fix is straightforward. I did not find a problem with Lemma 9's transversal bijection, which has independent support, and the polynomial-delay algorithm's structure is plausible. No machine-checked verification is present, so correctness rests on the narrative proofs. Given the two proof-level gaps, conditional acceptance with mandatory revision is the right verdict; I would not reject because both gaps appear repairable and the central ideas are sound.","tokens_in":15119,"tokens_out":23283,"duration_ms":266623,"concrete_test":"Re-derive Lemma 7 on the formula φ=(x1∨x2∨x3) with the satisfying assignment x1=x2=x3=1. Following the proof, take X={x1,x2,x3}; compute B-connectivity from s in D[V\\X]: the clause hyperarc tail {¬x1,¬x2,¬x3} is fully present, so c — and hence t via the final tree/Horn hyperarc — is reachable, falsifying the forward direction. Then repeat with the complementary set X={¬x1,¬x2,¬x3}; check whether some minimal subset of it is a separator not contained in X(φ). If yes, Lemma 7's statement survives with the assignment flipped, confirming a required corrective revision rather than a withdrawn theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2's Lemma 7 is the sole support for the Theorem 8 hardness claim, and its proof is invalid as written. Forward direction: X is the set of literals made true by a satisfying assignment α. If some clause C_j is all-true, then each negated literal in the tail of C_j's hyperarc is false, hence not in X; the whole tail is present in D[V\\X], so c is B-connected and, with all y_i reachable, t is reachable. Thus X is not an s-t separator. Reverse direction: a minimal separator X not in X(φ) contains neither c, nor any y_i, nor both literals of a variable. Blocking c requires that for every clause at least one negated literal lies in X, i.e. under the assignment αX defined in the proof every clause has at least one false literal. So αX satisfies the negated formula; the proof's assertion that αX satisfies φ is backwards. The lemma is likely repairable (using the complement assignment), but as written the main no-output-polynomial theorem for minimal separators lacks a correct proof. Separately, §2 defines an induced s-t hyperpath merely as a vertex set with t B-connected in the induced subhypergraph; Lemma 5 then uses minimality. Under the written definition the whole vertex set is always an induced hyperpath, which trivializes Theorem 6's reduction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies three output-sensitive enumeration problems on directed hypergraphs: induced s-t hyperpaths, minimal s-t separators, and (non-induced) s-t hyperpaths. It claims that the first two become NP-hard to enumerate in output-polynomial time on B-hypergraphs even when every hyperarc has at most two tails (Theorems 6 and 8), that output-polynomial enumeration of s-t hyperpaths on BF-hypergraphs would imply output-polynomial minimal transversal enumeration (Theorem 10), and that all S-T hyperpaths in a B-hypergraph can be enumerated with O(m^2||A||) delay and O(m||A||) space (Theorem 13). The positive algorithm uses a recursive branching strategy based on a characterization of S-T hyperpaths in B-hypergraphs.","tokens_in":15402,"tokens_out":15371,"duration_ms":161058,"significance":"If the two hardness theorems were correctly proved, they would show a clean dichotomy: classical graph enumeration problems that are easy by backtracking become hard in the directed-hypergraph generalization, and the connection to minimal transversal enumeration would place BF-hypergraph s-t hyperpath enumeration close to a famous open problem. The polynomial-delay algorithm for S-T hyperpaths is a substantive positive contribution and plausibly extends to minimal directed Steiner tree enumeration. However, the manuscript as submitted contains two load-bearing gaps: the notion of induced s-t hyperpath is defined without minimality, which invalidates the reduction in Section 3.1 as written, and the proof of Lemma 7 in Section 3.2 argues the wrong direction for the extracted assignment. Both appear repairable, so the underlying claims may still be correct, but the current text does not establish them.","major_comments":[{"comment":"The definition in Section 2 states only that a vertex set P_st is an induced s-t hyperpath if t is B-connected from s in D[P_st]; minimality is not part of the definition. Under this definition any superset of an induced hyperpath is again an induced hyperpath, so for an unsatisfiable formula the set {s, x1, xibar1, t, c1} in the reduction of Section 3.1 is an induced s-t hyperpath not contained in P_phi. This makes Lemma 5 false as stated, and the converse proof explicitly invokes 'minimality' without any supporting definition. The paper should either define an induced s-t hyperpath as an inclusion-wise minimal vertex set with t B-connected in the induced subhypergraph, or state a different intended notion and rework the reduction accordingly.","section":"Section 2, definition of induced s-t hyperpath, and Lemma 5"},{"comment":"The reverse direction of Lemma 7 defines alpha_X by xi in X and claims that each clause is satisfied; however, a non-trivial minimal separator blocks c by ensuring that for every clause at least one negated literal lies in X, which makes the corresponding original literal false under alpha_X, not true. Concretely, for phi = (x1 ∨ x2 ∨ x3), X = {xibar1} is a minimal s-t separator not in X(phi), and the proof's assignment sets all variables to 0, falsifying phi, yet D_phi[V \\ X] has no s-t hyperpath because c is unreachable. The repair is to define the assignment by xi = 1 iff xi notin X (equivalently, take the complement of alpha_X), but this correction is not present in the manuscript. Since Theorem 8 rests entirely on Lemma 7, the hardness claim is not established as written.","section":"Section 3.2, Lemma 7, reverse direction"},{"comment":"In the forward direction of Lemma 7, the proof says 'each y_i is connected to s in D_phi[X]', but since X is the set of vertices removed by the separator, y_i is not a vertex of D_phi[X]; the intended statement is presumably about D_phi[V \\ X]. This is a notational error in the proof as written, and it should be corrected along with the substantive reverse-direction error.","section":"Section 3.2, Lemma 7, forward direction"}],"minor_comments":[{"comment":"In the forward direction of Lemma 5, the proof asserts that an induced s-t hyperpath contained in U exists but does not specify which subset of U is taken; the argument would be cleaner if it first selected a minimal (inclusion-wise) vertex set with t B-connected from s.","section":"Section 3.1, Lemma 5 proof"},{"comment":"The sentence 'If there is a vertex c_j notin P, D[P] does not have a hyperarc A that contains t as the head' is only true after the preceding exclusion of both literals of any variable; the text should make this dependency explicit.","section":"Section 3.1, Lemma 5 proof"},{"comment":"The symbol X is overloaded: in Problem 4 it denotes a set of separators, while in Lemma 7 it denotes a vertex set that is a separator. Using different symbols would improve readability.","section":"Problems 2 and 4, Section 3.2"},{"comment":"The sentence 'This modification adds only {c_j} for each 1 ≤ j ≤ m as new minimal s-t separators' should also mention the O(n+m) dummy vertices introduced when decomposing the large hyperarc, as the same paragraph later accounts for them.","section":"Section 3.2, tail-size reduction"},{"comment":"The surjectivity proof of f asserts that each vertex v in T has a hyperedge E such that T ∩ E = {v}; this is correct but should be justified by the minimality of the hyperpath P_st rather than stated as immediate.","section":"Section 3.3, Lemma 9 proof"}],"recommendation":"major_revision","confidential_remarks":"The two hardness proofs are likely repairable, so I do not recommend rejection. However, the definitional gap in Section 2 is more than a typo because the problem being solved changes; the authors must revise the definition of induced s-t hyperpath and then re-verify Lemma 5. The connection to minimal transversal enumeration and the positive polynomial-delay algorithm are the strongest parts of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Paper is worth a serious referee, though not in current form. The best piece is Lemma 9: the construction from a hypergraph H to a BF-hypergraph D_H and the bijection between minimal transversals and s-t hyperpaths is correct and clean. It turns a 45-year-old open problem into a conditional lower bound for hyperpath enumeration, which is the kind of connection that makes the paper worth reading.\n\nThe positive result also looks right. I checked the characterization in Lemma 11 and the contraction step in Lemma 12; the Read-Tarjan style backtracking with polynomial delay for S-T hyperpaths in B-hypergraphs is a legitimate contribution, and the generalization to minimal Steiner trees and Horn SAT subformulas is a nice bonus.\n\nThe soft spots are both in Section 3. The definition of 'induced s-t hyperpath' in Section 2 omits minimality. Taken literally, any vertex set that contains s and t and B-connects t is an induced hyperpath, which trivializes Lemma 5. The authors clearly intended an inclusion-wise minimal vertex set; the definition needs to say that.\n\nLemma 7, which supports the minimal-separator hardness theorem, has a wrong proof in both directions. Forward: X is built from the true literals of a satisfying assignment. If a clause is all-true, none of its negated literals is in X, so c becomes reachable and X is not a separator. Reverse: with alpha defined by xi in X, the separator condition gives every clause a false literal, so alpha satisfies the negated formula. The repair is the complement construction: put false literals in X, and set alpha(xi)=1 iff xi is not in X. Then the lemma goes through. But as written, Theorem 8 does not have a valid proof.\n\nNeither flaw is fatal. I expect both can be fixed without changing the theorems. But they are not cosmetic, and a referee should ask for the corrected proofs before publication.\n\nThis is for people working on enumeration complexity, output-sensitive algorithms, and hypergraph connectivity. The minimal transversal reduction alone is worth citing after the revision. I would not accept the current version; I would send it to a serious referee with a request for major revision.","headline":"A clean reduction from minimal transversals to s-t hyperpath enumeration and a plausible backtracking algorithm, but both hardness proofs have correctable flaws and the current version should not be accepted as is.","tokens_in":15875,"tokens_out":12976,"would_cite":false,"duration_ms":149442,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Listing all induced s-t hyperpaths or minimal s-t separators in directed hypergraphs cannot be done in output-polynomial time unless P=NP; BF-hypergraph path enumeration is tied to a 45-year-open minimal transversal problem.","keywords":["output-sensitive enumeration","directed hypergraphs","s-t hyperpath","minimal s-t separator","NP-hardness","polynomial delay","B-hypergraph","minimal transversal enumeration"],"falsifier":"Take the separator reduction of Lemma 7 with $\\varphi=(x_1\\lor x_2\\lor x_3)$ and the assignment $x_1=x_2=x_3=1$; with $X=\\{x_1,x_2,x_3\\}$ the clause tail $\\{\\neg x_1,\\neg x_2,\\neg x_3\\}$ is fully present in $D_\\varphi[V\\setminus X]$, so $c$ is reachable and $X$ is not a separator, directly contradicting the forward direction as printed.","tokens_in":14938,"feed_emoji":"🔗","tokens_out":18861,"duration_ms":174968,"temperature":0.7,"pith_summary":"On ordinary directed graphs, listing all induced s-t paths or minimal s-t separators is easy by simple backtracking. This paper argues that in directed hypergraphs the picture changes: unless P=NP, no output-polynomial algorithm—one whose total time is polynomial in the input plus the number of outputs—can enumerate all induced s-t hyperpaths or all minimal s-t separators, even in B-hypergraphs (each hyperarc has a single head) with every tail of size at most two. It also shows that enumerating s-t hyperpaths in BF-hypergraphs (each hyperarc has a single tail or a single head) is at least as hard as enumerating all minimal transversals of hypergraphs, a problem open for more than 45 years. On the positive side, it gives a polynomial-delay, polynomial-space backtracking algorithm that lists all S-T hyperpaths in a B-hypergraph, covering minimal directed Steiner trees and minimal unsatisfiable subformulas of Horn formulas.","feed_headline":"No fast enumeration for hypergraph paths or separators unless P=NP","feed_subtitle":"Extending two classic graph problems to directed hypergraphs makes them NP-hard to list, barring P=NP.","key_machinery":"The central object is B-connectivity, the forward-chaining reachability of a directed hypergraph: a hyperarc's head becomes reachable only after all its tails are reachable. The hardness machinery is a pair of polynomial reductions from 3-SAT in which literals are vertices, clauses become hyperarcs whose tails are literals (or their negations), and a final hyperarc fires only when all clauses are satisfied; the 'another solution' principle then converts NP-hardness of finding an extra output into the nonexistence of output-polynomial enumeration. The positive machinery is Lemma 11, a three-condition characterization of $S$-$T$ hyperpaths in a B-hypergraph: an ordering exists in which each hyperarc's tails are already produced, each non-source vertex is produced exactly once, and every internal vertex is used as a tail. Algorithm 1 branches on one hyperarc of a currently found hyperpath and recurses both without that hyperarc and with it contracted—replacing its head by its tail set in other hyperarcs, deleting the head, and updating the target set.","core_discovery":"The paper's central claim is that enumeration problems that are easy on directed graphs become conditionally intractable on directed hypergraphs. It asserts (Theorems 6 and 8) that the 'another solution' versions of induced s-t hyperpath and minimal s-t separator enumeration are NP-complete on B-hypergraphs even with every tail of size at most two, so output-polynomial enumeration would imply P=NP. It further asserts (Theorem 10) that output-polynomial s-t hyperpath enumeration on BF-hypergraphs would yield output-polynomial enumeration of minimal transversals, and (Theorem 13) that all S-T hyperpaths in B-hypergraphs can be listed with $O(m^2 \\cdot \\|A\\|)$ delay and $O(m \\cdot \\|A\\|)$ space. The framing is that B-hypergraphs are the tractable boundary for forward-chaining reachability, while allowing F-hyperarcs reconnects the problem to longstanding dualization.","pith_inferences":["The polarity problem in Lemma 7 is likely repaired by taking the separator to be the false literals of a satisfying assignment, so the theorem may survive a corrected proof.","The definitional gap suggests that the intended 'induced s-t hyperpath' is an inclusion-minimal vertex set that still connects t from s; under that reading, the reductions and examples cohere.","Because of the bijection in Lemma 9, algorithms and lower bounds transfer in both directions between BF s-t hyperpath enumeration and minimal transversal enumeration.","A natural next test is whether Algorithm 1's contraction-based branching extends from B-hypergraphs to F-hypergraphs; the paper's conditional hardness suggests that would require genuinely new ideas."],"forward_implications":["No output-polynomial algorithm can list all induced s-t hyperpaths of a B-hypergraph unless P=NP, even when every hyperarc has at most two tails.","No output-polynomial algorithm can list all minimal s-t separators of a B-hypergraph unless P=NP, even when every hyperarc has at most two tails.","An output-polynomial s-t hyperpath enumeration on BF-hypergraphs would settle the 45-year-old minimal transversal enumeration problem by solving it in output-polynomial time.","On B-hypergraphs, all S-T hyperpaths can be listed with $O(m^2 \\cdot \\|A\\|)$ delay and $O(m \\cdot \\|A\\|)$ space, which also covers minimal directed Steiner trees and minimal unsatisfiable subformulas of Horn formulas."],"supporting_citations":[{"why":"Establishes that NP-hardness of the 'another solution' problem rules out output-polynomial enumeration, the technique behind Theorems 6 and 8.","marker":"[21]"},{"why":"Supplies the backtracking (flashlight) approach and delay analysis that the positive B-hypergraph algorithm adapts to S-T hyperpaths.","marker":"[29]"},{"why":"Provides the B-connectivity formalism and the linear-time reachability routine used to find a hyperpath at each recursion step.","marker":"[7]"},{"why":"Documents the over-45-year standing of the minimal transversal enumeration problem that the BF-hypergraph reduction targets.","marker":"[16]"},{"why":"Gives the best known output-quasi-polynomial dualization algorithm, the baseline showing the target problem is not known to be easy.","marker":"[17]"},{"why":"Provides the order characterization of B-hyperpaths that underlies the definitions and Lemma 11.","marker":"[5]"}],"fun_headline_variants":["No output-polynomial algorithm for induced hyperpath or separator enumeration unless P=NP","Output-polynomial listing of hypergraph paths and minimal separators would imply P=NP","B-hypergraphs allow polynomial-delay enumeration of all s-t hyperpaths","Enumeration of hypergraph paths and separators is no easier than P=NP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the 3-SAT reductions faithfully translate satisfiability into the existence of non-trivial hyperpaths and separators; the printed separator-reduction proof has a polarity problem (true literals can leave clause tails fully present), and the induced-hyperpath proof invokes a minimality condition not present in the definition, so both need correction for the hardness theorems to stand.","fun_headline_variants_meta":{"raw":{"variants":["No output-polynomial algorithm for induced hyperpath or separator enumeration unless P=NP","Output-polynomial listing of hypergraph paths and minimal separators would imply P=NP","B-hypergraphs allow polynomial-delay enumeration of all s-t hyperpaths","Enumeration of hypergraph paths and separators is no easier than P=NP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001891,"raw_usage":{"total_tokens":7445,"prompt_tokens":1010,"completion_tokens":6435,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":6348}},"tokens_in":626,"tokens_out":6435,"duration_ms":51460,"temperature":1.0,"reasoning_tokens":6348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:43:33.792261+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the separator reduction of Lemma 7 with $\\varphi=(x_1\\lor x_2\\lor x_3)$ and the assignment $x_1=x_2=x_3=1$; with $X=\\{x_1,x_2,x_3\\}$ the clause tail $\\{\\neg x_1,\\neg x_2,\\neg x_3\\}$ is fully present in $D_\\varphi[V\\setminus X]$, so $c$ is reachable and $X$ is not a separator, directly contradicting the forward direction as printed.","supporting_citations":[{"cited_title":"Computational aspects of monotone dualization: A brief survey","cited_arxiv_id":null,"evidence_quote":"Documents the over-45-year standing of the minimal transversal enumeration problem that the BF-hypergraph reduction targets."},{"cited_title":"Fredman and Leonid Khachiyan","cited_arxiv_id":null,"evidence_quote":"Gives the best known output-quasi-polynomial dualization algorithm, the baseline showing the target problem is not known to be easy."},{"cited_title":"Partially dynamic maintenance of minimum weight hyperpaths","cited_arxiv_id":null,"evidence_quote":"Provides the order characterization of B-hyperpaths that underlies the definitions and Lemma 11."}],"review_version":1}