1
$\begingroup$

Problem statement

We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. The price of an SCC is defined to be the sum of the weights of its vertices.

In the example below, reversing an edge $(7, 1)$ would create an SCC $(0,1,2,3,4,7)$ whose price is $27$ which is the maximal price.

If there are more edges whose reversion would result in the same maximal price, return the one with the lowest ID.

Example

Observations

  1. The graph is acyclic; therefore every vertex is an SCC.
  2. We only need to try reverting outgoing edges because of the symmetry (obviously), but let's only focus on them.
  3. By reverting an outgoing edge of a vertex $v$, sometimes we create an SCC, sometimes we don't. If we do, that is because we created a loop somewhere. Furthermore, the vertex $v$ must be a part of the newly created SCC and there is only one SCC that can be created.
  4. Given a certain vertex, we only need to test reverting its outgoing edges if its out-degree is at least $2$. If it was only $1$, reverting it would make it zero which wouldn't create any new loops.
  5. Given a vertex $(e_1, e_2)$, we only need to test reverting its outgoing edge if such reversion would create a cycle. That could happen only if there was another outgoing edge (implying the last point) through which we could reach $e_2$. Looking at the example, we see that the vertex $(7, 1)$ is worth trying to revert because there is another way $(7-0-1)$ of getting to the vertex $1$ (a loop would be closed by the reversion).
  6. When checking for an SCC created by an edge reversion of a vertex $v$, we may use Tarjan's DFS only for $v$ since it is guaranteed to be a part of the SCC.

Algorithm proposal

For each vertex $v$ whose out-degree is at least two, run Tarjan's algorithm which only checks for the SCC from that point. If there is an SCC, calculate its value (can be done during the search for an SCC) and compare it to the best found yet and remember the best edge.

Time complexity is $O(V \cdot E \cdot (V + E))$ since we go through all vertices, going through all the edges and firing a Tarjan's algorithm at each one of them (in the worst case).

Question

Is there a faster way? Both in terms of reducing the number of edges that need to be checked and asymptotically. I'm not sure how to utilize the fifth observation as the DFS to find all the reachable vertices would only make it slower.

Improve this question
$\endgroup$
3
  • $\begingroup$ Also could you credit the source where you got this problem? $\endgroup$
    – Nathaniel
    Commented Jan 3, 2023 at 15:09
  • $\begingroup$ Going through all the vertices is $V$. For every vertex, we visit its every edge. The maximum number of edges per vertex is dependent on $|E|$, therefore, asymptotically, times $E$. And everytime, we run Tarjan's algorithm in $O(V + E)$, so all of it times $(V + E)$. The problem is from a website gathering algortihm problems from an algorithms course in my university - I have no direct source. There were only this example image and two sentences describing the problem. $\endgroup$
    – tomashauser
    Commented Jan 3, 2023 at 15:19
  • $\begingroup$ I guess I don't understand how to reduce the expression in $O$ if it has two parameters then. Ignore it, I'll delete it. $\endgroup$
    – tomashauser
    Commented Jan 3, 2023 at 15:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.