AbstractFor any directed graphGwith node‐setV(G), we present anO([V(G)]3)algorithm that finds a partitionPofV(G)into directed paths and an independent setIof nodes, such that |P=|I| The existence of such aPandIis the Gallai‐Milgrm theorem. WhereGis transitive and acyclic, the well‐known Dilworth theorem that min |P| = max |I| follows immediately. WhereGis bipartitite and every edge ofGis directed from node‐setUto node‐setV, Pcorresponds to a largest mat