CODEWITHSUNDEEP
algorithmdata-structurestreegraph-theorycomplexity-theory
Abc
Abc

Reputation: 11

Spanning disjoint trees in directed bipartite graphs

Assume we have a directed bipartite graph G with two partitions, A and B. All the edges are assumed to start from A and end in B . Assume that every vertex has at least one adjacent edge. I want to span all the vertices of B with disjoint trees where the maximum number of edges of a tree in this disjoint tree set is minimized. The question is, what is the maximum number of edges of a tree in that set? (Notice that a tree starts from a vertex in A and may end in multiple vertices of B, but because the graph is directed, there can be only one vertex from A in each tree.) Ultimately, every vertex in B must have an adjacent edge in one of the disjoint trees.

I couldn't find an equivalent problem in the literature. Does anyone have an idea? What kind of problem is this, and is it NP-complete or NP-hard?

Upvotes: 1

Views: 58

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

"The question is, what is the maximum number of edges of a tree in that set?"

"All the edges are assumed to start from A and end in B."

So, there are no connections between vertices in a partition.

For a feasible answer to exist, every B vertex must have a connection from an A vertex and the maximum number of edges in a tree cannot be larger than the number of edges originating at an A vertex. This applies whatever algorithm is used to generate the tree set.

If an algorithm is used to generate the tree set that is guaranteed to generate a set where the maximum number of edges of any tree in this disjoint tree set is minimized, then the maximum number of edges in a tree cannot be larger than

maxEdgeCount =  minimum (
               excess number of vertices in B compared to A,
               greatest number of edges originating at a single A vertex )

Upvotes: 0

Related Questions