On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path.

If one was attempting to create examples of DAGs with small MPCs (i.e. use a program to create examples of DAGs with small MPCs), how could this be done? What condition would have to be satisfied?

  • $\begingroup$ Is Dilworth's Theorem (i.e.: the minimal size of a path partition of a DAG = the maximum size of an antichain) insufficient for your purposes? Or are you looking for other criteria that can bound the maximum size of antichains in a DAG? $\endgroup$
    – mhum
    Nov 10 '20 at 17:46
  • $\begingroup$ @mhum I was looking for something ... constructive? Dilworth's Theorem doesn't really say anything about why fundamentally the graph has small width. If you look at the condition provided in the question, that condition is actually the condition for the size of MPC with all edges covered, but there doesn't seem to be similar condition for vertices. $\endgroup$
    – shgr1092
    Nov 11 '20 at 11:14
  • $\begingroup$ Ah, I see. Indeed, Dilworth's Theorem is not super constructive on its own, though I suspect one could develop a constructive method based off of it. $\endgroup$
    – mhum
    Nov 12 '20 at 2:15
  • $\begingroup$ Also, you may want to update the question if you're actually interested in covering the edges of the DAG with paths since it's currently about covering the vertices. $\endgroup$
    – mhum
    Nov 12 '20 at 2:16
  • $\begingroup$ @mhum The question is about covering the vertices. The criterion provided in the question works for covering edges (and therefore also for covering vertices). Wondering what kind of reasons a DAG would have small MPC on vertices without it being a corollary of something more powerful. $\endgroup$
    – shgr1092
    Nov 12 '20 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.