Problem :
Given a directed acyclic graph and capacity of every edge. Let S be set of all Max flows ( sum of flows of outgoing edges is maximum ), find the flow among S with the minimum positive-flow edges OR maximum zero flow edges.
The problem is NP Hard.
I was trying to think of heuristics to approximate the sparsest max flow with a good bound but couldn't find any. The topic seems interesting but less explored. I would appreciate any kind of insights from others or already done research in this area.
Auto comment: topic has been updated by sharvil_cpp (previous revision, new revision, compare).
Youknowwho academy has some good problems in the graphs section and contains many problems of flows
Thank you for the tip but I want heuristics of the above problem which is NP hard.
You can try reducing some edges(randomly might give more weightage to small edges) to zero(removing them) and then running the Max Flow algorithm.
For me, randomization sometimes worked very well, I wish you good luck with that.
One other thing you might try is to assign a preference to each edge (or might be probabilities) that during the max flow, with some probability P, you will visit edge (u, v) among all the possible choices.
One idea that came to my mind is this: find what the max flow I can get from the source to this vertex is, and what is the max flow that can reach from this vertex to the sink. And use them to assign the priority to edges. One way might be for some vertex, I will give more priority to an edge that goes to a vertex that can lead to more flow, and among them, I will choose the one with max capacity. You might try assigning them a single value based on these two, like $$$val_i = w_i * 0.7 + in_u * 0.15 + out_v * 0.15$$$ if edge i is (u, v).
That is insightful. We also need some kind of randomisation... As the choice can't be greedy based on the val function you gave. maybe choose some top k candidates from these and try all. something like that or do a Monte Carlo tree search with your way of reward. .
How is this for an idea ?
lets say we find an undirected cycle. that is a->b->c->d and a->e->d. The undirected cycle is a b c d e a. I can convert the flow without changing source to sink flows by making it a->b->c->e->d. and adding the c->d flow to c->e and e->d. This reduced my edge by 1 whilst keeping the same flow. I can do this till I remove all the cycles ?