3
$\begingroup$

I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$.

Goal: Find the topological order such that the smallest edge weight of the complete DAG that corresponds to the topological order is maximized.

Example: Imagine we have 3 nodes and the topological order $\pi:=(1,2,3)$; then the complete DAG is the subgraph of $G$ with vertices 1,2 and 3 and edge weights $c_{12}$, $c_{13}$ and $c_{23}$. If $\pi_2:=(1,3,2)$, then the complete DAG is the subgraph of $G$ with vertices 1,2 and 3 and edge weights $c_{13}$, $c_{12}$ and $c_{32}$. I am looking for the topological order of vertices such that the minimum value of the corresponding DAG is maximized. So in our example for $\pi:=(1,2,3)$ we get the value $\min(c_{12},c_{13},c_{23})$, for $\pi_2:=(1,3,2)$ we get the value $\min(c_{13},c_{12},c_{32})$.

We are looking for a topological order such that the value is maximized. There may be more than one valid solution.

Is there an efficient algorithm for this problem?

More precisely, we can formulate the optimization problem as follows. Let $\Pi$ denote all possible topological orders of the nodes $\{1, \ldots, d\}$. Then what I want is

$$\text{arg}\max_{\pi \in \Pi}\min\limits_{(i,j) \in E: \\ \pi(i)<\pi(j)}c_{ij},$$

where $\pi(i)$ denotes the position of node $i$ in the topological order.

$\endgroup$
4
  • 1
    $\begingroup$ You're right. My proposed answer doesn't work. Sorry about all of my erroneous answers. $\endgroup$ – D.W. Jan 24 '20 at 16:10
  • $\begingroup$ Don't worry... I actually felt flattered - discovering a wrong answer from someone of your reputation is certainly nothing that happens every day :-) But let me just ask one thing: You have never seen any comparable optimization problem? Something I could check? I am not so much interested in the complexity but more in a similar problem $\endgroup$ – Johannes Jan 24 '20 at 19:26
  • 1
    $\begingroup$ Thanks for the kind words! I haven't seen anything that comes to mind, but I'm not very knowledgeable about these topics, so that might not mean much. (Rep probably tells you more about quantity of participation on the site than expertise....) $\endgroup$ – D.W. Jan 25 '20 at 0:00
  • $\begingroup$ Well in order to be active (and answer questions) you need to be knowledgeable in the first place.. I could barely answer a single of these questions so you do have lots of expertise, I am sure... $\endgroup$ – Johannes Jan 25 '20 at 1:48

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.