Hello

I need Help please in this graph problem

I think you all know the minimum path cover problem in a DAG

You are given a DAG and you have to compose it into K paths so that every vertex must belong to exactly one path

So you have to find a solution where K is minimum

This can be solved by maximum matching.

But what if the vertex can belong to more than one path in the composition ???

For further understanding ... let's imagine this DAG

1->2

2->3

4->2

2->5

The standard covering will give us 3 as a result (1->2->3 , 4 , 5)

But in this version the answer would be 2 (1->2->3 , 4->2->5)

Does anyone have any idea?

Thanks in advance