Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs

The girth of a directed graph is the length of its shortest directed cycle. We consider the problem of generating all subgraphs of girth at least g in a directed graph G with n vertices and m edges. This generalizes the problem of generating acyclic subgraphs (i.e., with no directed cycle), that correspond to the subgraphs of girth at least n+ 1. The problem of finding the acyclic subgraph with maximum size or weight has been thoroughly studied, however to the best of our knowledge there is no known efficient enumeration algorithm. We propose polynomial delay algorithms for listing both induced and edge subgraphs with girth g in time O(n) per solution; both improve upon a naive solution, respectively by a factor O(nm) and O(m2). Furthermore, this work is on the line of existing research for extracting acyclic structures from graphs.