CODEWITHSUNDEEP
algorithmgraphtime-complexitydepth-first-searchbreadth-first-search
user15862679
user15862679

Reputation:

Finding a Minimal set of vertices that satisfy the given constraints

Note: no need for formal proof or anything, just the general idea of the algorithm and I will go deeper myself.

Given a directed graph: G(V,E), I want to find the smallest set of vertices T, such that for each vertex t in T the following edges don't exist: {(t,v) | for every v outside t} in O(V+E)

In other words, it's allowed for t to get edges from vertices outside T, but not to send.

(You can demonstrate it as phone call, where I am allowed to be called from outside and it's free but it's not allowed to call them from my side)

I saw this problem to be so close or similar to finding all strongly connected components (scc) in a directed graph which its time complexity is O(V+E) and I'm thinking of building a new graph and running this algorithm but not totally sure about that.

Upvotes: 0

Views: 228

Answers (1)

Eloy Pérez Torres
Eloy Pérez Torres

Reputation: 1177

The main idea is to contract each strongly connected component (SCC) of G into a single vertex while keeping a score on how many vertices were contracted to create each vertex in the contracted graph (condensation of G). The resulting graph is a directed acyclic graph. The answer is the vertex with lower score among the ones with out-degree equal 0.

The answer structure is an union of strongly connected components because of the restriction over edges and you can prove that there is only a SCC involved in the answer because of the min restriction.

Upvotes: 2

Related Questions