Suppose I have a weighted directed graph, often with symmetric links. I was to compute a maximum weight spanning DAG subgraph that is connected. I can't find any references to anything like this, an it's not obviously trivial to me.
[Math] Algorithms for maximum weighted spanning (connected) dag (directed acyclic graph)
algorithmsgraph theory
Related Solutions
It's only helpful in the dense case, not the sparse case that you're asking about, but Yuster has recently shown that the diameter of an unweighted directed graph can in fact be computed more efficiently than known algorithms for all pairs shortest paths. See his paper "Computing the diameter polynomially faster than APSP" on arXiv:1011.6181.
The examples you gave can be extended. If a graph has a transitive group then it is weighted regular. Also if the graph such that one point is connected to all other points and if that point is removed the graph remaining has a transitive group then it is weighted regular.
Also there exists graphs that are not weighted regular Look at the graph on 5 points and look at the following graph 1 is connected to all other points for $n$ equal to 2 through 4 $n$ is connected to $n+1$. Then the sum of the weights on 3 and 4 is equal to the sum of the weights on all points of the graph plus the sum of weight one. The sum of the weights on 2 and 5 is the sum the weights on 3 and 4 plus twice the weight of 1. Combining these two results forces the weight on 2 and 5 to be zero and hence not positive so not all graphs are weighted regular.
Also for any graph if a point $x$ connects only to a point $y$ then if $z$ connects to point $y$ it cannot connect to any other point t if it does since the weights of $z$ and $x$ are the same the value assigned to $y$ must equal the sum of the values assigned to $y + t$ and hence $t$ is forced to be zero. This means that the only tree which can be weighted regular is a star and the only forest one with each component a star and if any graph has a component with a vertex connected to only one point it must be a star.
The join of any two weighted regular graphs is weighted regular. Let the graphs be $G$ and $H$ with $m$ and $n$ points respectively. Let there weights assigned to each graph so that each node in each graph has the same weight. Let the weight of each node in $G$ be $w_1$ and the weight of each node in $H$ be $w_2$. Let the sum of the weights of $G$ be $w_3$ and the sum of the weights of $H$ be $w_4$. multiply the weights of $G$ by $a$ and $H$ by $b$. Then the weight of any node of $G$ in the join is $aw_1 + bw_4$ and of any node of H in the join is $aw_2 + bw_3$ so for the join to be a weighted regular graph $aw_1 + bw_4 = bw_2 + aw_3$ or $a(w_1-w_3)= b (w_2-w_4)$ or $a/b =(w_1-w_3)/(w_2-w_4)$ we can find such $a$ and $b$ iff $w_1$ is not equal to $w_3$ and $w_2$ is not equal to $w_4$.But the sum of the weights on all points is not equal to the sum of the weights on all points on graph so that condition is satisfied.
Now using the comment by Douglas Zare that the convex hull of the rows of the adjacency matrix contains a multiple of the all-1s vector we can find whether any graph is weighted regular in polynomial time. We can convert it to a linear programming problem and there algorithms such as the ellipsoid method that solve linear programming problems in a polynomial amount of time.
In this paper: "On quantum perfect state transfer in weighted join graph" available at the URL: http://arxiv.org/abs/0909.0431 the concept of a weighted regular graph is applied to perfect state transfer on quantum networks.
Best Answer
To me, this sounds like the maximization version of the minimum feedback arc set problem. The feedback arc set problem is believed to be NP-Hard, and also APX-hard. For general graphs, I believe there is a O(log n log log n) approximation algorithm in [1].
Divide-and-conquer approximation algorithms via spreading metrics G. Even, S. Naor, S. Rao, B. Shrieber Journal of the ACM, 2000.