Listing minimal edge-covers of intersecting families with applications to connectivity problems

Let G=(V,E)G=(V,E) be a directed/undirected graph, let s,t∈Vs,t∈V, and let FF be an intersecting family on VV (that is, X∩Y,X∪Y∈FX∩Y,X∪Y∈F for any intersecting X,Y∈FX,Y∈F) so that s∈Xs∈X and t∉Xt∉X for every X∈FX∈F. An edge set I⊆EI⊆E is an edge-cover of FF if for every X∈FX∈F there is an edge in II from XX to V−XV−X. We show that minimal edge-covers of FF can be listed with polynomial delay, provided that, for any I⊆EI⊆E the minimal member of the residual family FIFI of the sets in FF not covered by II can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal kk-connected and kk-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.