# #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!!!

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