On enumerating all minimal solutions of feedback problems
We present an algorithm that generates all (inclusion-wise) minimal feedback vertex sets of a directed graph G=(V,E). The feedback vertex sets of G are generated with a polynomial delay of . We further show that the underlying technique can be tailored to generate all minimal solutions for the undirected case and the directed feedback arc set problem, both with a polynomial delay of . Finally, we prove that computing the number of minimal feedback arc sets is #P-hard.
feedback vertex sets polynomial delay feedback arc sets #p-hardness enumeration algorithm