4
$\begingroup$

Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following:

  1. Set $D$ to be a DAG with the same set of vertices but without any edges
  2. sort the edge weights $c_{ji}$ of the original graph by size
  3. From the biggest to the lowest edge weight: Add an edge $(j,i)$ to the DAG $D$ if we do not cause a cycle with it

Now I see two approaches to implement this.the first one is:

  1. Set $D$ to be a DAG with the same set of vertices but without any edges
  2. sort the edge weights $c_{ji}$ of the original graph by size
  3. From the biggest to the lowest edge weight: Add an edge $(j,i)$ to the DAG $D$ if there is no path from $i$ to $j$

Now sorting can be neglected in complexity ( $O(d^2\log(d))$)

And number three is performed at most $d(d-1)$ times and to check if a path exists we can use BFS or DFS and the number of edges, unfortunately, can be as big as $d^2$ so we have $d^4$ in total

My second idea: Work with a reachability matrix and update the reachability matrix in every iteration of the loop... But then updating the reachability matrix is again of complexity $d^2$ because if we set an edge from $j$ to $i$ then denoting the ancestors of $j$ by $k_1$ and the descendants of $i$ by $k_2$ we need to set $R(u,w)=1$, $R(u,i)=1$, $R(j,w)=1$ for any $u$ in $k_1$ and $w$ in $k_2$ .... Assuming that in the worst case that each of $k_1$ and $k_2$ have $d/2-1$ vertices we get a complexity of $d^2$ That we need to update the reachability matrix more than $O(d)$ times can e.g. be seen by looking at bipartite graphs... So I'm again stuck with the same complexity... Is there actually a more efficient solution?

$\endgroup$
  • 4
    $\begingroup$ The bottommost link in this excellent answer to a similar question promises to make adding edges to a DAG and checking for connectivity both amortised $O(d)$-time operations, bringing the overall complexity down to $O(d^3)$. $\endgroup$ – j_random_hacker Mar 27 at 15:54
  • $\begingroup$ For undirected graphs, this algorithm is called Kruskal's algorithm and returns the minimum spanning tree. But a different algorithm must be used for MSTs in directed graphs. Is that what you're attempting to find, or do you really want the "almost MST" graph returned by this algorithm? $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 27 at 16:50
  • 2
    $\begingroup$ @Johannes This method does not necessarily produce a MST analogue for directed, weighted graphs, as the edgeweight of the resulting acyclic graph needn't be maximal. Are you sure you don't want it to be maximal? $\endgroup$ – Sudix Mar 27 at 19:37
  • 3
    $\begingroup$ My (and @Sudix's) point was that you appear to be looking for the MST, but this algorithm only does that for undirected graphs. If so, it's not NP-hard. Chu-Liu's algorithm solves it in $O(d^3)$ $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 27 at 20:37
  • 1
    $\begingroup$ You are talking about Optimum branching I assume... of course the solution I am talking about is not a solution for the optimal branching because in my case I can get a complete DAG whereas Optimum branching I have $d-1$ edges - but thank you very much for this remark $\endgroup$ – Johannes Mar 27 at 21:20

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.