5
$\begingroup$

Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.

Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:

enter image description here

The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.

One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.

My question is the following: could we do better than brute-forcing all possibilities?

$\endgroup$
3
$\begingroup$

Hints:

When you remove an edge from the graph, you split it into two trees.

Given a tree, can you find the longest path in that tree? (It's not hard.)

Given two trees, can you find which edge to add to make the longest path in the resulting graph as long as possible? (Hint: first find the longest path in each of the two trees. Then..)

This is your exercise, so I'll let you take it from here. That should give you plenty to work with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.