# Finding the heaviest theoretical subpath of size ($n/2$), given a required cycle of size $n$ in a directed,weighted graph.

Let's say we have a graph of size 10. So, we have nodes $\{0,1,2,3,4,5,6,7,8,9\}$.

For the sake of keeping this problem under a certain level of complexity, accept that we somehow know that edges going out of node $0$ are always heavier than node $1$, and edges going out of node $1$ are always heavier than node $2$, etc etc, in a way where we don't need to worry about what the actual weights are. So, we know that for any given node, it's edges are lighter than the edges of all nodes with a lower value.

So my question is, given this value "$n$" that determined the numbers of nodes in our cycle, for any cycle of size n made from these nodes, what is the worst subpath of size $(n/2)$ that we can have?

It clearly is not $$0 \to 1 \to 2 \to 3 \to \cdots \to (n/2),$$ because if we have this configuration in our cycle then we could just start at $(n/2)$ and choose the subpath: $$\tfrac{n}{2} \to (\tfrac{n}{2} +1) \to \cdots \to n$$

So, there must be some scheme by which it balances out such that if you take the best possible subpath in the cycle, it will contain certain nodes relative to our value $n$. But, I do not know how to figure it out.

Good luck and thank you!

• This is very confusing. 1) Is this a directed graph? 2) Why should it have any cycles at all? 3) What is $n$? I don't think you're describing your problem completely. – saulspatz Feb 15 '18 at 17:52
• By "fully connected graph" do you mean that there is an edge between every pair of nodes? If so, can there be an edge in each direction? That is, can we have an edge $ab$ and also an edge $ba$ or must it be one or the other? – saulspatz Feb 15 '18 at 18:16