algorithm - Find the minimum set of vertices in a DAG that disconnects a certain fraction of paths -

the problem given follows: given dag , number 0 < p ≤ 1, return minimum-cardinality set of vertices disconnects @ least p-fraction of paths source (i.e., no incoming arcs) sink (i.e., no outgoing arcs). p = 1, problem equivalent minimum cut. other values of p, however, i'm not sure answer be.

an algorithm i'm thinking of first compute min-cut set dag , try prune satisfy criteria. interesting see if subset find minimum cut-set specific p given. problem algorithm is wasteful, because computes many nodes don't need in final answer , in fact, solving "bigger" problem in first place.

any pointers solution of problem? wouldn't possible of algorithms of min-cut, put constraint early-stopping criterion?

for checking how many paths removed, suppose have indexed each vertex (and keep updated if needed) know how many paths disconnected removal. please not worry complexity of index being updated. 1 last thing, there no constraint on resulting components in terms of size or anything.

here's idea getting approximately optimal solutions.

there's variant of set cover want call partial set cover have sets , elements , want minimum number of sets union contains p-fraction of elements. apply problem, sets correspond nodes, , elements correspond maximal paths. (yes, there many paths naively; see below.) set contains element if , if node contained in path.

it's not hard write partial set cover integer program.

minimize sum_{sets s} x_s subject elements e, sum_{sets s containing e} x_s >= y_e sum_{elements e} y_e >= p * number of elements sets s, x_s in {0, 1}      # 1 if set s chosen elements e, y_e in [0, 1]  # 1 if element e covered 

this program can solved integer program solver. solvers surprisingly good, though of course cannot promise optimal solutions np-hard set cover generalization.

in interesting dag, there of course far many paths enumerated. sampling rescue! since it's easy count maximal paths in dags, it's easy sample them uniformly @ random. sample number of paths , use these elements in integer program.

the tradeoff more paths, estimate of objective better, time solve integer program worse. hoeffding's inequality gives hint proper choice of number of samples. n vertices, there 2^n possible solutions. want estimated fraction each of these accurate within epsilon. hoeffding says need choose number of samples theta(n/epsilon^2) that, of time, of estimates approximately correct. i'd work out exact constant, doubt it's practically relevant.