#StackBounty: #ds.algorithms Add edges to a DAG to maximize increase in number of connected vertices

Bounty: 250

Let $G$ be a Directed Acyclic Graph.

$$C(G) = bigl|{(u,v):u,vin V(G),v text{ reachable from } u}bigr|$$

Goal is to add $k$ edges in a DAG such that for the new $G’$, $C(G’)$ is maximized.

My idea is as follows. DAG is given so, we can assume that it is bipartite graphs with $S$ called source and $T$ will be called as sinks. $(|S||T|)^{k}$ time algorithm seems working as per my calculation. A vertex is called as source if all edges it have are outgoing and a vertex is called sink if all edges it have are incoming.

What is the fastest algorithm for this problem?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.