# Modifying digraph to make it strongly connected

I came across this problem and have not been able to find a solution.

Given directed graph $$G$$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the modified graph $$G'$$ has a path from any vertex to any other vertex. That is, we can remove any edge between any two vertices and add them back to the graph any which way.

Anyone have any idea how to solve?

Clarification for edge modification: You can edit edges any which way for a cost of one move. Once you remove an edge between any two vertices, you can reattach it to the same two vertices but flipped, or attach it to two different vertices entirely, or just have the edge go from the original source vertex to another vertex, or a different source vertex to the same destination vertex.

• Note there is no reason to remove edges. – Yuval Filmus Nov 20 '19 at 19:57
• Answered on stackoverflow: stackoverflow.com/questions/14305236/…. – Yuval Filmus Nov 20 '19 at 19:58
• The link doesn't answer the question because the question linked is adding edges. You can have an SCC in this problem that has extra edges. Note you cannot add edges, only change edges. You must remove those edges and move them elsewhere if needed. The goal is to minimize the number of ops and flips are the same as changes. – Raorm Nov 20 '19 at 22:02
• Raom, can you edit the question to be more precise about what is allowed by a "flip/change/transplant" operation, and what isn't? – D.W. Nov 21 '19 at 2:39
• Raorm should confirm it but I think that starting from a->b edge, flip gives b->a, change to c gives a->c and transplant from c gives c->b. Thus, move an edge to anywhere costs at most 1 change + 1 transplant. – Optidad Nov 21 '19 at 12:45

Given an instance of Directed Hamiltonian Path consisting of a digraph $$(V, E)$$ with $$n=|V|, m=|E|$$, add $$m-n$$ isolated vertices. Observe that a single SCC can be formed by rearranging the $$m$$ edges into an arbitrary cycle that touches each of the $$m$$ vertices that now exist. This can be done trivially if we are prepared to move all $$m$$ edges, but if we limit ourselves to moving at most $$m-n+1$$ edges, then this is possible only if $$m-n+1$$ edges are moved from somewhere to form a path that connects some vertex $$u$$ of the original digraph to some new isolated vertex, visits each new isolated vertex in some order, and finally returns to some other vertex $$v$$ of the original digraph. (We have $$u \ne v$$ since $$u=v$$ would leave just $$n-1$$ edges available to visit all $$n$$ vertices of the original digraph, which is not enough.) In this case, the unmoved $$n-1$$ edges that remain necessarily form a path from $$v$$ to $$u$$ through the $$n$$ vertices of the original digraph, and thus constitute a DHP through it. This shows that a YES answer to the constructed instance implies a YES answer to the original problem.
To see that a YES answer to the original DHP problem implies a YES answer to the constructed instance, pick up the $$m-n+1$$ edges that are not part of the DHP, and construct a path as described above, forming a single cycle comprising all $$m$$ vertices using just $$m-n+1$$ moves.
• Well solvablilty condition is easy. If $m \geq n$ we can turn the graph into a simple cycle possibley with additional edges and hence solvable. Else not. The problem is to optimize the number of edits I guess. – narek Bojikian Nov 21 '19 at 22:58