5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note there is no reason to remove edges. $\endgroup$ – Yuval Filmus Nov 20 '19 at 19:57
  • 2
    $\begingroup$ Answered on stackoverflow: stackoverflow.com/questions/14305236/…. $\endgroup$ – Yuval Filmus Nov 20 '19 at 19:58
  • 2
    $\begingroup$ 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. $\endgroup$ – Raorm Nov 20 '19 at 22:02
  • 1
    $\begingroup$ Raom, can you edit the question to be more precise about what is allowed by a "flip/change/transplant" operation, and what isn't? $\endgroup$ – D.W. Nov 21 '19 at 2:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Optidad Nov 21 '19 at 12:45
3
$\begingroup$

On solvable instances (not all instances are solvable; see narek Bojikian's comment on my other answer for a simple necessary and sufficient condition), this is NP-hard by reduction from Directed Hamiltonian Path. The basic idea is to add enough isolated vertices to the input digraph to force the only possible solution to be a single cycle, and then see whether it is possible to accomplish this with few enough moves that the unmoved edges must form a DHP in the original digraph.

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Under the clarified definition of what moves are possible, the problem is unsolvable for many cases, e.g., the 2-vertex graph a->b. (a is not reachable from b, but the only allowed move is to change the graph to a<-b, and then b is not reachable from a.)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – narek Bojikian Nov 21 '19 at 22:58
  • 1
    $\begingroup$ @narekBojikian: That's true, but I think the first part of solving any problem is whether it can always be solved. My other answer shows this is NP-hard. $\endgroup$ – j_random_hacker Nov 21 '19 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.