# Can the running time be reduced to something lower than $O(d^4)$?

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?

• 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)$. Mar 27 '19 at 15:54
• 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? Mar 27 '19 at 16:50
• @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? Mar 27 '19 at 19:37
• 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)$ Mar 27 '19 at 20:37
• 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 Mar 27 '19 at 21:20