Enumerating all source-sink hyperpaths
Overview
Our hyperpath enumeration algorithm maintains a queue of hyperpath problem instances consisting of keep-sets and out-sets. An out-set for a problem instance is a set of hyperedges that are not allowed to be in the solution. A keep-set is a set of hyperedges that cannot be placed in the out-set of child problem instances spawned from the current instance. Together, these sets ensure that the solution to a problem instance is never computed twice.Note that this method differs from the technique of inclusion and exclusion of Hamacher and Queyranne. Their method makes use of an in-set instead of a keep-set, which ensures that no solution is ever computed twice. Interestingly, determining whether an s,t-hyperpath exists that contains a specified in-set is already NP-complete, so we instead use a keep-set.