Given a graph $G(V,E)$ with $n$ vertices labeled $1,2,...n$ and $m$ positively weighted edges $(u,v,w)$ with the condition that $u<v,$ $\forall u,v \in G$, so the graph we are considering is actually a DAG. We need to find an odd path from $1$ to $n$ that have the smallest weight median. i.e when the weights on the path are listed and sorted, the median of that list should be minimal.

Is it possible to solve this problem without enumerating all possible odd paths while maintaining a running median?

I have been trying to solve this problem for a couple of days and got stuck and solutions are not posted on the website.

Problem source: Problem G

  • $\begingroup$ 1. What does the notation $(u,v,w)$ represent? An edge has two endpoints, so I'm confused by why your notation has three variables. 2. What's the definition of an odd path? Is it a path whose length is odd? 3. What have you tried so far? What approaches have you considered? Can you solve simplifications of the problem (e.g., remove the "odd" constraint; or remove the "median" constraint)? Thinking about those simplifications will be instructive. $\endgroup$ – D.W. Nov 10 '17 at 7:12
  • $\begingroup$ 4. A big huge hint: suppose I claimed that there is a solution with median $x$. Could you write an algorithm to verify my claim, and check whether a path of median $x$ exists? Spend some time thinking about that, then if you're still stuck, edit the question to show us what progress you've made, which of the special cases you can solve, and what kinds of approaches you've considered. $\endgroup$ – D.W. Nov 10 '17 at 7:15

Your Answer

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

Browse other questions tagged or ask your own question.