I've a problem where I've a complete digraph \(G\) and edge weights \(0 \leq w_i\leq 1\) s.t. the weight of each path is the multiplication of the edge weights on that path. The objective is to select a maximum weight digraph  where the weight is the sum of the weights of all the paths in the digraph  s.t. there's only one edge between two nodes. Is this a known problem (for instance maybe some variant of feedback arc set)? If it is not known, are there any problems that are related to it? asked 19 Feb '13, 02:06 Sid
showing 5 of 10
show 5 more comments

Paths are supposed to be vertexdisjoint?
Not necessarily.
Usually, a digraph is called complete iff every pair of nodes is connected by a bidirectional edge. If this fits your case, imho, you don't have a "problem" at all: your graph already is its max weight "subgraph".
If edges are unidirected – and paths are not required to be disjoint – a simple check for connectedness should reveal the max weight subgraph.
If you restrict yourself to paths btw. two nodes \(s, t\), you also have to take reachability into account – yet, still easy.
If I'm missing an important point here (which probably is the case) – feel free to let me know!
PS, for the sake of completeness: in general, the problem of multiplicative weights in "path problems" can be avoided by using logweights (i.e., define the weights of paths as sums of the logs of arc weights instead of multiplications of the original arc weights; results are equivalent). [...which, again, you probably already know.]
I want only one edge between 2 nodes though so no bi directional edges
Also log weights don't work here I think as there's an outer sum over the multiplicative weights
Do you require directional consistency for a sequence of arcs to be a path?
Yes, ...10 char
Are paths defined to run from a single specified source node to a single specified sink? If not, does inclusion of arcs (a,b), (b,c) and (c,d) mean that (a,b), (a,c), (a,d), (b,c), (b,d) and (c,d) are treated as six separate paths (all contributing to the objective)?
Oh, I see. The weights are over all maximal paths. So (a,d) would be a path but (a,c) would not be.