Path Cover

A path cover is a set of paths that cover all vertices. Minimum cardinality path cover problem is NP-hard for general graph classes, however it can be solved in polynomial time for some special cases.

Given any acyclic directed graph a minimum path cover of G can be obtained by finding a maximum matching in a properly constructed bipartite graph.

Let’s see on an application.

A transportation problem

A company wants to organize some transports between given locations. Each transport has a specific departure time. The same vehicle can be used for two transports i and j if the following are satisfied:
(1) arrival location of i and departure location of j are the same
(2) arrival time of i is earlier then the departure time of j

The objective is to find the minimum number of vehicles necessary to ensure all the transports.

Solution method

Let us define a bipartite graph G = (U,V,E) where vertex sets U and V represent locations. We put an edge between two vertices u_i and v_j if the transport j can be done by the same vehicle after transport i.

The minimum number of vehicles to make all transports is equal to n-M where M is the size of a maximum matching. Each edge in the matching indicates that the corresponding transports can be done one after the other by the same vehicle. Paths in the cover are obtained by following the edges of the matching and every unmatched vertex corresponds to the end of a path.

An example

	v1	v2	v3	v4
v1	0	2	4	1
v2	-	0	3	3
v3	-	-	0	2
v4	-	-	-	0

transport	departure	arrival	departure time
t1	v1	v2	6pm
t2	v1	v4	3pm
t3	v2	v4	3pm
t4	v2	v3	12pm
t5	v3	v2	16pm
t6	v4	v2	11pm
t7	v4	v3	9pm

According to this matching transports (t1,t4,t5) can be done with a single vehicle as well as (t2,t6) and (t3,t7). Therefore the company needs 3 vehicles.