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?V s , t ? V , and let F F be an intersecting family on V V (that is, X?Y,X?Y?F X ? Y , X ? Y ? F for any intersecting X,Y?F X , Y ? F ) so that s?X s ? X and t?X t ? X for every X?F X ? F . An edge set I?E I ? E is an edge-cover of F F if for every X?F X ? F there is an edge in I I from X X to V?X V ? X . We show that minimal edge-covers of F F can be listed with polynomial delay, provided that, for any I?E I ? E the minimal member of the residual family FI F I of the sets in F F not covered by I I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k k -connected and k k -outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.
listing minimal edge-covers intersecting families steiner network