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's gravatar image

Sid
531315
accept rate: 18%

edited 19 Feb '13, 02:07

Paths are supposed to be vertex-disjoint?

(19 Feb '13, 09:00) fbahr ♦

Not necessarily.

(19 Feb '13, 12:34) Sid

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.

(19 Feb '13, 16:18) fbahr ♦

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 log-weights (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.]

(19 Feb '13, 16:26) fbahr ♦

I want only one edge between 2 nodes though so no bi directional edges

(19 Feb '13, 16:31) Sid

Also log weights don't work here I think as there's an outer sum over the multiplicative weights

(19 Feb '13, 16:33) Sid

Do you require directional consistency for a sequence of arcs to be a path?

(19 Feb '13, 18:02) Paul Rubin ♦

Yes, ...10 char

(19 Feb '13, 18:03) Sid
1

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)?

(21 Feb '13, 16:57) Paul Rubin ♦

Oh, I see. The weights are over all maximal paths. So (a,d) would be a path but (a,c) would not be.

(21 Feb '13, 17:13) Sid
showing 5 of 10 show 5 more comments
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×116
×86
×17

Asked: 19 Feb '13, 02:06

Seen: 403 times

Last updated: 21 Feb '13, 17:13

OR-Exchange! Your site for questions, answers, and announcements about operations research.