Pith. sign in

REVIEW 3 major objections 5 minor 35 references

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.07528 v1 pith:W2PQCT4A submitted 2025-07-10 cs.DS cs.CC

Kazuhiro Kurita , Kevin Mann This is my paper · ORCID
classification cs.DScs.CC
keywords output-sensitiveenumerationdirectedhypergraphss-thyperpathminimalseparatorNP-hardnesspolynomialdelayB-hypergraphtransversal
topics P versus NP
open problems P versus NP
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 2, definition of induced s-t hyperpath, and Lemma 5] 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.
  2. [Section 3.2, Lemma 7, reverse direction] 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.
  3. [Section 3.2, Lemma 7, forward direction] 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.
minor comments (5)
  1. [Section 3.1, Lemma 5 proof] 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.
  2. [Section 3.1, Lemma 5 proof] 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.
  3. [Problems 2 and 4, Section 3.2] 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.
  4. [Section 3.2, tail-size reduction] 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.
  5. [Section 3.3, Lemma 9 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the hardness reductions and polynomial-delay algorithm are derived directly from explicit constructions and proven bijections; self-citations are contextual and not load-bearing.

full rationale

The derivation chain is self-contained. The hardness results reduce 3-SAT directly to 'Another Induced s-t hyperpath' (Lemma 5, Theorem 6) and to 'Another Minimal s-t Separator' (Lemma 7, Theorem 8); neither reduction fits any model parameter to data, and the 'another solution' argument is a standard folklore reduction from NP-hardness rather than a prediction drawn from a fitted value. The conditional result connecting s-t hyperpath enumeration on BF-hypergraphs to minimal transversal enumeration (Lemma 9, Theorem 10) is an explicit bijective reduction: the construction from a hypergraph H to a BF-hypergraph D_H is given, and the bijection is proven in both directions. This is not a renaming of a known result presented as a prediction, but a genuine reduction with a stated open-problem consequence. The positive enumeration algorithm (Algorithm 1, Theorems 11-13) is proved by a partition argument and a bijection lemma; it does not assume output-polynomial time for the target problem, and its correctness does not rely on the conclusion it establishes. Self-citations (for example [13] and [24]) are contextual references to prior enumeration hardness results and algorithms; the present proofs do not invoke an unverified uniqueness theorem or adopt a substantive ansatz from the authors' prior work. One caveat is a definitional/correctness issue rather than circularity: the Section 2 definition of an induced s-t hyperpath as a vertex set in which t is B-connected omits minimality, while Lemma 5 invokes minimality, and Lemma 7's separator reduction has a directional flaw as written. These are proof defects that may be repairable, but they do not make any derivation equivalent to its own input and they do not involve fitting, self-citation chains, or definitional identity between premise and conclusion. Therefore no significant circularity is present, and the score is 0.

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

All central claims are derived from the definitions of B-connectivity and output-sensitive complexity; there are no fitted parameters, no fitted constants, and no ad hoc entities. The reductions use standard complexity assumptions and cited subroutines.

assumptions (4)
  • domain assumption P != NP
    The hardness results are conditional on P != NP, as stated in Theorems 6 and 8.
  • domain assumption B-connectivity is the adopted connectivity notion for directed hypergraphs
    All path and separator definitions in Section 2 depend on B-connectivity (forward chaining) rather than alternative hypergraph connectivity notions.
  • standard math NP-completeness of the Another Solution problem excludes output-polynomial enumeration unless P=NP
    Used in Section 3 to convert NP-hardness of Another Induced s-t Hyperpath and Another Minimal s-t Separator into non-existence of output-polynomial enumeration algorithms; standard folklore argument.
  • domain assumption B-connectivity can be checked in O(m||A||) time
    Used in Theorem 13's delay analysis, attributed to the survey [7].

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs." pith.science (2026). https://pith.science/paper/W2PQCT4A

@misc{pith2026250707528,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W2PQCT4A}},
  note         = {Machine review of arXiv:2507.07528}
}
abstract

In this paper, we address the enumeration of (induced) $s$-$t$ paths and minimal $s$-$t$ separators. These problems are some of the most famous classical enumeration problems that can be solved in polynomial delay by simple backtracking for a (un)directed graph. As a generalization of these problems, we consider the (induced) $s$-$t$ hyperpath and minimal $s$-$t$ separator enumeration in a \emph{directed hypergraph}. We show that extending these classical enumeration problems to directed hypergraphs drastically changes their complexity. More precisely, there are no output-polynomial time algorithms for the enumeration of induced $s$-$t$ hyperpaths and minimal $s$-$t$ separators unless $P = NP$, and if there is an output-polynomial time algorithm for the $s$-$t$ hyperpath enumeration, then the minimal transversal enumeration can be solved in output polynomial time even if a directed hypergraph is $BF$-hypergraph. Since the existence of an output-polynomial time algorithm for the minimal transversal enumeration has remained an open problem for over 45 years, it indicates that the $s$-$t$ hyperpath enumeration for a $BF$-hypergraph is not an easy problem. As a positive result, the $s$-$t$ hyperpath enumeration for a $B$-hypergraph can be solved in polynomial delay by backtracking.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 28 canonical work pages

  1. [1]

    Petri nets, hypergraphs and conflicts (preliminary version)

    Paola Alimonti and Esteban Feuerstein. Petri nets, hypergraphs and conflicts (preliminary version). In Ernst W. Mayr, editor, Graph-Theoretic Concepts in Computer Science , pages 293--309, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg

    work page 1993

  2. [2]

    Linear time analysis of properties of conflict-free and general petri nets

    Paola Alimonti, Esteban Feuerstein, Luigi Laura, and Umberto Nanni. Linear time analysis of properties of conflict-free and general petri nets. Theoretical Computer Science , 412(4):320--338, 2011. URL: https://www.sciencedirect.com/science/article/pii/S0304397510005335, https://doi.org/10.1016/j.tcs.2010.09.030 doi:10.1016/j.tcs.2010.09.030

    work page doi:10.1016/j.tcs.2010.09.030 2011

  3. [3]

    Linear time algorithms for liveness and boundedness in conflict-free petri nets

    Paola Alimonti, Esteban Feuerstein, and Umberto Nanni. Linear time algorithms for liveness and boundedness in conflict-free petri nets. In Imre Simon, editor, LATIN '92 , pages 1--14, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg

    work page 1992

  4. [4]

    On the complexity of strongly connected components in directed hypergraphs

    Xavier Allamigeon. On the complexity of strongly connected components in directed hypergraphs. Algorithmica , 69(2):335--369, 2014. https://doi.org/10.1007/s00453-012-9729-0 doi:10.1007/s00453-012-9729-0

    work page doi:10.1007/s00453-012-9729-0 2014

  5. [5]

    Partially dynamic maintenance of minimum weight hyperpaths

    Giorgio Ausiello, Paolo Giulio Franciosa, and Daniele Frigioni. Partially dynamic maintenance of minimum weight hyperpaths. Journal of Discrete Algorithms , 3(1):27--46, 2005. URL: https://www.sciencedirect.com/science/article/pii/S1570866703000893, https://doi.org/10.1016/j.jda.2003.12.005 doi:10.1016/j.jda.2003.12.005

    work page doi:10.1016/j.jda.2003.12.005 2005

  6. [6]

    Italiano, Luigi Laura, Umberto Nanni, and Fabiano Sarracco

    Giorgio Ausiello, Giuseppe F. Italiano, Luigi Laura, Umberto Nanni, and Fabiano Sarracco. Structure theorems for optimum hyperpaths in directed hypergraphs. In A. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, and Vangelis Th. Paschos, editors, Combinatorial Optimization , pages 1--14, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg

    work page 2012

  7. [7]

    Directed hypergraphs: Introduction and fundamental algorithms―a survey

    Giorgio Ausiello and Luigi Laura. Directed hypergraphs: Introduction and fundamental algorithms―a survey. Theoretical Computer Science , 658:293--306, 2017. Horn formulas, directed hypergraphs, lattices and closure systems: related formalism and application. URL: https://www.sciencedirect.com/science/article/pii/S0304397516002097, https://doi.org/10.1016/...

    doi:10.1016/j.tcs.2016.03.016 2017

  8. [8]

    Generating clause sequences of a cnf formula

    Krist^^c3^^b3f B^^c3^^a9rczi, Endre Boros, Ond^^c5^^99ej ^^c4^^8cepek, Khaled Elbassioni, Petr Ku^^c4^^8dera, and Kazuhisa Makino. Generating clause sequences of a cnf formula. Theoretical Computer Science , 856:68--74, 2021. URL: https://www.sciencedirect.com/science/article/pii/S0304397520307246, https://doi.org/10.1016/j.tcs.2020.12.021 doi:10.1016/j.t...

    work page doi:10.1016/j.tcs.2020.12.021 2021

Show all 35 references
  1. [9]

    Output-sensitive complexity of multiobjective combinatorial optimization

    Fritz B^^c3^^b6kler, Matthias Ehrgott, Christopher Morris, and Petra Mutzel. Output-sensitive complexity of multiobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis , 24(1-2):25--36, 2017. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/mcda....

    2017 doi

  2. [10]

    Generating all the minimal separators of a graph

    Anne Berry, Jean Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci. , 11(3):397--403, 2000. https://doi.org/10.1142/S0129054100000211 doi:10.1142/S0129054100000211

    doi

  3. [11]

    Optimal listing of cycles and st-paths in undirected graphs

    Etienne Birmel \' e , Rui Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. Optimal listing of cycles and st-paths in undirected graphs. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete A...

    2013

  4. [12]

    Generating minimal redundant and maximal irredundant subhypergraphs

    Endre Boros and Kazuhisa Makino. Generating minimal redundant and maximal irredundant subhypergraphs. Discret. Appl. Math. , 358:217--229, 2024. URL: https://doi.org/10.1016/j.dam.2024.07.006, https://doi.org/10.1016/J.DAM.2024.07.006 doi:10.1016/J.DAM.2024.07.006

    2024 doi

  5. [13]

    On the hardness of inclusion-wise minimal separators enumeration

    Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa. On the hardness of inclusion-wise minimal separators enumeration. Inf. Process. Lett. , 185:106469, 2024. URL: https://doi.org/10.1016/j.ipl.2023.106469, https://doi.org/10.1016/J...

    2024

  6. [14]

    On finding hypercycles in chemical reaction networks

    Can ^^c3^^96zturan. On finding hypercycles in chemical reaction networks. Applied Mathematics Letters , 21(9):881--884, 2008. URL: https://www.sciencedirect.com/science/article/pii/S0893965907002844, https://doi.org/10.1016/j.aml.2007.07.031 doi:10.1016/j.aml.2007.07.031

    2008 doi

  7. [15]

    On the enumeration of signatures of xor-cnf's

    Nadia Creignou, Oscar Defrain, Fr \' e d \' e ric Olive, and Simon Vilmin. On the enumeration of signatures of xor-cnf's. CoRR , abs/2402.18537, 2024. URL: https://doi.org/10.48550/arXiv.2402.18537, https://arxiv.org/abs/2402.18537 arXiv:2402.18537 , https://doi.org/10.48550/A...

    2024 doi arXiv

  8. [16]

    Computational aspects of monotone dualization: A brief survey

    Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey. Discrete Applied Mathematics , 156(11):2035--2049, 2008. In Memory of Leonid Khachiyan (1952 - 2005 ). URL: https://www.sciencedirect.com/science/article/pii/S01662...

    2008 doi

  9. [17]

    Fredman and Leonid Khachiyan

    Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms , 21(3):618--628, 1996. URL: https://www.sciencedirect.com/science/article/pii/S0196677496900620, https://doi.org/10.1006/jagm.1996.0062 doi:10...

    1996

  10. [18]

    Max Horn SAT and the minimum cut problem in directed hypergraphs

    G Gallo, C Gentile, D Pretolani, and G Rago. Max Horn SAT and the minimum cut problem in directed hypergraphs . Mathematical Programming , 80(2):213--237, 1998. https://doi.org/10.1007/BF01581727 doi:10.1007/BF01581727

    1998 doi

  11. [19]

    Directed hypergraphs and applications

    Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics , 42(2):177--201, 1993. URL: https://www.sciencedirect.com/science/article/pii/0166218X9390045P, https://doi.org/10.1016/0166-218X(93)90045-P...

    1993

  12. [20]

    Directed hypergraphs as a modelling paradigm

    Giorgio Gallo and Maria Grazia Scutell \` a . Directed hypergraphs as a modelling paradigm. Rivista di matematica per le scienze economiche e sociali , 21(1):97--123, 1998. https://doi.org/10.1007/BF02735318 doi:10.1007/BF02735318

    1998 doi

  13. [21]

    Johnson, Mihalis Yannakakis, and Christos H

    David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters , 27(3):119--123, 1988. URL: https://www.sciencedirect.com/science/article/pii/0020019088900658, https://doi.org/10.1016/0020-0190(88...

    1988

  14. [22]

    Elbassioni, and Vladimir Gurvich

    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich. On enumerating minimal dicuts and strongly connected subgraphs. Algorithmica , 50(1):159--172, 2008. URL: https://doi.org/10.1007/s00453-007-9074-x, https://doi.org/10.1007/S00453-007-9074-X doi:10.1007...

    2008 doi

  15. [23]

    Efficiently enumerating results of keyword search over data graphs

    Benny Kimelfeld and Yehoshua Sagiv. Efficiently enumerating results of keyword search over data graphs. Information Systems , 33(4):335--359, 2008. Selected Papers from the Tenth International Symposium on Database Programming Languages (DBPL 2005. URL: https://www.sciencedire...

    2008 doi

  16. [24]

    Linear-delay enumeration for minimal Steiner problems

    Yasuaki Kobayashi, Kazuhiro Kurita, and Kunihiro Wasa. Linear-delay enumeration for minimal Steiner problems. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '22, page 301^^e2^^80^^93313, New York, NY, USA, 2022. Associatio...

    2022

  17. [25]

    Shortest hyperpaths in directed hypergraphs for reaction pathway inference

    Spencer Krieger and John Kececioglu. Shortest hyperpaths in directed hypergraphs for reaction pathway inference. Journal of Computational Biology , 30(11):1198--1225, 2023. PMID: 37906100. https://arxiv.org/abs/https://doi.org/10.1089/cmb.2023.0242 arXiv:https://doi.org/10.108...

    2023

  18. [26]

    Efficient enumerations for minimal multicuts and multiway cuts

    Kazuhiro Kurita and Yasuaki Kobayashi. Efficient enumerations for minimal multicuts and multiway cuts. In Javier Esparza and Daniel Kr \' a l', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech R...

    2020 doi

  19. [27]

    A remark on the definition of a B -hyperpath

    Lars Relund Nielsen, Daniele Pretolani, and K Andersen. A remark on the definition of a B -hyperpath. Technical report, Department of Operations Research, University of Aarhus, Tech. Rep, 2001

    2001

  20. [28]

    Scott Provan and Douglas R

    J. Scott Provan and Douglas R. Shier. A paradigm for listing (s, t) -cuts in graphs. Algorithmica , 15(4):351--372, 1996

    1996

  21. [29]

    R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks , 5(3):237--252, 1975. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.1975.5.3.237, https://arxiv.org/abs/https://onlinelibrary.wiley.com/doi/pdf/10.10...

    1975 doi

  22. [30]

    R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks , 5(3):237--252, 1975

    1975

  23. [31]

    Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph

    Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discrete Applied Mathematics , 158(15):1660--1667, 2010

    2010

  24. [32]

    Linear connectivity problems in directed hypergraphs

    Mayur Thakur and Rahul Tripathi. Linear connectivity problems in directed hypergraphs. Theoretical Computer Science , 410(27):2592--2618, 2009. URL: https://www.sciencedirect.com/science/article/pii/S0304397509002011, https://doi.org/10.1016/j.tcs.2009.02.038 doi:10.1016/j.tcs...

    2009 doi

  25. [33]

    An algorithm to enumerate all cutsets of a graph in linear time per cutset

    S Tsukiyama, I Shirakawa, H Ozaki, and H Ariyoshi. An algorithm to enumerate all cutsets of a graph in linear time per cutset. Journal of the ACM , 27(4):619--632, oct 1980. URL: http://portal.acm.org/citation.cfm?doid=322217.322220, https://doi.org/10.1145/322217.322220 doi:1...

    1980

  26. [34]

    An efficient algorithm for enumerating chordless cycles and chordless paths

    Takeaki Uno and Hiroko Satoh. An efficient algorithm for enumerating chordless cycles and chordless paths. In Proc. DS 2014 , pages 313--324. Springer, 2014

    2014

  27. [35]

    Volpentesta

    Antonio P. Volpentesta. Hypernetworks in a directed hypergraph. European Journal of Operational Research , 188(2):390--405, 2008. URL: https://www.sciencedirect.com/science/article/pii/S0377221707004171, https://doi.org/10.1016/j.ejor.2007.04.023 doi:10.1016/j.ejor.2007.04.023

    2008 doi

Pith tools

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