CODEWITHSUNDEEP
algorithmgraph-algorithm
user5083166
user5083166

Reputation:

How do I explore a directed graph (DAG) by visting minimum number of starting vertices?

Given a DAG (possibly not strongly connected e.i consisting of several connected components), the goal is to find the minimum number of starting vertices required to visit to fully explore the graph.
One method I thought of was to generate all permutations of the given vertices and run a topological sort in that order. The one with the minimum backtracks would be the answer.
Is there an efficient algorithm to perform the above task?

Upvotes: 2

Views: 430

Answers (1)

throwit
throwit

Reputation: 714

This a famous problem called minimum path cover, it's a pity that wiki says nothing about it, you can search it in google.

As methioned, the minimum path cover problem is NP-hard in normal graph. But in DAG, it can be solved with Matching.

Method:

Dividing each vertex u into two different vertex u1 and u2. For every edge (u->v) in orginal graph, adding edge (u1->v2) in new graph. Then do any matching algorithm you like. The result is n - maximum matching, n is total number of vertex in orginal graph.

Upvotes: 3

Related Questions