# 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)$. – j_random_hacker 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? – BlueRaja - Danny Pflughoeft 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? – Sudix 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)$ – BlueRaja - Danny Pflughoeft 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 – Johannes Mar 27 '19 at 21:20