Translate this problem to graph theory

Question

Say I have a size $k$ set called $S_k$ with elements that are natural numbers (repetitions are allowed). For instance $\{2, 8, 6, 6, 1, 3\}$ is a valid set for $k = 6.$ I am trying to find the least number of strict partial orders such that each partial order uses a unique element. For instance, in the above set I have a minimum of two strict partial orders: $8>6>3>2>1$ and $6$.

Answer 1

Create a digraph $G=(V,A)$ as follows:

• $V=S_k$: so one node per element of the multi set $S_k$
• Create an arc from $u$ to $v$ if and only if $u<v$

You are now looking for a minimum number of paths that cover your graph $G$. Since $G$ has a transitive structure, you can use the Dilworth Theorem to answer your question (in polynomial time). It will give you an algorithm based on maximum flows that gives you exactly what you want.